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

08.09.2011
Разработка и анализ алгоритма
РАЗРАБОТКА и
ФОРМЫ ЗАПИСИ АЛГОРИТМА
Пример основных этапов работы над алгоритмом
Наибольший общий делитель (НОД) двух натуральных чисел
Greatest Common Divisor (GCD)
Дано : два натуральных числа a и b (a, b > 0). Требуется : найти натуральное число c = НОД(a, b).

08.09.2011
Разработка и анализ алгоритма
Школьный способ: вычислять НОД на основе разложения чисел a и b на простые множители
где целые aq и bq ≥ 0.

08.09.2011
Разработка и анализ алгоритма
Пример
a = 754, b = 143
a = 2 × 13 × 29, b = 11 × 13
НОД (a, b) = 20×110 × 131 × 290 = 13
! Получение разложения произвольного числа на простые множители само по себе является непростой задачей

08.09.2011
Разработка и анализ алгоритма
Другой способ вычисления НОД
Сначала рассмотрим
формальное (точное) определение НОД(a, b).
Запись p | q для натуральных p и q далее означает, что q является делителем (делит нацело) p.
Например, 754 | 13 (754 : 13 = 58)

08.09.2011
Разработка и анализ алгоритма
Определение. Натуральное число c = НОД(a, b), если
1) c − делитель a, т. е. 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.

08.09.2011
Разработка и анализ алгоритма
Способ вычисления НОД на основе определения
Последовательно перебираем числа c = 1, 2, 3, …, min(a, b) и находим максимальное среди тех из них, для которых справедливо a | c и b | c.
Улучшенный способ: числа перебираются в порядке убывания от min(a, b) до 1, тогда первое встретившееся c, такое, что a | c и b | c, и будет НОД(a, b).
! Оказывается, существует более эффективный
(по количеству операций) алгоритм.
Алгоритм Евклида

08.09.2011
Разработка и анализ алгоритма
Полезно строить вычисления не непосредственно на определении вычисляемой величины, а на её свойствах.
Свойства (очевидные):
gcd(a, b) = gcd(b, a)
gcd(a, a) = a
Можно расширить область значений входных чисел
a и b, допуская, что одно из них может быть равно 0.
Тогда
gcd(a, 0) = a.

08.09.2011
Разработка и анализ алгоритма
Для формулировки важного свойства НОД, напомним определения операций
деления нацело 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).

08.09.2011
Разработка и анализ алгоритма
Свойство НОД
Пусть a, b ∈ Ν и a > b > 0, тогда 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).

08.09.2011
Разработка и анализ алгоритма
Разработка алгоритма
В основу алгоритма положим два свойства НОД:
(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.

08.09.2011
Разработка и анализ алгоритма
Пример 1: a = 754, b = 143
Ответ gcd(754,143) = 13.

08.09.2011
Разработка и анализ алгоритма
Пример 2: a = 754, b = 144
Ответ gcd(754,144) = 2.

08.09.2011
Разработка и анализ алгоритма
Пример 3: a = 610, b = 144
Ответ gcd(610,144) = 2.

08.09.2011
Разработка и анализ алгоритма
Пример 4: a = 233, b = 144

08.09.2011
Разработка и анализ алгоритма
Ответ gcd(233,144) = 1.

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

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

08.09.2011
Разработка и анализ алгоритма
Цитата
Вычислительные процессы – это абстрактные существа, которые живут в компьютерах.
Развиваясь, процессы манипулируют абстракциями другого типа, которые называются данными.
Эволюция процесса направляется набором правил, называемым программой.
В сущности, мы заколдовываем дух компьютера с помощью своих чар.
Абельсон Х., Сассман Д.Д., Сассман Д.
Структура и интерпретация компьютерных программ –
М.: Добросвет, КДУ, 2006

Конец замечания об алгоритмах вычислительных процессах
Вернемся к алгоритму Евклида
08.09.2011
Разработка и анализ алгоритма

08.09.2011
Разработка и анализ алгоритма
Алгоритм Евклида («Математическая запись»)
Пусть c0 = a, c1 = b (a > b > 0). Тогда gcd(a, b) = gcd(c0, c1).

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

08.09.2011
Разработка и анализ алгоритма
Компьютерная запись
Отличная от «математической».
В виде блок-схемы
(графической схемы) алгоритма

08.09.2011
Разработка и анализ алгоритма
начало
конец
u := a
v := b
v ≠ 0
r := u mod v
u := v
v := r
Переменные a, b, u, v, r : Integer (целого типа)
Да
Нет

08.09.2011
Разработка и анализ алгоритма
Задание. Ослабить ограничения на входные данные:
a ≥ b ≥ 0 и (a ≠ 0 или b ≠ 0)
a ≥ 0, b ≥ 0 (доопределить gcd(0, 0) = 0)
Метод индуктивных утверждений
Утверждение о состоянии переменных программы в некоторой её точке даётся таким образом, что оно справедливо при любом проходе вычислений через эту точку независимо от количества предыдущих проходов и от предыстории (от того, какой путь при вычислениях привёл в эту точку).
Правильность программы означает, что если она начала выполняться при заданном предусловии (утверждении У1) и завершилась, то после завершения будет справедливо постусловие (утверждение У5).

08.09.2011
Разработка и анализ алгоритма
Запись алгоритма Евклида на языке Паскаль
u := 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
начало
конец
Нет
Да

08.09.2011
Разработка и анализ алгоритма
Запись алгоритма Евклида на языке С++
u = 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
начало
конец
Нет
Да

08.09.2011
Разработка и анализ алгоритма
// У1: Предусловие
u = a ; v = b ;
// У2: утверждение перед первым входом в цикл
while (v != 0 )
{
r = u %v ;
u = v ;
v = r ;
// У4: утверждение в точке выхода из тела цикла
}
// У5: Постусловие
Аннотирование программы (алгоритма)
// У3: утверждение в точке входа в тело цикла}

08.09.2011
Разработка и анализ алгоритма
Утверждения У1−У5 для алгоритма Евклида
У1: a > b > 0;
У2: u > v > 0, gcd(u, v) = gcd(a, b);
У3: u > v > 0, gcd(u, v) = gcd(a, b);
У4: u > v ≥ 0, gcd(u, v) = gcd(a, b);
У5: u = gcd(a, b), v = 0.

08.09.2011
Разработка и анализ алгоритма
Аннотированный алгоритм Евклида
// У1: a > b > 0
u = a ; 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)

08.09.2011
Разработка и анализ алгоритма
/* Сергеев А.И., гр.8304, 7.09.2008
Лабораторная работа 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";
Показать выполнение программы на языке Паскаль

08.09.2011
Разработка и анализ алгоритма
i = 0; // Dem
u = 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;
}

08.09.2011
Разработка и анализ алгоритма
Замечание
Например, Remainder = u % v;
2
%
2

Способ вычисления НОД на основе определения
// a > 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

Анализ АЕ
Отложен
08.09.2011
Разработка и анализ алгоритма