สมมติว่าเรามีจำนวนเต็ม N และ M สองจำนวน เราต้องหาจำนวนขั้นตอนขั้นต่ำในการไปถึง M จาก N โดยดำเนินการตามที่กำหนด -
- คูณจำนวน x ด้วย 2 ดังนั้น x จะเป็น 2*x
- ลบหนึ่งจากจำนวน x ดังนั้นจำนวนจะเป็น x – 1
ถ้า N =4 และ M =6 ผลลัพธ์จะเป็น 2 ดังนั้นหากเราดำเนินการหมายเลข 2 บน N ดังนั้น N จะกลายเป็น 3 จากนั้นดำเนินการหมายเลขหนึ่งกับค่าที่อัพเดตของ N ดังนั้นมันจะกลายเป็น 2 * 3 =6 ดังนั้นจำนวนขั้นตอนขั้นต่ำจะเป็น 2
เพื่อแก้ปัญหานี้ เราจะปฏิบัติตามกฎเหล่านี้ -
- เราสามารถย้อนกลับปัญหาได้ เหมือนเราใช้หมายเลข N เริ่มจาก M ดังนั้นการดำเนินการใหม่สองรายการจะเป็น
-
- หารจำนวนด้วย 2 เมื่อเป็นเลขคู่
- บวก 1 ด้วยตัวเลข
- ตอนนี้จำนวนการดำเนินการขั้นต่ำจะเป็น
- ถ้า N> M ให้คืนค่าส่วนต่างระหว่างกัน ดังนั้นจำนวนขั้นตอนจะเพิ่ม 1 ถึง M จนกว่าจะเท่ากับ N
- มิฉะนั้น เมื่อ N
ตัวอย่าง
#include<iostream>
using namespace std;
int countMinimumSteps(int n, int m) {
int count = 0;
while(m > n) {
if(m % 2 == 1) {
m++;
count++;
}
m /= 2;
count++;
}
return count + n - m;
}
int main() {
int n = 4, m = 6;
cout << "Minimum number of operations required: " << countMinimumSteps(n, m);
} ผลลัพธ์
Minimum number of operations required: 2
