Основы алгоритмизации

ОСНОВЫ АЛГОРИТМИЗАЦИИ

Основные способы записи алгоритма

Словесные

Графические

На алгоритмических языках

Последователь-ность рисунков

Словесное описание

Школьный алгоритмический

язык

Структурограмма

или таблица

Построчная запись

Язык программирова-ния

Блок-схема

Словесное описание

Словесное описание - самая простая запись алгоритма в виде набора высказываний на обычном разговорном языке.

Пример . Словесное описание алгоритма нахождения наибольшего общего делителя (НОД) пары целых чисел (алгоритм Евклида).

Чтобы найти НОД двух чисел, составьте таблицу из двух столбцов и назовите столбцы X и Y . Запишите первое из заданных чисел в столбец Х , а второе - в столбец Y . Если данные числа не равны, замените большее из них на результат вычитания из большего числа меньшего.

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

Последовательные картинки

Блок-схемы

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

Блок начала или конца алгоритма

Блок ввода или вывода данных

Блок обработки данных

Блок проверки условия

Блок пояснительных записей

Запись алгоритма Евклида с помощью блок-схемы

Начало

X,Y

Ввод значений X и Y

Да

Проверка равенства X и Y

Нет

X=Y

X

Нет

Да

Определение большего

из X и Y

Y=Y-X

Уменьшение большего числа на величину меньшего

X=X-Y

НОД=Х

Определение НОД

НОД

Вывод НОД

Конец

Алгоритмические языки

Алгоритмические языки - формальные языки, предназначенные для записи алгоритмов.

Характеристики алгоритмического языка

Набор используемых символов

Алфавит

Система правил образования

конструкций языка

Синтаксис

Семантика

Система правил, определяющих

смысл и способ употребления

конструкций языка

ОБЪЕКТЫ АЛГОРИТМОВ

Величины

Алгоритмы описывают последовательность действий над некоторыми информационными объектами .

Величина в информатике – это отдельный информационный объект.

Информационный объект

Число

Символ

Строка

Таблица

Величина

Постоянная

Переменная

(больше) (вычитание) НЕ (инверсия) * (умножение) = (не меньше) / (деление) = (равно) Операнды - объекты, над которыми выполняют операции. 6" width="640"

Операции над величинами

Операции над величинами

Арифметические

Отношения

Логические

И (конъюнкция)

+ (сложение)

ИЛИ (дизъюнкция)

(больше)

• (вычитание)

НЕ (инверсия)

* (умножение)

= (не меньше)

/ (деление)

= (равно)

Операнды - объекты, над которыми выполняют операции.

6

Типы величин

Тип величины в алгоритме

Целая

Числовой

Вещественная

Один

символ

Символьная

Текстовый

Литерная

Строка

символов

ДА (ИСТИНА, TRUE, 1)

Логический

НЕТ (ЛОЖЬ, FALSE, 0)

Имя величины

Имя величины в алгоритме

Латинская

буква

A, B, M, AP

Латинская

буква и цифра

A1, B4, M2

Мнемоническое

имя

SUMMA, PLAN

5 Операция Xсцепления (+). XА=`том` `a`+А= `атом`" width="640"

Выражения

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

Выражения

Логические

Арифметические

Строковые

X5

Операция

X

сцепления (+).

X

А=`том`

`a`+А= `атом`

Табличные величины

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

Таблица

Линейная

Прямоугольная

Одномерный

Двумерный

массив

массив

Дни недели

Табель

успеваемости

ОСНОВНЫЕ АЛГОРИТМИЧЕСКИЕ КОНСТРУКЦИИ

Основные алгоритмические конструкции

Для записи любого алгоритма достаточно трёх основных алгоритмических конструкций:

• следования,
• ветвления,
• Повторения.

( Э. Дейкстра )

Эдсгер Вибе Дейкстра (1930–2002). Выдающийся нидерландский учёный, идеи которого оказали огромное влияние на развитие компьютерной индустрии.

Следование

Следование - алгоритмическая конструкция, отображающая естественный, последовательный порядок действий.

Алгоритмы, в которых используется только структура «следование», называются линейными алгоритмами .

Действие 1

Действие 2

Алгоритмическая структура «следование»

Ветвление

Ветвление - алгоритмическая конструкция, в которой в зависимости от результата проверки условия («да» или «нет») предусмотрен выбор одной из двух последовательностей действий (ветвей).

Алгоритмы, в основе которых лежит структура «ветвление», называют разветвляющимися.

Полная форма ветвления

если

то

иначе

все

Условие

Действие 2

Действие 1

Пример

алг правописание частиц НЕ, НИ

нач

если частица под ударением

то писать НЕ

иначе писать НИ

все

кон

Сокращённая форма ветвления

если

то

все

Условие

Действие 1

Пример:

алг сборы на прогулку

нач

если на улице дождь

то взять зонтик

все

кон

B А больше В A = B А больше или равно В A B А не равно В A != B А не равно В" width="640"

Операции сравнения

A

А меньше В

A

А меньше или равно В

A = B

А равно В

A == B

А равно В

A B

А больше В

A = B

А больше или равно В

A B

А не равно В

A != B

А не равно В

Решение линейного уравнения ax + b = 0

Список данных

a, b, x - вещ

a, b

да

нет

a0

да

нет

b0

x:=-b/a

Корней нет

Любое число

Повторение

Повторение - последовательность действий, выполняемых многократно.

Алгоритмы , содержащие конструкцию повторения, называют циклическими или циклами .

Последовательность действий, многократно повторяющаяся в процессе выполнения цикла, называется телом цикла .

Типы циклов

Могут быть

Заданы условия

Заданы условия

продолжения работы

окончания работы

Пока есть кирпич

Пока не наступит ночь

Задано число

повторений

Ровно 100 кирпичей

Цикл с заданным условием продолжения работы

(цикл-ПОКА, цикл с предусловием)

нц пока

кц

нет

Условие

да

Тело цикла

= y да r:= r - y q:= q +1 r, y Конец" width="640"

Частное и остаток

Начало

Список данных

x, y, r, q - цел

x, y

r:=x

q:=0

нет

r = y

да

r:= r - y

q:= q +1

r, y

Конец

Цикл с заданным условием окончания работы

(цикл-ДО, цикл с постусловием)

Тело цикла

Условие

да

нет

Запись на алгоритмическом языке:

нц

кц при

Вычисление переменной b

Начало

Список данных

a, b - цел

a := 1

b := 1

a := a *2

b := b + a

a = 8

да

b

нет

Конец

Цикл с заданным числом повторений

(цикл-ДЛЯ, цикл с параметром)

i = i 1 , i 2

Тело цикла

Запись на алгоритмическом языке:

нц для i от i1 до i2

кц

Вычисление степени

Начало

Список данных

i, n – цел

a, y - вещ

a, n

y := 1

i = 1 , n

y

y := y * a

Конец

КОНСТРУИРОВАНИЕ АЛГОРИТМОВ

Последовательное построение алгоритма

• исходная задача разбивается на несколько частей, каждая из которых проще всей задачи, и решение каждой части формулируется в отдельной команде;
• если получаются команды, выходящие за пределы возможностей исполнителя, то они представляются в виде совокупности ещё более простых предписаний;
• процесс продолжается до тех пор, пока все предписания не будут понятны исполнителю.

Модели построения алгоритма (программы)

• Code and fix — модель кодирования и устранения ошибок;
• Waterfall Model — каскадная модель, или «водопад»;
• V-model — V-образная модель, разработка через тестирование;
• Incremental Model — инкрементная модель;
• Iterative Model — итеративная (или итерационная) модель;
• Spiral Model — спиральная модель;
• Chaos model — модель хаоса;
• Prototype Model — прототипная модель.

Waterfall (каскадная модель или «водопад»)

Преимущества «водопада»

• Разработку просто контролировать. 
• Стоимость проекта определяется на начальном этапе. 
• Не нужно нанимать тестировщиков с серьёзной технической подготовкой. 

Недостатки каскадной модели

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

V-образная модель (разработка через тестирование)

Преимущества V-образной модели

• Количество ошибок в архитектуре ПО сводится к минимуму.

Недостатки V-образной модели

• Если при разработке архитектуры была допущена ошибка, то вернуться и исправить её будет стоить дорого, как и в «водопаде».

Spiral Model (спиральная модель)

Преимущества спиральной модели

• Большое внимание уделяется проработке рисков.

Недостатки спиральной модели

• Есть риск застрять на начальном этапе   — бесконечно совершенствовать первую версию продукта и не продвинуться к следующим.
• Разработка длится долго и стоит дорого.