Задача 76228
|
|
 |
Условие
(Сообщил Ю. В.Матиясевич)
Дана функция
f : {1...N}{1...N} Найти период последовательности
1, f(1), f(f(1), ... Количество действий
должно быть пропорционально суммарной длине предпериода
и периода (эта сумма может быть существенно меньше N)
Решение
Если отбросить начальный кусок, последовательность периодична, причём все члены периода различны.
{Обозначение: f[n,1]=f(f(...f(1)...)) (n раз)}
k:=1; a:=f(1); b:=f(f(1));
{a=f[k,1]; b=f[2k,1]}
while a <> b do begin
| k:=k+1; a:=f(a); b:=f(f(b));
end;
{a=f[k,1]=f[2k,1]; f[k,1] входит в периодическую часть}
l:=1; b:=f(a);
{b=f[k+l,1]; f[k,1],...,f[k+l-1,1] различны}
while a <> b do begin
| l:=l+1; b:=f(b);
end;
{период равен l}
