الگوریتم اقلیدس
Euclidean Algorithmالگوریتم اقلیدس GCD را با تکرار تبدیل (a,b) به (b, a mod b) پیدا می‌کند تا remainder صفر شود.
اول این مفهوم را در ذهن نگه دار
الگوریتم اقلیدس GCD را با تکرار تبدیل (a,b) به (b, a mod b) پیدا می‌کند تا remainder صفر شود.
چطور کار می‌کند؟ ساده و مرحله‌ای
خاصیت اصلی این است که gcd(a,b) = gcd(b, a mod b).
نسبت به امتحان کردن همه divisorها بسیار سریع‌تر است.
الگوریتم را به شکل تصمیم‌های پشت سر هم بخوان
خاصیت یا رابطه ریاضی را واضح بگو.
محدوده اعداد و representation را مشخص کن.
رابطه را به computation تبدیل و precision/overflow را بررسی کن.
یک ورودی خیلی کوچک را دستی اجرا کن و بعد از هر عملیات مهم state را بنویس. برای الگوریتم اقلیدس هدف این است که invariant را ببینی، نه اینکه کد را حفظ کنی.
function gcd(a, b) {
a = Math.abs(a);
b = Math.abs(b);
while (b !== 0) {
[a, b] = [b, a % b];
}
return a;
}syntax را حفظ نکن. stateای را که در هر خط تغییر می‌کند دنبال کن و آن را به invariant توضیح‌داده‌شده در بالا وصل کن.
O(log min(a,b))
این Complexity را حفظی نگو. اول مشخص کن مربوط به کدام عملیات یا بعد ورودی است؛ بعد هزینه را از روی loopها، عمق recursion، عملیات ساختمان داده و فرض‌های preprocessing نتیجه بگیر.
موارد مناسب
- وقتی خاصیت ریاضی می‌تواند brute force را حذف کند از آن استفاده کن.
کجا معمولاً اشتباه می‌کنیم؟
- نادیده گرفتن precision ممیز شناور یا دامنه integer.
- استفاده از فرمول خارج از فرض‌های معتبرش.
مدل یک پاسخ حرفه‌ای
در مصاحبه خاصیتی که مرحله modulo را معتبر می‌کند توضیح بده؛ فقط یک loop حفظی تحویل نده.
الگوریتم اقلیدس چه مسئله‌ای را حل می‌کند؟
الگوریتم اقلیدس GCD را با تکرار تبدیل (a,b) به (b, a mod b) پیدا می‌کند تا remainder صفر شود.
درباره Complexity چه چیزی باید بگویم؟
پیچیدگی معمول اینجا O(log min(a,b)) است، اما جواب کامل باید این هزینه را به representation، constraint ورودی و عملیات غالب وصل کند.
رایج‌ترین اشتباه چیست؟
نادیده گرفتن precision ممیز شناور یا دامنه integer.