تفکر الگوریتمی

الگوریتم حدس و بررسی (Guess and Check): ریشهٔ سوم صحیح

۴ دقیقه مطالعه · به‌روزرسانی ۲۲ مهر ۱۴۰۵

الگوریتم‌های تکرارشونده (iterative) کارهایی را ممکن می‌کنند که با یک محاسبهٔ سادهٔ یک‌خطی نمی‌شود انجام داد: یک دنباله از قدم‌ها را بر اساس یک تصمیم، بارها تکرار می‌کنیم. یکی از ساده‌ترین و مفیدترین این الگوریتم‌ها روش «حدس بزن و بررسی کن» است.

ایده

یادتان هست ریشهٔ دوم را چطور تعریف می‌کردیم؟ «g ریشهٔ دوم x است اگر g * g == x».

این تعریف به ما نمی‌گوید جواب را چطور پیدا کنیم، ولی به ما می‌گوید یک حدس را چطور بررسی کنیم. پس اگر بتوانیم حدس‌ها را به‌ترتیب تولید کنیم، کافی است هر کدام را با تعریف چک کنیم.

فقط به یک راه خوب برای تولید حدس‌ها نیاز داریم.

ریشهٔ سوم کامل

مسئله: عدد صحیح x را بگیرید و اگر ریشهٔ سوم صحیح دارد (یعنی «مکعب کامل» است)، آن را پیدا کنید.

تولید حدس: اول 0 را امتحان می‌کنیم، بعد 1، بعد 2، … و هر بار بررسی می‌کنیم آیا g ** 3 == x. مثلاً برای x = 125:

کِی دست بکشیم؟ وقتی g ** 3 از x بزرگ‌تر شد، دیگر هیچ عدد بزرگ‌تری جواب نیست. چون تعداد حدس‌ها محدود است، الگوریتم حتماً تمام می‌شود.

با while

x = int(input("Enter an integer: "))
ans = 0
while ans ** 3 < x:
    ans = ans + 1

if ans ** 3 != x:
    print(str(x) + " is not a perfect cube")
else:
    print("Cube root of " + str(x) + " is " + str(ans))

با 125، 126 و 27 امتحان کنید. حلقه در هر حالت روی اولین ans که مکعبش کمتر نیست می‌ایستد؛ بعد از حلقه بررسی می‌کنیم آیا دقیقاً برابر شده یا از آن رد شده‌ایم.

💡 هر سه ویژگی متغیر حلقه را اینجا می‌بینید: ans بیرون حلقه مقدار گرفته، داخلش زیاد می‌شود و شرط پایان بر اساس آن است.

اعداد منفی

با -27 چه می‌شود؟ شرط 0 < -27 از همان اول False است و برنامه می‌گوید «مکعب کامل نیست»، که غلط است (جواب -3 است).

راه‌حل: روی قدر مطلق (abs) جست‌وجو کنید و اگر عدد منفی بود، آخر کار علامت جواب را برگردانید:

x = int(input("Enter an integer: "))
ans = 0
while ans ** 3 < abs(x):
    ans = ans + 1

if ans ** 3 != abs(x):
    print(str(x) + " is not a perfect cube")
else:
    if x < 0:
        ans = -ans
    print("Cube root of " + str(x) + " is " + str(ans))

با for

همین ایده را می‌شود با for هم نوشت. چون ریشهٔ سوم یک عدد هیچ‌وقت از خودش بزرگ‌تر نیست، حدس‌ها را از 0 تا abs(x) تولید می‌کنیم:

cube = -27
for guess in range(abs(cube) + 1):
    if guess ** 3 >= abs(cube):
        break

if guess ** 3 != abs(cube):
    print(cube, "is not a perfect cube")
else:
    if cube < 0:
        guess = -guess
    print("Cube root of " + str(cube) + " is " + str(guess))

break مهم است: بدون آن، حلقه تا آخر range ادامه می‌دهد، حتی بعد از پیدا کردن جواب.

جست‌وجوی جامع (Exhaustive Search)

به این شیوه جست‌وجوی جامع یا «فراگیر» (exhaustive search) هم می‌گویند: همهٔ حالت‌های ممکن را یکی‌یکی امتحان می‌کنیم.

• ✅ مزیت: ساده است و اگر جواب وجود داشته باشد، حتماً پیدایش می‌کند.
• ❌ عیب: برای فضای جست‌وجوی بزرگ کند است. برای x حدود یک میلیارد، حدود ۱۰۰۰ حدس لازم است (چون 1000 ** 3 یک میلیارد است)؛ ولی اگر می‌خواستیم ریشهٔ دوم بگیریم، حدود ۳۱۶۰۰ حدس.

یک مشکل بزرگ‌تر هم داریم: اگر x مکعب کامل نباشد چه؟ ریشهٔ سوم ۲۹ حدود 3.072 است. با حدس‌های صحیح هیچ‌وقت به آن نمی‌رسیم، و بین ۳ و ۴ بی‌نهایت عدد اعشاری وجود دارد. این مسئلهٔ درس بعد است.

تمرین

با روش حدس و بررسی برنامه‌ای بنویسید که عدد صحیح مثبت n را بگیرد و بگوید آیا مجذور کامل (مربع یک عدد صحیح) است. مثلاً ۴۹ هست (۷×۷) و ۵۰ نیست.

n = int(input("n: "))
g = 0
while g * g < n:
    g += 1

if g * g == n:
    print(f"{n} = {g} × {g}")
else:
    print(f"{n} مجذور کامل نیست")