Целочисленные алгоритмы (язык Си)

оптимизация

чисел – это наибольшее число, на которое

Перебор:

k = a; // или k = b;
while ( a % k != 0 ||
b % k != 0 )
k --;
printf ("НОД(%d,%d)=%d", a, b, k);

много операций для больших чисел

ИЛИ

= НОД(a, b-a)
Заменяем большее из двух чисел разностью

НОД (14, 21) = НОД (14, 21-14) = НОД (14, 7)

НОД (1998, 2) = НОД (1996, 2) = … = 2

Пример:

много шагов при большой разнице чисел:

= НОД (7, 7) = 7

НОД(a, b%a)
Заменяем большее из двух чисел остатком от деления большего

НОД (14, 21) = НОД (14, 7) = НОД (0, 7) = 7

Пример:

Еще один вариант:

НОД(2·a,2·b)= 2·НОД(a, b)
НОД(2·a,b)= НОД(a, b) // при нечетном b

b )
{
if ( a == b ) return a;

int NOD ( int a, int b )
{
while ( a != b )
if ( a > b ) a -= b;
else b -= a;
return a;
}

int NOD ( int a, int b )
{
if ( a*b == 0 ) return a + b;
if ( a < b )
return NOD ( a, b%a );
else return NOD ( a%b, b );
}

int NOD ( int a, int b )
{
while ( a*b != 0 )
if ( a > b ) a = a % b;
else b = b % a;
return a + b;
}

же самое, но сравнить для каждой пары число шагов обычного

на себя и на 1.
Применение:
криптография;
генераторы псевдослучайных чисел.
Наибольшее известное (сентябрь 2008):
243112609

for ( i = 1; i <= N; i++ ) {
isPrime = 1;
for ( k = 2; k < i ; k++ )
if ( i % k == 0 ) {
isPrime = 0; break;
}
if ( isPrime ) printf("%d\n", i);
}

k*k <= i

k*k <= i

O(N2)

растет не быстрее N2

решето Аткина .
1 2 3 4 5 6 7 8

Алгоритм:
начать с k = 2;
«выколоть» все числа через k, начиная с 2·k;
перейти к следующему «невыколотому» k;
если k·k <= N, то перейти к шагу 2;
напечатать все числа, оставшиеся «невыколотыми».

высокая скорость, количество операций

нужно хранить в памяти все числа от 1 до N

O((N·log N)·log log N )

2

3

i

Массив A[N+1], где A[i]=1, если число i не «выколото», A[i]=0, если число i «выколото».

же самое, но сравнить число шагов алгоритма для различных значений

содержит более 100 цифр…




Решение: хранить цифры в виде массива, по

100! < 100100

201 цифра

201/6 ≈ 34 ячейки

1234·10000002 +
568901·10000001 +

Хранить число по группам из 6 цифр – это значит представить его в системе счисления с основанием d = 1000000.

{A} = 1;
for ( k = 2; k <= 100; k ++ )
{ A} = {A} * k;
... // вывести { A}

Алгоритм:

{A} – длинное число, хранящееся как массив

умножение длинного числа на «короткое»

3
3703 706705 203701
k
a0
a1
a2
c0
c1
c2
734567·3

c0

перенос, r1

568901·3 + 2 = 1 706705

c1

r2

1234·3 + 1 = 3703

c2

c0 = ( a0·k + 0) % d
r1 = ( a0·k + 0) / d

c1 = ( a1·k + r1) % d
r2 = ( a1·k + r1) / d

c2 = ( a2·k + r2) % d
r3 = ( a2·k + r2) / d
...

A[40] = {1}, // A[0]=1, остальные A[i]=0

пока не кончились цифры числа {A} или есть перенос

>= 0; i -- )
printf ( "%d", A[i] );
Проблема:

for ( i = len-1; i >= 0; i -- )
if ( i == len-1 ) printf ( "%ld", A[i] );
else printf ( "%.6d", A[i] );

То же самое, но написать свою процедуру для вывода (не

оптимизация
© К.Ю. Поляков, 2008-2009

чисел
Комбинаторная оптимизация:
x – вектор (массив) целых чисел, причем все его

при малом количестве вариантов можно решить простым перебором

при большом количестве вариантов на решение перебором может потребоваться огромное время (для ряда задач другие алгоритмы неизвестны)

города и, посетив по разу в неизвестном порядке города 2,3,...N,

Точные методы:
простой перебор;
метод ветвей и границ;
метод Литтла;
…
Приближенные методы:
метод случайных перестановок (Matlab);
генетические алгоритмы;
метод муравьиных колоний;
…

большое время счета для больших N

O(N!)

не гарантируется оптимальное решение

массив x перестановку 2 3 … N найти длину