المپدیا

دانش‌نامه‌ی المپیاد کامپیوتر ایران

ابزار کاربر

ابزار سایت


سوالات المپیاد:مرحله ی اول:دوره ی ۳۴:سوالات ۱۱ تا ۱۲

سوالات ۱۱ تا ۱۲

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

راهنمایی

با توجه به اینکه کتیبه‌ها به شیوه‌ی بازگشتی ساخته می‌شوند، در هر دو بخش، تلاش برای حل مسئله به روش بازگشتی می‌تواند مفید باشد.

سوال ۱۱

راهنمایی

اگر تعداد مسیرهای با بزرگی $n$ در کتیبه‌ی شماره $n$ برابر $f(n)$ باشد، تلاش کنید $f(n)$ را به صورت بازگشتی محاسبه کنید.

راهنمایی

هر مسیر در کتیبه‌ی شماره $n$، یا کاملاً درون یکی از زیرکتیبه‌ها قرار دارد، یا از دایره‌ی بالایی کتیبه می‌گذرد.

سوال ۱۲

راهنمایی

اگر تعداد مسیرهای تکفام در کتیبه‌ی شماره $n$ برابر $g(n)$ باشد، محاسبه $g(n)$ به صورت بازگشتی شباهت زیادی به محاسبه $f(n)$ در سوال قبل دارد.

راهنمایی

اگر تعداد مسیرهای تکفام در کتیبه‌ی شماره $n$، که از راس بالایی کتیبه می‌گذرند برابر $h(n)$ باشد، تلاش کنید $h(n)$ را به صورت بازگشتی محاسبه کنید.

راهنمایی

رنگ راس بالایی کتیبه‌ی شماره $n$ با رنگ راس بالایی کتیبه‌ی شماره $n - 1$ متفاوت و با رنگ راس بالایی کتیبه‌ی شماره $n - 2$ یکسان است.


ابزار صفحه