点击打开原题链接
迭代加深搜索
题意：给出n，计算最少需要几次能让x成为x^n（x和已经生成的数相乘或相除）。
解题思路：运用了紫书上的最后一种方法，即每次只操作新出现的数，对新出现的数先进行加法，然后进行减法。虽然紫书上说这种思路没有的得到证明，但是在1-1000内没有反例（跪求大佬解释）。
这里着重说一下剪枝方法：设当前深度为d,当前深度的最大数为c， 如果c * pow（2，maxd-d）< n，便剪枝。
为什么这么做呢？
因为每当从一层到达下一层的时候，maxd最多增大2倍，所以从深度d到达深度maxd时c最多增加pow(2,maxd-d)倍，所以如果c*pow(2,maxd-d) < n的话，那么当前深度的其他数肯定也满足不了，所以这里就只能增大maxd了，因此这时进行剪枝。
这里可以钻个孔子，可以先打一个表，存下每个数需要多少次，然后直接输出就ok了。
上代码：
#include<cstdio> #include<cstring> #include<iostream> #include<algorithm> #include<cmath> using namespace std; int n,maxd,ci; int ans[100000]; bool dfs(int d,int tmp) { if(d>maxd) return false; if(tmp==n&&d==maxd) { return true; } if(tmp << (maxd-d) < n) return false; ans[d] = tmp; for(int i=0;i<=d;i++) { if( dfs(d+1,tmp+ans[i]) ) return true; if(tmp-ans[i]<=0)continue; if( dfs(d+1,tmp-ans[i]) ) return true; } return false; } int main() { while(scanf("%d", &n)!=EOF && n!=0 ) { maxd = 0; ci = 0; memset(ans,0, sizeof(ans)); if(n==1) { printf("0\n"); continue; } if(n==0) { printf("1\n"); continue; } ans[0]=1; for(maxd=1; ;maxd++) { if(dfs(0,1)){break;} } printf("%d\n", maxd); } return 0; } 打表的代码：
#include <iostream> #include <cstdio> using namespace std; const int ans[]={0,1,2,2,3,3,4,3,4,4,5,4,5,5,5,4,5,5,6,5,6,6,6,5,6,6,6,6,7,6,6,5,6,6, 7,6,7,7,7,6,7,7,7,7,7,7,7,6,7,7,7,7,8,7,8,7,8,8,8,7,8,7,7,6,7,7,8,7,8,8,8,7,8,8,8,8, 8,8,8,7,8,8,8,8,8,8,9,8,9,8,9,8,8,8,8,7,8,8,8,8,9,8,9,8,9,9,9,8,9,9,9,8,9,9,9,9,9,9,9,8, 9,9,9,8,9,8,8,7,8,8,9,8,9,9,9,8,9,9,9,9,9,9,9,8,9,9,9,9,9,9,10,9,9,9,9,9,9,9,9, 8,9,9,9,9,9,9,10,9,10,9,10,9,10,10,10,9,10,10,10,9,10,10,10,9,10,9,10,9,9,9,9,8, 9,9,9,9,10,9,10,9,10,10,10,9,10,10,10,9,10,10,10,10,10,10,10,9,10,10,10,10,10,10, 10,9,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,9,10,10,10,10,10,10,10,9,10,10, 10,9,10,9,9,8,9,9,10,9,10,10,10,9,10,10,11,10,11,10,10,9,10,10,11,10,11,10,10,10, 10,10,10,10,10,10,10,9,10,10,10,10,10,10,11,10,10,10,11,10,11,11,11,10,11,10,11,10, 11,10,11,10,11,10,10,10,10,10,10,9,10,10,10,10,10,10,11,10,11,10,11,10,11,11,11,10,11,11,11, 10,11,11,11,10,11,11,11,11,11,11,11,10,11,11,11,11,11,11,11,10,11,11,11,11,11,11,11, 10,11,11,11,10,11,11,11,10,11,10,11,10,10,10,10,9,10,10,10,10,11,10,11,10,11,11,11,10,11, 11,11,10,11,11,11,11,11,11,11,10,11,11,11,11,11,11,11,10,11,11,11,11,11,11,11,11, 11,11,11,11,11,11,11,10,11,11,11,11,11,11,11,11,11,11,11,11,11,11,11,10,11,11,11,11,11, 11,11,11,11,11,11,11,12,11,12,11,11,11,12,11,12,11,11,11,11,11,11,11,11,11,11,10,11,11, 11,11,11,11,11,11,11,11,12,11,12,11,11,10,11,11,12,11,12,11,11,10,11,11,11,10,11,10,10,9,10, 10,11,10,11,11,11,10,11,11,12,11,12,11,11,10,11,11,12,11,12,12,11,11,12,12,12,11,12,11,11,10, 11,11,12,11,12,12,12,11,11,12,12,11,12,11,12,11,11,11,12,11,12,11,11,11,12,11,11,11,11,11,11,10,11, 11,11,11,11,11,12,11,11,11,12,11,12,12,12,11,12,11,12,11,12,12,12,11,12,12,12,12,12, 12,12,11,12,12,12,11,12,12,12,11,12,12,12,11,12,12,12,11,12,12,12,11,12,11,12,11, 12,11,11,11,11,11,11,10,11,11,11,11,11,11,12,11,12,11,12,11,12,12, 12,11,12,12,12,11,12,12,12,11,12,12,12,12,12,12,12,11,12,12,12,12,12,12,12,11,12,12, 12,12,12,12,12,11,12,12,12,12,12,12,12,12,12,12,12,12,12,12,12,11,12,12,12,12,12,12, 12,12,12,12,12,12,12,12,12,11,12,12,12,12,12,12,12,12,12,12,12,12,12,12, 12,11,12,12,12,12,12,12,12,11,12,12,12,12,12,12,12,11,12,12,12,11,12,12,12,11,12, 11,12,11,11,11,11,10,11,11,11,11,12,11,12,11,12,12,12,11,12,12,12,11,12,12,12,12, 12,12,12,11,12,12,12,12,12,12,12,11,12,12,12,12,12,12,12,12,12,12,13,12,12,12, 12,11,12,12,12,12,13,12,12,12,12,12,12,12,12,12,12,11,12,12,12,12,12,12,12,12,12, 12,12,12,12,12,13,12,12,12,13,12,13,12,12,12,13,12,12,12,12,12,12,11,12,12,12,12,12, 12,13,12,12,12,13,12,13,12,12,12,13,12,13,12,13,12,12,12,12,12,12,12,12,12, 12,11,12,12,12,12,12,12,12,12,12,12,13,12,13,12,13,12,13,12,13,12,13,12,13,12,13, 13,13,12,13,13,13,12,13,12,13,12,13,13,13,12,13,13,13,12,13,12,13,12,12,12,13,12, 13,12,12,12,12,12,12,12,12,12,12,11,12,12,12,12,12,12,12,12,12,12,13,12,13,12, 12,12,12,12,13,12,13,13,13,12,13,13,13,12,13,12,12,11,12,12,13,12,13,13,13,12}; int main() { int n; while(cin>>n&& n) cout<<ans[n-1]<<endl; return 0; } 水波。
