المپدیا

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

ابزار کاربر

ابزار سایت


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

سوال ۲

‎۱۶‎ کامپیوتر مطابق شکل به هم ارتباط داده شده‌اند. هر کامپیوتر می‌تواند در هر ثانیه یک فایل اطلاعاتی را به فقط یکی از کامپیوترهایی که به آن مربوط است، منتقل کند. برای این که یک فایل اطلاعاتی جدید که فقط در یکی از کامپیوترها موجود است، به تمام کامپیوترها منتقل شود، حداقل چند ثانیه وقت لازم است؟

  1. ۳‎‎‎‎‎ ثانیه
  2. ۴ ثانیه
  3. ۵ ثانیه
  4. ۶ ثانیه
  5. بسته به این که فایل اولیه روی کدام کامپیوتر باشد زمان فرق می‌کند‎.‎

پاسخ

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

در انتهای ثانیه‌های اول٬ دوم و سوم به ترتیب حداکثر ۴٬۲ و ۸ کامپیوتر می‌توانند فایل اطلاعاتی جدید را دارا باشند. پس برای اینکه همه‌ی کامپیوتر‌ها٬ فایل اطلاعاتی جدید را دارا باشند حداقل ۴ ثانیه وقت لازم است. ثابت می‌کنیم در ۴ ثانیه این کار عملی است. برای این منظور فایل اطلاعاتی جدید را بر روی کامپیوتر $A_1$ فرض می‌کنیم. این فایل در انتهای ثانیه‌های اول تا چهارم به ترتیب زیر منتقل خواهند شد:

$\quad\quad$ثانیه چهارم $\quad\quad\quad\quad$ ثانیه سوم$\quad\quad\quad\quad$ثانیه دوم $\quad\quad\quad\quad$ ثانیه اول

$A_1 \longrightarrow A_2 \quad\quad\quad A_1 \longrightarrow A_3 \quad\quad\quad A_1 \longrightarrow A_4 \quad\quad\quad A_1 \longrightarrow A_5 \\ \quad\quad\quad\quad\quad\quad\quad\quad A_2 \longrightarrow A_9 \quad\quad\quad A_2 \longrightarrow A_6 \quad\quad\quad A_2 \longrightarrow A_8 \\ \quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad A_3 \longrightarrow A_{10} \quad\quad\quad A_3 \longrightarrow A_7 \\ \quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad A_9 \longrightarrow A_{12} \quad\quad\quad A_9 \longrightarrow A_{15} \\ \quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad A_4 \longrightarrow A_{11} \\ \quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad A_6 \longrightarrow A_{13} \\ \quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad A_{10} \longrightarrow A_{14} \\ \quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad A_{12} \longrightarrow A_{16} $

$A_1$ می‌تواند هر کدام از کامپیوترهای موجود باشد. به عنوان مثال یک نمونه از شماره‌گذاری کامپیوتر‌ها در زیر آمده است:


ابزار صفحه