Условие
(Сообщил Ю. В.Матиясевич)
Дана функция
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}
Источники и прецеденты использования
|
|
|
книга |
|
Автор |
А.Шень |
|
Название |
Программирование: теоремы и задачи |
|
Издательство |
МЦНМО |
|
Издание |
второе |
|
Год издания |
2004 |
|
глава |
|
Номер |
1 |
|
Название |
Переменные, выражения, присваивания |
|
параграф |
|
Номер |
1 |
|
Название |
Задачи без массивов |
|
задача |
|
Номер |
1.1.32 |
