題目大意：問從1變到n最少需要多少步。變換規則以下
1.變化進程中的中間結果可以任意使用
2.每次只能挑選兩個數進行加減
解題思路：先算1下最少需要多少步，然后在如果在當前步數下沒法到達結果的話，就當前步數加1，繼續搜索下去
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
#define maxn 1010
int num[maxn], cnt, n ,MIN_depth;
bool dfs(int cur, int depth) {
if(depth >= MIN_depth) {
if(cur == n)
return true;
return false;
}
int MAX = 0;
for(int i = 0; i < cnt; i++)
MAX = max(MAX,num[i]);
if( ((cur + MAX) << (MIN_depth - depth - 1)) < n)
return false;
for(int i = cnt - 1; i >= 0; i--) {
num[cnt++] = cur + num[i];
if(dfs(cur + num[i], depth+1))
return true;
cnt--;
num[cnt++] = cur - num[i];
if(dfs(cur - num[i],depth+1))
return true;
cnt--;
}
return false;
}
int main() {
while(scanf("%d", &n) == 1 && n) {
MIN_depth = 0;
int t = 1;
while(t < n) {
t += t;
MIN_depth++;
}
while(1) {
num[0] = cnt = 1;
if(dfs(1,0))
break;
MIN_depth++;
}
printf("%d
", MIN_depth);
}
return 0;
}
程序員人生，我編程，我富裕，記住wfuyu網，php教程，php學習，php手冊，CMS模版制作
聲明：本站大部分內容是作者原創，少部分收集于互聯網供大家一起學習，原版權很多不明，如有侵權請聯系本站，謝謝！
粵ICP備14040726號-1?? 2015-2020 程序員人生 版權所有
