所谓的IDA*就是dfs规定层数，并剪枝
#include <iostream> #include <algorithm> #include <cstring> #include <cstdio> using namespace std; const int maxn=1000+100; int a[maxn]; int n,maxd; bool dfs(int d,int num) { if(d==maxd) { if(num==n) return 1; return 0; } int mm=0; for(int i=0;i<=d;i++) mm=max(mm,a[i]); if(mm*(1<<(maxd-d))<n) return 0; for(int i=0;i<=d;i++) { a[d+1]=num+a[i]; if(dfs(d+1,a[d+1])) return 1; a[d+1]=abs(num-a[i]); if(dfs(d+1,a[d+1])) return 1; } return 0; } int main() { while(~scanf("%d",&n)&&n) { a[0]=1; if(n==a[0]) { printf("0\n"); continue; } for(maxd=1;;maxd++) { if(dfs(0,1)) { printf("%d\n",maxd); break; } } } return 0; }
转载于:https://www.cnblogs.com/Wangwanxiang/p/8455989.html
相关资源：数据结构—成绩单生成器