Processing math: 100%

المپدیا

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

ابزار کاربر

ابزار سایت


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

سوال ۲

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

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

پاسخ

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

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

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

A1A2A1A3A1A4A1A5A2A9A2A6A2A8A3A10A3A7A9A12A9A15A4A11A6A13A10A14A12A16

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


ابزار صفحه