Power calculus

IDA*

#include<stdio.h>
#include<string.h>
const int N = 100;                 //最大层次
int num[N];                        //记录一条路径上的数字，num[i]是路径上第i层的数字
int n, depth;
bool dfs(int now, int d) {         //now:当前路径走到的数字，d：now所在的深度
  if (d > depth) return false;     //当前深度大于层数限制
  if (now == n) return true;       //找到目标。注意：这一句不能放在上一句前面
  if (now << (depth - d) < n)      //剪枝：剩下的层数用最乐观的倍增也不能达到n
    return false;
  num[d] = now;                    //记录这条路径上第d层的数字
  for(int i = 0; i <= d; i++) {    //遍历之前算过的数，继续下一层
    if (dfs(now + num[i], d + 1)) return true;          //加：比输入的数字小
    else if (dfs(now - num[i], d + 1)) return true;     //减：比输入的数字大
  }
  return false;
}
int main() {
  while(~scanf("%d", &n) && n) {
    for(depth = 0;; depth++) {      //IDDFS：每次限制最大搜索depth层，死循环
      memset(num, 0, sizeof(num));  //初始化
      if (dfs(1, 0)) break;         //从数字1开始，当前层0
    }
    printf("%d\n", depth);
  }
  return 0;
}

笔记：IDA* 是对 IDDFS 的优化，可以把 IDA* 看成 A* 算法思想在 IDDFS 中的应用。本题的估价函数：如果当前的值用最快的方式（连续乘2，倍增）都不能到达n，停止用这个值继续 DFS。剪枝操作：如果当前深度 + 未来需要的步数 > 深度限制，立即返回 false。