Алгоритмизация. Алгоритмы. Алгоритмизация. Понятие алгоритма и его свойства
 Скачать 0.49 Mb.
|
Алгоритмы. Алгоритмизация.Понятие алгоритма и его свойстваАлгоритм (Мухаммеда ибн Муса ал-Хорезми (Alhorithmi), 783—850 гг.) — заранее заданное, понятное и точное предписание возможному исполнителю совершить определенную последовательность действий для получения решения задачи за конечное число шагов. Алгоритмы предназначены для выполнения некоторым исполнителем. Исполнитель алгоритма – абстрактная или реальная система, способная выполнить действия, предписанные алгоритмом. Исполнитель Человек Компьютер Робот Программный код Свойства алгоритмаФормальность (понятность для исполнителя) – исполнитель алгоритма должен понимать, как его выполнять. Дискретность (прерывность, раздельность) –каждый алгоритм состоит из отдельных законченных действий. Определенность (детерминированность, точность) –каждый шаг алгоритма должен не допускать различных толкований. Результативность (конечность) – алгоритм должен завершаться за конечное число шагов. Массовость – применимость алгоритма ко всем задачам рассматриваемого типа. Формы представления алгоритмовФормы Словесная (представляет структуру алгоритма на естественном языке) Графическая (изображение из графических символов – блок-схема) Псевдокод (описание структуры алгоритма на естественном, частично формализованном языке) Программа (описание структуры алгоритма на языке алгоритмического программирования) Словесное описание алгоритмаДостоинства
Недостатки
Словесное описание алгоритма представляет собой запись алгоритма в произвольной форме на естественном, например, русском языке. Пример: Найти наибольшее число из трех заданных (a, b, c) (словесное описание)Сравнить a и b.
Сравнить max и c.
max результат.
Графическое описание алгоритмаБлок-схема – описание структуры алгоритма с помощью геометрических фигур с линиями-связями, показывающими порядок выполнения отдельных инструкций. Достоинства
Недостатки
В блок-схеме каждому типу действия соответствует определенная геометрическая фигура, называемая блочным символом. Блочные символы соединяются линиями переходов, которые определяют очередность выполнения действий. основные конструкции, использующиеся для построения блок-схеМПример: Найти наибольшее число из трех заданных (a, b, c) (графическое описание)ПсевдокодПсевдокод – описание структуры алгоритма на естественном, частично формализованном языке. Представляет собой систему обозначений и правил, используемую для единообразной записи алгоритмов. В псевдокоде не приняты строгие синтаксические записи, но используются некоторые формальные конструкции и общепринятая математическая символика. В псевдокоде есть служебные слова смысл которых строго определен. Алгоритмический язык служебные словаКоманды алгоритмического языка
Пример: Найти наибольшее число из трех заданных (a, b, c) (псевдокод)алг max (арг цел a,b,c, рез цел max) нач ввод a,b,c если a>b то max:=a иначе max:=b все если max>c то вывод max иначе вывод c все кон Базовые алгоритмические структурыБазовые структуры Цикл Ветвление Следование Базовая структура «следование»Данная структура состоит из последовательно выполняющихся блоков. Примером является стандартный процесс вычисления: ввод значений, вычисление по формуле, вывод. Алгоритмический язык: Действие 1 Действие 2 … Действие n Базовая структура «Ветвление»Имеет 4 формы представления. Позволяет выбрать один из альтернативных вариантов. Форма 1. если-то (неполная развилка) Если «условие» верно , тогда выполнить «действия 1», иначе ничего не выполнять Алгоритмический язык: если условие то действия_1 все Блок-схема: Форма 2. если-то-иначе (полная развилка) Если «условие» верно , тогда выполнять «действия 1» (линия Да), иначе выполнять «действия 2» (линия Нет). Блок-схема: Алгоритмический язык: если условие то действия_1 иначе действия_2 все Форма 3. Выбор Алгоритмический язык: выбор при условие_1: действия_1 при условие_2: действия_2 … при условие_N: действия_N все Блок-схема: Форма 3. Выбор-иначе Алгоритмический язык: выбор при условие_1: действия_1 при условие_2: действия_2 … при условие_N: действия_N иначе действия_N+1 все Блок-схема: Базовая структура «Цикл»С помощью данной структуры выполняется одно и то же действие. Повторение осуществляется с помощью параметра цикла. Циклы С постусловием С параметром С предусловием Форма 1. Цикл с предусловием (цикл типа пока) Блок-схема: Алгоритмический язык: нц пока условие тело цикла кц В циклах с предусловием сначала проверяется условие, если оно истинно, то выполняются команды из тела цикла. Выполнение прекращается, когда условие становится ложным. Форма 2. Цикл с постусловием (цикл типа до) Блок-схема: Алгоритмический язык: нц тело цикла кц при условие В циклах с предусловием сначала выполняется действие (поэтому данный тип цикла выполняется хотя бы раз), а затем проверяется условие. Выполнение прекращается, когда условие становится истинным. Форма 3. Цикл с параметром (цикл типа для) Блок-схема: Алгоритмический язык: нц для i от i1 до i2 тело цикла кц Счетчику цикла i присваивается начальное значение i1 и выполняется тело. После счетчик i увеличивается на шаг n и проверяется условие i<=i2. Цикл завершается как только счетчик цикла i становится больше i2. Итерационные циклыИтерационные циклы – это циклы, в которых к решению приходят путем последовательного приближения к искомому результату. Особенностью данного цикла является то, что заранее число повторений команд неизвестно. Для корректной работы необходимо обеспечивать достижение условия выхода из цикла, иначе произойдет «зацикливание». Данные циклы используются в итерационных алгоритмах. Вложенные циклыВложенный цикл – это цикл, находящийся внутри другого цикла. Цикл, содержащий в себе другой цикл называют внешним, а цикл, содержащийся в теле другого цикла – внутренним. Глубина вложения циклов (количество циклов вложенных в друг друга) может быть различной. Пример: Вычислить сумму элементов заданной матрицы A(5,3). (вложенные циклы)Алгоритмический язык: … S:=0 нц для i от 1 до 5 нц для j от 1 до 3 S:=S+A[i,j] кц кц Блок-схема: Матрица A 1 2 3 1 2 3 4 5 |