给定一个整数 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