UVA1374 快速幂计算 Power Calculus 题解

Doveqise · 2019-03-08 17:02:43 · 题解

一道搜索题，搜索需要几步能到达目标预计状态。
记得搜索×的状态和÷的状态。
DFS例题赛高！
emmm细节看代码

#include<bits/stdc++.h>
using namespace std;
int maxn/*步数最大值*/,n/*输入数字*/,S[50]/*存储数组*/;
bool find(int step,int now){//DFS函数
    if(step>maxn||now<=0||now<<(maxn-step)<n) return 0;//判断非法状态
    if(now==n||now<<(maxn-step)==n) return 1;//记录答案
    S[step]=now;//存入数组
    for(int i=0;i<=step;i++){
        if(find(step+1,now+S[i]))return 1;//DFS乘S[i]的情况
        if(find(step+1,now-S[i]))return 1;//DFS除以S[i]的情况
        }
    return 0;
}
signed main(){
    while(scanf("%d",&n)&&n){//读入多组数据
    for(maxn=0;!find(0,1);maxn++);//查找最小需求步数
    printf("%d\n",maxn);//输出答案
    }
}