資料結構
網路
關係型資料庫管理系統
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理
化學
生物
數學
英語
經濟學
心理學
社會學
時尚研究
法律研究在 C++ 中透過給定操作將數字縮減到 1
給定一個整數 Number 作為輸入。目標是找到將輸入 Number 縮減到 1 所需的最少步驟或操作次數。
如果 Number 為偶數，則將其除以 2。
如果 Number 為奇數，則將其加 1 或減 1。
示例
輸入 − Number=28
輸出 − 將 28 縮減到 1 的最小步數：6
解釋−
28 是偶數 - 除以 2 = 14
14 是偶數 - 除以 2 = 7
7 是奇數 - 加 1 = 8
8 是偶數 - 除以 2 = 4
4 是偶數 - 除以 2 = 2
2 是偶數 - 除以 2 = 1
輸入 − Number=9
輸出 − 將 9 縮減到 1 的最小步數：4
解釋 −
9 是奇數 - 減 1 = 8
8 是偶數 - 除以 2 = 4
4 是偶數 - 除以 2 = 2
2 是偶數 - 除以 2 = 1
下面程式中使用的策略如下
在這種方法中，使用遞迴方法來檢查將 Number 縮減到 1 所需的最少操作次數。如果它是偶數，則簡單地除以 2，否則遞迴檢查 Number+1 或 Number-1 的最小方法，以較小的那個為準。
將輸入 Number 作為整數。
函式 minWays(int num) 以 num 作為輸入，並返回將 num 縮減到 1 所需的最少操作次數。
將變數 tmp1、tmp2 和 min 作為整數。
如果 num 為 0，則返回 1。
如果 num%2==0，則它是偶數，則設定 num=num/2
如果 num 為奇數，則設定 tmp1=minWays(num-1) 和 tmp2=minWays(num+1)。
設定 min 為 tmp1 和 tmp2 的最小值。
返回 1+min。
最後，我們將得到期望的結果。
在主函式中列印結果。
示例
#include <iostream>
using namespace std;
int minWays(int num){
int tmp1,tmp2,min;
if (num == 1){
return 0;
}
else if (num % 2 == 0){
tmp1=minWays(num/2);
return (1 + tmp1);
}
else{
int tmp1=minWays(num - 1);
int tmp2=minWays(num + 1);
int min=tmp1<tmp2?tmp1:tmp2;
return (1 + min);
}
}
int main(){
int Number = 21;
cout <<"Minimum steps to reduce "<<Number<<" to 1: "<<minWays(Number);
return 0;
}輸出
如果我們執行以上程式碼，它將生成以下輸出
Minimum steps to reduce 21 to 1: 6
更新於： 2021-11-03
959 次檢視
廣告