| 网站首页 | 业界新闻 | 小组 | 威客 | 人才 | 下载频道 | 博客 | 代码贴 | 在线编程 | 编程论坛
欢迎加入我们,一同切磋技术
用户名:   
 
密 码:  
共有 1143 人关注过本帖
标题:看看这个题目的算法
只看楼主 加入收藏
shangabc
Rank: 1
等 级:新手上路
帖 子:35
专家分:0
注 册:2008-10-7
收藏
得分:0 
能不能短一点,减少for语句的使用
2008-12-03 22:18
广陵绝唱
Rank: 10Rank: 10Rank: 10
等 级:贵宾
威 望:29
帖 子:3607
专家分:1709
注 册:2008-2-15
收藏
得分:0 
程序代码:
/*------------------------------------------------------------------------------

        依据题意,用全排列写了这么个程序,不过,运行起来可是够慢的了。

        如果把宏中的 N 值改为10,那样能快些。

------------------------------------------------------------------------------

        希望有高手写出更好的算法来解决这个问题。

------------------------------------------------------------------------------*/

#include <stdio.h>
#define SWAP(a,b) { int t=a;a=b;b=t;}
#define N 22
#define n 7
int a[N];
int x;
void SORT(int k)
{
    int i;
    if((k+1==n)&&(a[0]+2*a[1]+3*a[2]+4*a[3]+5*a[4]+6*a[5]+7*a[6]==x))
    {
        printf("%d =1*%d + 2*%d + 3*%d + 4*%d + 5*%d + 6*%d + 7*%d\n",
               x,a[0],a[1],a[2],a[3],a[4],a[5],a[6]);
        return ;
    }
    for(i=k+1;i<N;++i)
    {
        SWAP(a[k+1],a[i]);
        SORT(k+1);
        SWAP(a[k+1],a[i]);
    }
}
int main(void)
{
    int i;
    printf("input x:\n");
    scanf("%d",&x);
    for(i=0;i<N;++i)
        a[i]=i+1;
    SORT(0);
    return 0;
}


[[it] 本帖最后由 广陵绝唱 于 2008-12-3 23:40 编辑 [/it]]
2008-12-03 23:20
yangyong_629
Rank: 1
等 级:新手上路
帖 子:17
专家分:0
注 册:2008-11-15
收藏
得分:0 
Java 代码看不懂C的还懂。应该没错吧 我也是这么想的啊
2008-12-04 09:38
卧龙孔明
Rank: 9Rank: 9Rank: 9
等 级:贵宾
威 望:59
帖 子:3872
专家分:684
注 册:2006-10-13
收藏
得分:0 
直接枚举的最大复杂度为2494357888,优化简单的枚举后复杂度为113379904,前者不能满足1s内出解的时间要求,后者由于mod问题可能会卡时间出解或者超时。剪枝下会很快的。

搜索加剪枝会快许多,再者,这题可以部分dp.而且效果会更好。

My Blog: www.aiexp.info
虽然我的路是从这里开始的,但是这里不再是乐土.感谢曾经影响过,引导过,帮助过我的董凯,飞燕,leeco,starwing,Rockcarry,soft_wind等等等等.别了,BCCN.
2008-12-04 12:23
快速回复:看看这个题目的算法
数据加载中...
 
   



关于我们 | 广告合作 | 编程中国 | 清除Cookies | TOP | 手机版

编程中国 版权所有,并保留所有权利。
Powered by Discuz, Processed in 0.055342 second(s), 7 queries.
Copyright©2004-2024, BCCN.NET, All Rights Reserved