المپدیا

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

ابزار کاربر

ابزار سایت


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

سوال ۴۰

در نمودار مقابل از رأس ‎$A$‎ شروع می‌کنیم و با خواندن از چپ‌به‌راست رشته‌ی ورودی از رقم‌های صفر و یک، روی نمودار حرکت می‌کنیم. به‌عنوان مثال اگر رشته‌ی ورودی ‎۰۱۰۱۱‎ باشد، از ‎$A$‎ شروع می‌کنیم و به‌ترتیب به رأس‌های ‎$A$‎، ‎$C$‎، ‎$B$‎، ‎$A$‎ و ‎$B$‎ می‌رویم (در ‎$B$‎ متوقف می‌شویم). اگر رشته‌ی دریافتی، عدد دودویی معادل عدد ‎$200114211379$‎ باشد، پس از دریافت آخرین رقم عدد دودویی (کم‌ارزش‌ترین رقم) در کدام رأس متوقف می‌شویم؟

  1. $A$
  2. $B$
  3. $C$
  4. $D$
  5. $E$‎

پاسخ

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

اگر رئوس پایانی متناظر به اعداد ۴٬۳٬۲٬۱،… را در نظر بگیریم٬ به ترتیب رئوس $...،A،E،D،C،B،A،E،D،C،B$ خواهد شد که با دوره‌ی تناوب ۵ دنباله‌ی $A،E،D،C،B$ تکرار می‌شود٬ چون باقی‌مانده‌ی عدد داده شده بر ۵ برابر ۴ می‌باشد٬ بنابراین راس مورد نظر راس $E$ می‌باشد.


ابزار صفحه