สมมติว่ามีจำนวนเต็มสองจำนวน N และ M เราต้องหาจำนวนขั้นตอนน้อยที่สุดเพื่อไปจาก N ถึง M โดยทำการดังนี้:
- คูณตัวเลข x ด้วย 2 ดังนั้น x จะเป็น 2*x
- ลบ 1 จากตัวเลข x ดังนั้นตัวเลขจะเป็น x – 1
ถ้า N = 4 และ M = 6 ผลลัพธ์จะเป็น 2 ดังนั้นถ้าเราทำการที่ 2 กับ N แล้ว N กลายเป็น 3 จากนั้นทำการที่ 1 กับค่าที่ปรับปรุงแล้วของ N ดังนั้นมันจะกลายเป็น 2 * 3 = 6 ดังนั้นจำนวนขั้นตอนน้อยที่สุดจะเป็น 2
เพื่อแก้ปัญหานี้ เราจะทำตามกฎเหล่านี้:
- เราสามารถกลับปัญหาได้ เช่น เราเอาตัวเลข N เริ่มจาก M ดังนั้นสองการดำเนินการใหม่จะเป็น
- หารตัวเลขด้วย 2 เมื่อเป็นเลขคู่
- บวก 1 กับตัวเลข
- ตอนนี้จำนวนขั้นตอนน้อยที่สุดจะเป็น
- ถ้า N > M ให้คืนค่าความต่างระหว่างพวกเขา จำนวนขั้นตอนจะเป็นการบวก 1 เข้าไปใน M จนกว่าจะเท่ากับ N
- มิฉะนั้นเมื่อ N < M ให้หาร M ด้วย 2 ซ้ำๆ จนกว่าจะน้อยกว่า N หาก M เป็นคี่ ให้บวก 1 ก่อน แล้วค่อยหารด้วย 2 เมื่อ M น้อยกว่า 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
