สมมติว่าเรามีตัวเลข 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 ในขณะที่ n ไม่เท่ากับ 1 ทำ: ถ้า n mod 2 เท่ากับ 0 แล้ว: n := n / 2 (เพิ่ม m ขึ้น 1) มิฉะนั้นเมื่อ n mod 3 เท่ากับ 0 แล้ว: n := n / 3 m := m + 2 มิฉะนั้นเมื่อ n mod 5 เท่ากับ 0 แล้ว: n := n / 5 m := m + 3 มิฉะนั้น m := -1 ออกจากลูป คืนค่า 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
