Форум программистов [Powered by Invision Power Board]

Версия для печати темы
Нажмите сюда для просмотра этой темы в оригинальном формате

Форум программистов > Алгоритмы > Найти пересечение ряда и множества

Автор: Гость_Eugene 26.3.2004, 12:22

Hello, ALL
Приветствую Вас, господа МАТЕМАТИКИ !

Возникла такая вот задача.

Имеется 2 числовых ряда: ( в {} ,будут примеры )

a. Фибоначчи - { 1 2 3 5 8 13 ... } = R1
b. типа Фибоначчи - { 1 3 4 7 11 18 ... } = R2

на _заданном_ отрезке N
{ N ~ 8-ми байтовое целое, т.е. ~ 2^64 }

Дано множество, вычисляемое по формуле:

C = A * R % N , где

С - вычисленный член множества
А - заданная константа
N - отрезок поиска, (N > R, мощность множества)
R - _любое_ число из R1 или R2
% - операция "остаток от деления" в "C" ,
или mod(N) в математической записи

НАЙТИ: R =?= A * R % N
т. е. имеются ли пересечения рядов R и множества
A * R % N, и найти это(и) пересечение(я) (по возможности).
При решении задачи "в лоб" перебором, при N = 2^32 (4 байта)
P3-833 в чистом DOS "дохнет" :-(
Буду весьма признателен за помощь (желательно алгоритм).

Удачи !

Автор: Alex101 29.3.2004, 18:59

Найти пересечение достаточно просто - храни значение элемента множества в бите.
Т.е., сначала R1=R2=0;
...
Ri = Ri-2 + Ri-1
R1 = R1 OR (1 SHL (CRi - 1))

Ну и т.д.

А результат:
Res1 = R1 AND C
Res2 = R2 AND C

останется просмотреть единичные биты....

Автор: Arush 2.4.2004, 14:52

Задача сводится к следующей:

Пусть R3 = R1+R2.
Для всех Ri принадлежащих R3, Ri<N, найти Rj принадлежащее R3, такое что Ri= ( A*Rj ) mod N , либо доказать что оно не существует.

Если Rj должно быть меньше N, то :

1) Вычисляем R1 и R2 пока Ri < N (они будут содержать ~ по 60-70 членов)
2) Вычисляем С - оно будет содержать не более чем |R1| + |R2| членов.
3) Вычислем собственно пересечение.

На все это потребуется несколько секунд машинного времени

Если Rj может возрастать неограничено, то
Ri=A*Rj mod N=A*(R(j-1)+R(j-2)) mod N = A*R(j-1) + A*R(j-2) mod N = ( (A*R(j-1) mod N ) + (A*R(j-2) mod N) mod N. Т.е. все вычисления ведем в группе вычетов по модулю N (вроде так если я не забыл).

Соответственно алгоритм 3) получается примерно следующий:

Код


R1_j2=0;
R1_j1=A % N;

R2_j1=A % N;
R2_j2=( 3*A ) % N;

steps=0;
End=0;
while(!End){
    //Считаем ряд R1
    tmp=R1_j1;
    R1_j1=( R1_j2 + R1_j1 ) mod N;
    R1_j2=tmp;
    //Считаем ряд R1
    tmp=R2_j1;
    R2_j1=( R2_j2 + R2_j1 ) mod N;
    R2_j2=tmp;
    if( ! ( member(R1_j1,R3)  || member(R2_j2,R3) ) ){ 
        steps++;
        if(steps>100) End=1;
    }
     if( member(R1_j1,R3) ){
        steps=0;
        delete_member(R1_j1,R3); //Удаляем R1_j1 из множества R3
    }
     if( member(R2_j1,R3) ){
        steps=0;
        delete_member(R2_j1,R3); //Удаляем R2_j1 из множества R3
    }
     if( empty(R3) ){
        End=1;
    }
}

Т.е. считаем пока не найдем разложение каждого члена множества R3, либо за 100 шагов не найдем ни одного нового члена(это конечно эвристика, а что делать

.
Наверно имеет смысл ограничить число нерезультативных шагов не константой и функцией от N, например sqrt(N) или N.

Удачи.