用BFS的方法求2^100至少要算多少次乘法

admin

上次是用DFS做的，有些题目BFS和DFS都可以做的。

1. #include<iostream>
   
2. #include<iomanip>
   
3. using namespace std;
   
4. int a[200],x,y,n,iiii;
   
5. int head,tail,temp;
   
6. int m[10000][20],f[10000],l[10000];//这里做成结构类型更好
   
7. int tm[20],tl,tx;
   
8. //所有的数组都是0起步的
   
9. bool bfscan(int i,int k) //判断前面i-1个数字中能有某两个数字之和为k
   
10. {
    
11.     bool bb=false;
    
12.     for (int ii=0; ii<=i; ii++)
    
13.         for (int jj=0; jj<=i; jj++)
    
14.             if (tm[ii]+tm[jj]==k) bb=true;  //很笨的做法没有优化
    
15.     return bb;
    
16. }
    
17. void bfs(int i)
    
18. {
    
19.     int j,k;bool bb;
    
20.     m[0][0]=1;m[0][1]=2;f[0]=0;l[0]=1;//初始值
    
21. 
    
22.     head=tail=0;bb=false;
    
23.     while ((tail>=head) &&(tail<=9991) &&!bb)
    
24.     {
    
25.         for (j=0;j<=19;j++) tm[j]=m[head][j];//取队首元素
    
26.         tl=l[head];
    
27.         cout<<head<<':';
    
28.         for (j=0;j<=tl;j++) cout<<tm[j]<<' ';cout<<endl;//输出测试
    
29.         for(tx=tm[tl]+1;tx<=tm[tl]*2;tx++) //应用规则
    
30.            if (bfscan(tl,tx))   //判断前面tl个能否得到j
    
31.            {
    
32.                tail++;
    
33.                tm[tl+1]=tx;
    
34.                for (j=0;j<=19;j++) m[tail][j]=tm[j];//加入队尾
    
35.                f[tail]=head;l[tail]=tl+1;
    
36.                if (i==tx) {bb=true;break;}
    
37.            }
    
38.         head++;
    
39.      }
    
40.     for (j=0;j<=l[tail];j++) cout<<m[tail][j]<<' ';
    
41. }
    
42. 
    
43. int main()
    
44. {
    
45.     x=20;
    
46.     bfs(20);
    
47. }
    

复制代码

admin

1. #include<iostream>
   
2. using namespace std;
   
3. const int mm=10010; // 最多搜索多少个节点
   
4. int a[10][mm],l[mm];
   
5. int  head,tail;
   
6. int aa[10],la;
   
7. bool b;
   
8. int i,k,kk;
   
9. void printout(int i)
   
10. {
    
11.     int j;
    
12.     cout<<i<<':';
    
13.     for (j=0; j<=9; j++) cout<<a[j][i]<<' ';
    
14.     cout<<' '<<l[i];
    
15.     cout<<endl;
    
16. }
    
17. bool can(int i,int j)   ///i 能不能出现在第j位
    
18. {
    
19.     int  i1,i2;
    
20.     bool b=false;
    
21.     for (i1=0; i1<=j-1; i1++)
    
22.         for (i2=0; i2<=j-1; i2++)
    
23.             if (aa[i1]+aa[i2]==i) b=true;
    
24.     return b;
    
25. }
    
26. int main()
    
27. {
    
28.     head=tail=0;
    
29.     a[0][head]=1;
    
30.     a[1][head]=2;
    
31.     l[0]=1;  ///首元素显然是[1,2]
    
32.     b=false; /// 表示没有找到
    
33.     while ((!b) && (tail>=head) && (tail<=mm-100))
    
34.     {
    
35.         for (i=0; i<=9; i++) aa[i]=a[i][head];
    
36.         la=l[head];///取出头元素
    
37.         kk=a[la][head];
    
38.         ///printout(head);
    
39.         for (k=kk+1; k<=kk*2; k++)  ///按规则生儿子
    
40.             if (can(k,la+1))  ///符合条件进队列
    
41.             {
    
42.                 tail++;/// 写进去
    
43.                 for (i=0; i<=9; i++) a[i][tail]=aa[i];
    
44.                 a[la+1][tail]=k;
    
45.                 l[tail]=la+1;
    
46.                 ///printout(tail);  一般在这里加调试
    
47.                 if (a[la+1][tail]==10)
    
48.                 {
    
49.                     b=true;
    
50.                     break;
    
51.                 }
    
52.             }
    
53.         head++;
    
54.     }
    
55.     if (b) for (i=0; i<=la+1; i++) cout<<a[i][tail];
    
56.     else if (tail<head) cout<<"No Answer!";
    
57.     else if (tail>mm-100) cout<<"cannot found!";
    
58.     return 0;
    
59. }
    

复制代码