Chương trình C ++ để đếm số lượng phép toán tối thiểu cần thiết để biến số n thành 1

Giả sử chúng ta có một số n. Chúng tôi thực hiện bất kỳ một trong các hoạt động này với số lần tùy ý -

• Thay n bằng n / 2 khi n chia hết cho 2

• Thay n bằng 2n / 3 khi n chia hết cho 3

• Thay n bằng 4n / 5 khi n chia hết cho 5

Chúng tôi phải đếm số lần di chuyển tối thiểu cần thiết để thực hiện số 1. Nếu không thể, hãy trả về -1.

Vì vậy, nếu đầu vào giống như n =10, thì đầu ra sẽ là 4, bởi vì sử dụng n / 2 để nhận được 5, sau đó 4n / 5 để nhận được 4, sau đó n / 2 một lần nữa để nhận được 2 và n / 2 một lần nữa để nhận được 1.

Các bước

Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -

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

Ví dụ

Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn -

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

Đầu vào

10

Đầu ra

4