>> Типы алгоритмов
В алгоритмах команды записываются друг за другом в определенном порядке. Выполняются они не обязательно в записанной последовательности: в зависимости от порядка выполнения команд можно выделить три типа алгоритмов:
Линейные алгоритмы;
алгоритмы с ветвлениями;
алгоритмы с повторениями.
Линейные алгоритмы
В котором команды выполняются в порядке их записи, то есть последовательно друг за другом, называется линейным.
Например, линейным является следующий алгоритм посадки дерева:
1) выкопать в земле ямку;
2) опустить в ямку саженец;
3) засыпать ямку с саженцем землей;
4) полить саженец водой.
С помощью блок-схемы данный алгоритм можно изобразить так:
Алгоритмы о ветвлениями
Ситуации, когда заранее известна последовательность требуемых действий, встречаются крайне редко. В жизни часто приходится принимать решение в зависимости от сложившейся обстановки. Если идет дождь, мы берем зонт и надеваем плащ; если жарко, надеваем легкую одежду. Встречаются и более сложные условия выбора. В некоторых случаях от выбранного решения зависит дальнейшая судьба человека.
Логику принятия решения можно описать так:
ЕСЛИ <условие> ТО <действия 1> ИНАЧЕ <действия 2>
Примеры:
ЕСЛИ хочешь бытьздоров
, ТО закаляйся, ИНАЧЕ валяйся весь день на диване;
ЕСЛИ низко ласточки летают, ТО будет дождь, ИНАЧЕ дождя не будет;
ЕСЛИ уроки выучены, ТО иди гулять, ИНАЧЕ учи уроки.
В некоторых случаях <действия 2> могут отсутствовать;
ЕСЛИ <условие> ТО <действия 1>
Пример :
ЕСЛИ назвался груздем, ТО полезай в кузов.
Форма организации действий, при которой в зависимости от выполнения некоторого условия совершается одна или другая последовательность шагов, называется ветвлением.
Изобразим в виде блок-схемы последовательность действий ученика 6 класса Мухина Васи, которую он представляет себе так: "Если Павлик дома, будем решать задачи по математике. В противном случае следует позвонить Марине и вместе готовить доклад по биологии. Если же Марины нет дома, то надо сесть за сочинение."
А вот так, с помощью блок-схемы можно очень наглядно представить рассуждения при решении следующей задачи.
Из трёх монет одинакового достоинства одна фальшивая (более легкая). Как ее найти с помощью одного взвешивания на чашечных весах без гирь?
Алгоритмы с повторениями
На практике часто встречаются задачи, в которых одно или несколько действий бывает необходимо повторить несколько раз, пока соблюдается некоторое заранее установленное условие.
Алгоритм, содержащий циклы , называется циклическим алгоритмом или алгоритмом с повторениями.
Ситуация, при которой выполнение цикла никогда не заканчивается, называется зацикливанием. Следует разрабатывать алгоритмы, не допускающие таких ситуаций.
Рассмотрим пример из математики.
Натуральное число называют простым, если оно имеет только два делителя: единицу и само это число1.
2, 3, 5, 7 - простые числа; 4, 6, 8 - нет. В III веке до нашей эры греческий математик Эратосфен предложил следующий алгоритм для нахождения всех простых чисел, меньших заданного числа n:
1) выписать все натуральные числа от 1 до n;
2) вычеркнуть 1;
3) подчеркнуть наименьшее из неотмеченных чисел;
4) вычеркнуть все числа, кратные подчеркнутому на предыдущем шаге;
5) если в списке имеются неотмеченные числа, то перейти к шагу 3, в противном случае все подчеркнутые числа - простые.
Это циклический алгоритм. При его выполнении повторение шагов 3-5 происходит, пока в исходном списке остаются неотмеченные числа.
Вот так выглядит блок-схема действий школьника, которому перед вечерней прогулкой следует выполнить домашнее задание по математике:
Напомним, что число 1 не относят ни к составным (имеющим более двух делителей), ни к простым числам.
Самое главное
В зависимости от порядка выполнения команд можно выделить три типа алгоритмов:
> линейные алгоритмы;
> алгоритмы с ветвлениями;
> алгоритмы с повторениями.
Алгоритм, в котором команды выполняются в порядке их записи, то есть последовательно друг за другом, называется линейным.
Форма организации действий, при которой в зависимости от выполнения некоторого условия совершается одна или другая последовательность шагов, называется ветвлением.
Форма организации действий, при которой выполнение одной и той же последовательности команд повторяется, пока выполняется некоторое заранее установленное условие, называется циклом (повторением).
Вопросы и задания
1. Какие алгоритмы называют линейными?
2. Приведите пример линейного алгоритма,
3. Исполнитель «Вычислитель» умеет выполнять только две команды: умножать на 2 и прибавлять Придумайте для него наиболее короткий план получения из О числа 50.
4. Какая форма организации действий называется ветвлением?
5. Какие условия должна была выполнить героиня скази «Гуси-лебеди»?
6. Приведите пример алгоритма, содержащего ветвление»
7. Прочитайте отрывок из стихотворения Дж. Родари «Чем пахнут ремесла?»:
У каждого дела запах особый:
В булочной пахнет тестом и сдобой.
Мимо столярной идешь мастерской -
Стружкою пахнет и свежей доской.
Пахнет маляр скипидаром и краской.
Пахнет стекольщик оконной замазкой.
Куртка шофера пахнет бензином,
Блуза рабочего - маслом машинным.
Перефразируйте
о профессиях с помощью слов «ЕСЛИ... ТО»/
8. Вспомните, герои каких русских народных сказок совершают выбор, определяющий их судьбу.
9. Из 9 монет одинакового достоинства одна фальшивая (более легкая). За сколько взвешиваний на чашечных весах без гирь вы можете ее определить?
10. Какая форма организации действий называется повторением?
11. Приведите пример алгоритма, содержащего повторение.
12. В каких известных вам литературных произведениях имеет место циклическая форма организации действий?
13. Где окажется исполнитель, выполнивший 16 раз подряд следующую группу команд?
пройти 10 метров вперед
повернуть на 90° по часовой стрелке
14. Какую группу действий и сколько раз следует повторить при решении следующей задачи?
Сорок солдат подошли к реке, по которой на лодке катаются двое мальчиков. Как солдатам переправиться на другой берег, если лодка вмещает только одного солдата либо двух мальчиков, а солдата и мальчика уже не вмещает?
15. Вспомните задачу о Вычислителе, умеющем только умножать на 2 и прибавлять 1. Разрабатывать для него рациональные алгоритмы будет значительно проще, если воспользоваться следующей блок-схемой:
Используя эту блок-схему, разработайте рациональные алгоритмы получения из числа 0 чисел 1024 и 500.
Босова Л. Л. Информатика: Учебник для 6 класса / Л. Л. Босова. - 3-е изд., испр. и доп. - М.: БИНОМ. Лаборатория знаний, 2005. - 208 с.: ил.
Содержание урока конспект урока и опорный каркас презентация урока интерактивные технологии акселеративные методы обучения Практика тесты, тестирование онлайн задачи и упражнения домашние задания практикумы и тренинги вопросы для дискуссий в классе Иллюстрации видео- и аудиоматериалы фотографии, картинки графики, таблицы, схемы комиксы, притчи, поговорки, кроссворды, анекдоты, приколы, цитаты Дополнения рефераты шпаргалки фишки для любознательных статьи (МАН) литература основная и дополнительная словарь терминов Совершенствование учебников и уроков исправление ошибок в учебнике замена устаревших знаний новыми Только для учителей календарные планы учебные программы методические рекомендацииНа практике наиболее распространены следующие формы представления алгоритмов:
· словесная (записи на естественном языке);
· графическая (изображения из графических символов);
· псевдокоды (полуформализованные описания алгоритмов на условном алгоритмическом языке, включающие в себя как элементы языка программирования, так и фразы естественного языка, общепринятые математические обозначения и др.);
· программная (тексты на языках программирования).
Словесный способ записи алгоритмов представляет собой описание последовательных этапов обработки данных. Алгоритм задается в произвольном изложении на естественном языке. Например. Записать алгоритм нахождения наибольшего общего делителя (НОД) двух натуральных чисел.
Алгоритм может быть следующим:
· задать два числа;
· если числа равны, то взять любое из них в качестве ответа и остановиться, в
противном случае продолжить выполнение алгоритма;
· определить большее из чисел;
· заменить большее из чисел разностью большего и меньшего из чисел;
· повторить алгоритм с шага 2.
Описанный алгоритм применим к любым натуральным числам и должен приводить к решению поставленной задачи.
Словесный способ не имеет широкого распространения по следующим причинам:
· такие описания строго не формализуемы;
· страдают многословностью записей;
· допускают неоднозначность толкования отдельных предписаний.
Графический способ представления алгоритмов является более компактным и наглядным по сравнению со словесным.
Такое графическое представление называется схемой алгоритма или блок-схемой.
При графическом представлении алгоритм изображается в виде последовательности связанных между собой функциональных блоков, каждый из которых соответствует выполнению одного или нескольких действий.
В блок-схеме каждому типу действий (вводу исходных данных, вычислению значений выражений, проверке условий, управлению повторением действий, окончанию обработки и т.п.) соответствует геометрическая фигура, представленная в виде блочного символа. Блочные символы соединяются линиями переходов, определяющими очередность выполнения действий.
1)Блок начало-конец
Элемент отображает выход во внешнюю среду и вход из внешней среды (наиболее частое применение − начало и конец программы). Внутри фигуры записывается соответствующее действие.
2) Блок действия
Выполнение одной или нескольких операций, обработка данных любого вида (изменение значения данных, формы представления, расположения). Внутри фигуры записывают непосредственно сами операции, например, операцию присваивания: a = 10*b + c
3) Логический блок
Отображает решение или функцию переключательного типа с одним входом и двумя или более альтернативными выходами, из которых только один может быть выбран после вычисления условий, определенных внутри этого элемента. Вход в элемент обозначается линией, входящей обычно в верхнюю вершину элемента. Если выходов два или три, то обычно каждый выход обозначается линией, выходящей из оставшихся вершин (боковых и нижней). Если выходов больше трех, то их следует показывать одной линией, выходящей из вершины (чаще нижней) элемента, которая затем разветвляется. Соответствующие результаты вычислений могут записываться рядом с линиями, отображающими эти пути. Примеры решения: в общем случае − сравнение (три выхода: >, <, =); в программировании − условные операторы if (два выхода: true, false) и case (множество выходов).
Преобразование данных в форму, пригодную для обработки (ввод) или отображения результатов обработки (вывод). Данный символ не определяет носителя данных (для указания типа носителя данных используются специфические символы).
Типы алгоритмов
Разветвляющийся алгоритм - алгоритм, содержащий хотя бы одно условие, в результате проверки которого может осуществляться разделение на несколько параллельных ветвей алгоритма.
Линейный алгоритм - набор команд (указаний), выполняемых последовательно во времени друг за другом.
Циклический алгоритм - алгоритм, предусматривающий многократное повторение одного и того же действия (одних и тех же операций) над новыми исходными данными. К циклическим алгоритмам сводится большинство методов вычислений, перебора вариантов. Цикл программы - последовательность команд (серия, тело цикла), которая может выполняться многократно (для новых исходных данных) до удовлетворения некоторого условия.
| Цель урока: | повышение интереса к изучению предмета; воспитание навыка быстрого мышления; развитие творческой активности учащихся; развитие познавательных интересов. |
| Задачи урока: | 1. Образовательные: - Закрепить с учащимися понятия алгоритма, исполнителя, системы команд исполнителя, способы представления алгоритмов. - Познакомить учащихся с типами алгоритмов: линейным, разветвляющимся, циклическим. - Научить представлению алгоритмов в виде блок-схем. 2. Развивающие: - Активизировать познавательную активность учащихся через мультимедийные средства обучения. - Развивать образное, критическое, дивергентное мышление. 3. Воспитательные: - Повышение мотивации учащихся на уроке. - Достижение сознательного уровня усвоения материала учащимися. - Формирование чувства коллективизма и здорового соперничества. - Формирование алгоритмического мышления. |
| Требования к знаниям и умениям: | - Знать типы алгоритмов. - Знать понятия: линейный, разветвляющийся, циклический алгоритмы. - Уметь применять полученные знания при выполнении практических заданий. |
| Тип урока: | комбинированный. |
| Технология: | формирование коммуникативной компетенции. |
| Методы: | - частично-поисковый, практический; - информационный (словесный); - наглядно-иллюстративный. |
| Оборудование: | Флипчарт по теме (приложение 1), компьютеры, ресурс Технологическая карта ученика (приложение 2), разноуровневые карточки (приложение 3), локальная сеть NetOp. |
Ход урока
I.Организационный момент.
1. Приветствие ребят. Здравствуйте, ребята! Садитесь! Какое у вас настроение? Если хорошее - улыбнитесь всем! Если нет - посмотрите друг на друга и улыбнитесь! Начнем урок! Я представила вам алгоритм в словесной форме. Посмотрите на доску. Этот же алгоритм изображен графически. Сегодня на уроке мы научимся с вами представлять типы алгоритмов с помощью блок - схем (страница флипчарта 1).
Эпиграфом к нашему уроку будут слова знаменитого французского ученого Гюстава Гийома “Дорогу осилит идущий, а информатику мыслящий”.
2. Объявление целей урока.
II. Актуализация знаний учащихся
Но прежде чем приступим к изучению нового материала. Мы должны вспомнить, что изучали на прошлом уроке.
1. Проверка домашнего задания.
Проверить кроссворды, решенные учениками дома.
Ответы:
1. 1. графический
2. конечность
3. информация
4. исполнитель
5. алгоритм
6. программный
7. план
8. компьютер
9. инструмент
10. рисунок
11. шаг
Вариант 1. «Посадка саженца».
Вариант 2. Эпизод из сказки «Гуси-лебеди».
6. Домашнее задание.
1. Выучить конспект.
2. Нарисовать на А4 формате пример циклического алгоритма и блок - схему к сказке «Колобок».
7. Вопросы.
1. Какие типы алгоритмов различают?
2. Какие типы алгоритмов изображены на рисунках.
Приложение № 3
Разноуровневые карточки1. Выполните задание № 1,2,3 по ресурсу
Заполнить таблицу двумя примерами на каждый тип алгоритма.
Составьте алгоритм в программе Paint, используя команды перемещения и копирования.
Вариант 1.(страница флипчарта 25).
«Посадка саженца».
Вариант 2.(страница флипчарта 26).
Эпизод из сказки «Гуси-лебеди».
Для записи алгоритмов, наряду с естественным или математическим языком, удобно использовать язык блок-схем. Блок-схемой называется графическое изображение алгоритма, в котором каждый этап процесса обработки данных изображён в виде геометрической фигуры установленного вида, называемой символом. Символы соединяются линиями, указывающими направление потоков информации. Внутри каждого символа помещается описание соответствующего этапа обработки данных. Если описание громоздко, оно записывается отдельно в виде комментария. Основные символы приведены в таблице.
| ПРОЦЕСС - выполнение операции или группы операций, в результате которых изменяются параметры входящей информации | |
| УСЛОВИЕ - обозначает выбор направления работы алгоритма в зависимости от выполнения записанных внутри условий | |
| ПРЕДОПРЕДЕЛЁННЫЙ ПРОЦЕСС - обозначает использование ранее созданных и отдельно описанных алгоритмов и программ | |
| ВВОД - ВЫВОД ДАННЫХ - обозначает преобразование данных в форму, пригодную для обработки или регистрации | |
| ДИСПЛЕЙ - обозначает ввод-вывод данных для устройства, позволяющего вносить изменения в процесс их обработки | |
| ДОКУМЕНТ - обозначает ввод-вывод данных с использованием бумажного носителя | |
| СОЕДИНИТЕЛЬ - показывает связь между прерванными линиями потока информации | |
| ПУСК - ОСТАНОВ обозначает начало, конец или прерывание процесса обработки данных |
Символы соединяются линиями связи. В месте слияния символов ставится точка. Символы могут иметь номера для удобства показа соединений в местах разрыва схемы. Эти номера не определяют порядок выполнения алгоритма, зависящий только от соединяющих потоки линий.
Все алгоритмы по своей структуре делятся на три группы:
Линейные;
Разветвляющиеся;
Циклические.
Линейным называется алгоритм, не содержащий условий. Этот алгоритм безусловно определяет процесс преобразования данных. Примером такого алгоритма является поэтапное вычисление математической формулы. Каждая элементарная операция выполняется в установленном правилами вычислений порядке без анализа полученного ранее результата. Блок-схема линейного алгоритма представляет собой последовательную цепочку символов «процесс» , имеющих вид прямоугольника, дополненную символами «ввод-вывод» и «начало-конец».
Рис. 8. Блок-схема линейного алгоритма
Разветвляющийся алгоритм содержит, по крайней мере, одно условие. Для реализации разветвляющегося алгоритма используется типовая структура РАЗВЕТВЛЕНИЕ. Основой разветвляющегося алгоритма является логический элемент условия, изображаемый на схеме символом РОМБ. В логическом элементе производится проверка условия, которая даёт результат ДА или НЕТ. В зависимости от этого поток информации направляется по одному из двух выходных каналов логического элемента.
В таком алгоритме может быть два варианта:
1. Если условие выполняется, то информационный поток направляется в блок вычислительного процесса, для которого проводилась проверка условия; если условие не выполняется - информационный поток направляется к следующим элементам блок-схемы. Таким образом, логическая схема может быть записана как ЕСЛИ (условие) - ТО (формула).
2. Имеется ДВЕ ФОРМУЛЫ вычислений, и алгоритм работает по следующему логическому принципу: ЕСЛИ (условие) - ТО (формула 1), ИНАЧЕ (формула 2).
Если нужно проверить несколько условий, то алгоритм принимает форму «дерева» с разветвлениями в виде «веток». Количество логических элементов всегда на единицу меньше количества условий, т.к. каждый элемент имеет один вход и два выхода. Участок алгоритма до разветвления называется стволом , условие - точкой разветвления , альтернативные направления процесса вычисления после точки разветвления - ветвями.
Рис.9. Блок-схемы разветвляющихся алгоритмов
Циклическим называется такой алгоритм, часть действий в котором повторяется неоднократно. Такие повторяющиеся действия и носят название «цикл». Циклические алгоритмы содержат условия работы цикла, поэтому их можно считать разновидностью разветвляющихся алгоритмов, у которой одной из ветвей является часть ствола, которая неоднократно повторяется. Эти повторяющиеся действия и составляют цикл.
Циклические алгоритмы делятся на два вида:
С известным числом повторений (циклов)
Итерационные алгоритмы, в которых число циклов заранее неизвестно и окончание работы цикла определяется каким-либо условием (преимущественно заданной точностью вычислений).
Рассмотрим оба вида алгоритмов.
В рамках структурного программирования задачи, имеющие алгоритмическое решение, могут быть описаны с использованием следующих алгоритмических структур:
- Следование . Предполагает последовательное выполнение команд сверху вниз. Если алгоритм состоит только из структур следования, то он является линейным.
- Ветвление . Выполнение программы идет по одной из двух, нескольких или множества ветвей. Выбор ветви зависит от условия на входе ветвления и поступивших сюда данных.
- Цикл . Предполагает возможность многократного повторения определенных действий. Количество повторений зависит от условия цикла.
- Функция (подпрограмма) . Команды, отделенные от основной программы, выполняются лишь в случае их вызова из основной программы (из любого ее места). Одна и та же функция может вызываться из основной программы сколь угодно раз.
Описание различных алгоритмических структур на языке блок-схем
Ветвление if
Это самый простой тип ветвления. Если результат вычисления выражения-условия возвращает true (правда), то выполнение алгоритма идет по ветке «Да», в которую включены дополнительные выражения-действия. Если условие возвращает false (ложь), то выполнение алгоритма идет по ветке «нет», т.е продолжает выполняться основная ветка программы.
Ветвление if-else
Если выражение-условие возвращает true (правда), то выполнение алгоритма идет по ветке «Да», если условие не выполняется (false), то выполнение идет по ветке «Нет». При любом результате выражения-условия нельзя вернуться в основную ветку программы, минуя дополнительные действия.
Ветвление if-elif-else
Количество условий может быть различно. Если выполняется первое, то после выполнения действий, программа переходит к основной ветке, не проверяя дальнейшие условия. Если первое условие возвращает ложь, то проверяется второе условие. Если второе условие возвращает правду, то выполняются действия, включенные в вторую ветку конструкции. Последнее условие проверяется лишь в том случае, если ни одно до него не дало в результате true. Данную алгоритмическую конструкцию (if – elif – else) не следует путать с алгоритмической конструкцией «Выбор».
Цикл while
Пока условие выполняется (результат логического выражения дает true), будут выполняться действия тела цикла. После очередного выполнения вложенных действий условие снова проверяется. Для того чтобы выполнение алгоритма не зациклилось, в теле цикла (помимо прочих действий) должно быть выражение, в результате выполнения которого будет изменяться переменная, используемая в условии. Тело цикла может ни разу не выполнится, если условие с самого начала давало false.
Цикл do
В этом цикле первый раз условие проверяется лишь после выполнения действий тела цикла. Если условие возвращает true, то выражения-действия повторяются снова. Каким бы ни было условие, тело данного цикла хотя бы раз, но выполнится.
Цикл for
Данный цикл также называют циклом «Для» (for). В его заголовке указывается три параметра: начальное значение переменной (от), конечно значение (до) и ее изменение с помощью арифметической операции на каждом «обороте» цикла (шаг).
