В начале урока давайте
вспомним, что такое алгоритм.
Алгоритм –
это строгий порядок правил, которые определяют последовательность шагов
обработки информации.
Ранее говорилось о том,
что люди хотели создать машину, которая будет исполнять формальный алгоритм без
помощи человека.
Для создания такой машины
необходимо было выполнить некоторые условия: соответствие техническим
требованиям; доскональное изучение работы алгоритма для обработки информации;
разработка формализованного способа представления таких алгоритмов.
На этом уроке мы
познакомимся с моделями алгоритмических машин в теории алгоритмов, а также
вспомним свойства алгоритма.
Само понятие алгоритма
исследовалось и совершенствовалось на протяжении многих лет. Но несмотря на все
усилия, строгого определения понятия «алгоритм» не было. Поэтому начали появляться
различные определения алгоритма. Но в тоже время все они были равнозначными.
Например, Андрей
Николаевич Колмагоров, русский советский математик предложил следующее
определение: алгоритм – это всякая система вычислений, выполняемых по
строго определённым правилам, которая после какого-либо числа шагов заведомо
приводит к решению поставленной задачи.
А вот Андрей Андреевич
Марков, советский математик, дал следующее определение для алгоритма. Алгоритм
– это точное предписание, определяющее вычислительный процесс, идущий от
варьируемых исходных данных к искомому результату.
Несмотря на то, что было
много вариаций определения алгоритма, все они сводились к одним и тем же требованиям:
·
алгоритм
должен содержать конечное количество простых для выполнения команд, то есть
удовлетворять требованию конечности записи;
·
алгоритм
должен выполнять конечное количество шагов при решении задачи, то есть
удовлетворять требованию конечности действий;
·
алгоритм
должен быть единым для всех допустимых исходных данных, то есть удовлетворять
требованию универсальности;
·
алгоритм
должен приводить к правильному по отношению к поставленной задачи решению, то
есть удовлетворять требование правильности.
В 1930-х гг. возникает
новая наука – теория алгоритмов. Она занимается изучением алгоритмов. Главным
толчком для этого была работа Курта Гёделя, австрийского логика, математика и
философа математики.
Он сформулировал и
доказал теоремы о неполноте. Его работы были опубликованы в 1931 году. В
теореме о неполноте символических логик было показано, что некоторые
математические проблемы не могут быть решены при помощи алгоритмов. Эта работа
дала толчок к поиску и анализу различных формализаций алгоритма.
Основной вопрос, на
который ищет ответ теория алгоритмов таков: для всякой ли задачи обработки
информации может быть построен алгоритм решения? Для того, чтобы найти ответ на
этот вопрос нужно было изначально договориться об исполнителе, на которого
будет ориентирован алгоритм.
Алан Тьюринг, английский
математик, логик, криптограф, предложил в качестве исполнителя машину Тьюринга.
Машина использовалась для
расшифровки сообщений. На основе открытого текста (стандартные отрывки текста,
значение которых известно аналитику), машина Тьюринга искала возможные
настройки, использованные для шифрования сообщений. Она производила ряд
логических предположений, основываясь на открытом тексте, а затем находила
противоречия, отбрасывала набор параметров и переходила к следующему. Таким
образом, большая часть всевозможных наборов отсеивалась и для более тщательного
анализа оставалось всего несколько вариантов. В 1940 году была запущена такая
первая машина.
В 1936–1937 годах
американский математик и логик, Эмиль Пост описал другую модель алгоритмической
машины. Она называется машиной Поста.
Можно сказать, что эта
машина является более упрощённой версией машины Тьюринга. Работа машины Поста основана
на двоичном алфавите. Поэтому она представляет для нас наибольший интерес, так
как все компьютеры работают с двоичным алфавитом. Более подробно с этой машиной
мы познакомимся чуть позже.
Язык программирования
алгоритмических машин представляет собой описание конечного
числа простых команд, которые могут быть реализованы в автоматическом устройстве.
Таким образом, система
команд исполнителя (СКИ) – это совокупность всех команд языка исполнителя.
Алгоритм управления
работой алгоритмической машины – это конечная
последовательность команд, с помощью которой машина решает задачу обработки
информации.
Для алгоритма управления
такой машиной существуют свои требования:
·
Дискретность. Этот пункт говорит о
том, что исполнитель должен выполнять каждый шаг отдельно от других;
·
Понятность. В алгоритме
используются только команды СКИ, предназначенные конкретно для этого
исполнителя;
·
Точность. Каждая команда должна
конкретно говорить о действии, которое должен выполнять исполнитель;
·
Конечность. Для исполнителя должно
быть задано определённое (конечное) число шагов, после выполнения которых
должен получится искомый результат.
Рассмотрим пример. Нам
необходимо записать алгоритм перемещения исполнителя Робот в клетку с домом.
Данному исполнителю доступны три команды: вперёд, налево и направо.
Итак, наш алгоритм будет
звучать следующим образом:
·
вперёд;
·
вперёд;
·
вперёд;
·
налево;
·
вперёд;
·
направо;
·
вперёд;
·
вперёд;
·
направо;
·
вперёд;
·
вперёд;
·
налево;
·
вперёд;
·
вперёд;
·
вперёд.
При выполнении этого
алгоритма исполнитель Робот дошёл до клетки с домом. В этом алгоритме мы с вами
можем увидеть все вышеприведённые требования. Давайте разберёмся.
Дискретность.
Исполнитель будет выполнять каждый шаг отдельно от других, так как, например,
он не сможет одновременно идти вперёд и выполнять поворот.
Далее идёт критерий «Понятность».
То есть в алгоритме должны использоваться только команды, которые поймёт данный
исполнитель. Так, например, в нашем случае нельзя было бы использовать команду
«Назад», иначе исполнитель бы просто не понял, что мы хотим этим сказать,
потому что такой команды в его системе нет по условию.
Следующий пункт «Точность».
В нашем алгоритме все действия записаны в том порядке, в котором нужно их
выполнять, и записаны конкретные команды для выполнения действий.
И последний критерий «Конечность».
У нас задано определённое количество ходов, после выполнения которых
исполнитель робот попадёт в клетку, где находится дом.
Таким образом мы можем
видеть, что в составленном алгоритме действий соблюдены все требования для
управления исполнителем.
Также необходимо различать
такие понятия, как команда и шаг.
Команда
– это отдельная инструкция в описании алгоритма.
А шаг алгоритма –
это отдельное действие, которое исполнитель выполняет по команде.
Давайте разберёмся на
примере. Мама попросила Катю помочь собрать ягоды малины.
Девочка взяла корзину и
подошла к кусту.
Она срывала ягоду и
опускала её в корзину. Так Катя делала до тех пор, пока на кусте не осталось ни
одной ягоды.
Из этих ягод сварили
варенье.
Записать действия Кати в
виде блок-схемы.
Рисуем овал и впишем в
него слово начало. Затем будет идти блок процесса. Впишем внутрь первое
действие «Взять корзину». Далее снова идёт блок процесса. Впишем в него
словосочетание «Подойти к кусту». Затем Катя должна посмотреть есть ли на кусте
ягода. Для этого нарисуем блок принятия решения и впишем в него вопрос «Куст с
ягодами?». От блока будут идти две стрелки «Да» и «Нет». Если идти по стрелке «Да»,
то у нас снова будут два блока процесса, в которых будут записаны следующие действия:
«Сорвать ягоду», «Положить в корзину», после чего возвращаемся к нашему блоку
принятия решения. Катя будет выполнять все эти действия до тех пор, пока куст
не опустеет. Тогда в блоке принятия решения с вопросом «Куст с ягодами?» мы
получим ответ «Нет». Идём по стрелке, после которой будет идти блок процесса, где
будет написано «Сварить варенье». Конец.
У нас получилась
блок-схема с циклическим алгоритмом. Мы можем видеть, что если выполнить данную
блок-схему для этого рисунка, то число команд у нас будет меньше, чем число
шагов, так как действия «Сорвать ягоду» и «Положить в корзину» будут
повторяться несколько раз.
Пришла пора подвести
итоги урока. Сегодня мы с вами узнали, что в 1930-х годах были предложены две
модели алгоритмических машин в теории алгоритмов: машина Тьюринга и машина
Поста. Для нас наибольший интерес представляет машина Поста, так как работа
этой машины основана на двоичном алфавите.
Также сегодня мы с вами
узнали, что любой алгоритм должен обладать следующими свойствами: дискретность
(каждый шаг алгоритма выполняется отдельно от других), понятность (в алгоритме
используются только команды из СКИ), точность (каждая команда определяет
однозначное действие исполнителя), конечность (за конечное число шагов
алгоритма получается искомый результат).
Not your computer? Use Guest mode to sign in privately. Learn more about using Guest mode
1.
Повторить материал темы
«ПОНЯТИЕ АЛГОРИТМА.
СВОЙСТВА АЛГОРИТМА»
Пройти тест по ссылке:
https://forms.yandex.ru/u/629f642518704a3a754bf655/
2. ПОНЯТИЕ АЛГОРИТМА. СВОЙСТВА АЛГОРИТМА
ОСНОВНЫЕ СВЕДЕНИЯ ОБ АЛГОРИТМАХ
3. Исполнитель алгоритма
МК
Исполнитель алгоритма
!
Исполнитель алгоритма – это субъект или устройство, способные
правильно интерпретировать описание алгоритма и выполнить содержащийся в нём перечень действий.
Неформальный
исполнитель
понимает смысл алгоритма,
может его корректировать и
изменять, а также отказаться
выполнять
одну и ту же команду
выполняет каждый раз поразному
неформальный
исполнитель
сам отвечает за свои действия
в
роли
неформального
исполнителя
чаще
всего
Художник Василий
Тропинин «Золотошвейка» (1826)
выступает
человек
Формальный
исполнитель
не размышляет над выполняемыми командами, а строго
следует пошаговым инструкциям алгоритма
одну и ту же команду всегда
выполняет одинаково
за
действия
формального
исполнителя отвечает управляющий им объект
в роли формального исполнителя чаще всего выступает
техническое устройство
4. Понятие алгоритма
МК
Понятие алгоритма
!
Алгоритм – точная система предписаний, определяющая
содержание и порядок действий исполнителя над некоторыми
объектами (исходными и промежуточными данными) для
получения искомого результата за конечное число шагов.
ПРИМЕРЫ АЛГОРИТМОВ
Закрыть
входную дверь
ключом
Нахождение n первых
простых чисел
(метод Эратосфена)
Построение
перпендикуляра
к прямой
5. Пример 1
МК
Пример 1
Алгоритм
«Закрыть входную дверь ключом»
1. Вставить ключ в замочную скважину.
2. Повернуть ключ два раза на 180 градусов против часовой стрелки.
3. Вынуть ключ из замочной скважины.
Исполнитель: человек
Объекты алгоритма: ключ, дверь
6. Свойства алгоритма
МК
Свойства алгоритма
!
Алгоритм – конечная система правил, сформулированных на
языке исполнителя, которая определяет последовательность
перехода от допустимых исходных данных к конечному результату
и обладает свойствами дискретности, детерминированности,
понятности, результативности, конечности и массовости.
Дискретность
Детерминированность
Понятность
Результативность
Массовость
Массовость
Дискретность
Детерминированность
Понятность
Результативность
Выполнение
Каждая
При
Алгоритм
точном
команда
пригоден
не
алгоритма
исполнении
алгоритма
должен
для решения
разбивается
определяет
содержать
команд
любой
на
последовательность
однозначное
предписаний,
алгоритма
задачи
из некоторого
процесс
действие
смысл
должен
законченных
класса
которых
исполнителя,
прекратиться
задач,
может
дейстт. е.
и
вий-шагов.
недвусмысленно
восприниматься
за
алгоритм
конечное
правильно
Только
число
исполнителем
указывает,
шагов,
работает
выполнив
и при
на
неоднокакая
некоодно
этом
действие,множестве
команда
значно,
должен
тором
т.
быть
должна
е. можно
запись
получен
выполняться
исходных
алгоритма
ответ
приступать
на данных,
следуюдолжна
вопроск
выполнению
щей.
быть
задачи.
которое
настолько
Многократное
Вназывается
качестве
следующего.
чёткой
одного
областью
выполнение
и полной,
из Произвести
возможных
применичтобы
алго-у
каждоеалгоритма.
ритма
исполнителя
ответов
мости
при
отдельное
может
одном
не возникло
быть
действие
иустановление
томпотребности
исполнителю
же наборе
тогов
предписывает
входных
принятии
факта,
что задача
данных,
каких-либо
специальное
решений
дает
самостоятельных
неодинаковые
указание в
имеет.
записи алгоритмаи –выходной
промежуточные
решений.
команда.результаты.
7. Способы записи алгоритмов
МК
Способы записи алгоритмов
Нахождение максимума
Шахматный
из 10 целыхэтюд
чисел
Мат взапись
два хода.
словесная
алгоритма
Белые
и выигрывают
наначинают
естественном
языке
запись алгоритма на языке
программирования
Сложение смешанных дробей
Нахождение НОД
1. Привести дробные части чисел
Programалгоритма
NOD;
запись
с помощью
к наименьшему общему
var a, b, рисунков,
n: integer; таблиц
формул,
знаменателю.
Begin
2. Сложить только целые части.
writeln (‘Введите два числа: ‘);
3. Отдельно сложить дробные
readln (a, b);
части.
while a <> b do
4. Сложить результаты,
if a>b then a := a — b
Решение:
полученные в п.2 и п. 3.
else b := b – a;
5.
Если
при
сложении
дробных
№ Белые
Черные
№ Белые
Черные
n:=
a;
с помощью
блок-схемы
получилась
1 Ф f1-a1 –K h8-g8
1 Ф частей
f1-a1
g6-g5
writeln
(‘НОД =графических
‘, n);
стандартных
дробь,
выделить
2 Ф a1-a8
2 K неправильная
f6-f7
End.
объектов
целуюЧерные
часть
из этой дроби и
№ Белые
(геометрических
фигур)целой
к полученной
1 Ф прибавить
f1-a1
С h7-g8
2 K части.
f6-g6
6. Сократить полученную дробь.
8. Блок-схема
МК
Блок-схема
СИМВОЛ
ФУНКЦИЯ
Пуск/остановка. Начало, конец, прерывание процесса
обработки данных или выполнения программы
Ввод/вывод. Преобразование данных в форму, пригодную для
обработки (ввод) или отображения результатов (вывод)
Процесс. Выполнение операций или группы операций, в
результате которых изменяется значение, форма представления
или расположение данных
Решение. Выбор направления выполнения алгоритма или
программы в зависимости от некоторых переменных условий
Модификация. Выполнение операций, меняющих команды или
группу команд, изменяющих программу
Предопределённый процесс. Использование ранее созданных и
отдельно описанных алгоритмов или программ
Правила выполнения блок-схем, внешний вид графических блоков и их назначение
определяются стандартом ГОСТ 19.701–90 (ИСО 5807–85) «Схемы алгоритмов, программ,
данных и систем. Обозначения условные и правила выполнения».
9.
МК
Самое главное
Алгоритм – конечная система правил, сформулированных на языке
исполнителя, которая определяет последовательность перехода от
допустимых исходных данных к конечному результату и обладает
свойствами
дискретности,
детерминированности,
понятности,
результативности, конечности и массовости.
Исполнитель алгоритма – субъект или устройство, способные правильно
интерпретировать описание алгоритма и выполнить содержащийся в нём
перечень действий.
Один и тот же алгоритм может быть записан разными способами: на
естественном языке, псевдокодом, с помощью блок-схем, на языке
программирования и т. д.
Теория алгоритмов предоставляет аппарат анализа различных алгоритмов
решения одной и той же задачи, на основе которого можно выбрать
самый эффективный (наилучший) алгоритм.
10.
МК
Самое главное
Алгоритм состоит из команд. Команда – отдельная инструкция в описании
алгоритма. Шаг алгоритма – отдельное действие, которое исполнитель
выполняет по команде. Вычислительным процессом, порождённым
алгоритмом, называется последовательность шагов алгоритма,
пройденных при его исполнении.
Сложность алгоритма – количество элементарных шагов (действий) в
вычислительном процессе этого алгоритма. Наряду со сложностью важной
характеристикой алгоритма является эффективность. Эффективность
оценивается количеством элементарных операций, которые необходимо
выполнить для решения задачи, а также количеством памяти,
требующейся для выполнения алгоритма.
Основы алгоритмизации и технологии программирования
Понятие алгоритма и его свойства
Каждый из нас постоянно решает множество задач: как быстрее обраться на работу, как лучше спланировать дела текущего дня и многие другие. Некоторые задачи мы решаем автоматически, так как на протяжении многих лет привыкли к их выполнению, другие требуют длительного размышления над решением, но в любом случае, решение каждой задачи всегда делится на простые действия.
Алгоритм – описанная на некотором языке точная конечная система правил, определяющая содержание и порядок действий над некоторыми объектами, строгое выполнение которых дает решение, поставленной задачи. Понятие алгоритма, являющееся фундаментальным в математике и информатике, возникло задолго до появления средств вычислительной техники. Слово «алгоритм» появилось в средние века, когда европейцы познакомились со способами выполнения арифметических действий в десятичной системе счисления, описанными узбекским математиком Муххамедом бен Аль-Хорезми («аль-Хорезми» — человек из города Хорезми); в настоящее время город Хива в Хорезмской области Узбекистана). Слово алгоритм – есть результат европейского произношения слов аль-Хорезми. Первоначально под алгоритмом понимали способ выполнения арифметических действий над десятичными числами. В дальнейшем это понятие стали использовать для обозначения любой последовательности действий, приводящей к решению поставленной задачи.
Любой алгоритм существует не сам по себе, а предназначен для определенного исполнителя (человека, робота, компьютера, языка программирования и т.д.). Свойством, характеризующим любого исполнителя, является то, что он умеет выполнять некоторые команды. Совокупность команд, которые данный исполнитель умеет выполнять, называется системой команд исполнителя. Алгоритм описывается в командах исполнителя, который будет его реализовывать. Объекты, над которыми исполнитель может совершать действия, образуют так называемую среду исполнителя. Исходные данные и результаты любого алгоритма всегда принадлежат среде того исполнителя, для которого предназначен алгоритм.
Значение слова «алгоритм» очень схоже со значениями слов «рецепт», «метод», «процесс». Однако, в отличие от рецепта или процесса, алгоритм характеризуется следующими свойствами: дискретностью, массовостью, определенностью, результативностью, формальностью.
Дискретность (разрывность – противоположно непрерывности) – это свойство алгоритма, характеризующее его структуру: каждый алгоритм состоит из отдельных законченных действий, говорят: «Делится на шаги».
Массовость – применимость алгоритма ко всем задачам рассматриваемого типа, при любых исходных данных. Например, алгоритм решения квадратного уравнения в области действительных чисел должен содержать все возможные исходы решения, т.е., рассмотрев значения дискриминанта, алгоритм находит либо два различных корня уравнения, либо два равных, либо делает вывод о том, что действительных корней нет.
Определенность (детерминированность, точность) – свойство алгоритма, указывающее на то, что каждый шаг алгоритма должен быть строго определен и не допускать различных толкований; также строго должен быть определен порядок выполнения отдельных шагов. Помните сказку про Ивана-царевича? «Шел Иван-царевич по дороге, дошел до развилки. Видит большой камень, на нем надпись: «Прямо пойдешь – голову потеряешь, направо пойдешь – жену найдешь, налево пойдешь – разбогатеешь. Стоит Иван и думает, что дальше делать». Таких инструкций алгоритм содержать не может.
Результативность – свойство, состоящее в том, что любой алгоритм должен завершаться за конечное (может быть очень большое) число шагов. Вопрос о рассмотрении бесконечных алгоритмов остается за рамками теории алгоритмов.
Формальность – это свойство указывает на то, что любой исполнитель, способный воспринимать и выполнять инструкции алгоритма, действует формально, т.е. отвлекается от содержания поставленной задачи и лишь строго выполняет инструкции. Рассуждать «что, как и почему» должен разработчик алгоритма, а исполнитель формально (не думая) поочередно исполняет предложенные команды и получает необходимый результат.
Способы описания алгоритмов
Рассмотрим следующие способы описания алгоритма: словесное описание, псевдокод, блок-схема, программа.
Словесное описание представляет структуру алгоритма на естественном языке. Например, любой прибор бытовой техники (утюг, электропила, дрель и т.п.) имеет инструкцию по эксплуатации, т.е. словесное описание алгоритма, в соответствии которому данный прибор должен использоваться.
Никаких правил составления словесного описания не существует. Запись алгоритма осуществляется в произвольной форме на естественном, например, русском языке. Этот способ описания не имеет широкого распространения, так как строго не формализуем (под «формальным» понимается то, что описание абсолютно полное и учитывает все возможные ситуации, которые могут возникнуть в ходе решения); допускает неоднозначность толкования при описании некоторых действий; страдает многословностью.
Псевдокод – описание структуры алгоритма на естественном, частично формализованном языке, позволяющее выявить основные этапы решения задачи, перед точной его записью на языке программирования. В псевдокоде используются некоторые формальные конструкции и общепринятая математическая символика.
Строгих синтаксических правил для записи псевдокода не существует. Это облегчает запись алгоритма при проектировании и позволяет описать алгоритм, используя любой набор команд. Однако в псевдокоде обычно используются некоторые конструкции, присущие формальным языкам, что облегчает переход от псевдокода к записи алгоритма на языке программирования. Единого или формального определения псевдокода не существует, поэтому возможны различные псевдокоды, отличающиеся набором используемых слов и конструкций.
Блок-схема – описание структуры алгоритма с помощью геометрических фигур с линиями-связями, показывающими порядок выполнения отдельных инструкций. Этот способ имеет ряд преимуществ. Благодаря наглядности, он обеспечивает «читаемость» алгоритма и явно отображает порядок: выполнения отдельных команд. В блок-схеме каждой формальной конструкции соответствует определенная геометрическая фигура или связанная линиями совокупность фигур.
Рассмотрим некоторые основные конструкции, использующиеся для построения блок-схем (рис. 1).
(1) Блок, характеризующий начало/конец алгоритма (для подпрограмм – вызов/возврат);
(2) Блок — процесс, предназначенный для описания отдельных действий;
(3) Блок — предопределенный процесс, предназначенный для обращения к вспомогательным алгоритмам (подпрограммам);
(4) Блок — ввода/вывода с неопределенного носителя;
(5) Блок — ввод с клавиатуры;
(6) Блок — вывод на монитор;
(7) Блок — вывод на печатающее устройство;
(8) Блок – решение (проверка условия или условный блок);
(9) Блок, описывающий блок с параметром;
(10) Блок – границы цикла, описывающий циклические процессы типа: «цикл с предусловием», «цикл с постусловием»;
Описания алгоритма в словесной форме, на псевдокоде или в виде блок-схемы допускают некоторый произвол при изображении команд. Вместе с тем она настолько достаточна, что позволяет человеку понять суть дела и исполнить алгоритм. На практике исполнителями алгоритмов выступают компьютеры. Поэтому алгоритм, предназначенный для исполнения на компьютере, должен быть записан на «понятном» ему языке, такой формализованный язык называют языком программирования.
Программа – описание структуры алгоритма на языке алгоритмического программирования. Программа на языке декларативного программирования представляет собой совокупность описанных знаний и не содержит явного алгоритма исполнения.
Основные алгоритмические конструкции
Элементарные шаги алгоритма можно объединить в следующие алгоритмические конструкции: линейные (последовательные), разветвляющиеся, циклические и рекурсивные.
Линейная алгоритмическая конструкция
Линейной называют алгоритмическую конструкцию, реализованную в виде последовательности действий (шагов), в которой каждое действие (шаг) алгоритма выполняется ровно один раз, причем после каждого i- гo действия (шага) выполняется (i+ 1)-е действие (шаг), если i-e действие – не конец алгоритма.
Пример 1.
Опишем алгоритм сложения двух чисел на псевдокоде в виде блок-схемы (рис. 2).
Псевдокод:
Ввод двух чисел а, b .
Вычисляем сумму S = а + b .
Вывод S.
Конец.
Разветвляющаяся алгоритмическая конструкция
Разветвляющейся (или ветвящейся) называется алгоритмическая конструкция, обеспечивающая выбор между двумя альтернативами в зависимости от значения входных данных. При каждом конкретном наборе входных данных разветвляющийся алгоритм сводится к линейному. Различают неполное (если – то) и полное (если – то – иначе) ветвления. Полное ветвление позволяет организовать две ветви в алгоритме (то или иначе), каждая из которых ведет к общей точке их слияния, так что выполнение алгоритма продолжается независимо от того, какой путь был выбран (рис. 3). Неполное ветвление предполагает наличие некоторых действий алгоритма только на одной ветви (то), вторая ветвь отсутствует, т.е. для одного из результатов проверки никаких действий выполнять не надо, управление сразу переходит к точке слияния (рис. 4).
Рассмотрим стандартный алгоритм поиска наибольшего (наименьшего) значения среди нескольких заданных. Основная идея алгоритма сводится к следующему: за наибольшее (наименьшее) принимаем значение любого из данных. Поочередно сравниваем оставшиеся данные с наибольшим (наименьшим). если окажется, что очередное значение входного данного больше (меньше) наибольшего (наименьшего), то наибольшему (наименьшему) присваиваем это значение. Таким образом, сравнив все входные данные, найдем наибольшее (наименьшее) среди них. Алгоритм использует неполное ветвление.
Пример 2.
Заданы три числа. Найти значение наименьшего из них Заданные числа обозначим: а, b, с; результирующее наименьшее – min. На рис. 5 представлена блок-схема алгоритма решения данной задачи.
Алгоритмическая конструкция «Цикл»
Циклической (или циклом) называют алгоритмическую конструкцию, в кoтoрoй некая, идущая подряд группа действий (шагов) алгоритма может выполняться несколько раз, в зависимости от входных данных или условия задачи. Группа повторяющихся действий на каждом шагу цикла называется телом цикла. Любая циклическая конструкция содержит себе элементы ветвящейся алгоритмической конструкции.
Рассмотрим три типа циклических алгоритмов: ц uкл с параметром (который называют арифметическим циклом), цикл с предусловием и цикл с постусловием (их называют итерационными) .
Арифметический цикл
В арифметическом цикле число его шагов (повторений) однозначно определяется правилом изменения параметра, которое задается с помощью начального (N) и конечного (К) значений параметра и шагом (h) его изменения. Т.е., на первом шаге цикла значение параметра равно N, на втором – N + h, на третьем – N + 2h и т.д. На последнем шаге цикла значение параметра не больше К, но такое, что дальнейшее его изменение приведет к значению, большему, чем К.
Пример 3.
Вывести 10 раз слово «Привет!».
Параметр цикла обозначим i, он будет отвечать за количество выведенных слов. При i=1 будет выведено первое слово, при i=2 будет выведено второе слова и т. д. Так как требуется вывести 10 слов, то последнее значение параметра i=10. В заданном примере требуется 10 раз повторить одно и то же действие: вывести слово «Привет!». Составим алгоритм, используя арифметический цикл, в котором правило изменения параметра i=1,10, 1. т. е. начальное значение параметра i=1; конечное значение i=10; шаг изменения h=1. На рис. 6 представлена блок-схема алгоритма решения данной задачи.
Цикл с предусловием
Количество шагов цикла заранее не определено и зависит от входных данных задачи. В данной циклической структуре сначала проверяется значение условного выражения (условие) перед выполнением очередного шага цикла. Если значение условного выражения истинно, исполняется тело цикла. После чего управление вновь передается проверке условия и т.д. Эти действия повторяются до тех пор, пока условное выражение не примет значение ложь. При первом же несоблюдении условия цикл завершается.
Блок-схема данной конструкции представлена на рис. 7 двумя способами: с помощью условного блока а и с помощью блока границы цикла б. Особенностью цикла с предусловием является то, что если изначально условное выражение ложно, то тело цикла не выполнится ни разу.
Цикл с постусловием
Как и в цикле с предусловием, в циклической конструкции с постусловием заранее не определено число повторений тела цикла, оно зависит от входных данных задачи. В отличие от цикла с предусловием, тело цикла с постусловием всегда будет выполнено хотя бы один раз, после чего проверяется условие. В этой конструкции тело цикла будет выполняться до тех пор, пока значение условного выражения ложно. Как только оно становится истинным, выполнение команды прекращается. Блок-схема данной конструкции представлена на рис. 8 двумя способами: с помощью условного блока а и с помощью блока управления б.
Рекурсивный алгоритм
Рекурсивным называется алгоритм, организованный таким образом, что в процессе выполнения команд на каком-либо шаге он прямо или косвенно обращается сам к себе.
Простые типы данных: переменные и константы
Реальные данные, которые обрабатывает программа, — это целые и вещественные числа, символы и логические величины. Эти простые типы данных называют базовыми. Все данные, обрабатываемые компьютером, хранятся в ячейках памяти компьютера, каждая из которых имеет свой адрес. Для того чтобы не следить за тем, по какому адресу будут записаны те или иные данные, в языках программирования используется понятие переменной, позволяющее отвлечься от адреса ячейки памяти и обращаться к ней с помощью имени (идентификатора).
Переменная – есть именованный объект (ячейка памяти), который может изменять свое значение. Имя переменной указывает на зн ачение, а способ ее хранения и адрес остаются скрытыми от программиста. Кроме имени и значения, переменная имеет тип, определяющий, какая информация находится в памяти. Тип переменной задает:
-
используемый способ записи информации в ячейки памяти;
-
необходимый объем памяти для ее хранения.
Объем памяти для каждого типа определяется таким образом, чтобы в него можно было поместить любое значение из допустимого диапазона значений данного типа. Например, тип «байт» может принимать значения от О до 255, что в двоичном коде (255(10)=11111111(2)) соответствует ячейке памяти длиной в 8 бит (или 1 байт).
В описанных выше алгоритмах (примеры 1-3) все данные хранятся в виде переменных. Например, инструкция «Ввод двух чисел а, b » означает введение пользователем значений двух переменных, а инструкция «К=К + 1» означает увеличение значения переменной К на единицу.
Если переменные присутствуют в программе, на протяжении всего времени ее работы – их называют статическими. Переменные, создающиеся и уничтожающиеся на разных этапах выполнения программы, называют динамическими.
Все остальные данные в программе, значения которых не изменяются на протяжении ее работы, называют константами или постоянными. Константы, как и переменные, имеют тип. Их можно указывать явно, например, в инструкции «К=К+1» 1 есть константа, или для удобства обозначать идентификаторами: pi=3,1415926536. Только значение pi нельзя изменить, так как это константа, а не переменная.
Структурированные данные и алгоритмы их обработки
Для повышения производительности и качества работы необходимо иметь данные, максимально приближенные к реальным аналогам. Тип данных, позволяющий хранить вместе под одним именем несколько переменных, называется структурированным. Каждый язык программирования имеет свои структурированные типы. Рассмотрим структуру, объединяющую элементы одного типа данных, — массив.
Массивом называется упорядоченная совокупность однотипных величин, имеющих общее имя, элементы которой адресуются (различаются) порядковыми номерами (индексами). В качестве иллюстрации можно представить шкаф, содержащий множество пронумерованных ящиков (совокупность — «Ящик № 1», «Ящик № 2», «Ящик № 3» и т.д.; «Ящик» — общее имя всех ее элементов). Доступ к содержимому конкретного ящика (элементу массива) осуществляется после выбора ящика по его номеру (индексу). Элементы массива в памяти компьютера хранятся по соседству, одиночные элементы простого типа такого расположения данных в памяти не предполагают. Массивы различаются количеством индексов, определяющих их элементы.
Одномерный массив (шкаф ящиков в один ряд) предполагает наличие у каждого элемента только одного индекса. Примерами одномерных массивов служат арифметическая (аi) и геометрическая (bi) последовательности, определяющие конечные ряды чисел. Количество элементов массива называют размерностью. При определении одномерного массива его размерность записывается в круглых скобках, рядом с его именем. Например, если сказано: «задан массив A (10)», это означает, что даны элементы: a 1 , a 2 , …, a 10 . Рассмотрим алгоритмы обработки элементов одномерных массивов.
Ввод элементов одномерного массива осуществляется поэлементно, в порядке, необходимом для решения конкретной задачи. Обычно, когда требуется ввести весь массив, порядок ввода элементов не важен, и элементы вводятся в порядке возрастания их индексов. Алгоритм ввода элементов массива А(10) представлен на рис.9.
Пример 4.
В заданном числовом массиве A(l0) найти наибольший элемент и его индекс, при условии, что такой элемент в массиве существует, и единственный.
Обозначим индекс наибольшего элемента т. Будем считать, что первый элемент массива является наибольшим (т = 1). Сравним поочередно наибольший с остальными элементами массива. Если оказывается, что текущий элемент массива а i (тот, c которым идет сравнение) больше выбранного нами наибольшего ат, то считаем его наибольшим (т=i) (рис.10).
Рассмотрим двумерный массив (шкаф с множеством ящиков, положение которых определяется двумя координатами – по горизонтали и по вертикали). В математике двумерный массив (таблица чисел) называется матрицей. Каждый ее элемент имеет два индекса а ij , первый индекс i определяет номер строки, в которой находится элемент (координата по горизонтали), а второй j – номер столбца (координата по вертикали). Двумерный массив характеризуется двумя размерностями N и М, определяющими число строк и столбцов соответственно (рис. 11).
Ввод элементов двумерного массива осуществляется построчно, в свою очередь, ввод каждой строки производится поэлементно, тем самым определяется циклическая конструкция, реализующая вложение циклов. Внешний цикл определяет номер вводимой строки ( i ), внутренний – номер элемента по столбцу ( j ). На рис. 12 представлен алгоритм ввода матрицы A(MxN) .
Пример 5.
Задана матрица символов (100х100), представляющая собой карту ночного неба; звездам на карте соответствует символы «*». Определить: сколько звезд на карте?
Алгоритм решения задачи достаточно прост, необходимо перебрать все элементы матрицы и посчитать, сколько среди них символов «*». Обозначим К переменную – счетчик. На рис 13. представлена блок-схема решения этой задачи.
В информатике план действий называют алгоритмом.
Алгоритм состоит из отдельных шагов – команд. Ни одну из них нельзя пропустить, чаще всего никакие команды нельзя поменять местами.
Исполнитель – человек, животное или машина, способные понимать и выполнять некоторые команды.
Среда исполнителя – предметы, которые окружают исполнителя и с которыми он работает.
Список Команд Исполнителя (СКИ) – набор команд, понятных исполнителю. Исполнитель может выполнить только те команды, которые входят в его СКИ.
Для решения большинства задач недостаточно отдать одну команду исполнителю, надо составить для него алгоритм – план действий, состоящий из команд, которые ему понятны (входят в его СКИ).
Алгоритм – точно определенный план действий исполнителя, направленный на решение какой-то задачи. В алгоритм можно включать только те команды, которые есть в СКИ.
Какие бывают алгоритмы
Линейный алгоритм
В линейном алгоритме команды выполняются последовательно, одна за другой. Примером линейного алгоритма может служить алгоритм заварки чая.
Разветвляющийся алгоритм
В разветвляющемся алгоритме порядок следования команд может быть разный в зависимости от того, какова окружающая обстановка. Примером разветвляющегося алгоритма может служить алгоритм перехода улицы.
Циклический алгоритм
В циклическом алгоритме некоторые действия повторяются несколько раз (в информатике говорят, что выполняется цикл). Существуют два вида циклических алгоритмов. В одном из них мы знаем заранее, сколько раз надо сделать эти действия, в другом мы должны остановиться лишь тогда, когда выполним работу, то есть наши действия прекращаются при выполнении какого-то условия.
Примером цикла первого типа является наша жизнь в рабочие дни (от понедельника до субботы) – мы выполняем 6 раз почти одни и те же действия.
Пример цикла второго типа – алгоритм распилки бревна: мы не можем заранее сказать, сколько раз нам надо провести пилой от себя и на себя — это зависит от плотности дерева, качества пилы и наших усилий. Однако мы точно знаем, что надо закончить работу, когда очередное отпиленное полено упадет на землю.
Способы записи алгоритмов
Выделяют три наиболее распространенные на практике способа записи алгоритмов:
- словесный (запись на естественном языке);
- графический (запись с использованием графических символов);
- программный (тексты на языках программирования).
Словесный способ записи алгоритмов
Словесный способ – способ записи алгоритма на естественном языке. Данный способ очень удобен, если нужно приближенно описать суть алгоритма. Однако при словесном описании не всегда удается ясно и точно выразить логику действий.
В качестве примера словесного способа записи алгоритма рассмотрим алгоритм нахождения площади прямоугольника
S=a*b,
где S – площадь прямоугольника; а, b – длины его сторон.
Очевидно, что a, b должны быть заданы заранее, иначе задачу решить невозможно.
Словестный способ записи алгоритма выглядит так:
- Начало алгоритма.
- Задать численное значение стороны a.
- Задать численное значение стороны b.
- Вычислить площадь S прямоугольника по формуле S=a*b.
- Вывести результат вычислений.
- Конец алгоритма.
Графический способ описания алгоритмов
Для более наглядного представления алгоритма используется графический способ. Существует несколько способов графического описания алгоритмов. Наиболее широко используемым на практике графическим описанием алгоритмов является использование блок-схем. Несомненное достоинство блок схем – наглядность и простота записи алгоритма.
Каждому действию алгоритма соответствует геометрическая фигура (блочный символ). Перечень наиболее часто употребляемых символов приведен в таблице ниже.
Так как в линейном алгоритме команды выполняются последовательно, то блок-схема будет иметь вид:
Так как в разветвляющемся алгоритме порядок следования команд может быть разный в зависимости от того, какова окружающая обстановка, то блок-схема примет вид:
В циклическом алгоритме некоторые действия повторяются несколько раз и для него блок-схема примет вид:
Программный способ записи алгоритмов
Для того, чтобы алгоритм был понятен роботу, компьютеру или другой машине, недостаточно только написать команды, надо еще и оформить алгоритм в таком виде, в котором его понимает машина (написать программу), т.е. записать его с использованием команд из СКИ, соблюдая правила оформления.
Правила оформления программы:
- любой алгоритм имеет название;
- алгоритм начинается с открывающей фигурной скобки “{“ и заканчивается закрывающей фигурной скобкой “}”; команды, расположенные между этими скобками, называются телом алгоритма;
- в алгоритм могут входить только те команды, которые есть в СКИ исполнителя;
- каждая команда заканчивается знаком “;”, который обозначает конец команды;
- для того, чтобы нам было легче разбираться в программах, используют комментарии — текстовые пояснения, которые начинаются знаками “/*” и заканчиваются знаками “*/”; исполнитель не обращает внимания на комментарии в алгоритме.
Практические задания:
- Составить блок-схему для нахождения периметра квадрата.
- Составить блок схему для заваривания чая.
- Составить блок-схему для перехода перекрестка со светофором.
Использован материал из книг:
- «Современные информационные технологии», авторы преподаватели центра «Турбо»
- «Алгоритмы и исполнители», автор Поляков К.