جواب سوال 15: مسیرهای یک شبکه منظم Lattice paths

پروژه اویلر

چالش پانزدهم سایت Project Euler یک سوال خیلی جالب هست. من کمی توی یافتن راه حل به مشکل برخوردم اما وقتی راه حساب کردن جواب ها را پیدا کردم پیاده سازی کدبرنامه نویسی کار سختی نبود:

با شروع از گوشه بالا سمت چپ یک شبکه 2 در 2، وقتی فقط قادر به حرکت به سمت راست یا پایین باشیم، دقیقا 6 مسیر متفاوت برای رسیدن به نقطه پایین سمت راست داریم:

چالش 15 پروژه اویلر

چند مسیر در شبکه 20 در 20 وجود دارد؟

ابتدا کمی درمورد مسئله فکر کنید…

خوب راه حل ساده است، اما رسیدن به آن سخت wink ما در مربع یک در یک دقیقا 2 مسیر داریم، در مربع 2 در یک و یک در 2 هم 3 مسیر. و همینطور در مربع های 3*1 چهار مسیر، 4*1 پنج مسیر و الی آخر. پس نتیجه میگیریم مربع های گوشه شبکه از آخرین مربع 2 مسیر و همینطور هرچه به سمت چپ یا بالا حرکت کنیم به ازای هر حرکت یک مسیر به آن اضافه می شود.

پس تا اینجا ما تعداد مسیرهای مربع های سمت راست و مربع های پایین شبکه را پیدا کردیم. حالا تعداد مسیرهای مربع های داخل را باید پیدا کنیم که جواب آن هم ساده است و از جمع تعداد مسیرهای مربع سمت راستی و زیری آن به دست می آید! پس مسئله ما حل شد و با چند حلقه قابل پیاده سازی است.

import numpy as np
n = 20
a = np.zeros((n, n))

for i in range(n):
    a[i, 0] = i+2
    a[0, i] = i+2

for i in range(1, n):
    for j in range(1, n):
        a[i, j] = a[i, j-1]+a[i-1, j]

print(int(a[n-1, n-1]))

دیدگاهتان را بنویسید

نشانی ایمیل شما منتشر نخواهد شد.