سوال پانزدهم - 15 Project Euler (همراه راه حل)
متن سوال:
اگر از سمت چپ و بالای یک جدول 2*2 شروع کرده،6 راه برای رسیدن به سمت راست و پایین جدول وجود دارد(فقط حرکت های راست و پایین).
در یک جدول 20*20 چند راه وجود دارد؟
راه حل:
راه حل اول همیشه brute force هست ولی در مورد بعضی از سوالات کاربرد ندارد واین سوال جزو این دسته از سوالات هست و راه های خیلی بهتری هم وجود دارد پس این راه حل کنار گذاشته می شود.
راه حل دوم:
برنامه نویسی پویا(Dynamic Programming)
خوب راه حل من این است که به جای اینکه از اول شروع کرده و تعداد راه هایی که می شود به یک نقطه رسید را بشماریم و کم کم مربع ها را بزرگ تر کنیم.
خوب اگر یکی از مربع ها را در نظر بگیریم دو نقطه اطراف نقطه راست پایین فقط یک راه برای رسیدن به آنها وجود دارد.
پس تمام نقاط روی دو ضلع کناری و مجاور نقطه مورد نظر ما تعدا راهشان برابر با یک است(چرا؟).
حالا می رویم سراغ نقطه روبرویی.خوب ما اگر دو نقطه پایینی و سمت راستی نقطه رو با هم جمع کنیم تعداد راه های رسیدن به نقطه مذکور به دست می آید زیرا هردونقطه کناری و پایینی فقط یک راه به نقطه ما دارند پس اگر تعداد راه های رسیدن به این دوتا نقطه را یاهم جمع کنیم در واقع تعداد راه های نقطه مورد نظر ما به دست می آید.مثلا در شکل پایین راه رسیدن به نقطه روبرو یی برابر با 2 است که از حاصل جمع دونقطه دیگر به دست آمده است. و همین کار را برای بقیه نقطه ها نیز انجام می دهیم تا به جواب برسیم.
اینم کد این راه حل:
راه حل سوم:
ترکیبیات(Combinatorics)
خوب بدیهی است که ما باید به اندازه ول مربع به راست و به اندازه عرض به پایین حرکت کنیم(چرا؟).
اگر به ازای هر حرکت به سمت راست Rو هر حرکت به سمت پایین D بگذاریم یک رشته به طول دو برابر ضلع مربع به دست می آید.
برای مثال در مربع 2*2 کلمه های درست شده برابر هستند با
1) DDRR 2) DRDR 3) DRRD 4) RDRD 5) RDDR 6) RRDD.
پس تعداد راه های ما برابر است با تعدا کلمه های متمایزی که با این حروف می توانیم درست کنیم و طبق قوانین ترکیبیات تعداد برابر است با
(!m+n)!/(m!*n)
که برابر است با (m,m+n) و از طرفی خود این فرمول(مطالب بیشتر در ویکی پدیا)برابر است با
پس از طریق آخریه می تونید کدش رو بزنید کد زدنش با خودتون خیلی آسونه D:
امید وارم خوشتون بیاد.
بس عالی هستش :
به کارتون ادامه بدید اما از مسیر اصلی دور نشید :)