通过在 C++ 中执行给定的操作将数字减少到 1

给定一个整数 Number 作为输入。目标是找到将输入 Number 减少到 1 所需的最少步骤或操作数。可以执行的操作将是-:

  • 如果 Number 是偶数,则将其除以 2。

  • 如果 Number 为奇数,则将其增加或减少 1。

例子

输入 - 数字=28

输出 - 将 28 减少到 1 的最小步骤:6

说明-

28 是偶数 - 除以 2 = 14

14 是偶数 - 除以 2 = 7

7 是奇数 - 增加 1 = 8

8 是偶数 - 除以 2 = 4

4 是偶数 - 除以 2 = 2

2 是偶数 - 除以 2 = 1

输入 - 数字=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+分钟。

  • 最后我们会得到想要的结果。

  • 在 main 中打印结果。

示例

#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 <<"减少的最小步骤 "<<Number<<" to 1: "<<minWays(Number);
   return 0;
}
输出结果

如果我们运行上面的代码,它将生成以下输出

减少的最小步骤 21 to 1: 6