数据结构
网络
关系型数据库管理系统
操作系统
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 次查看
广告