BFS
#include<cstdio>
#include<iostream>
#define MAXN 800000
using namespace std;
struct T
{
int num1,num2,step; //较大数，较小数，步长
}q[MAXN];
bool vis[20500][105];
int n;
int head,tail;
bool add(int num1,int num2,int step) //其实就是一个BFS，维护num1 > num2
{
if(num1 == n||num2 == n) //达到目标状态
{
return true;
}
if(num1 < num2) //x比y大
swap(num1,num2);
if(num1 == num2||num1 >= n + 101|| num2 >= 101) //两个数相等，则无最优解；第一个数超过n太多无解；第二个数太大会运行错误
return false;
if(!vis[num1][num2]) //入队列
{
vis[num1][num2] = 1;
tail++;
q[tail].num1 = num1;
q[tail].num2 = num2;
q[tail].step = step;
}
return false;
}
int main()
{
scanf("%d",&n);
head = tail = -1; //初始化
add(1,0,0); //初始状态的两个数,num1 = 1,num2 = 0
int num1,num2,step;
int ans;
while(head < tail)
{
++head;
num1 = q[head].num1,num2 = q[head].num2,step = q[head].step + 1;
if(add(num1+num1,num2,step) || add(num1,num2+num2,step) || add(num1,num1+num2,step) || add(num2,num1+num2,step) || add(num1,num1+num1,step) || add(num2,num2+num2,step) || add(num1 - num2,num2,step) || add(num1,num1 - num2,step)) //考虑所有保和运算的情况，全部入队
{
ans = step;
break;
}
}
printf("%d\n",ans);
}
笔记：爆搜+优化，将八种运算情况全部放到一个判断里，将x和y的所有的情况全部都搜索一遍，vis标记去重
版权声明：
本文为博主原创文章，遵循 CC 4.0 BY-SA 版权协议，转载请附上原文出处链接和本声明。本文链接：https://blog.csdn.net/cqbzwja/article/details/47069893
A*
#include<iostream>
#include<cstring>
#include<cstdio>
#include<queue>
using namespace std;
const int N = 30007, SIZE = 1e6 + 10;
int n;
struct node{
int x, y, g, h; //较大数，较小数，当前步数，预期步数
bool operator < (const node &a)const{
return g + h == a.g + a.h ? h > a.h : g + h > a.g + a.h; //综合步数少优先，如果全部步数相等，预期步数小者优先
}
};
struct Node{ //链式向前星
int to, next, w; //xy组合、哈希值、权重
};
struct hash_map{ //哈希表
int head[N], now;
Node a[SIZE];
bool insert(int sta, int w){ //插入新值
int x = sta % N;
for(int i = head[x]; i; i = a[i].next){ //遍历链表
if(a[i].to == sta){ //xy组合相同
if(a[i].w <= w) return 0; //剪枝：权值大退出
a[i].w = w; return 1; //更新最短路径
}
}
a[++now].to = sta; a[now].next=head[x]; a[now].w=w; //新增
head[x] = now; //哈希表关联链表
return 1;
}
}dict;
priority_queue<node> heap; //优先队列
node now;
int gcd(int a, int b){ return b ? gcd(b, a % b) : a;} //最大公约数：辗转相除
void che(int x, int y){ //运算函数
if(x < y) swap(x, y); //剪枝：x为最大数
if(x > 2 * n) return ; //剪枝：超过
if(x > n && y == 0) return ; //剪枝：无解
if(x == y) return ; //剪枝：回退寻找最优解
if(n % gcd(x, y)) return; //剪枝：无解
if(!dict.insert(x * 50000 + y, now.g + 1)) return; //去重
int h = 0, tx = x;
while(tx < n) h++, tx <<= 1; //用*2预估预期步数
node s = {x, y, now.g + 1, h};
heap.push(s); //放入优先队列
}
void A_star(){
node s ={1, 0, 0, 0};
heap.push(s); //起点放进优先队列
while(!heap.empty()){
now = heap.top(); heap.pop();
if(now.x == n || now.y == n){ //找到
printf("%d\n", now.g); break; //输出步数，跳出
}
int a[2] = {now.x, now.y}; //较大数，较小数
for(int i = 0; i < 2; i++) //二进制0、1、2、3、6、7
for(int j = i; j < 2; j++)
for(int k = 0; k < 2; k++){
int b[2] = {a[0], a[1]};
b[k] = a[i] + a[j]; //2x、2y、x+y赋值给x或者y
che(b[0], b[1]);
}
che(now.x - now.y, now.y); //|x-y|赋值给x或者y
che(now.x, now.x - now.y);
}
}
int main(){
scanf("%d", &n);
A_star();
return 0;
}
笔记：核心是启发函数：当前步数+预期至少需要的步数，用启发函数选择最优搜索路线，哈希表择优去重，运算方式也是饱和运算
版权声明：
本文为博主原创文章，遵循 CC 4.0 BY-SA 版权协议，转载请附上原文出处链接和本声明。本文链接：https://blog.csdn.net/weixin_30527143/article/details/95552284
神之一手
#include<iostream>
using namespace std;
int main ()
{
int n;
cin >>n;
switch (n)
{
case 19997 : cout <<“18″<<endl; break;
case 15151 : cout <<“17″<<endl; break;
case 11111 : cout <<“17″<<endl; break;
case 10007 : cout <<“16″<<endl; break;
case 5123 : cout <<“14″<<endl; break;
case 5111 : cout <<“15″<<endl; break;
case 1234 : cout <<“13″<<endl; break;
case 1024 : cout <<“10″<<endl; break;
case 1023 : cout <<“11″<<endl; break;
case 1010 : cout <<“12″<<endl; break;
case 31 : cout <<“6” <<endl; break;
}
return 0;
}
笔记：测试值都能试出来，是个狠人
版权声明：
本文为博主原创文章，遵循 CC 4.0 BY-SA 版权协议，转载请附上原文出处链接和本声明。本文链接：https://blog.csdn.net/erutan_pku/article/details/24501203