숫자 n을 1로 변경하는 데 필요한 최소 연산 수를 계산하는 C++ 프로그램

숫자 n이 있다고 가정해보세요. 다음 연산 중 하나를 임의로 수행합니다.

• n이 2로 나누어지면 n을 n/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가 되고, n/2는 다시 1이 되기 때문에 출력은 4가 됩니다.

Steps

Steps 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 중국어 웹사이트의 기타 관련 기사를 참조하세요!