المپدیا

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

ابزار کاربر

ابزار سایت


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

سوال ۷

درخت وراثت نموداری برای نشان دادن میزان ارثی است که به هر یک از اعضای یک خانواده طی سال‌ها رسیده است. فرض کنید تمام اموال هر فرد بین فرزندانش (در صورتی که فرزندی داشته باشد) تقسیم می‌شود. میزان ارث هر نفر عددی صحیح و نامنفی است.

به چند طریق می‌توان درخت وراثت روبه‌رو را تکمیل نمود؟

  1. ۱۱۳۴
  2. ۴۰۳۲
  3. ۳۷۸۰
  4. ۱۵۱۲
  5. ۲۰۱۶

راهنمایی

اعداد مربوط به ارث رئوسی را که به صورت یکتا تعیین می‌شوند، مشخص کنید.

راهنمایی

آیا می‌توانید زیردرخت‌هایی را که میزان ارث رئوسشان مستقل از رئوس دیگر زیردرخت‌ها تعیین می‌شود، مشخص کنید؟

راهنمایی

روی مقدار ارث برگ‌های درخت حالت‌بندی کنید.

پاسخ

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

کافی است میزان اموال افرادی را مشخص کنیم که فرزندی ندارند (برگ‌های درخت ریشه‌دار). اموال بقیه‌ی افراد به صورت یکتا مشخص می‌شود. باید زیردرخت رئوسی که مقدارشان معلوم است را به صورت جداگانه حل کنیم و برای به دست آوردن جواب نهایی جواب زیر مسئله‌ها را در هم ضرب کنیم. برای مثال برای معلوم کردن برگ‌های مربوط به رأس با عدد ۱۴ باید مقدار $14-5-4-3 = 2$ را بین دو برگ مربوطه پخش کنیم، که این کار به سه روش ممکن است. به همین ترتیب می‌توان تعداد روش‌های حل بقیه‌ی زیر درخت‌ها را پیدا کرد. جواب نهایی برابر با $21 \times 3 \times 4 \times 15 = 3780$ می‌باشد.


ابزار صفحه