سوال ۱۹

الگوریتم زیر را در نظر بگیرید. این الگوریتم عدد نامنفی $x$ را به عنوان ورودی دریافت می کند و عدد صحیح $z$ را به عنوان خروجی برمی گرداند.

منظور از $\lfloor x \rfloor$ بزرگترین عدد صحیح کوچکتر یا مساوی $x$ است. منظور از $x \oplus y$ نیز عمل $XOR$ بیتی بین این دو عدد است که برابر است با حاصل جمع تمام $۲^i$هایی که بیت $i$ام از سمت راست (با شروع از اندیس صفر) در دقیقا یکی از آن دو عدد٬ برابر با «یک» باشد. برای مثال $XOR$ هر عددی با صفر خود همان عدد می شود و ۱۴ = ۵ $ \oplus $ ۱۱.

  1. عدد $y$ را برابر با $x$ قرار بده و $z$ را برابر با صفر قرار بده.
  2. $x$ را برابر با $\lfloor \frac x۲ \rfloor$ قرار بده.
  3. اگر $x$ برابر با صفر نبود $y$ را برابر با $x \oplus y$ قرار بده و به خط ۲ برو.
  4. $z$ را برابر با دو برابر $z$ قرار بده.
  5. $z$ را با باقیمانده‌ي $y$ بر ۲ جمع کن.
  6. $y$ را برابر با $\lfloor \frac y۴ \rfloor$ قرار بده.
  7. اگر $y$ مخالف صفر بود به خط ۴ برو.
  8. $z$ را به عنوان خروجی برگردان.

به ازای چند $x$ کمتر یا مساوی ۱۰۲۳ خروجی این الگوریتم برابر با صفر است؟

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

پاسخ

گزینه‌ی «۲» درست است.

ابتدا باید توجه داشته باشیم که نمایش دودویی عدد$⌊\frac{x}{2}⌋$همانند عدد $x$ است با این تفاوت که راست ترین رقم آن حذف شده است . نمایش دودویی عدد$⌊\frac{x}{4}⌋$هم همانند $x$ است با این تفاوت که دو رقم سمت راست آن حذف شده است .

در مرحله ی اول بررسی الگوریتم ، می خواهیم ببینیم با رسیدن به خط 4 برنامه ، $y$ چه عددی را نشان می‌دهد . با توجه به توضیح بالا در هر بار اجرای خط 2 ، رقم سمت راست $x$ خذف شده و عدد جدید با $y$ ،$XOR$ می شود. به این ترتیب می‌توان گفت به ازای رقم $k$ ام نمایش دودویی $x$ ،$XOR$ آن رقم با رقم های سمت چپ آن در جای رقم $k$ام نمایش دودویی $y$ قرار داده می شود.

حال باید ببینیم $z$ در چه صورت صفر است. در طی اجرای الگوریتم ابتدا اولین رقم سمت راست نمایش دودویی $y$ را به $z$ اضافه کرده سپس دوبرابر می‌کنیم. پس از آن رقم سوم نمایش دودویی $y$ را به $z$ اضافه کرده و آن را دو برابر می‌کنیم و پس از آن رقم پنجم ، هفتم و … . در هیچ یک از این مراحل رقم اضافه شده به $z$ نباید صفر باشد. بنابراین $z$ در صورتی صفر است که از سمت راست نمایش دودویی $y$ رقم اول ، سوم ، پنجم ، هفتم و … صفر باشد .

اگر $y$ فردرقم داشته باشد در نمایش دودویی آخرین رقمی که به $z$ اضافه می‌شود سمت چپ ترین رقم $y$ در نمایش دودویی آن است . از آن‌جایی که این رقم 1 است پس $z$ دیگر صفر نخواهد بود.

اما اگر $y$ زوج رقم داشته باشد ، در نمایش دودویی سمت چپ ترین رقم 1 است. اما چون رقم بعدی آن (دومین رقم از سمت چپ) در جایگاه رقم فرد قرار دارد پس باید 0 باشد. بنابراین این رقم باید در $x$ یک باشد تا $XOR$ آن با آخرین رقم برابر صفر شود .(زیرا این رقم به $z$ اضافه می‌شود) . بعد این دو رقم باید $XOR$ رقم سوم و چهارم از سمت چپ نمایش دودویی $x$ ، 0 باشد.(چون $XOR$ چهار رقم اول از سمت چپ در جای چهارمین رقم از سمت چپ $y$ قرار می‌گیرد. به همین ترتیب $XOR$ رقم پنجم و ششم هم باید صفر باشد . و پس از آن هم به همین ترتیب. پس اگر این ارقام را دوتا دوتا دسته بندی کنیم همه‌ی دسته‌ها به جز چپ‌ترین دسته که یک حالت دارد ، دو حالت دارند (11 یا 00) .

حال با توجه به تعداد ارقام $x$ ، تعداد حالات ممکن برای $x$ را می‌شماریم :

  1. $x$ صفر باشد : 1حالت
  2. $x$ دو رقم داشته باشد : 20 = 1 حالت
  3. $x$ چهار رقم داشته باشد: 21 حالت
  4. $x$ شش رقم داشته باشد: 22 حالت
  5. $x$ هشت رقم داشته باشد: 23 حالت
  6. $x$ ده رقم داشته باشد: 24 حالت

و در کل 32 عدد ممکن برای $x$ خواهیم داشت.