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

Содержание

Слайд 2

08.09.2011

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

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

Пример основных этапов работы над

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

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

Слайд 3

08.09.2011

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

Школьный способ: вычислять НОД на основе разложения чисел a

08.09.2011 Разработка и анализ алгоритма Школьный способ: вычислять НОД на основе разложения
и b на простые множители

где целые aq и bq ≥ 0.

Слайд 4

08.09.2011

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

Пример
a = 754, b = 143
a = 2

08.09.2011 Разработка и анализ алгоритма Пример a = 754, b = 143
× 13 × 29, b = 11 × 13
НОД (a, b) = 20×110 × 131 × 290 = 13

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

Слайд 5

08.09.2011

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

Другой способ вычисления НОД

Сначала рассмотрим
формальное (точное) определение НОД(a, b).

08.09.2011 Разработка и анализ алгоритма Другой способ вычисления НОД Сначала рассмотрим формальное

Запись p | q для натуральных p и q далее означает, что q является делителем (делит нацело) p.
Например, 754 | 13 (754 : 13 = 58)

Слайд 6

08.09.2011

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

Определение. Натуральное число c = НОД(a, b), если
1) c − делитель a, т. е. a | c;
2)

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

Слайд 7

08.09.2011

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

Способ вычисления НОД на основе определения

Последовательно перебираем числа c = 1, 2, 3, …, min(a, b)

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

Слайд 8

08.09.2011

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

Полезно строить вычисления не непосредственно на определении вычисляемой величины,

08.09.2011 Разработка и анализ алгоритма Полезно строить вычисления не непосредственно на определении
а на её свойствах.

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

Слайд 9

08.09.2011

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

Для формулировки важного свойства НОД, напомним определения операций
деления

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

Слайд 10

08.09.2011

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

Свойство НОД
Пусть a, b ∈ Ν и a > b > 0, тогда gcd(a, b) = gcd(b, r), где

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

Слайд 11

08.09.2011

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

Разработка алгоритма
В основу алгоритма положим два свойства НОД:
(a > b > 0) → gcd(a, b) = gcd(b, a mod b);

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

Слайд 12

08.09.2011

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

Пример 1: a = 754, b = 143

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

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

Слайд 13

08.09.2011

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

Пример 2: a = 754, b = 144

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

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

Слайд 14

08.09.2011

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

Пример 3: a = 610, b = 144

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

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

Слайд 15

08.09.2011

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

Пример 4: a = 233, b = 144

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

Слайд 16

08.09.2011

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

Ответ gcd(233,144) = 1.

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

Слайд 17

08.09.2011

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

Замечание о вычислительном процессе и алгоритме (программе)

Каждый пример содержит

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

Слайд 18

08.09.2011

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

О вычислительном процессе и алгоритме (продолжение)

Реальные осуществления вычислительного процесса (ВП)

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

Слайд 19

08.09.2011

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

Цитата

Вычислительные процессы – это абстрактные существа, которые живут в

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

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

Слайд 20

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

08.09.2011

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

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

Слайд 21

08.09.2011

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

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

08.09.2011 Разработка и анализ алгоритма Алгоритм Евклида («Математическая запись») Пусть c0 =

Слайд 22

08.09.2011

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

Предполагается, что n-й шаг вычислений последний, т. е. с n + 1 = 0

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

Слайд 23

08.09.2011

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

Компьютерная запись

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

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

Слайд 24

08.09.2011

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

начало

конец

u := a
v := b

v ≠ 0

r := u mod

08.09.2011 Разработка и анализ алгоритма начало конец u := a v :=
v

u := v
v := r

Переменные a, b, u, v, r : Integer (целого типа)

Да

Нет

Слайд 25

08.09.2011

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

Задание. Ослабить ограничения на входные данные:
a ≥ b

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

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

Слайд 26

08.09.2011

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

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

u := a

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

начало

конец

Нет

Да

Слайд 27

08.09.2011

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

Запись алгоритма Евклида на языке С++

u = a;
v

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

начало

конец

Нет

Да

Слайд 28

08.09.2011

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

// У1: Предусловие
u = a ; v = b

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

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

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

Слайд 29

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−У5 для алгоритма Евклида У1: a

Слайд 30

08.09.2011

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

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

// У1: a > b > 0
u = a ; v

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

Слайд 31

08.09.2011

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

/* Сергеев А.И., гр.8304, 7.09.2008
Лабораторная работа N

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

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

Слайд 32

08.09.2011

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

i = 0; // Dem
u = a;
v =

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

Слайд 33

08.09.2011

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

Замечание

Например, Remainder = u % v;

2
%

2

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

Слайд 34

Способ вычисления НОД на основе определения

// a > 0 & b >

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

Слайд 35

Анализ АЕ

Отложен

08.09.2011

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

Анализ АЕ Отложен 08.09.2011 Разработка и анализ алгоритма
Имя файла: Разработка-алгоритма-и-программы.pptx
Количество просмотров: 147
Количество скачиваний: 0