Если у вас возникли сложности с курсовой, контрольной, дипломной, рефератом, отчетом по практике, научно-исследовательской и любой другой работой - мы готовы помочь.
Предоплата всего
Подписываем
Муниципальное общеобразовательное учреждение
Андрейковская с.ш.
Информатика
серия «Введение в основы программирования»
Алгоритмизация
Часть 1: Основы алгоритмизации
с.Андрейково
2010
Серия «Введение в основы программирования»
Информатика
Алгоритмизация
Часть 1: Основы алгоритмизации
Методическое пособие
для профильных и непрофильных классов общеобразовательной и очно-заочной школы
ВККИ 000.002.001
Мандриков В.Г.
М–0 Алгоритмизация. Основы алгоритмизации. Блок-схемы. Методическое пособие. – Андрейково: кабинет Информатики, 2010.
Методическое пособие предназначено для учащихся профильных и общеобразовательных классов и учащихся очно–заочной школы, существующей при МОУ Андрейковская средняя школа, в рамках изучения предмета информатики, а также для преподавателей школы, изучающих различные приложения компьютерных технологий.
© МОУ Андрейковская с.ш., 2010
© Мандриков В.Г., 2010
Пояснительная записка
Решение любых задач – научных, школьных, статистических, повседневных бытовых и др. – всегда производится по определенному алгоритму, независимо от того хотим мы этого или нет. Поэтому очень важно иметь представление, что такое алгоритм, как его составить и использовать, и в каком его виде можно зафиксировать (записать, описать словесно и т.п.) для того, чтобы передать другим людям, или внести в память ЭВМ или другой автоматической машины.
|
[1]
[2]
[3] [3.1] Способы записи алгоритма
[4] [4.1] Основные блоки [4.2] Алгоритмические структуры
[5] [5.1] Линейные алгоритмы [5.2] Алгоритмы ветвления [5.3] Алгоритмы циклов
[6]
[7] |
Слово «алгоритм» происходит от латинской формы написания имени арабского математика Аль Хорезми, жившего в 800-ых годах в Багдаде – крупном научном центре Древнего Востока. Заслуга Аль Хорезми состояла в том, что он сформулировал правила четырех арифметических действий (сложения, вычитания, умножения, деления) над многозначными числами. Первоначально под алгоритмом понимали только эти правила, но в последствии понятие алгоритма стали использовать более широко.
Каждый из нас в своей повседневной жизни сталкивается с огромным количеством разнообразных по своей сложности задач. Многие из них настолько привычны и естественны, что мы не задумываемся над способом их решения. Как правило, нам они хорошо известны и, более того, сформулированы в виде специальных инструкций.
Решение многих задач связано с их тщательным анализом, со сложными рассуждениями, требующими высокой профессиональной квалификации и большой изобретательности. Совсем другое дело, когда те же задачи решаются по уже готовому предписанию – алгоритму, ведь намного проще исполнять придуманные кем-то инструкции, часто даже не задумываясь об их назначении и смысле.
Рассмотрим одну часто встречающую ситуацию: пешеходу необходимо перейти улицу с двухсторонним движением. Когда он пользуется переходом на перекрестке улиц, где движение регулируется светофором, действия пешехода предельно просты. Нужно убедиться в том, что на светофоре горит зеленый свет, и прейти улицу. Гораздо более сложную последовательность действий необходимо совершить, когда нет светофора. В этом случае пешеход должен вести себя, например, следующим образом. Посмотреть налево и, убедившись в том, что опасности столкновения с автомобилем нет, дойти до середины улицы. Очевидно, что все автомобили, следующие слева направо, представляют для него опасности. Находясь на осевой линии дороги, пешеходу теперь следует посмотреть направо. Если автомобилей вблизи нет, то дорогу можно переходить.
Более четко действия пешехода можно записать так:
Несложно придумать огромное количество примеров, где для достижения цели определен набор правил или инструкций, приводящих к определенному результату. Такие наборы правил называют алгоритмами.
В конечном итоге исполнитель воспринимает в виде набора каких-то команд (инструкций, правил).
Алгоритм – подробное описание последовательности действий, расположенных в определенном логическом порядке, которое позволяет решить конкретную задачу.
Составление такого пошагового описания процесса решения задачи называется ее алгоритмизацией.
Командой, инструкцией или правилом можно назвать элементарные действия (шаги), понятные исполнителю, на которые разбивается процесс решения задачи.
Таких команд должно быть конечное число, иначе решение задачи не будет возможным. Т.е. можно сказать, что алгоритм – это конечная последовательность инструкций, которая должна быть выполнена исполнителем для решения поставленной задачи.
Для каждого алгоритма необходимо соблюдать ряд требований.
Во-первых, недопустимы инструкции, которые имеют неопределенное или неоднозначное толкование. Алгоритм должен быть однозначным и понятным. Это означает, что исполнителю ясно, каким образом выполняется алгоритм, причем любой исполнитель однозначно понимает смысл последовательности действий, составляющих алгоритм.
Алгоритм перехода улиц остается одинаковым как для каждого человека, так и для перекрестков улиц в различных районах и даже в других городах. Такая пригодность алгоритма для решения не только данной задачи, но и множества родственных задач, относящихся в общему классу, называется массовостью. Это свойство позволяет один и тот же алгоритм использовать для решения задачи при различных начальных данных.
Важно, чтобы при повторе исходных данных, повторился и результат выполнения алгоритма. Данное свойство называется детерминированность. Из этого свойства вытекает независимость решения задачи от индивидуальных особенностей исполнителя.
Алгоритм не имеет смысла создавать, если он не обладает корректностью, т.е. способностью давать правильные результаты решения задачи при различных исходных данных.
Всегда ли можно получить результат, применяя алгоритм к некоторому набору из множества допустимых исходных данных? Оказывается, что не всегда. Рассмотрим алгоритм деления двух чисел и с качестве делимого возьмем число 11, а в качестве делителя – число 9. Оба числа допустимы для алгоритма деления двух чисел. Но совершенно очевидно, что процесс деления никогда не закончится, так как результатом будет являться бесконечная десятичная дробь 1,22222… Об алгоритмах подобного рода говорят, что они потенциально осуществимы, но состоят из бесконечного числа шагов. В связи с этим надо говорить о конечности алгоритма. Т.е. решение задачи должно быть получено через конечное число шагов алгоритма и за конечное время.
Эффективность: для успешного решения задачи должны использоваться ограниченные ресурсы.
Каким образом нужно представить алгоритм, чтобы исполнитель мог его использовать?
Алгоритм можно задать любым способом, но выбор способа зависит, в первую очередь, от того, кто будет исполнителем алгоритма.
Для описания алгоритмических процессов можно использовать обычный разговорный язык.
Однако такая запись для сложных алгоритмов оказывается, как правило, очень громоздкой. А главное – недостаточно четкой и строгой.
Для ЭВМ алгоритм можно описывать на внутреннем языке машины. Этот способ использовался на первых ЭВМ. В этом случае нужно алгоритм решения задачи записать в виде последовательности элементарных операций. В этом случае, если задача достаточно сложная, то и запись алгоритма ее решения будет громоздкой, труднообозримой и может содержать значительное число ошибок. Да и обмениваться такими алгоритмами неудобно, ведь каждая ЭВМ имеет ряд присущих только ей особенностей.
Таким образом, нужны языки записи алгоритмов, т.е. некоторые формализованные средства, правила представления общепринятых символов записывать алгоритмы. Язык этот должен быть достаточно гибким, чтобы описывать сложные алгоритмы, используя при этом минимум изобразительных средств, позволять человеку отчетливо, но в то же время сжато выразить свою мысль.
Для задания алгоритмов используются следующие способы.
Описание алгоритма на профессиональном языке той области знаний, которой принадлежит задача: с использованием математической символики, терминов и понятий, характерных для конкретной области знаний.
Описательный или словесный – способ записи алгоритма на естественном языке или с использованием специального псевдоязыка.
Некоторые алгоритмы можно записать табличным способом – в виде таблицы, устанавливающей зависимость результата от исходных данных.
Графическое представление алгоритма в виде совокупности его фрагментов с указанием связей между ними.
Представление графического изображения алгоритма в виде плоских геометрических фигур (блоков), соединенных линиями (стрелками), как правило, называют блок-схемой. Внутри блока записывается действие, которое необходимо выполнить, или условие, которое необходимо проверить.
Описание алгоритма на языке программирования. Текст, представляющий запись алгоритма на языке программирования, называют программой.
Самый наглядный способ записи алгоритма – блок-схема. Поэтому основные алгоритмические структуры удобнее рассматривать, используя эту форму записи.
Блок-схема – последовательность блоков, соединенных линиями передачи (ветвями).
Блоки – это, как правило, геометрические фигуры, каждая из которых обозначает строго определенное действие.
Рисунок .
Существуют другие виды блоков, но здесь перечислены основные, которых практически во всех случаях достаточно для записи алгоритма.
Блоки соединяются ветвями, т.е. линиями передачи. Ветви указывают направление выполнения действий. Нормальное направление сверху вниз и слева направо. В этих случаях стрелки ставить необязательно. Во всех других случаях ставить стрелки обязательно.
Блок-схема начинается с блока начало, поэтому у нее нет входа, а есть только выход на следующий блок:
Рисунок
Внутри блока обмена информацией или ввода-вывода пишется команда ввода информации или вывода. Он всегда располагается внутри алгоритма, поэтому у него всегда есть один вход от предыдущего блока и один выход на следующий:
Рисунок
Блок действия или процесса предназначен для записи в нем вычислительных операций и также имеет один вход и один выход:
Рисунок
Блок условия изображается в виде ромба, а внутри пишется сравнение (равенство или неравенство). Так как любое сравнение может быть истинным или ложным, то блок имеет один вход, но два выхода. Часто из-за этого данный блок называют ветвлением:
Рисунок
Блок конца алгоритма закрывает алгоритм, поэтому имеет только один вход и ни одного выхода:
Рисунок
Блок узел является вспомогательным и применяется для связывания ветвей алгоритма в одну ветвь. Узел может иметь один выход и два или три входа:
Рисунок
Учтите, что при составлении алгоритма, во-первых, ветви, соединяющие два блока, должны рисоваться только из горизонтальных или вертикальных отрезков, а, во-вторых, необходимо четко соблюдать указанное количество входящих и выходящих ветвей для каждого блока.
Любой алгоритм можно представить в виде комбинации трех базовых алгоритмических структур.
Самая простая структура – линейная или структура следования. В данной структуре все команды выполняются последовательно, друг за другом без возврата назад и без разделения на несколько ветвей.
Рисунок
Структура ветвления представляет алгоритм, содержащий одно или несколько условий и соответственно две и более ветви, одна из которых указывает действия, совершаемые если условие выполняется, а вторая ветвь – действия, совершаемые если условие не выполняется.
Ниже представлена полная структура ветвления:
Рисунок
Существует также сокращенная (неполная) форма алгоритма выбора:
Рисунок
Иногда некоторые действия в зависимости от условия нужно повторить несколько раз. Такое многократное повторение одного или нескольких действий называют циклом, а действия внутри цикла – телом цикла.
Выделяют три вида циклов: цикл с предусловием, цикл с постусловием и цикл-счетчик.
Блок-схема цикла с предусловием:
Рисунок
Структура цикла с постусловием:
Рисунок
Существуют циклы, в которых при входе в них известно, сколько повторений действий произойдет. В нем указываются начальное и конечное. Каждый раз при выполнении действий, составляющих тело цикла, счетчик получает приращение, называемое шагом. По умолчания шаг обычно равен единице. Цикл-счетчик выглядит так:
Рисунок
Счетчик можно изобразить так:
Рисунок
Реальные алгоритмы обычно являются сочетанием всех основных алгоритмических структур.
Задача 1: Записать алгоритм создания бутерброда в виде блок-схемы.
Далее блоки начала и конца будут опускаться для сокращения записи блок-схемы.
Задача 2: Записать алгоритм сложения двух чисел в виде блок-схемы.
Задача 3: Записать алгоритм создания бутерброда с маслом или вареньем по выбору в виде блок-схемы.
Задача 4: Записать алгоритм решения квадратного уравнения ax2+bx+c=0 в виде блок-схемы.
Задача 5: Записать алгоритм создания нескольких бутербродов.
Задача 6: Записать алгоритм построения таблицы умножения целого числа на числа от 1 до 9.
Создайте блок-схемы для алгоритмов решения следующих задач:
Алгоритм
Исполнитель
инструкции или команды
Алгоритм
Исполнитель
инструкции или команды
Задача
действия
а
б
в
г
д
ж
е
Начало
Конец
Действие 1
Действие 2
Действие n
…
словие
Действие 1
…
Действие n
Действие 1
…
Действие m
Да
Нет
условие
Действие 1
…
Действие n
Да
Нет
Условие
Действие 1
…
Действие n
Да
Нет
Условие
Действие 1
…
Действие n
Да
Нет
i:=перв. значение; посл. значение; шаг
Действие 1
…
Действие n
i<=посл. значение
Действие 1
…
Действие n
i:=первое значение
i:=i+шаг
Начало
Режем хлеб
Мажем масло
Режем сыр;
Кладем его на бутерброд
Конец
Ввод:
число 1;
число 2
Складываем числа:
Сумма:=число1+число2
Вывод:
сумма
Режем хлеб
Хотим с маслом?
Мажем масло
Мажем варенье
Вывод:
бутерброд готов
Вычисление дискриминанта D
Ввод:
a, b, c
D>0
Вывод:
«Корней нет»
Вычисление корней
Вывод:
корни х1, х2
Режем хлеб
Мажем масло
Режем сыр;
кладем его на бутерброд
Достаточно бутербродов?
Нет
Да
Ввод целого числа L
N>9
Result:=L*N
N:=N+1
N:=1
Вывод: Result
Да
Нет