数据结构
网络
关系数据库管理系统 (RDBMS)
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
时尚研究
法学研究在 C++ 中查找从 N 到达 M 的最小步数
假设我们有两个整数 N 和 M。我们必须找到通过执行给定操作从 N 到达 M 的最小步数：
- 将数字 x 乘以 2，因此 x 将变为 2*x
- 从数字 x 中减去 1，因此数字将变为 x – 1
如果 N = 4 且 M = 6，则输出为 2。因此，如果我们对 N 执行操作编号 2，则 N 变为 3，然后对 N 的更新值执行操作编号 1，因此它变为 2 * 3 = 6。因此，最小步数为 2。
为了解决这个问题，我们将遵循以下规则：
- 我们可以反转问题，例如我们从 M 开始取数字 N，因此新的两个操作将是
- 当数字为偶数时，将其除以 2；
- 在数字上加 1
- 现在，最小操作数将是
- 如果 N > M，则返回它们之间的差值，因此步数将是将 1 加到 M 上，直到它等于 N
- 否则，当 N < M 时，继续将 M 除以 2，直到它小于 N。如果 M 是奇数，则首先加 1，然后除以 2。一旦 M 小于 N，将它们之间的差值与上述操作的计数一起添加到计数中。
示例
#include<iostream> using namespace std; int countMinimumSteps(int n, int m) { int count = 0; while(m > n) { if(m % 2 == 1) { m++; count++; } m /= 2; count++; } return count + n - m; } int main() { int n = 4, m = 6; cout << "Minimum number of operations required: " << countMinimumSteps(n, m); }
输出
Minimum number of operations required: 2
更新于：2019年12月18日
771 次浏览
广告