Типы алгоритмов.
Линейные алгоритмы.
Алгоритм, в котором команды выполняются в порядке их записи, то есть последовательно друг за другом, называется линейным .
Например, линейным является следующий алгоритм посадки дерева (рис. 58, стр.111):
1) выкопать в земле ямку;
2) опустить в ямку саженец;
3) засыпать ямку с саженцем землёй;
4) полить саженец водой.
С помощью блок-схемы данный алгоритм можно изобразить так (рис. 59, стр.112).
Алгоритмы с ветвлениями
В жизни часто приходится принимать решение в зависимости от сложившейся обстановки. Если идёт дождь, мы берём зонт и надеваем плащ; если жарко, надеваем лёгкую одежду. Встречаются и более сложные условия выбора. В некоторых случаях от выбранного решения зависит дальнейшая судьба человека.
Логику принятия решения можно описать так:
ЕСЛИ <условие> ТО <действия 1> ИНАЧЕ <действия 2>
Пример:
ЕСЛИ хочешь быть здоров, ТО закаляйся, ИНАЧЕ валяйся весь день на диване.
В некоторых случаях <действия 2> могут отсутствовать:
ЕСЛИ <условие> ТО <действия 1>
ЕСЛИ назвался груздем, ТО полезай в кузов.
Форма организации действий, при которой в зависимости от выполнения или невыполнения некоторого условия совершается либо одна, либо другая последовательность действий, называется ветвлением .
Изобразим в виде блок-схемы последовательность действий ученика 6 класса Мухина Васи, которую он представляет себе так: «Если Павлик дома, будем решать задачи по математике. В противном случае следует позвонить Марине и вместе готовить доклад по биологии. Если же Марины нет дома, то надо сесть за сочинение» (рис. 60, стр.113).
А вот так, с помощью блок-схемы можно очень наглядно представить рассуждения при решении следующей задачи (рис. 61, стр.114).
Из трёх монет одинакового достоинства одна фальшивая (более лёгкая). Как её найти с помощью одного взвешивания на чашечных весах без гирь?
Алгоритмы с повторениями
На практике часто встречаются задачи, в которых одно или несколько действий бывает необходимо повторить несколько раз, пока соблюдается некоторое заранее установленное условие.
Форма организации действий, при которой выполнение одной и той же последовательности действий повторяется, пока выполняется некоторое заранее установленное условие, называется циклом (повторением). Алгоритм, содержащий циклы, называется циклическим алгоритмом или алгоритмом с повторениями.
Ситуация, при которой выполнение цикла никогда не заканчивается, называется зацикливанием . Следует разрабатывать алгоритмы, не допускающие таких ситуаций.
Рассмотрим пример из жизни. Вот так может выглядеть блок-схема действий школьника, которому перед вечерней прогулкой следует выполнить домашнее задание по математике (рис. 62, стр. 115).
Это циклический алгоритм. При его исполнении действие «Решить задачу» будет выполнено столько раз, сколько задач содержит домашнее задание ученика.
Src="http://present5.com/presentacii-2/20171208%5C17864-7_klas_urok_8.ppt%5C17864-7_klas_urok_8_1.jpg" alt=">Урок 8 Алгоритмы с повторением Алгоритмы с повторением">
Src="http://present5.com/presentacii-2/20171208%5C17864-7_klas_urok_8.ppt%5C17864-7_klas_urok_8_2.jpg" alt=">Вопросы: Какие явления природы, события в вашей жизни неоднократно повторяются? Вспомните правило, которое предусматривает"> Вопросы: Какие явления природы, события в вашей жизни неоднократно повторяются? Вспомните правило, которое предусматривает последовательность действий, которые должны повториться несколько раз. Что такое алгоритм? Назовите несколько известных вам алгоритмов.
Src="http://present5.com/presentacii-2/20171208%5C17864-7_klas_urok_8.ppt%5C17864-7_klas_urok_8_3.jpg" alt=">Циклические процессы: В природе можно наблюдать процессы, которые многократно повторяются. Так, например, каждый день"> Циклические процессы: В природе можно наблюдать процессы, которые многократно повторяются. Так, например, каждый день Солнце восходит над горизонтом и заходит за горизонт.
Src="http://present5.com/presentacii-2/20171208%5C17864-7_klas_urok_8.ppt%5C17864-7_klas_urok_8_4.jpg" alt=">Циклические процессы: Каждый месяц можно увидеть на небосклоне одно и то же изменение фаз"> Циклические процессы: Каждый месяц можно увидеть на небосклоне одно и то же изменение фаз Луны.
Src="http://present5.com/presentacii-2/20171208%5C17864-7_klas_urok_8.ppt%5C17864-7_klas_urok_8_5.jpg" alt=">Циклические процессы: Ежегодно Солнце проходит через одни и те же созвездия - созвездие Зодиака.">
Src="http://present5.com/presentacii-2/20171208%5C17864-7_klas_urok_8.ppt%5C17864-7_klas_urok_8_6.jpg" alt=">Циклические процессы: Процессы, которые повторяются, називаются циклическими.">
Src="http://present5.com/presentacii-2/20171208%5C17864-7_klas_urok_8.ppt%5C17864-7_klas_urok_8_7.jpg" alt=">Циклические процессы: Каждый из вас участвует в циклических процессах. Так, в школе в течение"> Циклические процессы: Каждый из вас участвует в циклических процессах. Так, в школе в течение одного семестра еженедельно в одни и те же дни проходят одни и те же уроки согласно расписанию. Каждый рабочий день в школе уроки и перерыва продолжаются в течение одних и тех же интервалов времени.
Src="http://present5.com/presentacii-2/20171208%5C17864-7_klas_urok_8.ppt%5C17864-7_klas_urok_8_8.jpg" alt=">Циклические процессы: Каждый раз, когда вам нужно вскипятить воду в чайнике, вы выполняете одну"> Циклические процессы: Каждый раз, когда вам нужно вскипятить воду в чайнике, вы выполняете одну и ту же последовательность действий. Чаще всего вы идете или идете из дома в спортивную секцию или музыкальную школу одним и тем же маршрутом.
Src="http://present5.com/presentacii-2/20171208%5C17864-7_klas_urok_8.ppt%5C17864-7_klas_urok_8_9.jpg" alt=">Циклические процессы: На уроках математики при подъеме, например, числа 2 до пятой степени нужно"> Циклические процессы: На уроках математики при подъеме, например, числа 2 до пятой степени нужно найти произведение чисел 2 и 2, а затем еще 3 раза умножить предыдущий произведение на число 2. На уроках украинского языка, разбирая различные предложения по строению, вы также каждый раз выполняете одну и ту же последовательность действий.
Src="http://present5.com/presentacii-2/20171208%5C17864-7_klas_urok_8.ppt%5C17864-7_klas_urok_8_10.jpg" alt=">Повторение(цикл) в алгоритмах В алгоритмах решения многих задач нужно выполнить одну или несколько команд"> Повторение(цикл) в алгоритмах В алгоритмах решения многих задач нужно выполнить одну или несколько команд более одного раза. Для этого такие алгоритмы должны содержать команды, которые будут определять, какие команды должны исполниться неоднократно и сколько именно раз.
Src="http://present5.com/presentacii-2/20171208%5C17864-7_klas_urok_8.ppt%5C17864-7_klas_urok_8_11.jpg" alt=">Повторение(цикл) в алгоритмах Рассмотрим такую задачу. Задача. Во дворе есть пустая бочка и ведро"> Повторение(цикл) в алгоритмах Рассмотрим такую задачу. Задача. Во дворе есть пустая бочка и ведро емкостью 50 л и 10 л соответственно и колодец. Нужно наполнить бочку водой.
Src="http://present5.com/presentacii-2/20171208%5C17864-7_klas_urok_8.ppt%5C17864-7_klas_urok_8_12.jpg" alt=">Повторение(цикл) в алгоритмах Очевидно, для решения этой задачи нужно выполнить такой алгоритм: Взять ведро."> Повторение(цикл) в алгоритмах Очевидно, для решения этой задачи нужно выполнить такой алгоритм: Взять ведро. Повторить б раз Подойти к колодцу. Набрать полное ведро воды. Подойти с полным ведром воды к бочке. Вылеть воду из ведра в бочку. Поставить ведро.
Src="http://present5.com/presentacii-2/20171208%5C17864-7_klas_urok_8.ppt%5C17864-7_klas_urok_8_13.jpg" alt=">Повторение(цикл) в алгоритмах Какая команда называется командой цикла со счетчиком. Тело циклу Заглавие цикла">
Src="http://present5.com/presentacii-2/20171208%5C17864-7_klas_urok_8.ppt%5C17864-7_klas_urok_8_14.jpg" alt=">Повторение(цикл) в алгоритмах Фрагмент алгоритма, в котором одна или несколько команд могут выполняться более"> Повторение(цикл) в алгоритмах Фрагмент алгоритма, в котором одна или несколько команд могут выполняться более одного раза, называется циклом. Алгоритм, который содержит цикл, называется алгоритмом с циклом, или алгоритмом с повторением.
Src="http://present5.com/presentacii-2/20171208%5C17864-7_klas_urok_8.ppt%5C17864-7_klas_urok_8_15.jpg" alt=">Повторение в Scratch В среде Scratch можно составлять алгоритмы с циклами. Для этого в"> Повторение в Scratch В среде Scratch можно составлять алгоритмы с циклами. Для этого в системе команд исполнителей есть специальные команды. В частности, для организации в алгоритме цикла со счетчиком можно использовать команду которая размещена в группе Управление. Ее выбор приводит к выполнению указанное количество раз команд, которые содержатся внутри этого блока. Понятно, что количество повторений команд тела цикла можно менять.
Src="http://present5.com/presentacii-2/20171208%5C17864-7_klas_urok_8.ppt%5C17864-7_klas_urok_8_16.jpg" alt=">Повторение в Scratch Например, выполнив приведенный алгоритм, содержащий цикл. Рыжий кот нарисует орнамент.">
Src="http://present5.com/presentacii-2/20171208%5C17864-7_klas_urok_8.ppt%5C17864-7_klas_urok_8_17.jpg" alt=">Повторення в Scratch Тело цикла предложенного алгоритма содержит команды рисования квадрата и поворота исполнителя"> Повторення в Scratch Тело цикла предложенного алгоритма содержит команды рисования квадрата и поворота исполнителя на угол 600 повторяться это тело цикла 6 раз. Поэтому полученный орнамент состоит из шести квадратов, каждый следующий из которых возвращено относительно предыдущего на угол 600. Обращаем ваше внимание, что в теле цикла алгоритма рисования орнамента две команды повторяются 4 раза подряд.
Src="http://present5.com/presentacii-2/20171208%5C17864-7_klas_urok_8.ppt%5C17864-7_klas_urok_8_18.jpg" alt=">Повторення в Scratch Тому цей алгоритм можна записати коротше, використовуючи в тілі, циклу ще"> Повторення в Scratch Тому цей алгоритм можна записати коротше, використовуючи в тілі, циклу ще одну команду циклу. Цикл Повторити 6 називається зовнішнім, а цикл Повторити 4 - внутрішній, або вкладеним. Кожне наступне виконання зовнішнього циклу буде відбуватися лише після того, як завершиться чергове виконання внутрішнього.
Src="http://present5.com/presentacii-2/20171208%5C17864-7_klas_urok_8.ppt%5C17864-7_klas_urok_8_19.jpg" alt=">Повторение в Scratch Если изменить количество повторений тела цикла, например на 20, то и"> Повторение в Scratch Если изменить количество повторений тела цикла, например на 20, то и угол в команде внешнего цикла нужно изменить на 180. В этом случае Рыжий кот нарисует другой орнамент.
Src="http://present5.com/presentacii-2/20171208%5C17864-7_klas_urok_8.ppt%5C17864-7_klas_urok_8_20.jpg" alt=">Повторення в Scratch Команду цикла со счетчиком можно использовать для циклического изменен цвета рисования."> Повторення в Scratch Команду цикла со счетчиком можно использовать для циклического изменен цвета рисования. В Scratch каждому цвету карандаша соответствует определенное число, код этого цвета. В алгоритме, перед командой цикла размещено команду, задающей исходный цвет карандаша. Во время выполнения команды тела приведенного цикла каждый раз код цвета карандаша увеличивается на 30.
Src="http://present5.com/presentacii-2/20171208%5C17864-7_klas_urok_8.ppt%5C17864-7_klas_urok_8_21.jpg" alt=">Повторення в Scratch">
Src="http://present5.com/presentacii-2/20171208%5C17864-7_klas_urok_8.ppt%5C17864-7_klas_urok_8_22.jpg" alt=">Повторение в Scratch Приведем еще пример алгоритма с циклом, выполнив который, Рыжий кот нарисует"> Повторение в Scratch Приведем еще пример алгоритма с циклом, выполнив который, Рыжий кот нарисует круг.
Src="http://present5.com/presentacii-2/20171208%5C17864-7_klas_urok_8.ppt%5C17864-7_klas_urok_8_23.jpg" alt=">Домашнее задание § 3.1, ст. 65-72">
Src="http://present5.com/presentacii-2/20171208%5C17864-7_klas_urok_8.ppt%5C17864-7_klas_urok_8_24.jpg" alt=">Физкультминутка www.teach-inf.at.ua">
Src="http://present5.com/presentacii-2/20171208%5C17864-7_klas_urok_8.ppt%5C17864-7_klas_urok_8_25.jpg" alt=">Работаем за компьютером Виконати ст. 70-71">
В алгоритмические структуры цикл входит серия команд, выполняемая многократно. Такая последовательность команд называется телом цикла.
Циклические алгоритмические структуры бывают двух типов:
Циклы со счетчиком, в которых тело цикла выполняется определенное количество раз;
Циклы с условием, в которых тело цикла выполняется до тех пор, пока выполняется условие.
Алгоритмическая структура цикл может быть зафиксирована различными способами:
Графически, с помощью блок-схемы;
На языке программирования, например на языках Visual Basic и VBA, с использованием специальных инструкций, реализующих циклы различного типа.
Цикл со счетчиком. Когда заранее известно, какое число повторений тела цикла необходимо выполнить, можно воспользоваться циклической инструкцией (оператором цикла со счетчиком) For. . . Next (рис. 19).
Синтаксис оператора For. . . Next следующий: строка, начинающаяся с ключевого слова For, является заголовком цикла, а строка с ключевым словом
Next - концом цикла; между ними располагаются операторы, представляющие собой тело цикла.
В начале выполнения цикла значение переменной Счетчик устанавливается равным НачЗнач. При каждом «проходе» цикла переменная Счетчик увеличивается на величину шага. Если она достигает величины КонЗнач, то цикл завершается и выполняются следующие за ним операторы.
Циклы с условием. Часто бывает так, что необходимо повторить тело цикла, но заранее неизвестно, какое количество раз это надо сделать. В таких случаях количество повторений зависит от некоторого условия. Этот цикл реализуется с помощью инструкции Do... Loop.
Условие выхода из цикла можно поставить в начале, перед телом цикла (рис. 20) или в конце, после тела цикла (рис. 21).
Проверка условия выхода из цикла проводится с помощью ключевых слов While или Until. Эти слова
Придают одному и тому же условию противоположный смысл. Ключевое слово While обеспечивает выполнение цикла до тех пор, пока выполняется условие, т. е. пока условие имеет значение истина. В этом случае условие является условием продолжения цикла. Как только условие примет значение ложь, выполнение цикла закончится.
Ключевое слово Until обеспечивает выполнение цикла до тех пор, пока не выполняется условие, т. е. пока условие имеет значение ложь. В этом случае условие становится условием завершения цикла. Как только условие примет значение истина, выполнение цикла закончится.
11Понятие алгоритма. Исполнитель алгоритма. Система команд исполнителя (на примере учебного исполнителя). Свойства алгоритма. Способы записи алгоритмов; блок-схемы.
Появление алгоритмов связывают с зарождением математики. Более 1000 лет назад (в 825 году) ученый из города Хорезма Абдулла (или Абу Джафар) Мухаммед бен Муса аль-Хорезми создал книгу по математике, в которой описал способы выполнения арифметических действий над многозначными числами. Само слово алгоритм возникло в Европе после перевода на латынь книги этого математика.
Алгоритм – описание последовательности действий (план), строгое исполнение которых приводит к решению поставленной задачи за конечное число шагов.
Вы постоянно сталкиваетесь с этим понятием в различных сферах деятельности человека (кулинарные книги, инструкции по использованию различных приборов, правила решения математических задач...). Обычно мы выполняем привычные действия не задумываясь, механически. Например, вы хорошо знаете, как открывать ключом дверь. Однако, чтобы научить этому малыша, придется четко разъяснить и сами эти действия и порядок их выполнения:
1. Достать ключ из кармана.2. Вставить ключ в замочную скважину.3. Повернуть ключ два раза против часовой стрелки.4. Вынуть ключ.
Виды алгоритмов:
1. Линейный алгоритм (описание действий, которые выполняются однократно в заданном порядке);
2. Циклический алгоритм (описание действий, которые должны повторятся указанное число раз или пока не выполнено заданное условие);
3. Разветвляющийся алгоритм (алгоритм, в котором в зависимости от условия выполняется либо одна, либо другая последовательность действий);
4. Вспомогательный алгоритм (алгоритм, который можно использовать в других алгоритмах, указав только его имя).
На практике наиболее распространены следующие формы представления алгоритмов :
· В устной форме.
· В письменной форме на естественном языке.
· В письменной форме на формальном языке.
· Для более наглядного представления алгоритма широко используется графическая форма – блок-схема , которая составляется из стандартных графических объектов.
План-конспект урока в 8 классе
Тема: Составление и реализация алгоритмов с ветвлением и повторением.
Цели обучения:
Закрепление материала предыдущих уроков;
Формирование навыков составления алгоритмов с ветвлением и повторением;
Развитие логического и алгоритмического мышления;
Тип урока: урок закрепления знаний, навыков и умений.
Учащиеся должны знать: операторы ветвления и повторения.
Учащиеся должны уметь: реализовывать и составлять программы с использованием операторов ветвления и повторения.
Программное и методическое обеспечение урока: система программирования Pascal ABC, учебное пособие «Информатика. 8 класс», §4.
1. Актуализация знаний и мотивация учащихся на изучение учебного материала (фронтальная форма работы). Решение задач с учащимися:
Задача 1.
var a,f,s: real;
writeln("Введите величину силы тяги (н): ");
writeln("Введите расстояние (м): ");
writeln("Совершенная работа силы тяги ",a:5:2," Дж");
Задача 2.
writeln("Введите число: ");
if k=0 then begin
writeln("Квадратный корень из числа: ",k1:5:2);
writeln("Обратное число: ",k1:9:6);
2. Составление и реализация алгоритмов (Объяснительно-иллюстративный метод обучения в сочетании с частично-поисковым методом, фронтальная и индивидуальная формы работы).
Задача 1.
var m,n,o,min: byte;
{для значения роста (в см) достаточно 1 байта памяти}
{в этом случае рост может принимать значения от 0 до 255}
writeln("Введите рост трех подружек(см)");
write("Маша: "); readln(m);
write("Наташа: "); readln(n);
write("Оля: "); readln(o);
min:= m; {самая маленькая - Маша}
if o min then min:=o; {самая маленькая - Оля}
write("Самая маленькая из подружек - ");
if min = m then writeln("Маша")
else if min = n then writeln("Наташа")
else writeln("Оля");
Задача 2.
var a,b,c: real;
writeln("Неравенство вида ax
write("a= "); readln(a);
write("b= "); readln(b);
write("x"); {начинаем вывод решения}
{при делении неравенства на отрицательное число знак неравенства меняется}
if a 0 then write(" выводим знак неравенства}
else write(" ");
writeln(c:5:2); {завершаем вывод решения}
if (a = 0) and (b 0) then writeln("Любое число является решением неравенства");
if (a = 0) and (b
Задача 3.
var i,k,b,sum,sball_c: integer; {для значения указанных переменных достаточно 1 байта памяти}
writeln("Введите количество учащихся в группе: ");
writeln("Введите отметки по информатике за четверть");
for i:= 1 to k do
writeln("Cредний балл группы за четверть: ",sball:5:2);
Задача 4.
program cykl_if_1;
var i,k,b,sum,sball_c: byte; {для значения переменных достаточно 1 байта памяти}
{в этом случае они могут принимать значения от 0 до 255}
write("Введите количество отметок: ");
for i:= 1 to k do
sum:= sum+b; {сумма отметок}
sball:= sum/k; {средний балл}
writeln("Ваш средний балл: ",sball:5:2);
sball_c:= round(sball); {округлим средний бал до целых}
writeln("Округлим: ",sball_c);
if sball_c = 8 then writeln("Молодец!");
if (sball_c = 6) and(sball_c Неплохо");
if (sball_c = 4) and (sball_c Надо подтянуться!");
4. Подведение итогов урока. Рефлексия.
Самооценка работы учащихся на уроке. Адекватность самооценки учащегося оценке учителя. Дать учащимся информацию о реальных результатах достижения целей изучаемой темы. Выставление отметок.
Рефлексия с помощью приема «Синквейн»:
существительное
прилагательное прилагательное
глагол глагол глагол
ключевая фраза
существительное
5. Информация о домашнем задании.
Повторить материалы §3,4, выполнить упражнение 5 (§4).
Дополнительные задания к уроку.
Сильным учащимся может быть дополнительно предложено задание:
Задание 5.
var a,b,x,y,NOD,NOK:integer;
write ("x="); readln (x);
write ("y="); readln (y);
if ab then a:=a-b
NOD:=a; NOK:= a*b div NOD;
writeln ("НОК=",NOK)
Фронтальная работа
Задача 1. Под действием силы тяги F (Н) автомобиль совершает путь s (м). Определить работу силы F.
Задача 2. Введите число. Если введенное число неотрицательное, то найдите квадратный корень из числа, иначе вычислите обратное число.
Задача 1. Введите рост (в сантиметрах) трех подружек Маши, Наташи и Оли. Узнайте, какая из подружек самая маленькая.
Задача 2. Напишите программу для решения линейного неравенства вида a*x b
Задача 3. Введите количество учащихся в группе по информатике и четвертную отметку каждого учащегося. Вычислите средний балл успеваемости по информатике в группе за четверть.
Задача 4. Введите количество отметок по одному из предметов за четверть и сами отметки. Выведите информацию о средней отметке с комментирующим текстом.
Задание 5. Найдите НОК двух данных чисел. НОК(a,b)=a*b/НОД(a,b).
Карточка к уроку «Составление и реализация алгоритмов с ветвлением и повторением».
Фронтальная работа
Задача 1. Под действием силы тяги F (Н) автомобиль совершает путь s (м). Определить работу силы F.
Задача 2. Введите число. Если введенное число неотрицательное, то найдите квадратный корень из числа, иначе вычислите обратное число.
Самостоятельная работа за компьютерами
Задача 1. Введите рост (в сантиметрах) трех подружек Маши, Наташи и Оли. Узнайте, какая из подружек самая маленькая.
Задача 2. Напишите программу для решения линейного неравенства вида a*x b
Задача 3. Введите количество учащихся в группе по информатике и четвертную отметку каждого учащегося. Вычислите средний балл успеваемости по информатике в группе за четверть.
Задача 4. Введите количество отметок по одному из предметов за четверть и сами отметки. Выведите информацию о средней отметке с комментирующим текстом.
Задание 5. Найдите НОК двух данных чисел. НОК(a,b)=a*b/НОД(a,b).
Карточка к уроку «Составление и реализация алгоритмов с ветвлением и повторением».
Фронтальная работа
Задача 1. Под действием силы тяги F (Н) автомобиль совершает путь s (м). Определить работу силы F.
Задача 2. Введите число. Если введенное число неотрицательное, то найдите квадратный корень из числа, иначе вычислите обратное число.
Самостоятельная работа за компьютерами
Задача 1. Введите рост (в сантиметрах) трех подружек Маши, Наташи и Оли. Узнайте, какая из подружек самая маленькая.
Задача 2. Напишите программу для решения линейного неравенства вида a*x b
Задача 3. Введите количество учащихся в группе по информатике и четвертную отметку каждого учащегося. Вычислите средний балл успеваемости по информатике в группе за четверть.
Задача 4. Введите количество отметок по одному из предметов за четверть и сами отметки. Выведите информацию о средней отметке с комментирующим текстом.
Задание 5. Найдите НОК двух данных чисел. НОК(a,b)=a*b/НОД(a,b).
существительное
прилагательное прилагательное
глагол глагол глагол
ключевая фраза
