โปรแกรม C++ เพื่อนับจำนวนการดำเนินการขั้นต่ำที่จำเป็นในการสร้างตัวเลข n ถึง 1

สมมติว่าเรามีตัวเลข n เราดำเนินการอย่างใดอย่างหนึ่งในจำนวนนี้ตามอำเภอใจ -

แทนที่ n ด้วย n/2 เมื่อ n หารด้วย 2 ลงตัว
แทนที่ n ด้วย 2n/3 เมื่อ n หารด้วย 3 ลงตัว
แทนที่ n ด้วย 4n/5 เมื่อ n หารด้วย 5 ลงตัว

เราต้องนับจำนวนการเคลื่อนไหวขั้นต่ำที่จำเป็นเพื่อให้ได้เป็น 1 หากทำไม่ได้ ให้คืนค่า -1

ดังนั้น ถ้าอินพุตเป็นเหมือน n =10 ผลลัพธ์จะเป็น 4 เพราะใช้ n/2 เพื่อรับ 5 จากนั้น 4n/5 เพื่อให้ได้ 4 จากนั้น n/2 อีกครั้งเพื่อให้ได้ 2 และ n/2 อีกครั้งเพื่อให้ได้ 1.

ขั้นตอน

เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้ -

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