C++程序用于计算使数字n变为1所需的最小操作次数-C++-PHP中文网

C++程序用于计算使数字n变为1所需的最小操作次数

WBOY

发布： 2023-09-14 22:53:12

转载

1375人浏览过

c++程序用于计算使数字n变为1所需的最小操作次数

假设我们有一个数字n。我们任意执行这些操作之一 -

当 n 可被 2 整除时，将 n 替换为 n/2
当 n 可被 3 整除时，将 n 替换为 2n/3
当 n 可被 5 整除时，将 n 替换为 4n/5

立即学习“C++免费学习笔记（深入）”；

怪兽AI数字人
数字人短视频创作，数字人直播，实时驱动数字人

44

查看详情
li>

我们必须计算出数字 1 所需的最小移动次数。如果不可能，则返回 -1。

因此，如果输入类似于 n = 10，则输出将为 4，因为使用 n/2 得到 5，然后使用 4n/5 得到 4，然后再次 n/2 得到 2，再次 n/2 得到 1。

步骤

步骤 h2>

为了解决这个问题，我们将按照以下步骤操作 -

m := 0
while n is not equal to 1, do:
   if n mod 2 is same as 0, then:
      n := n / 2
      (increase m by 1)
   otherwise when n mod 3 is same as 0, then:
      n := n / 3
      m := m + 2
   otherwise when n mod 5 is same as 0, then:
      n := n / 5
      m := m + 3
   Otherwise
      m := -1
      Come out from the loop
return m

登录后复制

示例

让我们看看以下实现，以便更好地理解 -

#include <bits/stdc++.h>
using namespace std;

int solve(int n) {
   int m = 0;
   while (n != 1) {
      if (n % 2 == 0) {
         n = n / 2;
         m++;
      }
      else if (n % 3 == 0) {
         n = n / 3;
         m += 2;
      }
      else if (n % 5 == 0) {
         n = n / 5;
         m += 3;
      }
      else {
         m = -1;
         break;
      }
   }

   return m;
}
int main() {
   int n = 10;
   cout << solve(n) << endl;
}

登录后复制