C++程式用來計算使數字n變成1所需的最小操作次數

假設我們有一個數字n。我們任意執行這些操作之一-

• 當n 可被2 整除時，將n 替換為n/2

• 當n 可被3 整除時，將n 替換為2n/3

• 當n 可被5 整除時，將n 替換為4n/5

  ## 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;
}

輸入

10

輸出

4

以上是C++程式用來計算使數字n變成1所需的最小操作次數的詳細內容。更多資訊請關注PHP中文網其他相關文章！