本文共 1048 字，大约阅读时间需要 3 分钟。

hello大家好，欢迎大家访问 林深时不见鹿 的博客，算法小白，记录学习的点滴日常，致力于通俗易懂的题解，相遇即是上上签，如有不足，还请多多指教。

1.题目

给定一个自然数，有两种操作，

1.将数字乘 2。 2.将数字减去 1。 如果某次操作后数字不为正数，则终止。 一开始你拥有的是数字 n 。

你的目标是得到数字 m 。为了获得这个结果，他最少需要做多少次操作？

输入格式

输入一行，两个整数 n 和 m (1 ≤ n, m ≤ 104)，以空格分隔。

输出格式

输出最少操作的次数。

输入输出样例

输入 2 3 输出 2 输入 11 1 输出 10 样例说明 样例1中，先乘2，再减1

样例2中，疯狂减一即可

2.思路(1) 逆向思维

1.如果n>m，只能通过减一操作来获得m。

2.n<=m，考虑逆向思维，n变到m需要n-1和n*2两种操作，那么反过来由m变到n需要m+1和m/2两种操作，对应的操作数是相同的，但逆向更有助于我们思考。 3.如果m是奇数，无法进行m/2操作，进行m+1，使其变为偶数。如果m是偶数，直接m/2，重复上述操作，直到n>=m时退出，最后的操作数再加上n-m。

3.代码

#include
   
    #include
    
     using namespace std;int main(){   	int n,m;	cin>>n>>m;	int ans=0;	if(n>m) 	{   		ans=n-m;	}	else	{   		while(n
    
   

4思路(2) bfs

这道题非常类似于 可以说是那道题的缩小版

直接bfs搜索。

5.代码

#include
   
    #include
    
     #include
     
       using namespace std;const int N=1e4+10;int q[N];int dist[N]; int n,m;int bfs(){       memset(dist,-1,sizeof(dist));    int hh=0,tt=0;    q[0]=n;    dist[n]=0;    while(hh<=tt)    {       	int t=q[hh++];    	if(t==m)  return dist[m];    	if(t-1
      
       >n>>m;   cout<
       
        <