随笔 - 15  文章 - 5  trackbacks - 0
<2024年3月>
252627282912
3456789
10111213141516
17181920212223
24252627282930
31123456

常用链接

留言簿

随笔分类

随笔档案

文章分类

文章档案

搜索

  •  

最新评论

  • 1. re: 2011年9月26日[未登录]
  • 我不是吹嘘,为什么1,2,3,4,5,7,9,10,11,12我都知道一点????
    看来我估计可以过电面啊~_~
  • --ZJ
  • 2. re: 2011年9月26日
  • 有计划的人生会很精彩。。
  • --Cheap glueless lace front wigs
  • 3. re: 2011年9月26日
  • (14)举个例子说明你学习能力比较强,
    牛!

    那个腾讯就是做QQ的吧,QQ里面还内嵌个木马,有事没事的扫描下用户磁盘,唉,公司技术就这鸟水平,还对应聘者提那么多要求。
  • --Chipset
  • 4. re: 2011年9月26日
  • 问这么多问题,要求不低啊,呵呵,要回答好需要很扎实的基础
  • --LoveBeyond
  • 5. re: 2011年9月26日
  • 这些问题我十有八九答不上来...惭愧啊
  • --pezy

阅读排行榜

评论排行榜

 穷举(枚举)算法,又称是暴力破解法,也是我接触最多的理解比较全面深刻的一个算法。 
穷举算法就是一一列出所有可能的元素,用题目已知的条件验证每个结果,看是否满足。
枚举法的本质就是从所有候选答案中去搜索正确的解,使用该算法需要满足两个条件:
1)可预先确定候选答案的数量;
2)候选答案的范围在求解之前必须有一个确定的集合。
一般应用在规模比较小的问题上,因为穷举算法一般都是循环和条件判断来实现的,当循环比较多的时候可能,时间复杂性和空间复杂性都很大。
举几个例子来看看:
委派任务
 某侦察队接到一项紧急任务,要求在A、B、C、D、E、F六个队员中尽可能多地挑若干人,但有以下限制条件:
 1)A和B两人中至少去一人;
 2)A和D不能一起去;
 3)A、E和F三人中要派两人去;
 4)B和C都去或都不去;
 5)C和D两人中去一个;
 6)若D不去,则E也不去。
 问应当让哪几个人去?
我们可以根据已知信息得到一些限制性的条件,假设能去执行任务的代表是1,而不能去执行任务的是0,
A+B >1 :表示A,B至少一人要去
A+D != 2:表示AD不能同时去
A+E+F == 2:表示三者中派两人去
B+C == 0 & B+C == 2:表示BC要么都去,要么都不去
C+D == 1:表示CD只能有一人去,
D+E == 0 & D==1表示:D不去的话,则E也不去,D去的话,E随便,
核心算法
nt a,b,c,d,e,f;
 for(a=1;a>=0;a--) /*穷举每个人是否去的所有情况*/
 for(b=1;b>=0;b--) /*1:去 0:不去*/
 for(c=1;c>=0;c--)
 for(d=1;d>=0;d--)
 for(e=1;e>=0;e--)
 for(f=1;f>=0;f--)
 if(a+b>=1&&a+d!=2&&a+e+f==2
 &&(b+c==0||b+c==2)&&c+d==1
 &&(d+e==0||d==1))
 {
 printf("A will%s be assigned. \n",a?"":"not");
 printf("B will%s be assigned. \n",b?"":"not");
 printf("C will%s be assigned. \n",c?"":"not");
 printf("D will%s be assigned. \n",d?"":"not");
 printf("E will%s be assigned. \n",e?"":"not");
 printf("F will%s be assigned. \n",f?"":"not");
 }
一个比较有代表性的问题就是填写运算符的游戏
5 5 5 5 5 =5 
由于算术表达式的特殊性,在编程求解这个算式时,需要注意以下几点:
(1)当填入除号时,要求右侧的数不能为0
(2)乘除的运算级别比加减高。       
代码如下:
    int j,i[5]; //循环变量 ,数组i用来表示4个运算符
    int sign;//累加运算时的符号  
    int result; //保存运算式的结果值
    int count=0; //计数器,统计符合条件的方案
    int num[6];  //保存操作数
    float left,right; //保存中间结果
    char oper[5]={' ','+','-','*','/'}; //运算符
    printf("请输入5个数:");
    for(j=1;j<=5;j++)
        scanf("%d",&num[j]);
    printf("请输入结果:");
    scanf("%d",&result);
    for(i[1]=1;i[1]<=4;i[1]++)//循环4种运算符,1表示+,2表示-,3表示*,4表示/
    {
        if((i[1]<4) || (num[2]!=0))//运算符若是/,则第二个运算数不能为0
        {
            for(i[2]=1;i[2]<=4;i[2]++)
            {
                if((i[2]<4) || (num[3]!=0))
                {
                    for(i[3]=1;i[3]<=4;i[3]++)
                    {
                        if((i[3]<4) || num[4]!=0)
                        {
                            for(i[4]=1;i[4]<=4;i[4]++)
                            {
                                if((i[4]<4) || (num[5]!=0))
                                {
                                    left=0;
                                    right=num[1];
                                    sign=1;
                                    for(j=1;j<=4;j++)
                                    {
                                        switch(oper[i[j]])
                                        {
                                            case '+':
                                                 left=left+sign*right;
                                                 sign=1;
                                                 right=num[j+1];
                                                 break;
                                            case '-':
                                                 left=left+sign*right;
                                                 sign=-1;
                                                 right=num[j+1];
                                                 break;//通过f=-1实现减法
                                            case '*':
                                                 right=right*num[j+1];
                                                 break;//实现乘法
                                            case '/':
                                                 right=right/num[j+1];//实现除法
                                                 break;
                                        }
                                    }
                                    if(left+sign*right==result)
                                    {
                                        count++;
                                        printf("%3d:",count);
                                        for(j=1;j<=4;j++)
                                            printf("%d%c",num[j],oper[i[j]]);
                                        printf("%d=%d\n",num[5],result);
                                    }
                                }
                            }
                        }
                    }
                }
            }
        }
    }
    if(count==0)
        printf("没有符合要求的方法!\n");    

posted on 2011-09-25 10:22 mengkai 阅读(923) 评论(0)  编辑 收藏 引用

只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理