Processing math: 100%

المپدیا

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

ابزار کاربر

ابزار سایت


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

سوال ۱۰

استاد شیفو می‌خواهد یک برنامه‌ی تمرینیِ 12 ساعته برای تقویت عضلات دست و پا طراحی کند. این برنامه به‌صورت دنباله‌ای از بلوک‌های تمرینی است. هر بلوک تمرینی، یا مربوط به ورزش دست است یا ورزش پا، و مدت زمان آن نیز بر حسب ساعت، عددی طبیعی است. مثلا یک بلوک تمرینی می‌تواند از 3 ساعت تمرین پا تشکیل شده باشد. استاد شیفو به این نتیجه رسیده است که یک برنامه‌ی تمرینی مناسب، دارای شرایط زیر است:

  1. بلوک‌های تمرینی باید به‌شکل یکی‌درمیان، مربوط به ورزش دست و ورزش پا باشند.
  2. اولین بلوک تمرینی باید مربوط به ورزش دست باشد.
  3. آخرین بلوک تمرینی باید مربوط به ورزش پا باشد.
  4. یک بلوک تمرینیِ ورزشِ پا، نباید از بلوک تمرینیِ قبل از آن، مدت زمان بیشتری داشته باشد.

شکل زیر نمونه‌ای از یک برنامه‌ی تمرینی با شرایط مذکور را نشان می‌دهد. چند برنامه‌ی تمرینیِ 12 ساعته وجود دارد که از نظر استاد شیفو مناسب باشد؟ دو برنامه‌ی تمرینی، متمایز محسوب می‌شوند اگر زمانی (در طولِ 12 ساعت) وجود داشته باشد که در یک برنامه، برای آن زمان، ورزشِ دست تعیین شده باشد، و در برنامه‌ی دیگر، برای آن زمان، ورزشِ پا تعیین شده باشد.

  1. 155
  2. 123
  3. 286
  4. 284
  5. 144

پاسخ

گزینه (۳) درست است.

برای حل این مسئله، f(n) را به‌عنوان تعداد روش‌های ساخت یک برنامه‌ی تمرینی n ساعته تعریف می‌کنیم. با حالت‌بندی روی مجموع طول دو بلوک تمرینی اول به بازگشتی زیر می‌رسیم:

f(n)=nk=2f(nk)k2

چرا که اگر مجموع طول دو بازه‌ی اول k باشد، از آنجایی که بلوک اول باید بزرگ‌تر یا مساوی بلوک دوم باشد، k2 حالت برای مشخص کردن طولشان وجود دارد. باقی برنامه‌ی تمرینی نیز دارای f(nk) حالت است.

به‌طور مشابه می‌دانیم:

f(n1)=n1k=2f(n1k)k2

بنابراین می‌توانیم بنویسیم:

f(n)=f(n1)+f(n2)+f(n4)+f(n6)+f(n8)+

اگر با استفاده از این ارتباط f(n2) را بنویسیم، داریم:

f(n2)=f(n3)+f(n4)+f(n6)+f(n8)+

پس به نتیجه می‌رسیم که:

f(n)=f(n1)+2f(n2)f(n3)

و همچنین داریم:

f(1)=0,f(2)=1,f(3)=1

با استفاده از رابطه‌ی بازگشتی به دست آمده، f(12) را به شکل زیر محاسبه می‌کنیم:

f=0,1,1,3,4,9,14,28,47,89,155,286.

بنابراین تعداد برنامه‌های تمرینی 12 ساعته که متناسب با شرایط مورد نظر استاد شیفو است، همان 286 می‌باشد.


ابزار صفحه