พิจารณาว่าเรามีค่าเริ่มต้นของจำนวนเต็มบวกสองจำนวน X และ Y หาค่าสุดท้ายของ X และ Y ซึ่งจะมีการเปลี่ยนแปลงดังนี้ −
- ขั้นตอน 1 − ถ้า X = 0 และ Y = 0 ให้หยุดกระบวนการ มิฉะนั้นไปขั้นตอน 2
- ขั้นตอน 2 − ถ้า X >= 2Y ให้ตั้งค่า X = X - 2Y และไปขั้นตอน 1 มิฉะนั้นไปขั้นตอน 3
- ขั้นตอน 3 − ถ้า Y >= 2X ให้ตั้งค่า Y = Y - 2X และไปขั้นตอน 1 มิฉะนั้นจบกระบวนการ
ตัวเลข X และ Y จะอยู่ในช่วง [0 และ 1018] ดังนั้นเราสามารถใช้วิธี Brute Force ได้
ตัวอย่าง
#include <iostream>
using namespace std;
void alterNumber(long long x, long long y) {
while (1) {
if (x == 0 || y == 0)
break;
if (x >= 2 * y)
x = x % (2 * y);
else if (y >= 2 * x)
y = y % (2 * x);
else
break;
}
cout << "X: " << x << "\n" << "Y: " << y;
}
int main() {
long long x = 12, y = 5;
alterNumber(x, y);
}
ผลลัพธ์
X: 0 Y: 1
