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

наибольшее число, на которое оба исходных числа делятся без остатка.

Перебор:

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

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

ИЛИ

b-a)

Заменяем большее из двух чисел разностью большего и меньшего до тех пор, пока они не станут равны. Это и есть НОД.

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

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

Пример:

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

= НОД (7, 7) = 7

двух чисел остатком от деления большего на меньшее до тех пор, пока меньшее не станет равно нулю. Тогда большее — это НОД.

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

Пример:

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

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

)
{
if ( a == b ) return a;
if ( a < b )
return NOD ( a, b-a );
else return NOD ( a-b, b );
}

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 − 1 (содержит 12 978 189 цифр).
Задача. Найти все простые числа в интервале от 1 до заданного N.
Простое решение:

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 9 10 11 12 13 14 15 16

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

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

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

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

2

3

<= N; i ++ )
A[i] = 1;
// основной цикл
for ( k = 2; k*k <= N; k ++ )
if ( A[k] != 0 )
for ( i = k+k; i <= N; i += k ) A[i] = 0;
// выводим оставшиеся числа
for ( i = 1; i <= N; i ++ )
if ( A[i] == 1 )
printf ( "%d\n", i );

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

самое, но сравнить число шагов алгоритма для различных значений N. Построить график в Excel, сравнить сложность с линейной. Заполнить таблицу:

более 100 цифр…
Решение: хранить цифры в виде массива, по группам (например, 6 цифр в ячейке).

100! < 100100

201 цифра

201/6 ≈ 34 ячейки

+
734567·10000000

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

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

Алгоритм:

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

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

203701

k

a0

a1

a2

c0

c1

c2

734567·3 = 2 203701

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
...

{1}, // A[0]=1, остальные A[i]=0
s, r; // произведение, остаток
int i, k, len = 1; // len – длина числа
for ( k = 2; k <= 100; k ++ ) {
i = 0;
r = 0;
while ( i < len || r > 0 ) {
s = A[i]*k + r;
A[i] = s % d; // остается в этом разряде
r = s / d; // перенос
i ++;
}
len = i; // новая длина числа
}

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

основание системы
lnum A = {1};
int s, r; // произведение, остаток
int i, k, len = 1; // len – длина числа
for ( k = 2; k <= 100; k ++ ) {
i = 0;
r = 0;
while ( i < A.size() || r > 0 ) {
if (i==A.size()) a.pushback(0);
s = A[i]*k + r;
A[i] = s % d; // остается в этом разряде
r = s / d; // перенос
i ++;
}
while (A.size() > 1 && A.back() == 0) A.pop_back();
}

0; i -- )
printf ( "%d", A[i] );

Проблема: как не потерять первые нули при выводе чисел, длина которых менее 6 знаков?
123 000123
Решение:
составить свою процедуру;
использовать формат "%.6d"!

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

, если вектор пустой), а затем выводим все оставшиеся элементы вектора, дополняя их нулями до 6 символов:

printf ("%d", A.empty() ? 0 : a.back()); for (int i=(int)A.size()-2; i>=0; --i) printf ("%06d", a[i]);

здесь небольшой тонкий момент: нужно не забыть записать приведение типа (int), поскольку в противном случае число будут беззнаковым, и если , то при вычитании произойдёт переполнение

самое, но написать свою процедуру для вывода (не использовать формат "%.6d").
“6": Написать программу для умножения двух длинных чисел (ввод из файла).
“7": Написать программу для извлечения квадратного корня из длинного числа (ввод из файла).

оптимизация:

x – вектор (массив) целых чисел, причем все его элементы принадлежат заданному набору чисел

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

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

и, посетив по разу в неизвестном порядке города 2,3,...N, вернуться обратно в первый город. В каком порядке надо обходить города, чтобы замкнутый путь (тур) коммивояжера был кратчайшим?

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

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

O(N!)

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

x перестановку 2 3 … N найти длину маршрута 1 2 3 … N 1 и записать ее в Lmin;
выбрать случайно два элемента массива x и поменять их местами;
найти длину маршрута, соответствующего x и, если она меньше Lmin, записать ее в Lmin и запомнить перестановку;
если число шагов меньше заданного, перейти к шагу 2.