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

diggersun

其实就是求一个最短的序列 A1 A2 A3** An 满足
1、A1=1
2、对于x >1有Ax=Ay+Az，其中y<=x,z<x;
3、An=100
我们尝试使用回溯法（也叫递归，深度优先搜索，意义都差不多）

diggersun

1. #include<iostream>
   
2. #include<iomanip>
   
3. using namespace std;
   
4. int a[200],x,y,n,iiii;
   
5. bool can(int i,int k) //判断前面i-1个数字中能有某两个数字之和为k
   
6. {
   
7.     bool bb=false;
   
8.     for (int ii=0; ii<=i; ii++)
   
9.         for (int jj=0; jj<=i; jj++)
   
10.             if (a[ii]+a[jj]==k) bb=true;  //很笨的做法没有优化
    
11.     return bb;
    
12. }
    
13. void dfs(int i)
    
14. {
    
15.     int j,k;
    
16.     if (i>=n) //达到预定的长度就不再往下找了
    
17.     {
    
18.         if (a[n-1]==x)  //符合要求的话
    
19.         {
    
20.             for (j=0; j<=n-1; j++) cout<<setw(3)<<a[j];
    
21.             cout<<endl;
    
22.             n--;  //下次就最大长度减一
    
23.         }
    
24.     }
    
25.     else
    
26.         for (k=1+a[i-1]; k<=(2*a[i-1]); k++) // 下一个数字的范围若能由大到小更好
    
27.             if (can(i-1,k))
    
28.             {
    
29.                 a[i]=k;
    
30.                 dfs(i+1);
    
31.             }
    
32. }
    
33. int main()
    
34. {
    
35.     x=20;
    
36.     n=20;//假设最大值要算20次，这个是很保守的。
    
37.     a[0]=1; a[1]=2; //前面两个数字没有选择只能是1和2
    
38.     dfs(2);//从第三个数字开始搜索
    
39. }
    

复制代码

diggersun

二楼的只是一个标准的参考程序，有很多的地方可以优化，比如，n=20，假设最大次数要算20次，其实，我们可以使用类似快速幂的形式计算最大计算次数，（神奇的是：快速幂算法80%情况下都是对的，除非15,23,46等）或者使用log2(x)*2。再比如，我们在递归的时候一般是由小到大搜索，此题也不例外，但是，可以想象，应该由大到小找更快捷， 第26行 for (k=1+a[i-1]; k<=(2*a[i-1]); k++) 可以考虑改成 k--的形式。