Power Calculus (IDDFS)

题意：求只用乘法和除法最快多少步可以求到x^n

思路：迭代加深搜索

//Accepted164K1094MSC++840Binclude<cstdio>#include<iostream>#include<algorithm>#include<cstring>using namespace std;int step[100005];int n;int cur;bool IDDFS(int lim,int g){if(cur>lim) return false;if(step[cur]==g) return true;if((step[cur]<<(lim-cur))<g) return false; //剪枝for(int i=0;i<=cur;i++){cur++;step[cur]=step[i]+step[cur-1];if(step[cur]<=10000&&IDDFS(lim,g)) return true; //比1000^2大的时候就没意义了，剪枝step[cur]=step[cur-1]-step[i];if(step[cur]>0&&IDDFS(lim,g)) return true;cur–;}return false;}int main(){while(scanf("%d",&n),n){int ans=-1;while(1){cur=0;step[cur] = 1;ans++;if(IDDFS(ans,n)) break;}printf("%d\n",ans);}return 0;}

，我无所事事的度过了今天，是昨天死去的人们所期望的明天。