พิจารณาว่าเรามีค่าเริ่มต้นของจำนวนเต็มบวกสองจำนวน 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
