اگه صورت مساله رو راحت تر کنی راه حل رو راحت بدست میاری.فرض کن این خونه 3 در 3 باشه.:
کد:
برای مشاهده محتوا ، لطفا وارد شوید یا ثبت نام کنید
چون فقط مسیر به پایین و راست مجازه, تنها راه رسیده به b دو بار حرکت به راست و 2 بار حرکت به پایین توی حالت های مختلف هست.اگر R رو بگیریم حرکت به راست و D رو بگیریم حرکت به پایین, مساله این طوری میشه که R, R, D, D رو به چند صورت و چه صورت هایی میتونیم کنار هم بگذاریم؟
اگه خونه ی ما M سطر و N ستون داشته باشه, N-1 تا R و M-1 تا D داریم و باید مساله رو برای این مقدار ها حل کنیم.
قسمت اول یعنی" چند صورت" مثل یه مساله ی احتمال حل میشه:
کد:
برای مشاهده محتوا ، لطفا وارد شوید یا ثبت نام کنید
که ! علامت فاکتوریل هست که با پیاده سازیش توی C میشه جواب این قسمت رو راحت حساب کرد.
اما قسمت مشکل تر پیدا کردن کل راه هاست:
بدست آوردن راه هایی که میشه (M-1) تا R و (N-1) تا D رو کنار هم گذاشت.
خودم یکم زور زدم که بنویسمش اما الان 6 صبحه و من هنوز نخوابیدم مخم نمیکشه.
شاید اینایی که گفتم رو خودت میدونستی ولی به هر حال نوشتم تا بعدا دوباره نخوام بدستشون بیارم!