Loading [MathJax]/jax/output/HTML-CSS/jax.js

المپدیا

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

ابزار کاربر

ابزار سایت


سوالات المپیاد:دوره ی تابستان:دوره ی ۱۱:الگوریتم ها:سوال ۱

تناوبی و غیر تناوبی

روی مجموعه‌ی متناهی S، تابع f تعریف شده است؛ به نحوی که به ازای هر xS،f(x) وجود دارد و عضوی از S است.

برای عنصر دلخواه z از مجموعه‌ی S می‌توان دنباله‌ی زیر را در نظر گرفت:

z,f(z),f(f(z)),f(f(f(z))),

همه‌ی عناصر این دنباله متعلق به S هستند و با شروع از z و استفاده از تابع f مرتبا عنصر جدیدی حاصل می‌شود. در دنباله‌ی فوق با به وجود آمدن اولین عنصر تکراری قسمتی از دنباله حالت تناوبی به خود می‌گیرد. مثلا:

si1,si2,,sia,sia+1,,sib=sia

در دنباله‌ی فوق bامین عنصر برابر aامین عنصر شده است، بنابراین در دنباله مرتبا قسمت sia,,sib1 تکرار خواهد شد.

در آغاز si1 را داریم و هدف یافتن عددهای b و a است به طوری که b اولین جایی باشد که sib با یکی از عناصر قبلی دنباله برابر است و a عددی است که 1a<b و sia=sib. تابع f در دسترس ما قرار ندارد و تنها می‌دانیم که اگر عنصر x را داشته باشیم، پیدا کردن f(x) از مرتبه‌ی زمانی O(1) است. اما حافظه نیز کم است، مجموعا تعداد عددها و تعداد عناصری از S که در حافظه ذخیره شده‌اند باید از O(1) باشد.

  1. الگوریتمی ارائه دهید که در مرتبه‌ی زمانی O(a+b) عدد b را پیدا کند.
  2. الگوریتمی ارائه دهید که در مرتبه‌ی زمانی O(a+b) عدد a را پیدا کند.

پاسخ


ابزار صفحه