Программирование 1

ФОРМЫ ЗАПИСИ
  АЛГОРИТМА и ПРОГРАММЫ

работы над алгоритмом

Наибольший общий делитель (НОД) двух натуральных чисел

Greatest Common Divisor (GCD)

Дано : два натуральных числа a и b (a, b > 0). Требуется : найти натуральное число c = НОД(a, b).

чисел a и b на простые множители
где целые aq и

bq  0.

b = 143
a = 2  13  29,

b = 11  13
НОД (a, b) = 20110  131  290 = 13

! Получение разложения произвольного числа на простые множители само по себе является непростой задачей

определение НОД(a, b).

Запись p  q для натуральных p и q далее означает, что

q является делителем (делит нацело) p.

Например, 754  13 (754 : 13 = 58)

т. е. a  c;
2) c  делитель b, т. е. b  c;
3) c  наибольшее из натуральных чисел,

удовлетворяющих 1) и 2).

4) для натуральных p и q запись p  q означает, что существует такое натуральное s, что p = s q;
5) наибольшим из множества M натуральных чисел является такое p  M, что не существует другого числа q  M, такого, что q > p.

числа c = 1, 2, 3, …, min(a, b) и находим максимальное среди тех из них, для

которых справедливо a  c и b  c.

Улучшенный способ: числа перебираются в порядке убывания от min(a, b) до 1, тогда первое встретившееся c, такое, что a  c и b  c, и будет НОД(a, b).

! Оказывается, существует более эффективный
(по количеству операций) алгоритм.
Алгоритм Евклида

вычисляемой величины, а на её свойствах.
Свойства (очевидные):
gcd(a, b) = gcd(b, a)
gcd(a, a) = a
Можно расширить область значений

входных чисел
a и b, допуская, что одно из них может быть равно 0.
Тогда
gcd(a, 0) = a.

операций
деления нацело div и нахождения остатка от деления mod.

Пусть a, b   и a > b > 0, тогда существуют, и притом единственные q    и r  0 , такие, что имеет место представление
a = q b + r, 0  r < b.

Например, 25=3*7+4.
Обычно используют обозначения
q = a div b, r = a mod b,
и тогда
a = (a div b) b + (a mod b).

тогда gcd(a, b) = gcd(b, r), где r = a mod b,
В других обозначениях gcd(a, b) = gcd(b, a mod b),

gcd(a, b) = gcd(b, a  q b).

Доказательство см. в учеб. пособии
Пример: gcd( 754, 143 ) = gcd(143, 39),
754 = 5*143 + 39

Можно сформулировать и доказать аналогичное свойство НОД, включающее операцию вычитания: (a > b > 0)  gcd(a, b) = gcd(a  b, b).

НОД:
(a > b > 0)  gcd(a, b) = gcd(b, a mod b);
gcd(a, 0) = a.
Общая идея алгоритма:
последовательно от пары чисел (a, b)

переходить к новой паре чисел (b, a mod b).
При этом max(b, a mod b) < max(a, b),
т. е. каждый такой шаг «уменьшает» текущую пару.
Шаги продолжаются, пока не будет получена пара (a, 0) , и тогда gcd(a, 0) = a.

b = 143
Ответ gcd(754,143) = 13.

b = 144
Ответ gcd(754,144) = 2.

b = 144
Ответ gcd(610,144) = 2.

b = 144

пример содержит последовательность шагов.
Шаг определяется текущим состоянием (парой чисел) и

вызывает определенное действие
(нахождение остатка и замену предыдущей пары на новую).
В каждом примере набор конкретных состояний (в том числе начальное) и действий, вообще говоря, разные.
Все примеры – это один вычислительный процесс, но разные его реализации (проявления), определяемые начальным состоянием – входными данными).

процесса (ВП) – его реализации.
Сам ВП – это совокупность всех

своих реализаций – уже абстракция.
Что объединяет все реализации ВП?
Ответ: алгоритм (или программа), как описание ВП.
Программа = набор правил (инструкций), который направляет эволюцию ВП.
Иногда мы не будем различать ВП и его реализацию (из контекста будет ясно о чём речь), но всегда различаем ВП и алгоритм (программу).

живут в компьютерах.
Развиваясь, процессы манипулируют абстракциями другого типа, которые

называются данными.
Эволюция процесса направляется набором правил, называемым программой.
В сущности, мы заколдовываем дух компьютера с помощью своих чар.

Абельсон Х., Сассман Д.Д., Сассман Д. Структура и интерпретация компьютерных программ –
М.: Добросвет, КДУ, 2006

анализ алгоритма

Тогда gcd(a, b) = gcd(c0, c1).

с n + 1 = 0 и gcd(cn, 0) = cn, а следовательно, cn

= gcd(a, b).
Обоснование правильности алгоритма (отложим)
Обоснование завершимости алгоритма:
c0 > c1 > c2 > c3 > … >cn 1 > cn > cn + 1 = 0
Не может существовать бесконечной строго убывающей последовательности целых неотрицательных чисел (ck  0).

схемы) алгоритма

u mod v
u := v
v := r
Переменные a,

b, u, v, r : Integer (целого типа)

Да

Нет

a  b  0 и (a  0

или b  0)
a  0, b  0 (доопределить gcd(0, 0) = 0)
Метод индуктивных утверждений
Утверждение о состоянии переменных программы в некоторой её точке даётся таким образом, что оно справедливо при любом проходе вычислений через эту точку независимо от количества предыдущих проходов и от предыстории (от того, какой путь при вычислениях привёл в эту точку).

Правильность программы означает, что если она начала выполняться при заданном предусловии (утверждении У1) и завершилась, то после завершения будет справедливо постусловие (утверждение У5).

:= a ; v := b ;
while  v  0  do
begin
r :=

u mod v ;
u := v ;
v := r ;
end

u := a; v := b

r := u mod v;
u := v;
v := r

v  0

начало

конец

Нет

Да

= a;
v = b;
while ( v != 0 )
{ r

= u % v;
u = v;
v = r;
}

u := a; v := b

r := u mod v;
u := v;
v := r

v  0

начало

конец

Нет

Да

= b ;
// У2: утверждение перед первым входом в цикл
while

(v != 0 )
{
r = u %v ;
u = v ;
v = r ;
// У4: утверждение в точке выхода из тела цикла
}
// У5: Постусловие

Аннотирование программы (алгоритма)

// У3: утверждение в точке входа в тело цикла}

gcd(u, v) = gcd(a, b);
У5: u = gcd(a, b),  v = 0.

; v = b ;
// У2: u > v > 0, gcd(u, v) = gcd(a, b)
while (v != 0 )
{

r =

u % v ;
u = v ;
v = r ;
// У4: u > v  0, gcd(u, v) = gcd(a, b)
}
// У5: u = gcd(a, b),  v = 0

// У3: u > v > 0, gcd(u, v) = gcd(a, b)

работа N 0
Greatest Common Divisor
GCD(a,b) -

наибольший общий делитель натуральных a,b
примечание: пометка "Dem" в тексте указывает на демонстрационный фрагмент */
#include
using namespace std ;
int main ( )
{unsigned int a,b,u,v;
unsigned int Remainder, Quotient, i; // Dem
cout << "Введите два натуральных числа: \n" ;
cin >> a >> b;
cout << "Находим НОД пары чисел : " << a << ", " << b <<"\n";

Показать выполнение программы на языке Паскаль

a;
v = b;
// u>=0 & v>=0 & GCD(u,v)=GCD(a,b)
while (

v != 0 )
{ // u>=0 & v>0 & GCD(u,v)=GCD(a,b)
i = i + 1; // Dem
cout << "Step " << i ; // Dem
Quotient = u / v; // Dem
Remainder = u % v;
cout << " :: " << u << " = " << Quotient << " * " << v << " + " << Remainder << "\n"; // Dem
u = v;
v = Remainder;
// u>0 & v>=0 & GCD(u,v)=GCD(a,b)
}
// u>=0 & v=0 & u=GCD(u,0)=GCD(a,b)
cout << "Результат : --> НОД(" << a << ", " << b << ") = " << u << "\n";
return 0;
}

b > 0
if ( a < b ) c =

a;
else c = b;
// c=min(a,b)}

while ( ((a % c ) != 0) || ((b % c ) != 0))
{ c = c - 1;
} ;
// c = gcd(a, b)}

08.09.2011

Разработка и анализ алгоритма

См. файл gcd_w4.cpp

ЛЕКЦИИ
КОНЕЦ ЛЕКЦИИ
КОНЕЦ ЛЕКЦИИ
КОНЕЦ ЛЕКЦИИ
КОНЕЦ ЛЕКЦИИ