Алгоритмы, построение блок-схемы алгоритмов,
понятие алгоритмического языка
Цель занятия:
Познакомить учащихся с понятием алгоритма, со структурой и блок схе-
мой с целью обучения учащихся свободно и самостоятельно разрабатывать
блок - схемы алгоритмов решения поставленных задач, для дальнейшего
переложения решения задачи на алгоритмический язык программирования
ЭВМ.
План занятия:
1. Организационный момент.
2. Краткий анализ предыдущих знаний учащихся по структурной схеме и
языку электронно-вычислительных машин.
3. Понятие алгоритма.
а) алгоритмы циклические, линейные, ветвлящиеся
б) алгоритмы решения задач не вычислительного характера
в) детерминированность, массовость, результативность алгоритма
4. Методы описания алгоритма
а) блок-схема алгоритма
б) построение блок схемы
в) блоки - вычислительный
подготовительный
логический
стандартный
5. Алгоритмический язык
а) символы языка
б) слова языка
6. Подведение итогов занятия , закрепление пройденного материала.
Развернутый план зханятий.
1. Организационный момент.
Решение общих мелких вопросов группы, отметка посещаемости, настрой на
рабочую атмосферу занятия, обьявление и запмсь темы.
2. Краткий анализ предварительных знаний.
Повторение структурной схемы электронно-вычислительной машины.
Системный блок, внешнее запоминающее устройство, устройство ввода вы-
вода, физические принципы запоминания информации.
Учащиеся должны вообразно воссоздать структурную схему ЭВМ , процессы
происходящие при вычислении в ЭВМ , последовательность выполнения
простых операций электронно-вычислительной машиной, подойти к состав-
лению описания процесса вычисления , ( т.е. алгоритма ), подойти к по-
нятию алгоритма.
3. Понятие алгоритма.
С понятием алгоритма человек встречается на каждом шагу своей дея-
тельности, однако часто не отдает себе в этом отчета.
Рассмотрим в качестве примера задачу о выборе наибольшего из трех за-
данных чисел 15,20,45 ( x,y и z ). Для решения этой задачи нам доста-
точно беглого взгляда, но в основе всего этого лежит некоторая зара-
нее предписанная последовательность достаточно простых действий. Ка-
кая же она -
1. сравнить x с y , если x=z то перейти к пункту 3., в противном слу-
чае положить a=z и перейти к пункту 3.
3.Принять a в качестве окончательного результата и прекратить процесс
решения задачи.
Таким образом, под алгоритмом понимают точное предписание по выполне-
нию некоторого вычислительного процесса, который через конечное число
шагов приводит к решению любой задачи данного типа.
Происхождение слова allgorism долгое время оставалось не ясным. Исто-
рики математики обнаружили истинное происхождение слова algorism - о-
но произошло от имени автора известного арабского учебника по матема-
тике: - Aby Ja far Mohammed ibn Musa Al-Khowarizmi , означающего бук-
вально - " отец Джафара , Магомет, сын Моисея, уроженец Ховаризма ) -(
русское название - Аль-Хрезм)
Сам термин алгоритм происходит от имени узбекского математика
Аль-Хорезми, который еще в 9 в. н.э. сформулировал и применил последо-
вательность простых правил при выполнении арифметических операций. В
качестве следующего примера рассмотрим алгоритм нахождения всех прос-
тых чисел , меньших заданного числа N. Этот алгоритм был предложен
Эратосфеном около 250 г. до н.э. и носит название " решето Эратосфена
". Идея этого алгоритма заключается в вычеркивании всех чисел , крат-
ных простым числам , причем невычеркнутыми остаются только числа , не
кратные ни одному числу, предшествующему им. , т.е. простые числа.
Построим алгоритм нахождения всех простых чисел меньших N=30 . Снача-
ла выпишем все целые числа от 1 до 29:
1 2 3 4 5 6
7 8 9 10 11 12
13 14 15 16 17 18
19 20 21 22 23 24
25 26 27 28 29
перейдем к указанию 1.
1. Вычеркнем 1, так как это не простое чмсло, перейдем к указанию 2.
2. Оставим первое невычеркнутое число ( им окажется 2 ) и вычеркнем
каждое второе число после него. Получаем:
1 2 3 4 5 6
7 8 9 10 11 12
13 14 15 16 17 18
19 20 21 22 23 24
25 26 27 28 29
Перейдем к указанию 3.
3. Оствавим первое невычеркнутое после 2 число, большее 2 ( им будет
3), и вычеркнем каждое третье число после него. Получаем:
1 2 3 4 5 6
7 8 9 10 11 12
13 14 15 16 17 18
19 20 21 22 23 24
25 26 27 28 29
перейдем к указанию 4.
4. Оставим первое невычеркнутое число, большее 3 ( им будет 5 ), и вы-
черкнем каждое пятое число после него. Получаем:
1 2 3 4 5 6
7 8 9 10 11 12
13 14 15 16 17 18
19 20 21 22 23 24
25 26 27 28 29
После выполнения указания 4 остались числа 2.3, 5,7,11,13,17,19,23,29,
т.е. все простые числа, меньшие 30.
В качестве еще одного примера можно рассмотреть алгоритма поис-
ка наибольшего общего делителя (НОД). Алгоритм Эвклида.
Для двух заданных чисел найти их общий наибольший делитель. Алгоритм
будет иметь следующий вид.
1.Сравнить числа а и б. При сравнении возможны два случая а=б, а<>б.
Если а=б, то за НОД принять любое из них. Вычисление прекратить. Если
а<>б , перейти к указанию 2.
2. Если а<б , перейти к указанию 3, если а>б , перейти к указанию 4.
3. Поменять местами а и б. Перейти к указанию 4.
4. Вычесть из большего числа меньшее. Перейти к указанию 5.
5. Если разность равна 90, то за НОД принять вычитаемое. Вычисление
прекратить. Если разность отлична от нуля, перейти к указанию 6.
6. За новое вычитаемое взять полученную разность, а за новое уменьшае-
мое взять старое вычитаемое. Перейти к указанию 1.
Практически любой сложный алгоритм обычно строится из комбинации трех
базовых структур: линейной, разветляющейся, и циклической.
Линейная базовая структура состоит из простой последовательности дей-
ствий, которые выполняются только один раз в порядке их следования7
Разветвляющая структура, называемая так же развилкой, обычно содержит
блок проверки некоторого логического условия, например , a>=0,a меньше
b и т.д.В зависимости от результата проверки выполняется та или иная пос-
ледовательность действий, называемая ветвью.
Циклическая структура, называемая так же повторением, содержит некото-
рую последовательность действий, выполняемых многократно.
Данные структуры рассматриваются учащимися на выше рассмотренных при-
мерах.
Примеры не вычислительного алгоритма, например, человека, незнакомого
с правилами уличного движения, инструктируют относительно перехода
улицы ( будем считать сфетофор двухцветным ).
1. Если горит красный свет то улицу не переходи.
2. Если горит зеленый свет, то улицу переходи до половины, смотря на
транспорт слева.
3. Если по достижении средины улицы продолжает гореть зеленый свет, то
переходи улицу до конца, смотря на транспорт справа.
Руководствуясь таким алгоритмом, человек будет правильно вести себя
при переходе улицы. Но в ней мы обнаруживаем ряд неточностей. Какие?
Буквальное выполнение инструкции привело бы к нелепости.
Алгоритм перехода улицы в математическом смысле этого слова приобре-
тет следующий вид.
1. Посмотреть на светофор, если горит зеленый свет, перейти к дей-
ствию 3.
2. Стоять и ждать зеленого света.
3. Переходить улицу до средины, смотря на транспорт слева.
4. Посмотреть на светофор, если горит зеленый свет, перейти к дей-
ствию 6.
5. Стоять и ждать зеленого света.
6. Переход улицы до конца, смотря на транспорт справа.
Задача о сортировке шариков.
Имеется три урны: белая, черная, и полосатая. В полосатой урне нахо-
дятся белые и черные шарики. Надо все черные шарики переложить в чер-
ную урну.
Алгоритм учащиеся пытаются составить самостоятельно.
1. Взять шарик из полосатой урны.
2. Если он белый, то опустить его в белую урну.
3. Если он черный, то опустить его в черную урну.
4. Если полосатая урна не пуста, то перейти к действию 1.
5. Конец.
Это так называемый циклический алгоритм.
Задание: Построить алгоритм поведения пассажира лифта, учитывая типич-
ные ситуации, которые могут с ним случиться.
Подводя итог рассмотрению предыдущих примеров, можно выделить следую-
щие общие черты, присущие любому алгоритму.
Детерминированность алгоритма. Так как перечень правил являющийся ал-
горитмом, полностью однозначен, то его многократное применение к од-
ним и тем же начальным условиям дает тот же результат.
Массовость алгоритма - алгоритм не является предписанием для решения
одной конкретной задачи, а позволяет решить серию однотипных задач при
различных начальных условиях.
Результативность алгоритма.
Алгоритм является предписанием при применении которого получаем либо
результат решения через конечное число шагов, либо сигнал о невозмож-
ности решения.
4. Методы описания алгоритма.
Словесное описание алгоритма не приемлимо для ввода в вычислительную
машину. Для этого необходимо изложить алгоритм на машинном языке та-
ким образом, чтобы с его помощью происходило автоматическое управле-
ние работой ЭВМ.
Запись алгоритма на языке машины называется программой решения задачи.
Однако для относительно сложных задач переходить сразу от алгоритма к
программе крайне затруднительно.
Обычно алгоритм разрабатывается в несколько приемов.
Наиболее удобным способом записи алгоритма на первых этапах его разра-
ботки является структурная схема алгоритма.
Структурная схема алгоритма представляет собой графическое изображе-
ние последовательности действий при реализации данного алгоритма. Эта-
пы решения задачи представляются в структурной схеме отдельными блока-
ми, которые изображаются соответствующими символами - прямоугольника-
ми, ромбами, кругами, овалами и т.д.
Внутри символов структурной схемы указывается содержание соответствую-
щих этапов вычислений.
Блок-схемой алгоритма называется такое графическое изображение ал-
горитма, в котором этапы решения задачи изображаются в виде различных
геометрических фигур: прямоугольников, кругов, многоугольников и т.д.
Внутри этих фигур указывается содержание данного этапа вычесления,
причем если описание этапа вычисляется оказывается громоздким, внутри
блока ставится номер этапа вычисления, а описание дается в приложении
к блок-схеме. Геометрические фигуры (блоки) соединяются стрелками, по-
казывающими направление развития вычислительного процесса. Иногда око-
ло стрелок делают надписи, показывающие, при каких условиях происхо-
дит выбор данного направления. В самом общем случае можно выделить
следующие группы блоков.
1.Выделенный блок - такой участок программы, который связан либо с
непосредственным выделением функции, либо с выполнением арифметичес-
ких действии по обработке информации.
2.Подготовительный блок - группа команд, которые выполняют функции
переадресации, восстановления, засылки данных в специальные ячейки,
отчистки рабочих ячеек памяти и т.д. Иными словами, это участок прог-
раммы, выполняющий функции подготовки других блоков к началу вычисли-
тельного процесса. Обычно эти блоки используют при организации таких
процессов вычислений, при которых вычисления выполняются по одним и
тем же формулам, но для различных исходных данных.
3.Логический блок - участок программы, связанный с изменениями вы-
числительного процесса.Такие блоки используют, когда необходимо прово-
дить расчеты по различным формулам, что зависит от соотношения либо
исходных данных, либо промежуточных результатов расчета.
4.Стандартный блок, имеющий широкое распространение в самых различ-
ных программах. Такие блоки отрабатываются заранее, и программист ис-
пользует их уже готовыми. Примерами стандартных блоков могут служить
группы команд, осуществляющие ввод информации в цифровую ЭВМ, перевод
чисел из десятичной системы счисления в двоичную, из двоичной в деся-
тичную, выдачу результатов на печать, останов машины и т.д.
Приведенное разбиение является условным, так как, строго говоря,
все эти блоки являются вычислительными.
В качестве примера использования обозначений, приведенных в табл.3,
рассмотрим блок-схему алгоритма нахождения НОД двух чисел a и b.
На приведенной блок-схеме ромбом выделен этап на котором происхо-
дит разветвление вычислительного процесса. При выполнении условия, за-
писанного в ромбе следует перейти по стрелке "Да" к соответсвующей
части программы; при невыполнении условия осуществляется переход по
стрелке "Нет". Если данный этап имеет всегда одно и тоже продолжение,
то он обозначается прямоугольником.
Основным достоинством блок-схемы алгоритма является ее наглядность,
однако при большой детализации блок-схема становится громоздкой и те-
ряет наглядность.
Заметим, что, используя только блок-схему алгоритма не всегда, мож-
но выполнить изображаемый алгоритм. Чтобы выполнение алгоритма всегда
было возможным, он должен быть представлен либо в оперативной форме,
либо на алгоритмическом языке, и в этом случае блок-схема алгоритма
намного упрощает работу программиста.
5. Алгоритмический язык.
Алгоритмический язык - это набор символов, являющихся алфавитом
языка, система правил связи символов для образования слов, с помощью
которых представляются отдельные составляющие компоненты языка (син-
таксис языка), и система правил истолкования слов языка (семантика).
Рассмотрим четыре элемента языка, а именно: символы, выражения,
операторы.
Символы языка - это основные, неделимые знаки, с помощью которых
пишутся тексты на языка.
Слова языка - это структуры, образованные непосредственно из симво-
лов языка и являющиеся минимальными структурами, которые имеют смысл
сами по себе. Таким образом, слово - это комбинация символов, за кото-
рыми следует пробел или знак препинания. В этом смысле число также яв-
ляется словом. Однако печатающие устройства вычислительных машин скон-
струированы так, что выдают не отдельные слова, а строки символов,
состоящих из букв и цифр. В этом случае слова, т.е. строки букв и
цифр, называются идентификаторами, переменными, метками или числами.
Выражения - это группы слов или части предложений языка. В алгорит-
мических языках выражениям приписывается значение некоторой величины.
Оператор алгоритмического языка - это минимальная структура, пред-
ставляющая законченную мысль или задающая полное описание некоторого
вычисления, которое надо выполнить.
6. Подведение итогов занятия по данной теме.
Знание основных понятий и приобретение начальных навыков в разработке
алгоритма поставленных задач является основой начального этапа прог-
раммирования.
Из вышеизложенного материала следует, что алгоритмизация процесса пе-
реработки данных ( решения задач ) и является сущностью программирова-
ния.
|
.............................. |
|
............................. |
|
| Дворец Творчества Детей и Молодежи |