Алгоритмы, структуры алгоритмов, структурное программирование

Алгоритмы, структуры алгоритмов, структурное программирование

Этапы решения задачи на компьютере

• Постановка задачи
• Формализация
• Алгоритмизация
• Программирование
• Отладка и тестирование программы
• Проведение расчетов и анализ полученных результатов

Понятие алгоритма

• Алгоритм (от лат. «Algorithmi» - написания имени Мухамеда аль-Хорезми, выдающегося математика средневекового Востока)

• В XII веке латинский перевод его математического трактата о десятичной СС и правилах арифметики многозначных чисел. Эти правила и называли в то время алгоритмами.

Исполнитель - Компьютер " width="640"

Понятие алгоритма

• Алгоритм – последовательность команд управления каким-либо исполнителем.

Исполнители, работающие в обстановке

Методы программного

управления компьютером =

Исполнитель - Компьютер

Данные и величины

• Компьютер работает с величинами – различными информационными объектами: числами, символами, кодами и т.д.
• Совокупность величин ,с которыми работает компьютер, принято называть данными .

Классификация данных

По отношению к алгоритму:

• исходные данные;
• промежуточные данные;
• результаты (окончательные данные).

ax 2 +bx+c=0

Исходные данные

Результаты (окончательные данные)

Программа (промежуточные данные)

D=b 2 -4ac

a, b, c

x1, x2

Классификация данных

По значениям:

• константы – представляются собственным значением, например: 15, 34.7, ‘k’;
• переменные – представляются идентификаторами, например: x, s2, cod12.

Классификация данных

По типам:

• целочисленные;
• вещественные;
• символьные;
• строковые;
• логические.

Название

Допустимые значения

Целочисленный

- 32 768 … 32 767

Вещественный

 (2.9 *10 -39 …1.7*10 +38 )

Символьный

Произвольный символ алфавита

Строковый

Последовательность символов длиной меньше 255

Логический

True и False

Классификация данных

По структуре:

• простые (скалярные) – одна величина – одно значение;
• структурированные – одна величина – множество значений (множества, массивы и т.д.).

Базовые алгоритмические структуры

• В 1969 г. голландский ученый-программист Эдсгер Вибе Дейкстр доказал, что алгоритм для решения каждой логической задачи можно составить только

из структур: следование; ветвление; цикл.

• Их называют базовыми алгоритмическими структурами .
• Методика программирования, основанная на этой теореме, называется структурным

программированием .

Следование

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

Действие 1

Действие 2

Ветвление

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

Цикл

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

i = i 1 , i 2

нет

Условие

Тело цикла

да

Тело цикла

Тело цикла

нет

Условие

да

Комбинации базовых структур

• Сложный алгоритм состоит из соединенных между собой базовых структур. Соединяться они могут двумя способами:
• последовательным ;
• вложенным .

• см. учебник стр. 95-96

История программирования

• С изобретением программно-управляемых вычислительных машин появилась новая профессия – программист . (? в каком году и кем)
• Программирование на ЭВМ I поколения представляло сложный процесс (использование команд процессора), производительность программистов была низкой.
• В 1950-х гг. возникло направление «автоматизация программирования». Появились первые языки программирования

Первые языки программирования

• Первыми ЯП были машинно-ориентированные автокоды (позднее – ассемблеры).
• Ассемблер – программа-переводчик с языка ассемблера в машинный код, позднее – сам язык ассемблера.
• Работу по распределению памяти под данные и команды, перевод команд ассемблера в машинные коды берет на себя транслятор .

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

Примеры ЯПВУ:

• Паскаль;
• Бейсик;
• Фортран;
• Java;
• Си и др.

Освоить ЯПВУ гораздо проще, поэтому возросло число прикладных программистов, расширилось применение ЭВМ во многих областях.

Близки к естественным языкам

(чаще всего – английскому),

к языку математики

История Паскаля

• ЯП Паскаль создан швейцарским ученым Никлаусом Виртом в 1969 г. для обучения студентов структурной методике программирования (? в честь кого название)
• Позднее фирма Borland International разработала Турбо Паскаль, которая вышла за рамки учебного применения.
• Со временем в язык ввелись средства объектного программирования, что привело к созданию Object Pascal.

Структура процедурных ЯПВУ

• Три основные составляющие ЯП:
• алфавит – множество символов, допустимых в записи текстов программ;
• синтаксис – правописание языковых конструкций (имен, констант, выражений, операторов и т.д.)
• семантика – смысловое содержание языковой конструкции.

Соблюдение правил в ЯП должно быть строгим!

Структура программы на Паскале

Заголовок

программы

• Program ;
• Label ;
• Const ;
• Type ;
• Var ;
• Procedure (Function)

;

• Begin

• End.

Тело

программы