Processing math: 100%

المپدیا

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

ابزار کاربر

ابزار سایت


سوالات المپیاد:مرحله ی دوم:دوره ی ۲۰:سوال پنج

دنباله

دنباله‌ی A=<a1,a2,...,an> از اعداد طبیعی را در نظر بگیرید. در ابتدای کار٬ به ازای هر 1in می‌دانیم که ai=i. هم‌چنین یک متغیر b تعریف می‌کنیم و مقدار اولیه‌ی آن را برابر ۰ می‌گذاریم.

فرض کنید f(z) برابر تعداد اعدادی از دنباله‌ی A است که مقدارشان برابر z است. مثلاً اگر n=۸ در ابتدای کار داریم: A=<1,2,3,4,5,6,7,8> و هم‌چنین f(8)=1 و f(9)=0. الگوریتم زیر را در نظر بگیرید که در هر بار اجرا٬ دو عدد طبیعی x و y را از ورودی می‌گیرد و پردازش می‌کند (1x,yn):

  1. مقدار x و y را از ورودی دریافت کن.
  2. اگر ax=ay٬ به مرحله‌ی ۹ برو٬ در غیر این صورت به مرحله‌ی ۳ برو.
  3. اگر f(ax)f(ay)٬ به مرحله‌ی ۴ برو٬ در غیر این صورت به مرحله‌ی ۷ برو.
  4. B را به اندازه‌ی f(ax) واحد اضافه کن.
  5. تمام اعداد دنباله‌ی A که مقدارشان برابر ax است را به ay تبدیل کن.
  6. به مرحله‌ی ۹ برو.
  7. B را به اندازه‌ی f(ay) واحد اضافه کن.
  8. تمام اعداد دنباله‌ی A که مقدارشان برابر ay است را به ax تبدیل کن.
  9. پایان.

برای مثال اگر n=۸ و الگوریتم را دو بار٬ ابتدا به ازای (x,y)=(۲,۳) و سپس به ازای (x,y)=(۲,۷) اجرا کنیم٬ پس از اجرای الگوریتم خواهیم داشت:

A=<1,3,3,4,5,6,3,8>. هم‌چنین مقدار B بعد از این دو اجرا برابر ۲ خواهد بود.

الف) فرض کنید n=۱۶ و می‌خواهیم الگوریتم را ۱۵ بار اجرا کنیم. مقدار x و y را برای هر اجرا طوری تعیین کنید که پس از پایان کار٬ مقدار B برابر ۳۲ باشد.

ب) فرض کنید n=2k و می‌خواهیم الگوریتم را n1 بار اجرا کنیم (1k). ثابت کنید نمی‌توان مقادیر x و y را در این دفعات اجرا طوری تعیین کرد که پس از پایان کار مقدار B بیش‌تر از k×2k شود.


ابزار صفحه