المپیاد کامپیوتر

ترکیبیات,برنامه نویسی,گراف,الگوریتم , و کلا کامپیوتر

المپیاد کامپیوتر

ترکیبیات,برنامه نویسی,گراف,الگوریتم , و کلا کامپیوتر

المپیاد کامپیوتر
دنبال کنندگان ۳ نفر
این وبلاگ را دنبال کنید

سوال پانزدهم - 15 Project Euler (همراه راه حل)

چهارشنبه, ۲۵ بهمن ۱۳۹۱، ۰۵:۲۴ ب.ظ

متن سوال:

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

                                        

در یک جدول 20*20 چند راه وجود دارد؟

راه حل:

راه حل اول همیشه brute force هست ولی در مورد بعضی  از سوالات کاربرد ندارد واین سوال جزو این دسته از سوالات هست و راه های خیلی بهتری هم وجود دارد پس این راه حل کنار گذاشته می شود.

راه حل دوم:

برنامه نویسی پویا(Dynamic Programming)

خوب راه حل من این است که به جای اینکه از اول شروع کرده و تعداد راه هایی که می شود به یک نقطه رسید را بشماریم و کم کم مربع ها را بزرگ تر کنیم.

خوب اگر یکی از مربع ها را در نظر بگیریم دو نقطه اطراف نقطه راست پایین فقط یک راه برای رسیدن به آنها وجود دارد.

                                                           Example Grid 1 step from Goal

پس تمام نقاط روی دو ضلع کناری و مجاور نقطه مورد نظر ما تعدا راهشان برابر با یک است(چرا؟).

حالا می رویم سراغ نقطه روبرویی.خوب ما اگر دو نقطه پایینی و سمت راستی نقطه رو با هم جمع کنیم تعداد راه های رسیدن به نقطه مذکور به دست می آید زیرا هردونقطه کناری و پایینی فقط یک راه به نقطه ما دارند پس اگر تعداد راه های رسیدن به این دوتا نقطه را یاهم جمع کنیم در واقع تعداد راه های نقطه مورد نظر ما به دست می آید.مثلا در شکل پایین راه رسیدن به نقطه روبرو یی برابر با 2 است که از حاصل جمع دونقطه دیگر به دست آمده است. و همین کار را برای بقیه نقطه ها نیز انجام می دهیم تا به جواب برسیم.

                                                                Example Grid - Larger subproblem

اینم کد این راه حل:

کد

راه حل سوم:

ترکیبیات(Combinatorics)

خوب بدیهی است که ما باید به اندازه ول مربع به راست و به اندازه عرض به پایین حرکت کنیم(چرا؟).

اگر به ازای هر حرکت به سمت راست Rو هر حرکت به سمت پایین D بگذاریم یک رشته به طول دو برابر ضلع مربع به دست می آید.

برای مثال در مربع 2*2 کلمه های درست شده برابر هستند با

1) DDRR 2) DRDR 3) DRRD 4) RDRD 5) RDDR 6) RRDD.

پس تعداد راه های ما برابر است با تعدا کلمه های متمایزی که با این حروف می توانیم درست کنیم و طبق قوانین ترکیبیات تعداد برابر است با

(!m+n)!/(m!*n)

که برابر است با (m,m+n) و از طرفی خود این فرمول(مطالب بیشتر در ویکی پدیا)برابر است با

                              \displaystyle \binom{n}{k} = \frac{n(n-1)(n-2)\hdots(n-k 1)}{k(k-1)(k-2)\hdots1} = \prod_{i=1}^k \frac{n-k i}{i}

پس از طریق آخریه می تونید کدش رو بزنید کد زدنش با خودتون خیلی آسونه D:

امید وارم خوشتون بیاد.

  • موافقین ۲ مخالفین ۲
  • ۹۱/۱۱/۲۵
  • ۹۶۰ نمایش
  • محمدصادق دهقان نیری

نظرات (۲)

بس عالی هستش :

به کارتون ادامه بدید اما از مسیر اصلی دور نشید :)

پاسخ:
نظر لطفتونه
  • نگار ابراهیمی
  • توی روش ترکیبیات تعداد برابر   (!m+n)!/(m!*n) هست. :)
    پاسخ:
    D:
    ارسال نظر آزاد است، اما اگر قبلا در بیان ثبت نام کرده اید می توانید ابتدا وارد شوید.
    شما میتوانید از این تگهای html استفاده کنید:
    <b> یا <strong>، <em> یا <i>، <u>، <strike> یا <s>، <sup>، <sub>، <blockquote>، <code>، <pre>، <hr>، <br>، <p>، <a href="" title="">، <span style="">، <div align="">
    تجدید کد امنیتی