المپدیا

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

ابزار کاربر

ابزار سایت


سوالات المپیاد:مرحله‌ی اول:دوره‌ی ۲۸:سوال ۲۰

تفاوت‌ها

تفاوت دو نسخه‌ی متفاوت از صفحه را مشاهده می‌کنید.

پیوند به صفحه‌ی تفاوت‌ها

سوالات_المپیاد:مرحله‌ی_اول:دوره‌ی_۲۸:سوال_۲۰ [2018/12/20 09:59] (فعلی)
Hamidreza seydi ایجاد شد
خط 1: خط 1:
 +====== سوال ۲۰ ======
 +
 +
 +در سوال قبل، به چند طریق می‌توانیم مهره را از خانه‌ی پایین-چپ به خانه‌ی بالا-راست برسانیم، طوری که از هر خانه ​
 +__حداکثر یک بار__
 +عبور کنیم؟
 +
 +
 +
 +  - ۱۰۰
 +  - ۱۱۶
 +  - ۵۶۰
 +  - ۴۶۴
 +  - ۴۸۰
 +
 +
 +
 +<​پاسخ>​
 + ​گزینه‌ی ۳ درست است.
 +
 +
 +
 +تعداد روش‌های رسیدن از خانه‌ی پایین-چپ به خانه‌ی بالا-راست در یک جدول
 +$2 \times n$ را
 +$a_n$
 +و تعداد روش‌های رسیدن از خانه‌ی بالا-چپ به خانه‌ی بالا-راست ​ در همین جدول را
 +$b_n$
 +در نظر می‌گیریم. با حالت‌بندی روی گام نخست، روابط بازگشتی زیر را داریم:
 +\begin{align*}
 +a_n&​=2a_{n-1}+2b_{n-1}+2a_{n-2}+2b_{n-2}\\
 +b_n&​=2a_{n-1}+2b_{n-1}+2a_{n-2}+2b_{n-2}\\
 +\end{align*}
 +از آن‌جایی که
 +$$a_1 = 1 \qquad a_2 = 5 \qquad b_1 = 1 \qquad b_2 = 5$$ 
 +مقدار
 +$a_5 = 560$
 +به دست می‌آید.
 +
 +
 +</​پاسخ>​
 +
 +  * [[سوال ۱۹|سوال قبل]]
 +  * [[سوال ۲۱|سوال بعد]]
  

ابزار صفحه