есть некая функция
x2=f(x1)
она генерирует (по неизвестному нам закону) следующее число некой последовательности (кстати, целочисленной)
соответственно x3=f(f(x1)))
как известно все языки программирования имеют ограниченную разрядность целых типов, соответственно эта последовательность рано или поздно замкнётся (либо по переполнению, либо по алгоритму).

задача: составить алгоритм поиска периода цикла.

пример последовательности: 5-12-9-38-144-52-9

Здравствуйте, vitaly_spb, Вы писали:

_>есть некая функция

Замаскировал, замаскировал задачку Ну, не буду кричать про [|||] и другим не советую. Вдруг кто ещё не знает?

Здравствуйте, vitaly_spb, Вы писали:

_>пример последовательности: 5-12-9-38-144-52-9
Поиск цикла двумя указателями (пустить их по последовательности с взаимно простым шагом).

Здравствуйте, andyJB, Вы писали:

JB>Здравствуйте, vitaly_spb, Вы писали:

_>>пример последовательности: 5-12-9-38-144-52-9
JB>Поиск цикла двумя указателями (пустить их по последовательности с взаимно простым шагом).

У нас последовательность генерируется, так что указателей нема. Но вообще подход верный. А за "взаимно простой шаг" — отдельное спасибо!

Здравствуйте, Кодт, Вы писали:

К>Здравствуйте, andyJB, Вы писали:

JB>>Здравствуйте, vitaly_spb, Вы писали:

_>>>пример последовательности: 5-12-9-38-144-52-9
JB>>Поиск цикла двумя указателями (пустить их по последовательности с взаимно простым шагом).

К>У нас последовательность генерируется, так что указателей нема. Но вообще подход верный. А за "взаимно простой шаг" — отдельное спасибо!
Числа = указатели в данном случае (а f(x) = next(pointer)).

Здравствуйте, andyJB, Вы писали:

<>

А вот другая задача. У функции нет аргумента, но есть внутреннее состояние. Например, rand()
Как быть в этом случае?

Здравствуйте, vitaly_spb, Вы писали:

_>задача: составить алгоритм поиска периода цикла.

_>пример последовательности: 5-12-9-38-144-52-9

Вообще говоря не обязательно период искать руками, его можно рассчитать. Читайте ТА. Можно найти максимальный период, а все остальные будут его делителями.

JB>Поиск цикла двумя указателями (пустить их по последовательности с взаимно простым шагом).

А можно поподробнее в чем смысл? Я понимаю что это какая-то аналогия с поиском цикла в односвязном списке, просто не могу уловить...

Здравствуйте, Кодт, Вы писали:

К>А вот другая задача. У функции нет аргумента, но есть внутреннее состояние. Например, rand()
К>Как быть в этом случае?

А в этом случаее есть функция randomize(seed)

Здравствуйте, Аноним, Вы писали:
[...]
Последовательность выглядит так: <начало><цикл><цикл><цикл>...
Если у нас есть член последовательности, лежащий в цикле, то поиск длины цикла — это простой while пока последовательность опять не примет это значение. Таким образом, для решения задачи достаточно найти член последовательности, расположенный не в фрагменте <начало>, а в каком-нибудь фрагменте <цикл>. Это и делается алгоритмом аналогичным поиску односвязного цикла в списке.

Здравствуйте, andyJB, Вы писали:

фрагменте <цикл>. Это и делается алгоритмом аналогичным поиску односвязного цикла в списке.
...цикла в односвязном списке...

JB>Последовательность выглядит так: <начало><цикл><цикл><цикл>...
JB>Если у нас есть член последовательности, лежащий в цикле, то поиск длины цикла — это простой while пока последовательность опять не примет это значение. Таким образом, для решения задачи достаточно найти член последовательности, расположенный не в фрагменте <начало>, а в каком-нибудь фрагменте <цикл>. Это и делается алгоритмом аналогичным поиску односвязного цикла в списке.

Каким образом? Там понятно — сравниваются ссылки, т.к. какой-то элемент конца ссылается назад на какой-то элемент хвоста. Тут же совсем не так.
3-5-2-5-2-6-6-6
^тот же 5, что и второй элемент в последовательности, но это еще ни о чем не говорит

_>Каким образом? Там понятно — сравниваются ссылки, т.к. какой-то элемент конца ссылается назад на какой-то элемент хвоста. Тут же совсем не так.
_>3-5-2-5-2-6-6-6
_> ^тот же 5, что и второй элемент в последовательности, но это еще ни о чем не говорит

сообщение съехало ;(

Здравствуйте, vitaly_spb, Вы писали:

_>Каким образом? Там понятно — сравниваются ссылки, т.к. какой-то элемент конца ссылается назад на какой-то элемент хвоста. Тут же совсем не так.
_>3-5-2-5-2-6-6-6
_> ^тот же 5, что и второй элемент в последовательности, но это еще ни о чем не говорит

Это говорит о многом. В частности, о том, что функция имеет состояние
Потому что не может иначе быть, что f(2)=5 в первом случае и f(2)=6 во втором.

Здравствуйте, vitaly_spb, Вы писали:

_>3-5-2-5-2-6-6-6
f(2)=5 или f(2)=6? Если в условии последовательность чисел задается функцией, то должно быть верно либо одно, либо другое. Если в условии последовательность x_n задает не функция (в математическом смысле), а нечто, то она и зацикливаться не обязана, например, x_n = n-ая цифра числа e.

Здравствуйте, vitaly_spb, Вы писали:

_>есть некая функция
_>x2=f(x1)
_>она генерирует (по неизвестному нам закону) следующее число некой последовательности (кстати, целочисленной)
_>соответственно x3=f(f(x1)))
_>как известно все языки программирования имеют ограниченную разрядность целых типов, соответственно эта последовательность рано или поздно замкнётся (либо по переполнению, либо по алгоритму).

_>задача: составить алгоритм поиска периода цикла.

_>пример последовательности: 5-12-9-38-144-52-9


Поиск двумя указателями?

nPeriod=0;
x=x1;
while(f(x)!=x1)
{
    nPeriod++;
    x=f(x);
}
printf("%d",nPeriod);

S>

S>nPeriod=0;
S>x=x1;
S>while(f(x)!=x1)
S>{
S>    nPeriod++;
S>    x=f(x);
S>}
S>printf("%d",nPeriod);  
S>

А, нет! Облажался

Здравствуйте, Кодт, Вы писали:

К>А вот другая задача. У функции нет аргумента, но есть внутреннее состояние. Например, rand()
К>Как быть в этом случае?
В этом случае задача неразрешима в общем случае (можно свести к проблеме останова).

Нужны дополнительные условия: функция гарантирована переодическая и длина ее периода не больше некоторого числа N. Тогда делаем такой алгоритм:
1. Храним стек пар (Xi,i), причем i и Xi образуют строго возрастающую последовательность. Изначально стек пуст.
2. На каждом шаге j достаем из стека все элементы (Xi,i), где Xi>=Xj. Если был найден Xi==Xj, то мы нашли кандидат для размера периода. Возможный размер периода будет равен j-i.
3. Если же Xi<Xj — то кладем его на стек.
4. Повторяем 1 до тех пор, пока j<=N*2.

Размер цикла будет равен максимальному размеру кандидата, полученному на шаге 2.

Здравствуйте, andyJB, Вы писали:

_>>пример последовательности: 5-12-9-38-144-52-9
JB>Поиск цикла двумя указателями (пустить их по последовательности с взаимно простым шагом).

А почему обязательно с "взаимно простым шагом"? Ведь если они стартуют из одной точки, они все равно "пересекуться" через НОК(шаг1, шаг2) шагов.

Здравствуйте, _McSIMM, Вы писали:

_MS>Здравствуйте, andyJB, Вы писали:

_MS>А почему обязательно с "взаимно простым шагом"? Ведь если они стартуют из одной точки, они все равно "пересекуться" через НОК(шаг1, шаг2) шагов.
Первый указатель — это скажем, y_n = x_(k1*n), второй — z_n = x_(k2*n) (k1<k2). Зацикливание x_n => существует n_0 такое что y_n0 = z_n0. Доказательсво следствия сводится к тому, что нужно получить одинаковый остаток от деления на период цикла у k1*n и k2*n при достаточно большом n. Этого, пожалуй, можно добиться выбором n0, кратного длине цикла даже и при не взаимнопростых k1 и k2, но при чем здесь НОК?