Processing math: 42%

المپدیا

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

ابزار کاربر

ابزار سایت


سوالات المپیاد:دوره ی تابستان:دوره ی ۲۴:تئوری مقدماتی اول:سوال ۱

سوال ۱

می‌دانیم ‎2n‎ عدد باینری به طول ‎n‎ داریم. ‎e(m)‎ را جایگاه اولین رقم ‎1‎ ازسمت راست عدد ‎m‎ در مبنای ‎2‎ فرض کنید. برای مثال ‎e(3)=1‎ و ‎e(12)=3‎ . ثابت کنید خروجی الگوریتم زیر دنباله‌ی ‎w1,w2,,w2n1‎ است که ‎wj‎ دنباله‌ای ‎n‎ کاراکتری و باینری است و ثابت کنید به ازای هر ‎a‎, ‎b‎ متفاوت، ‎w_a‎ و ‎w_{b}‎ متفاوت اند. ‎

  • w_0=(000\ldots0)‎ (تعداد صفرها ‎n‌تا)‎
  • k=1
  • j‎ را برابر با ‎e(k)‎ قرار بده.
  • در دنباله w_{k-1}‎ ‎، a_j (رقمی که در مکان ‎j‎ام از راست قرار دارد) را با ‎(1-a_j)‎ عوض کن و آن را ‎w_k‎ نام‌گذاری کن.
  • به مقدار ‎k‎ یکی اضافه کن.
  • اگر ‎k<2^n‎ به خط ‎3‎ برو.
  • پایان.

ابزار صفحه