資料結構
網路
關係資料庫管理系統 (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 次瀏覽
廣告