笔试题：输入两个数n和m，现在只有两种变换方法，第一种是减1，第二种是*2，问：从n到m最少使用多少步？

输入两个数n和m，现在只有两种变换方法，第一种是减1，第二种是*2，问：从n到m最少使用多少步？ 输入：4  5   输出：3 输入：5  12   输出：
2023-11-24 技术

输入两个数n和m，现在只有两种变换方法，第一种是减1，第二种是*2，问：从n到m最少使用多少步？

输入：4  5   输出：3

输入：5  12   输出：4

输入：5  14  输出：4

输入：4  6   输出：2

 

思路为分段改写：

1. n>=m  说明*2根本用不上，只能用减法  步骤就是   n-m

2.如果nm 这种情况下，首先让n减少到m/2，在*2是最快的（可以把他们都变换成二进制证明，证明略....）

如果m是奇数则给m+1，让它变成偶数，然后在最后的步骤上加1（最后-1）

3.如果2n 

#include
#include
#include
#include 
#include 
#include 
using namespace std;int main() 
{int n = 0, m = 0;cin >> n >> m;if (n>=m)cout << n-m << endl;else{int count = 0;  //减1int temp = 0;if (m % 2 == 1){count++;m++;}if (m - n <= n)cout << n - m / 2 + 1 + count << endl;else {while (1){if (m - n <= n)  //判断是否在范围内{cout << n - m / 2 + 1 + count + temp << endl;break;}m = m / 2;temp++;   //乘2if (m % 2 == 1){count++;m++;   //扩充为偶数}}}}system("pause");return 0;
}

 

版权声明

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若转载，请注明出处。如若内容有涉嫌抄袭侵权/违法违规/事实不符，请点击 举报 进行投诉反馈！

推荐阅读