在 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。

  • 最后，我们将得到期望的结果。

  • 在主函数中打印结果。

Explore our latest online courses and learn new skills at your own pace. Enroll and become a certified expert to boost your career.

示例

Open Compiler
#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 次查看

开启你的 职业生涯

通过完成课程获得认证

开始学习
广告