Целочисленные алгоритмы © К.Ю. Поляков, Алгоритм Евклида Алгоритм Евклида 2. Решето Эратосфена Решето Эратосфена 3. Длинные числа Длинные числа 4. Целочисленная оптимизация Целочисленная оптимизация

Целочисленные алгоритмы Тема 1. Алгоритм Евклида © К.Ю. Поляков, 2008

3 Вычисление НОД НОД = наибольший общий делитель двух натуральных чисел – это наибольшее число, на которое оба исходных числа делятся без остатка. Перебор: k = a; // или k = b; while ( a % k != 0 || b % k != 0 ) k --; printf ("НОД(%d,%d)=%d", a, b, k); k = a; // или k = b; while ( a % k != 0 || b % k != 0 ) k --; printf ("НОД(%d,%d)=%d", a, b, k); много операций для больших чисел ИЛИ

4 Алгоритм Евклида Евклид ( до. н. э.) НОД(a,b)= НОД(a-b, b) = НОД(a, b-a) НОД(a,b)= НОД(a-b, b) = НОД(a, b-a) Заменяем большее из двух чисел разностью большего и меньшего до тех пор, пока они не станут равны. Это и есть НОД. НОД (14, 21) = НОД (14, 21-14) = НОД (14, 7) НОД (1998, 2) = НОД (1996, 2) = … = 2 Пример: много шагов при большой разнице чисел: = НОД (7, 7) = 7

5 Модифицированный алгоритм Евклида НОД(a,b)= НОД(a%b, b) = НОД(a, b%a) НОД(a,b)= НОД(a%b, b) = НОД(a, b%a) Заменяем большее из двух чисел остатком от деления большего на меньшее до тех пор, пока меньшее не станет равно нулю. Тогда большее это НОД. НОД (14, 21) = НОД (14, 7) = НОД (0, 7) = 7 Пример: Еще один вариант: НОД(2 · a,2 · b)= 2 · НОД(a, b) НОД(2 · a,b)= НОД(a, b) // при нечетном b НОД(2 · a,2 · b)= 2 · НОД(a, b) НОД(2 · a,b)= НОД(a, b) // при нечетном b

6 Реализация алгоритма Евклида Рекурсивный вариант:Без рекурсии: int NOD ( int a, int 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 ) { 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 ) { 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 ) { 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; } int NOD ( int a, int b ) { while ( a*b != 0 ) if ( a > b ) a = a % b; else b = b % a; return a + b; } Почему return a+b ? ?

Целочисленные алгоритмы Тема 2. Решето Эратосфена © К.Ю. Поляков, 2008

8 Поиск простых чисел Простые числа – это числа, которые делятся только на себя и на 1. Применение: 1)криптография; 2)генераторы псевдослучайных чисел. Наибольшее известное (сентябрь 2006): (содержит цифр). Задача. Найти все простые числа в интервале от 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); } 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 Как уменьшить число шагов внутреннего цикла? ? Как оценить число операций? ? ki k*k <= i O(N 2 ) растет не быстрее N 2

9 Решето Эратосфена Эратосфен Киренский (Eratosthenes, Ερατοσθδνη) (ок до н.э.) Новая версия – решето Аткина.решето Аткина Алгоритм: 1)начать с k = 2 ; 2)«выколоть» все числа через k, начиная с 2 · k ; 3)перейти к следующему «невыколотому» k ; 4)если k · k <= N, то перейти к шагу 2; 5)напечатать все числа, оставшиеся «невыколотыми». высокая скорость, количество операций нужно хранить в памяти все числа от 1 до N O((N · log N) · log log N ) 23

10 Реализация // сначала все числа не выколоты for ( i = 1; i <= 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 ); // сначала все числа не выколоты for ( i = 1; i <= 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 «выколото».

Целочисленные алгоритмы Тема 3. Длинные числа © К.Ю. Поляков, 2008

12 Что такое длинные числа? Задача. Вычислить (точно) 100! = 1·2·3·...·99·100 Проблема: это число содержит более 100 цифр… Решение: хранить цифры в виде массива, по группам (например, 6 цифр в ячейке). Сколько нулей в конце этого числа? ? Какая последняя ненулевая цифра? ? Сколько ячеек нужно? ? 100! < цифра 201/6 34 ячейки

13 Хранение длинных чисел = = 1234· · · Хранить число по группам из 6 цифр – это значит представить его в системе счисления с основанием d = {A} = 1; for ( k = 2; k <= 100; k ++ ) { A} = {A} * k;... // вывести { A} {A} = 1; for ( k = 2; k <= 100; k ++ ) { A} = {A} * k;... // вывести { A} Алгоритм: {A} – длинное число, хранящееся как массив умножение длинного числа на «короткое» На что это похоже? ?

14 Умножение длинного числа на короткое × k k a0a0 a0a0 a1a1 a1a1 a2a2 a2a2 c0c0 c0c0 c1c1 c1c1 c2c2 c2c ·3 = c0c0 c0c0 перенос, r ·3 + 2 = c1c1 c1c1 r2r2 r2r2 1234·3 + 1 = 3703 c2c2 c2c2 c 0 = ( a 0 ·k + 0) % d r 1 = ( a 0 ·k + 0) / d c 1 = ( a 1 ·k + r 1 ) % d r 2 = ( a 1 ·k + r 1 ) / d c 2 = ( a 2 ·k + r 2 ) % d r 3 = ( a 2 ·k + r 2 ) / d... c 0 = ( a 0 ·k + 0) % d r 1 = ( a 0 ·k + 0) / d c 1 = ( a 1 ·k + r 1 ) % d r 2 = ( a 1 ·k + r 1 ) / d c 2 = ( a 2 ·k + r 2 ) % d r 3 = ( a 2 ·k + r 2 ) / d...

15 Вычисление 100! const long d = L; // основание системы long A[40] = {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 0 ) { s = A[i]*k + r; A[i] = s % d; // остается в этом разряде r = s / d; // перенос i ++; } len = i; // новая длина числа } const long d = L; // основание системы long A[40] = {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 0 ) { s = A[i]*k + r; A[i] = s % d; // остается в этом разряде r = s / d; // перенос i ++; } len = i; // новая длина числа } пока не кончились цифры числа {A} или есть перенос Где результат? ? Можно ли брать другое d ? ?

16 Как вывести длинное число? «Первая мысль»: for ( i = len-1; i >= 0; i -- ) printf ( "%ld", A[i] ); for ( i = len-1; i >= 0; i -- ) printf ( "%ld", A[i] ); Что плохо? ? Проблема: как не потерять первые нули при выводе чисел, длина которых менее 6 знаков? Решение: 1)составить свою процедуру; 2)использовать формат "%.6ld" ! for ( i = len-1; i >= 0; i -- ) if ( i == len-1 ) printf ( "%ld", A[i] ); else printf ( "%.6ld", A[i] ); for ( i = len-1; i >= 0; i -- ) if ( i == len-1 ) printf ( "%ld", A[i] ); else printf ( "%.6ld", A[i] );

17 Задания "4": Составить программу для вычисления 99!! = 1·3·...·97·99 "5": То же самое, но написать свою процедуру для вывода (не использовать формат "%.6ld" ). 6": Написать программу для умножения двух длинных чисел (ввод из файла). 7": Написать программу для извлечения квадратного корня из длинного числа (ввод из файла).

Целочисленные алгоритмы Тема 4. Целочисленная оптимизация © К.Ю. Поляков, 2008

19 Задачи целочисленной оптимизации Оптимизация: при заданных ограничениях Целочисленная оптимизация: x – вектор (массив) целых чисел Комбинаторная оптимизация: x – вектор (массив) целых чисел, причем все его элементы принадлежат заданному набору чисел при малом количестве вариантов можно решить простым перебором при большом количестве вариантов на решение перебором может потребоваться огромное время (для ряда задач другие алгоритмы неизвестны)

20 Задача коммивояжера Задача коммивояжера. Коммивояжер (бродячий торговец) должен выйти из первого города и, посетив по разу в неизвестном порядке города 2,3,...N, вернуться обратно в первый город. В каком порядке надо обходить города, чтобы замкнутый путь (тур) коммивояжера был кратчайшим? Это NP-полная задача, которая строго решается только перебором вариантов (пока) ! ! ! Точные методы: 1)простой перебор; 2)метод ветвей и границ; 3)метод Литтла; 4)… Приближенные методы: 1)метод случайных перестановок (Matlab); 2)генетические алгоритмы; 3)метод муравьиных колоний; 4)… большое время счета для больших N O(N!) не гарантируется оптимальное решение

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

22 Конец фильма