بستن پنجره
فرادرس - مجموعه آموزش‌های ویدئویی  مهندسی کامپیوتر - طراحی الگوریتم - ساختمان داده
بستن پنجره     نوشته‌های پربازدید اخیر

»    محاسبه‌ی دترمینان ماتریس

»    اشاره‌گرها در زبان ++C

»    حلقه‌های تکرار در ++C

»    معمای هشت وزیر

»    الگوریتم جستجوی اول سطح (BFS)

»    مسابقه‌ی برنامه‌نویسی آنلاین Codeforces Round 406

»    درخت جستجوی دودویی

بستن پنجره
وبگاه
این صفحه
اشتراک‌گذاری در LinkedIn     Cloob     اشتراک‌گذاری در Twitter
اشتراک‌گذاری در Facebook     ارسال با Telegram     Google Plus
بستن پنجره
وبگاه     این صفحه
اشتراک‌گذاری در LinkedIn     Cloob     اشتراک‌گذاری در Twitter     اشتراک‌گذاری در Facebook     ارسال با Telegram     Google Plus
مسأله‌ی مربی ناامید - الگوریتمستان
الگوریتمستان
1114.555.00
  »  

       

بررسی مسأله‌ی مربی ناامید، از سوالات مسابقات برنامه‌نویسی ACM

http://www.aachp.ir آنچه می‌خوانید ویراست جدید نوشته‌ای است که اولین بار با عنوان «مساله شماره 12» دی ماه 1386 از طریق وبگاه برنامه‌نویسی و طراحی الگوریتم (عنوان و طرح پیشین وبگاه الگوریتمستان) منتشر شده بود.


آنچه در این نوشته می‌خوانید:
   •  مسأله‌ی مربی ناامید
       »  مسأله
       »  ورودی مسأله
       »  خروجی مسأله
       »  حل مسأله

مسأله

  [بازگشت به فهرست]

    یکی از تیم‌های لیگ برتر فوتبال (جام خلیج فارس) امسال نتایج خیلی بدی گرفته است. هیئت مدیره‌ی باشگاه برای اخراج مربی تحت فشار هستند. اما این مربی از سوی طرفداران تیم به عنوان یک قهرمان محبوب حمایت می‌شود. به همین دلیل تصمیم می‌گیرند یک فرصت دیگر به مربی بدهند. سخنگوی باشگاه به رسانه‌ها اعلام می‌کند که هیئت مدیره‌ی باشگاه تنها زمانی از مربی حمایت می‌کنند که بتواند در 5 بازی آینده 11 امتیاز برای تیمشان کسب کند. مربی می‌خواهد بداند چقدر احتمال دارد به این موفقیت دست پیدا کند و از شما کمک می‌خواهد.فرض کنید احتمال کسب برد، باخت و تساوی در مسابقه‌های بعدی از روی مسابقات انجام شده تا به حال به دست می‌آید. به عنوان مثال اگر این تیم از 10 بازی انجام داده‌ی قبلی 3 برد داشته باشد، احتمال برد در آینده 30% خواهد بود.

    هجده تیم در این لیگ حضور دارند که همه‌ی آنها دو بازی رفت و برگشت با تیم‌های دیگر انجام می‌دهند. هر برد 3 امتیاز، هر تساوی 1 امتیاز و هر باخت صفر امتیاز دارد.

    

ورودی مسأله

  [بازگشت به فهرست]

هر ورودی دو سطر را شامل می‌شود. در سطر اول تعداد بازی‌های آتی و امتیازی که باید کسب شود قرار دارد. سطر دوم تعداد بردها، تساوی‌ها و باخت‌های قبلی تیم را نشان می‌دهد. انتهای ورودی با دو صفر مشخص می‌شود.

      

5  11

3  5  4

2  3

5  0  5

3  5

5  5  4

1  1

1  1  1

0  0

      

خروجی مسأله

  [بازگشت به فهرست]

خروجی به ازای هر ورودی یک سطر خواهد بود که احتمال موفقیت مربی بر اساس ورودی‌ها را نشان می‌دهد. این احتمالات باید دقیقا یک رقم اعشار دقت داشته باشند.

      

4.3

75.0

42.8

66.7

  

    منبع: مسابقه‌ی ACM منطقه‌ای آسیا 2007 - سایت تهران - مسأله‌ی Hopeless Coach

      

حل مسأله

  [بازگشت به فهرست]

ورودی‌های برنامه را به ترتیب n (تعداد بازی‌ها)، p (امتیازی که باید کسب شود)، w (تعداد بردها در گذشته)، d (تعداد تساوی‌ها در گذشته)، l (تعداد باخت‌ها در گذشته) در نظر بگیرید. اگر متغیرهای dp ،wp و lp برای ذخیره کردن احتمال برد، تساوی و باخت در هر یک از مسابقه‌های آتی تعریف شوند، بر اساس فرض‌های مسأله می‌توان نوشت:

      

\[ wp = \frac{w}{w+d+l} \] \[ dp = \frac{d}{w+d+l} \] \[ lp = \frac{l}{w+d+l} \]

      

    در آینده n بازی انجام خواهد شد. اگر تعداد بردها برابر i و تعداد تساوی‌ها برابر j باشد، احتمال برد (Pw)، تساوی (Pd) و باخت (Pl) بر اساس اصول شمارش به این صورت می‌شود:

      

\[ P_d = \begin{pmatrix} n  \\ i \end{pmatrix} wp^i \] \[ P_w = \begin{pmatrix} n - i \\ j \end{pmatrix} dp^j \] \[ P_l = \begin{pmatrix} n - i - j \\ n - i - j \end{pmatrix} lp^{n-i-j} \]

      

    این رویدادها مستقل از هم اتفاق می‌افتند. پس احتمال وقوع i برد، j تساوی و n - i - j باخت در n بازی به این صورت است:

      

\[ P = P_w \times P_d \times P_l = \begin{pmatrix} n \\ i \end{pmatrix} \begin{pmatrix} n - i \\ j \end{pmatrix} \; wp^i \; dp^j \; lp^{n-i-j} \]

      

    حال اگر این احتمال را برای تمام انتخاب‌های ممکن i و j که شرط حداقل امتیاز را برآورده کند (یعنی 3i + j ≥ p) جمع بزنیم، احتمال موفقیت مربی به دست می‌آید:

      

  

\[ P_{total} = \sum_{i=0}^{n} \sum_{j=0}^{n-i}\begin{pmatrix} n \\ i \end{pmatrix} \begin{pmatrix} n - i \\ j \end{pmatrix} \; wp^i \; dp^j \; lp^{n-i-j} \]

      

    پیاده‌سازی کد محاسبه‌ی این عبارت چندان دشوار نیست. مسأله‌ی اصلی به دست آوردن همین رابطه است.

      

    نکته: ترکیب دو عدد صحیح نامنفی با رابطه‌ی زیر محاسبه می‌شود:

      

\[ \begin{pmatrix} n \\ r \end{pmatrix} = \frac{n!}{(n-r)!r!} \]

      

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

      

\[ \begin{pmatrix} n \\ r \end{pmatrix} = \begin{pmatrix} n - 1 \\ r \end{pmatrix}  + \begin{pmatrix} n - 1 \\ r - 1 \end{pmatrix} \qquad, \qquad \begin{pmatrix} n \\ 0 \end{pmatrix}  = \begin{pmatrix} n \\ n \end{pmatrix} = 1 \]

      


نوشته‌های مرتبط
فرادرس - مجموعه آموزش‌های ویدئویی  مهندسی کامپیوتر - طراحی الگوریتم - ساختمان داده
        معرفی کتاب آموزش الکترونیکی رایگان «ساختمان داده‌ها» به زبان فارسی با قابلیت دانلود
        معرفی کتاب Introduction to Algorithms: A Creative Approach
        بررسی مسأله‌ی انتخابات، از سوالات مسابقه‌ی برنامه‌نویسی ACM-ICPC 2016 سایت تهران
        بررسی مسأله‌ی تاریخچه‌ی جدول (Grid History)، از سوالات مسابقات برنامه‌نویسی بیان
        بررسی مسأله‌ی اعداد اردوش (Erdos Numbers) یا فاصله‌ی همکاری اردوش از سوالات آمادگی مسابقات برنامه‌نویسی
        معرفی کتاب Introduction to Algorithms (ویراست سوم) به عنوان مرجع مباحث طراحی الگوریتم‌ها و ساختمان داده‌ها
        بررسی مسأله‌ی حداکثر مجموع، از سوالات آمادگی مسابقات برنامه‌نویسی
        بررسی مسأله‌ی آسانسورها (Elevators)، از سوالات مسابقات برنامه‌نویسی ACM
        بررسی مسأله‌ی بشکه‌های آب (Water Barrels)، از سوالات مسابقات برنامه‌نویسی بیان
        معرفی کتاب Concrete Mathematics برای علاقه‌مندان حل سوالات الگوریتمی و شرکت‌کنندگان مسابقات برنامه‌نویسی
پیوند کوتاه صفحه دسته‌بندی
امتیاز نوشته
  • 1
  • 2
  • 3
  • 4
  • 5
ارسال پیام

نام: *  

پست الکترونیک:

وبگاه:

متن پیام: *

right 01 02 03 04 05 06 07 08 09 10 11 12 13 14 left