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

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

$$z,f(z),f(f(z)),f(f(f(z))),…$$

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

$$s_{i_1},s_{i_2},…,s_{i_a},s_{i_{a+1}},…,s_{i_b}=s_{i_a}$$

در دنباله‌ی فوق $b$امین عنصر برابر $a$امین عنصر شده است، بنابراین در دنباله مرتبا قسمت $s_{i_a},…,s_{i_{b-1}}$ تکرار خواهد شد.

در آغاز $s_{i_1}$ را داریم و هدف یافتن عددهای $b$ و $a$ است به طوری که $b$ اولین جایی باشد که $s_{i_b}$ با یکی از عناصر قبلی دنباله برابر است و $a$ عددی است که $1\leq a <b$ و $s_{i_a}=s_{i_b}$. تابع $f$ در دسترس ما قرار ندارد و تنها می‌دانیم که اگر عنصر $x$ را داشته باشیم، پیدا کردن $f(x)$ از مرتبه‌ی زمانی $O(1)$ است. اما حافظه نیز کم است، مجموعا تعداد عددها و تعداد عناصری از $S$ که در حافظه ذخیره شده‌اند باید از $O(1)$ باشد.

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

• سوال بعد