数値 n を 1 に変更するために必要な最小操作数を計算する C++ プログラム

数値 n があるとします。これらの演算の 1 つを任意に実行します -

• n が 2 で割り切れる場合、n を n/2 に置き換えます

• n が 2 で割り切れる場合2 n が 3 で割り切れる場合、n を 2n/3

• n が 5 で割り切れる場合、n を 4n/5

  li>

に置き換えます。

数値 1 に必要な最小手数を計算する必要があります。不可能な場合は、-1 が返されます。

入力が n = 10 のような場合、n/2 を使用すると 5 が得られ、次に 4n/5 を使用して 4 が得られ、さらに n/2 を使用すると 2 が得られるため、出力は 4 になります。そして再び 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

Example

次の実装を見てみましょう。理解を深める -

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

input

10

output

4

以上が数値 n を 1 に変更するために必要な最小操作数を計算する C++ プログラムの詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。