Паскаль_ЦелочисленныеАлгоритмы.ppt

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

Тема 1. Алгоритм Евклида

Вычисление НОД

Перебор:

k := a; { или k := b; }
while (a mod k <> 0) or
(b mod k <> 0) do
k := k - 1;
writeln ('НОД(', a, ',', b, ')=', k);

ИЛИ

Алгоритм Евклида

НОД(a,b)= НОД(a-b, b)
= НОД(a, b-a)

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

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

Пример:

= НОД (7, 7) = 7

Модифицированный алгоритм Евклида

НОД(a,b)= НОД(a mod b, b)
= НОД(a, b mod a)

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

Пример:

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

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

Реализация алгоритма Евклида

Рекурсивный вариант:

function NOD (a, b: integer): integer;
begin
if a = b then NOD := a
else
if a < b then
NOD := NOD(a, b-a)
else NOD := NOD(a-b, b);
end;

function NOD (a, b: integer): integer;
begin
if a*b = 0 then NOD := a+b
else
if a < b then
NOD := NOD(a, b mod a)
else NOD := NOD(a mod b, b);
end;

Реализация алгоритма Евклида

Без рекурсии:

function NOD (a, b: integer): integer;
begin
while a <> b do
if a > b then a := a - b
else b := b - a;
NOD := a;
end;

function NOD (a, b: integer): integer;
begin
while a*b <> 0 do
if a > b then a := a mod b
else b := b mod a;
NOD := a + b;
end;

Задания

«4»: Составить программу для вычисления НОД и заполнить таблицу:


«5»: То же самое, но сравнить для всех пар число шагов обычного и модифицированного алгоритмов (добавить в таблицу еще две строчки).

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

Тема 2. Решето Эратосфена

Поиск простых чисел

for i:=1 to N do begin
isPrime := True;
for k:=2 to i-1 do
if i mod k = 0 then
isPrime := False;
if isPrime then
writeln(i);
end;

k*k <= i

O(N2)

Решето Эратосфена

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16

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

2

3

Реализация

{ сначала все числа не выколоты }
for i:=1 to N do A[i] := True;
{ основной цикл
«выкалывание» составных чисел }
{ выводим оставшиеся числа }
for i:=1 to N do
if A[i] then writeln(i);

Реализация

k := 2;
while k*k <= N do begin
if A[k] then begin





end;
k := k + 1;
end;

Основной цикл:

i := k*k;
while i <= N do begin
A[i] := False;
i := i + k;
end;

Задания

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

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

Тема 3. Длинные числа

Что такое длинные числа?

100! < 100100

Хранение длинных чисел

1234 568901 734567 =
= 1234·10000002 +
568901·10000001 +
734567·10000000

[A] = 1;
for k: = 2 to 100 do
[A] = [A]* k;
{ вывести [A] }

Алгоритм:

Умножение длинного числа на короткое

1234 568901 734567
× 3
3703 706705 203701

k

a0

a1

a2

c0

c1

c2

734567·3 = 2 203701

c0

568901·3 + 2 = 1 706705

c1

r2

1234·3 + 1 = 3703

c2

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

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

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

Вычисление 100!

const d = 1000000; { основание системы }
var A: array[0..40] of integer;
s, r, { произведение, остаток }
i, k, { вспомогательные }
len: integer; { длина числа }
begin
{ присвоить [A] = 1 }
{ последовательно умножать
[A] на 2, 3, ..., 100 }
{ вывести [A] }
end.

Вычисление 100!

len := 1; { записать [A]=1 }
A[0] := 1;
for i:=1 to 40 do
A[i] := 0;
for k:=2 to 100 do begin
i := 0; { с младшего разряда}
r := 0; { пока нет переноса}
while (i < len) or (r > 0) do begin
s := A[i]*k + r;
A[i] := s mod d; { в этом разряде }
r := s div d; { перенос }
i := i + 1; { к следующему разряду }
end;
len := i; { новая длина числа }
end;

Как вывести длинное число?

«Первая мысль»:

for i:=len-1 downto 0 do
write(A[i]);

write(A[len-1]); { старший разряд }
for i: = len-2 downto 0 do  Write6(A[i] );

Как вывести длинное число?

Процедура:

procedure Write6(N: integer);
var x, d: integer;
begin
x := 100000;
while x > 0 do begin
d := N div x;
N := N mod x;
x := x div 10;
write(d);
end;
end;

Задания

«4»: Составить программу для вычисления
99!! = 1·3·...·97·99
«5»: То же самое, но написать свою процедуру для вывода, использующую символьные строки.

«6»: Написать программу для умножения двух длинных чисел (ввод из файла).

«7»: Написать программу для извлечения квадратного корня из длинного числа (ввод из файла).

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

Тема 4. Целочисленная  оптимизация

Задачи целочисленной оптимизации

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

Целочисленная оптимизация:

Комбинаторная оптимизация:

Задача коммивояжера

O(N!)

Метод случайных перестановок

1

3

5

2

4

1