В алгоритмах команды записываются друг за другом в определённом порядке.
Линейные алгоритмы
Алгоритм, в котором команды выполняются в порядке их записи, то есть последовательно друг за другом, называется линейным .
Например, линейным является следующий алгоритм посадки дерева (рис. 58):
- выкопать в земле ямку;
- опустить в ямку саженец;
- засыпать ямку с саженцем землёй;
- полить саженец водой.
Рис. 58
С помощью блок-схемы данный алгоритм можно изобразить так (рис. 59).
Рис. 59
Алгоритмы с ветвлениями
В жизни часто приходится принимать решение в зависимости от сложившейся обстановки. Если идёт дождь, мы берём зонт и надеваем плащ; если жарко, надеваем лёгкую одежду. Встречаются и более сложные условия выбора. В некоторых случаях от выбранного решения зависит дальнейшая судьба человека.
Логику принятия решения можно описать так:
ЕСЛИ ТО ИНАЧЕ
Пример:
ЕСЛИ хочешь быть здоров, ТО закаляйся, ИНАЧЕ валяйся весь день на диване.
В некоторых случаях могут отсутствовать: ЕСЛИ ТО
Пример:
ЕСЛИ назвался груздем, ТО полезай в кузов.
Форма организации действий, при которой в зависимости от выполнения или невыполнения некоторого условия совершается либо одна, либо другая последовательность действий, называется ветвлением .
Изобразим в виде блок-схемы последовательность действий ученика 6 класса Мухина Васи, которую он представляет себе так: «Если Павлик дома, будем решать задачи по математике. В противном случае следует позвонить Марине и вместе готовить доклад по биологии. Если же Марины нет дома, то надо сесть за сочинение» (рис. 60).
Рис. 60
А вот так, с помощью блок-схемы можно очень наглядно представить рассуждения при решении следующей задачи (рис. 61).
Рис. 61
Из трёх монет одинакового достоинства одна фальшивая (более лёгкая). Как её найти с помощью одного взвешивания на чашечных весах без гирь?
Алгоритмы с повторениями
На практике часто встречаются задачи, в которых одно или несколько действий бывает необходимо повторить несколько раз, пока соблюдается некоторое заранее установленное условие.
Форма организации действий, при которой выполнение одной и той же последовательности действий повторяется, пока выполняется некоторое заранее установленное условие, называется циклом (повторением). Алгоритм, содержащий циклы, называется циклическим алгоритмом или алгоритмом с повторениями .
Ситуация, при которой выполнение цикла никогда не заканчивается, называется зацикливанием . Следует разрабатывать алгоритмы, не допускающие таких ситуаций.
Рассмотрим пример из жизни. Вот так может выглядеть блок-схема действий школьника, которому перед вечерней прогулкой следует выполнить домашнее задание по математике (рис. 62).
Рис. 62
Это циклический алгоритм. При его исполнении действие «Решить задачу» будет выполнено столько раз, сколько задач содержит домашнее задание ученика.
Могут быть простыми, сложными, однако у всех из них есть общие черты. Вот по этим чертам и принято выделять три типа алгоритмов, с которыми мы и познакомимся.
В алгоритмах команды записываются друг за другом в определенном порядке. Выполняются они не обязательно в записанной последовательности. Могут существовать внутренние отсылки к различным командам.
Вообще, выполнение команд по алгоритму чем-то напоминает настольные игры, в которых участники по очереди бросают кубики и ходят по полям. Причем на полях могут быть комментарии в стиле: «Вернитесь на 2 клетки назад» или «Пройдите на 5 клеток вперед»
Более сложной моделью выполнения алгоритма является известная игра «Монополия» или «Менеджер»
Существенное отличие этой игры от простого выполнения алгоритма состоит в том, что конечной целью участников является не прохождение пути, а накопление денег при помощи определенных действий.
В зависимости от порядка выполнения команд можно выделить три типа алгоритмов:
Линейные алгоритмы;
Алгоритмы с ветвлениями;
Алгоритмы с повторениями.
«Монополия»
«Монополия» относится к одной из самых популярных настольных игр. Ее правила достаточно просты и понятны каждому, кто хоть раз в нее играл.
На момент старта игроки обладают равным количеством наличных денег. Бросая кубики и передвигая свои фишки по закольцованному игровому полю, они приобретают участки недвижимости разных цветов. Оказавшись на приобретенном противником участке, игрок обязан выплатить тому установленную арендную плату. Выкупив все участки одной цветовой группы, участник может строить на них дома и отели, которые увеличивают размеры аренды. Цель всего происходящего банальна – разорить всех соперников.
Согласно официальным источникам – компании Parker Brothers, с 1935 года и по сей день выпускающей «Монополию», – легендарная настольная игра появилась на свет следующим образом. В 1934 году безработный инженер Чарльз Дарроу предложил вышеуказанной конторе выпустить придуманную им игру о торговле недвижимостью.
Обнаружив в настольной игре 52 дизайнерские ошибки, братья Паркеры отказали изобретателю. Тот с чисто американской предприимчивостью отправился в типографию, заказал 5 тысяч экземпляров игры и довольно быстро их распродал. Осознав, что прибыль утекает прямо у них из-под носа, Parker Brothers спешно приобрели права на «Монополию», и уже в следующем году она стала самой продаваемой настольной игрой в США, а Дарроу – живым воплощением американской мечты.
Однако вместе с тем известны и более ранние игры, поразительно напоминающие «Монополию». Выходит, Дарроу просто оказался первым, кто подсуетился и получил патент на «народную» забаву? И да, и нет. Расследования последних лет проливают свет на тайну происхождения «Монополии».
Во второй половине позапрошлого века в Соединенных Штатах жил и работал политэкономист Генри Джордж. Он предлагал заменить все поборы одним-единственным налогом – на землю. Проникшись его идеями, в январе 1904 года Мэги получает патент на настольную игру The Landlord’s Game, которая и правилами, и внешним видом напоминает нынешнюю «Монополию». Считается, что «Игра владельца земли» обладала двумя вариантами правил: сыграв партию по действующим законам налогообложения, игроки переходили к модели, предложенной Джорджем, – и якобы убеждались в ее необходимых преимуществах. Таким образом, игра была не развлечением, но инструментом идеологической борьбы.
До массового производства дело не дошло, зато The Landlord’s Game постепенно распространилась по Северной Америке в кустарных копиях. Всплеск интереса к настольной игре пришелся на годы Великой депрессии: тысячи безработных были рады вообразить себя денежными мешками хотя бы за игровым столом. Появление предприимчивого человека вроде Чарльза Дарроу стало делом нескольких месяцев – и он появился, на многие десятилетия присвоив славу единоличного изобретателя «Монополии».
Нашлись, конечно, и те, кто счел должным урвать кусок у правообладателей. Нелицензионные «Монополии» наводнили Китай. И в нашей стране выпускались и выпускаются стройные ряды клонов – «Маклер», «Кооператив», «Менеджер»
В свете недавнего переосмысления роли Дэрроу в создании «Монополии» и истечения действия авторских прав засудить такие компании не получится. Даже если предположить, что никакой Элизабет Мэги на свете не было, правила «Монополии» давно перешли в общественное достояние. Впрочем, часть патента Hasbro все еще держит при себе: дизайн фишек, графическое оформление, последовательность клеток на игровом поле.
Линейные алгоритмы
Алгоритм, в котором команды выполняются в порядке их записи, то есть последовательно друг за другом, называется линейным.
Например, линейным является следующий алгоритм замены перегоревшей лампочки:
1. выключить выключатель света;
2. выкрутить перегоревшую лампочку;
3. вкрутить новую лампочку;
4. включить выключатель, чтобы проверить, что лампочка горит.
Алгоритмы с ветвлениями
Ситуации, когда заранее известна последовательность требуемых действий, встречаются крайне редко. В жизни часто приходится принимать решение в зависимости от сложившейся обстановки. Если идет дождь, мы берем зонт и надеваем плащ; если жарко, надеваем легкую одежду. Встречаются и более сложные условия выбора. В некоторых случаях от выбранного решения зависит дальнейшая судьба человека.
Логику принятия решения можно описать так:
ЕСЛИ <условие>, ТО <действия 1>,
ИНАЧЕ <действия 2>
ЕСЛИ будут деньги, ТО купи хлеба, ИНАЧЕ не покупай.
ЕСЛИ будешь сегодня в центре, ТО набери меня, ИНАЧЕ не набирай.
ЕСЛИ уроки выучены, ТО иди гулять, ИНАЧЕ учи уроки.
В некоторых случаях <действия 2> могут отсутствовать. Это может быть связано как с его очевидностью (как, например, в первом примере – понятно, что если у тебя нет денег, то хлеба ты купить просто не сможешь), так и с отсутствием необходимости в нем.
ЕСЛИ <условие>, ТО <действия 1>
ЕСЛИ назвался груздем, ТО полезай в кузов.
ЕСЛИ хочешь быть здоров, ТО закаляйся.
Форма организации действий, при которой в зависимости от выполнения или невыполнения некоторого условия совершается либо одна, либо другая последовательность действий, называется ветвлением.
Изобразим в виде блок-схемы последовательность действий ученика 6 класса, забывшего ключи от квартиры, которую он представляет себе так: «Если мама дома, то я приду и сяду делать домашнее задание. Если мамы дома нет, то я пойду поиграть с друзьями в футбол, пока не придет мама. Если друзей на улице не будет, то покатаюсь на качелях до тех пор, пока не придет мама».
Необходимые и достаточные условия
Мы уже обсуждали с вами, что существуют необходимые и достаточные условия.
Примером необходимого условия может служить такое:
Чтобы стать врачом, необходимо получить медицинское образование.
Условие наличия медицинского образования является необходимым для работы врачом, однако не является достаточным. Действительно, не все выпускники медицинских вузов становятся врачами.
Примером достаточного условия может стать такое:
Для того чтобы стало прохладнее, достаточно включить кондиционер.
Это условие является достаточным: если включить кондиционер, то действительно станет прохладнее. Однако это условие не является необходимым, ведь для достижения той де цели можно включить вентилятор, открыть окно и т. п.
Конечно же, существуют необходимые и достаточные условия одновременно (такие условия называются равносильными). Например:
Для того чтобы наступило лето, необходимо и достаточно, чтобы закончилась весна.
Действительно, если весна закончилась, то наступает лето, а если весна не закончилась, то лето наступить не может. То есть условия окончания весны и начала лета являются равносильными.
Понятия необходимого, достаточного и равносильного условий очень важны в таком разделе математики, как математическая логика. К тому же, они очень часто встречаются при доказательстве различных теорем.
Алгоритмы с повторениями
На практике часто встречаются задачи, в которых одно или несколько действий бывает необходимо повторить несколько раз, пока соблюдается некоторое заранее установленное условие.
Например, если вам необходимо перебрать ящик с яблоками, чтобы отделить гнилые от спелых, то нам необходимо повторять следующие действия:
1. Взять яблоко.
2. Посмотреть, не гнилое ли оно.
3. Если гнилое – выбросить, если нет – переложить в другой ящик.
Выполнять этот набор действий необходимо до тех пор, пока не закончатся яблоки в ящике.
Форма организации действий, при которой выполнение одной и той же последовательности действий повторяется, пока выполняется некоторое заранее установленное условие, называется циклом (повторением).
Ситуация, при которой выполнение цикла никогда не заканчивается, называется зацикливанием.
Следует разрабатывать алгоритмы, не допускающие таких ситуаций.
Рассмотрим алгоритм работы будильника на телефоне, который должен зазвонить в 8:00 утра, а затем звонить через каждые 10 минут, до тех пор пока его не выключат.
В этом случае его блок-схема выглядит так: (блок-схему (рис. 9.) см. в конце конспекта)
На этом уроке мы обсудили три типа алгоритмов – линейные алгоритмы, алгоритмы с ветвлениями и алгоритмы с повторениями.
На следующем уроке мы на практике обсудим составление алгоритмов.
Решето Эратосфена
Вспомним определение простого натурального числа.
Натуральное число называют простым, если оно имеет только два делителя: единицу и само это число. Остальные числа называются составными. При этом число 1 не является ни простым, ни составным.
Примеры простых чисел: 2, 3, 5, 7.
Примеры составных чисел: 4, 6, 8.
В III веке до нашей эры греческий математик Эратосфен предложил следующий алгоритм для нахождения всех простых чисел, меньших заданного числа п:
1. выписать все натуральные числа от 1 до n;
2. вычеркнуть 1;
3. подчеркнуть наименьшее из неотмеченных чисел;
4. вычеркнуть все числа, кратные подчеркнутому на предыдущем шаге числу;
5. если в списке имеются неотмеченные числа, то перейти к шагу 3, в противном случае все подчеркнутые числа – простые.
Это циклический алгоритм. При его выполнении повторение шагов 3–5 происходит, пока в исходном списке остаются неотмеченные числа.
Рассмотрим результат этого алгоритма. Выпишем все простые числа от 1 до 25.
Выпишем числа от 1 до 25.
Вычеркнем 1. Теперь подчеркнем двойку. Вычеркнем все четные числа.
Так как не все числа отмечены, то подчеркиваем 3. Теперь вычеркиваем все числа, которые делятся на 3.
Так как не все числа отмечены, то подчеркиваем 5. Теперь вычеркиваем число 25.
Так как не все числа отмечены, то подчеркиваем 7.
Вычеркнуть ничего нельзя, но не все числа отмечены, поэтому подчеркиваем 11.
Вычеркнуть ничего нельзя, но не все числа отмечены, поэтому подчеркиваем 13. Снова нельзя ничего вычеркнуть – подчеркиваем 17, затем 19 и 23.
Теперь все числа отмечены.
Получаем простые числа: 2, 3, 5, 7, 11, 13, 17, 19, 23.
Литература
1. Босова Л.Л. Информатика и ИКТ: Учебник для 6 класса. – М.: БИНОМ. Лаборатория знаний, 2012.
2. Босова Л.Л. Информатика: Рабочая тетрадь для 6 класса. – М.: БИНОМ. Лаборатория знаний, 2010.
3. Босова Л.Л., Босова А.Ю. Уроки информатики в 5-6 классах: Методическое пособие. – М.: БИНОМ. Лаборатория знаний, 2010.
В алгоритмические структуры цикл входит серия команд, выполняемая многократно. Такая последовательность команд называется телом цикла.
Циклические алгоритмические структуры бывают двух типов:
Циклы со счетчиком, в которых тело цикла выполняется определенное количество раз;
Циклы с условием, в которых тело цикла выполняется до тех пор, пока выполняется условие.
Алгоритмическая структура цикл может быть зафиксирована различными способами:
Графически, с помощью блок-схемы;
На языке программирования, например на языках 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. Вспомогательный алгоритм (алгоритм, который можно использовать в других алгоритмах, указав только его имя).
На практике наиболее распространены следующие формы представления алгоритмов :
· В устной форме.
· В письменной форме на естественном языке.
· В письменной форме на формальном языке.
· Для более наглядного представления алгоритма широко используется графическая форма – блок-схема , которая составляется из стандартных графических объектов.
Урок информатики 7 класс
Дата проведения 12.11.2015г.
Цель урока : научить составлять алгоритм ы с повторение; использовать циклы в алгоритмах для решения задач , создать условия для формирования первичного представления о цикле в алгоритме и команды "повторить";
развивать логическое и алгоритмическое мышление учащихся; развивать навыки работы в программной среде;
воспитывать любознательность и углубленный интерес к изучению информатики.
Тип урока: урок изучения и первичных закреплений новых знаний
Используемое оборудование: пк учителя, пк ученика, мультимедийный проектор
Используемые учебники и учебные пособия: Інформатика: Підруч.для 7-го кл.загальноосвіт.навч.закл. / Й.Я.Рівкинд [та ін.].- К.: Генеза, 2015.
Программное обеспечение: Scratch
Опорные слова: алгоритм; команда повтори N раз, тело цикла
Тема урока: Алгоритмы с повторением. Составление и исполнение алгоритмов
с повторением в программной среде
План урока : 1. Организационный момент
2. Проверка домашнего задания
3. Актуализация опорных знаний (фронтальный опрос)
4. Изучение нового материала
5. Работа на пк
6. Итог урока
7. Д/З
Ход урока:
1. Организационный момент:
Приветствие.
Напоминаю: на прошлом уроке мы свами начали изучать тему: Алгоритмы с повторением и ветвлением , ознакомились с базовыми структурами алгоритма, его свойствами и формами представления. Сегодня мы с вами изучим алгоритм с повторением, научимся составлять такие алгоритмы и применять на практике - исполнять алгоритмы с повторением в программной среде Scratch .
2. Проверка домашнего задания:
1. Что называют алгоритмом?
Что такое команда алгоритма?
Кто или что может выступать в роли исполнителя алгоритма?
2. Назовите базовые структуры алгоритма?
[линейный, алгоритм с повторением, алгоритм с ветвлением ]
В какой форме может быть представлен алгоритм?
[словестной, в виде текста, графически: блок-схема]
Какие алгоритмы называют линейными?
3. Какие можно выделить свойства алгоритма?
[массовость, результативность, эффективность, конечность алгоритма]
Приведите примеры линейных алгоритмов из повседневной жизни.
3. Актуализация опорных знаний (фронтальный опрос)
* Подумайте, какие явления в природе постоянно повторяются? [День сменяет ночь, восход и закат солнца, фазы луны, времена года сменяют друг друга и так происходит много лет]. Процессы, которые повторяются, называются - циклическими.
* Вспомните народные сказки: «Колобок»; «Репка»; «Золушка» и др. в них используется повторение одних и тех же действий. Какие действия в сказке «Золушка» повторяются несколько раз?
* Мы постоянно участвуем в циклических процессах:
Занятия в школе по конкретному предмету каждую неделю повторяются, согласно расписания;
Звонки на урок и с урока ежедневно звонят в одно, и тоже время;
Домой мы идем по одному и тому же маршруту;
На уроке украинского языка каждый раз разбирая строение слова мы выполняем один и тот же набор команд;
Когда вы решаете уравнение по алгебре, повторяете каждый раз один и тот же порядок действий……
4. Изучение нового материала
Итак, запишите сегодняшнее число и тему урока!
Рассмотрим задачу (учебник стр.66)
Дано: емкость 50л, ведро 10л, колодец. Необходимо наполнить бочку водой.
Наша задача записать алгоритм, в результате выполнение которого, поставленная задача будет решена: бочка будет наполнена водой.
(На проекторе презентация)
Запишем алгоритм решения данной задачи, представленный в виде текста:
1. Взять ведро
2. Набрать полное ведро воды в колодце
3. Вылить в бочку.
…………………………..
Поставить ведро
Давайте определим, какие команды повторяются в данном алгоритме и сколько раз
(Запишем наш алгоритм с использованием команды повтори)
1. Взять ведро
2.Повтори 5 раз
Набрать полное ведро воды в колодце
Вылить в бочку
Поставить ведро
2-3 повтори 5 раз
Мы с вами решили задачу используя, алгоритм с повторением.
Итак, Алгоритм - команды которого повторяются N раз называется алгоритмом с повторением.
Алгоритм с повторением называют еще алгоритм с циклом или циклическим алгоритмом !
Если в условии задачи определено количество повторений команд, значит, алгоритм решения задачи имеет команду цикла со счетчиком . На примере решенной задачи мы видим, как выглядит простейший алгоритм с повторением, который содержит команду цикла со счетчиком:
Запишем общий вид команды цикла со счетчиком:
Повторить N раз (заголовок цикла)
Команды (где команды образуют тело цикла)
Мы знаем, что алгоритм удобно представлять графическим способом, для этого используют блок-схему. Внимание на экран давайте вспомним, как выглядит блок- схема линейного алгоритма: см. слайд 4.
Составление алгоритма в тетради:
Составте алгоритм нахождения периметра равностороннего 7 угольника со стороной а=5. Представте данный алгоритм в виде блок- схемы.
5. Работа на пк
Инструктаж по технике безопасности.В кабинете строго запрещается:
Трогать разъемы, кабели и розетки.
Трогать монитор.
Трогать тыльную строну монитора.
Работать во влажной одежде и влажными руками.
Растояние от глаз до экрана монитора 40-60 см.
Работать за компьютером можно только при разрешении учителя.
Практическая часть:
6. Итог урока:
Итак, что такое алгоритм с повторением?
Как обозначается команда цикла со счетчиком, на что она указывает?
Что такое тело цикла?
Когда используется команды повтори в алгоритмах?
7. Д/З
§ 3.1 стр 65-71 проработать
Составить алгоритм нахождения среднего арифметического шести чисел.
Практическая часть:
(Дети рассаживаются на свои рабочие места, раздать карточки с заданиями)
1. Запускаем программную среду Скретч.
2. Поменяйте язык программной среды нажав на панели инструментов кнопку в форме земного шара (при необходимости)
3. Переместите кота в Верхний левый угол
4. Необходимо выбрать блок/перо и в область скриптов перетянуть команду/опустить перо
Задание№ 1:
Напишите программу для рисования Скретчем квадрата со стороной 60 шагов
1) Без использования команды повтори;
2) С использованием команды повтори
(Выберите блок/контроль/повторить укажите команды, которые должен повторить Скретч необходимое количество раз для рисования квадрата)
Проанализируйте, на сколько сократилась запись вашего алгоритма.
Задание №2 :
Проверь, какое получается изображение в результате выполнения следующих команд:
Повторить 120 раз перемещение на 4 шага, поворот на 3 градуса
Задание№3 : Напишите программу для создания орнамента
