المپدیا

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

ابزار کاربر

ابزار سایت


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

سوال ۳۵

عدد صحیح $N$ و یک چراغ روشن مفروض است. دستورالعمل زیر را به ترتیب یک بار برای $N=۱۳۸۲$ و یک بار دیگر برای $N=۲۰۰۴$ اجرا کنید و معین کنید که به ترتیب چند بار در بار اول اجرا ($N=۱۳۸۲$) و چند بار در بار دوم اجرا ($N=۲۰۰۴$)٬ هوپ می‌گویید. مثلاً اگر دستورالعمل را به ترتیب برای $N=۳$٬ و $N=۵$ اجرا کنید٬ جواب سوال ۱ و ۰ (یک هوپ برای $N=۳$ و صفر هوپ برای $N=۵$) خواهد بود.

دستورالعمل:

  1. چراغ را خاموش کن.
  2. اگر $N=۰$ است٬ برو به ۷ وگرنه برو به ۳.
  3. $N$ را بر ۲ تقسیم کن. خارج‌قسمت آن را $N$ و باقی‌مانده را $R$ نام ده. برو به ۴.
  4. اگر $R=1$ است برو به ۵ وگرنه برو به ۶.
  5. اگر چراغ خاموش است آن را روشن کن٬ وگرنه بگو «هوپ». در هر صورت برو به ۲.
  6. اگر چراغ روشن است آن را خاموش کن و برو به ۲.
  7. پایان دستورالعمل.
  1. ۲ و ۲
  2. ۲ و ۴
  3. ۶ و ۷
  4. ۴ و ۳
  5. ۴ و ۵

پاسخ

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

کلمه «هوپ» موقعی گفته می‌شود که دو بار متوالی به باقی‌مانده ۱ برسیم. از طرف دیگر باقی‌مانده‌های به‌دست آمده نشانگر ارقام آن عدد در مبنای ۲ می‌باشد٬ بنابراین تعداد «هوپ»های گفته شده برای هر عدد بیانگر تعداد «۱۱»های موجود در معادل آن عدد در مبنای ۲ می‌باشد. تبدیل یافته هر یک از اعداد ۱۳۸۲ و ۲۰۰۴ در مبنای ۲ به ترتیب به شکل(۱۰۱۰۱۱۰۰۱۱۰) و (۱۱۱۱۱۰۱۰۱۰۰) می‌باشد که در مورد اولی ۲ سری «۱۱» و در مورد دومی ۴ سری «۱۱» وجود دارد.


ابزار صفحه