در برکه ای ۷ قطعه سنگ وجود دارد که از چپ به راست با اعداد ۱ تا ۷ شماره گذاری شده اند. قورباغه ای روی سنگ شماره یک نشسته است. فاصله سنگ ها به گونه ای است که اگر قورباغه روی سنگ i ام باشد می تواند حداکثر تا i سنگ جلوتر بپرد. به چند طریق ممکن است قورباغه، بدون برگشتن به سمت چپ، به سنگ شماره ۷ برسد؟ الف) ۱۰ ب) ۱۱ ج) ۱۲ د) ۱۳
جواب گزینه ب ۱۱ تا
روش سوم : گزینه ی (ب) صحیح است. بیایید از آخر مسئله را حل کنیم. فرض میکنیم که در حال حاضر روی سنگ i-اُم هستیم و تعداد روشهای مختلف برای رسیدن به سنگ ۷اُم را یادداشت می کنیم. ابتدا مسئله را برای سنگ ۷اُم حل می کنیم (۱ روش).
سپس برای سنگ ۶اُم و … در هر مرحله کافی است که برای سنگ iاُم، مجموع تعداد روشهای سنگهای ۱ +i اُم تا ۲iاُم را محاسبه کنیم. در نتیجه جواب مسئله اینگونه به دست می آید:
۷: ۱ → ۶: ۱ → ۵: ۲ → ۴: ۴ → ۳: ۷ → ۲: ۱۱ → ۱: ۱۱ روش دوم: استفاده از گراف های جهت دار و استفاده از ماتریس مجاورت آن است
در زیر نگاه کنید چون مسیر ها در واقع از ۲ شروع می شود در کل ۱۱ مسیر داریم . قسمت ۱ به ۲ در همه مسیر ها مشترک است