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">
Центр организации и проведения Международных и Всероссийских дистанционных конкурсов официального сайта "ГОРДОСТЬ РОССИИ!" (2015-2016)
ЗАЯВКА НА УЧАСТИЕ В ЭКСПРЕСС-КОНКУРСЕ
ДЛЯ ПЕДАГОГОВ
Должность: учитель начальных классов
Сокращённое название ОУ: МБОУ СОШ № 5
Местонахождения ОУ: г. Пыть-Ях
E-mail: 17727718@mail .ru
Номинация: Мой лучший урок
Название работы: урок «Алгоритм с повторением»
Формат конкурса (Международный, Всероссийский): Всероссийский конкурс
Количество дипломов: 1
Данные об оплате (подробно): онлайн
Просмотр содержимого документа
«Конспект урока»
учитель МБОУ «СОШ № 5 г.Пыть-Ях
Тюменской обл.
Конспект урока математики по теме «Алгоритмы с повторением (циклом)». Программа 2100
Цель:
Закрепить представление об алгоритме, схеме алгоритма, видах алгоритмов
Познакомить с алгоритмом с повторением (циклом)
Закрепить умения составлять и выполнять линейные и нелинейные алгоритмы, записывать и читать схемы алгоритмов, используя условные знаки.
Задачи:
1. Предметные: познакомить с новым видом алгоритмов, понимать запись алгоритмов, составлять линейные и нелинейные алгоритмы (с ветвлениями и циклами)
а) познавательные УУД:
Развитие внимания, мышления, зрительной памяти учащихся;
Извлекать знания из различных источников(текста, рисунков, схем, условных обозначений);
Умение ориентироваться в своей системе знаний: отличать новое от уже известного;
б) коммуникативные УУД:
Учить детей контролировать свою речь (строить связной ответ) при выражении своей точки зрения по заданной тематике;
Развивать умение высказывать свои мысли и доказывать свою точку зрения;
Взаимодействовать друг с другом (слушать сравнивать и оценивать ответы других)
в) регулятивные УУД:
Составлять план решения учебной задачи;
- планировать последовательность шагов алгоритма для достижения цели;
3. Личностные:
Формирование умения рефлексивной самооценки, умения анализировать свои действия, управлять ими
Прививать учащимся умения общения и сотрудничества, опираясь на этические нормы, уважать мнение других.
Оборудование:
учебник «Математика» (авт. Т.Е. Демидова, С.А. Козлова, А.П. Тонких), мультимедийная презентация, проектор, раздаточный материал.
1.Орг. момент.
Комментированная запись числа и вида работы. Слайд
2. Актуализация знаний
А начнём мы наш урок с разгадывания кроссворда. Слайд
Что такое алгоритм?
(Алгори́тм - последовательность, порядок действий исполнителя для достижения результата)
Из чего состоит алгоритм?
(из шагов, которые называют командами)
Назовите формы записи алгоритмов.
(словесные, блок-схемы) Слайд
Что используется для записи блок схем? (геометрические фигуры) Слайд
Наш урок – урок-путешествие. А вот куда мы отправимся – вы узнаете, выполнив действия по заданному алгоритму.
Используя данную программу действий, найди значения Х и запиши их в таблицу. Расположи ответы в порядке убывания и расшифруй слово.
| ||||||||||||||||||||||||||
В обычный день, в урочный час
Я в сказки приглашаю вас!
А сопровождать в сказках нас будут алгоритмы.
Какого вида алгоритм использовался в этом задании?
В сказках, как и в жизни, тоже встречаются алгоритмы.
И чтобы открыть эти ворота в сказку нам нужно создать алгоритм открывания дверей.
Составьте алгоритм открывания двери ключом.
(на листах в паре) на фоне музыки
Какого вида алгоритм использовался в этом задании? (линейный)
Ну а так как у нас урок математики выполним математические алгоритмы.
3. Создание проблемной ситуации.
А вот и волшебный яблоневый сад, в котором нужно собрать яблоки.
Нам нужно составить алгоритм наших действий. Слайд
Мы положили в корзину одно яблоко, но ведь на нем больше одного яблока. Как продолжить наш алгоритм?
Наши действия повторились. Как же назвать такой алгоритм?
(алгоритм с повторением)
Есть ли такие в математике?
Дайте определение алгоритма с повторением.
4. Применение нового знания
Продолжая наш урок, научимся применять новые знания
б) Работа в группах
Алгоритм 1. Оформите в виде алгоритма работу Золушки из сказки «Золушка»
После свадьбы мачеха сразу показала свой злой нрав. Она прекрасно понимала, что рядом с красивой добросердечной падчерицей её родные дочки выглядят ещё некрасивее и уродливее. Поэтому она возненавидела падчерицу и заставляла её делать всю самую трудную и грязную работу по дому.
Так она заставляла Золушку разбирать всю собранную фасоль в две разные корзины: белую – в овальную, а красную - в круглую.
И Падчерица не могла лечь спать, пока не выполнит всю работу.
Алгоритм 2. Оформите в виде алгоритма выбор принцем невесты из сказки «Золушка».
На следующий день принц объявил, что женится на той девушке, которой хрустальная туфелька окажется впору. Принцессы, герцогини и придворные дамы – все пришли во дворец. Принц встречал каждую девушку, примерял им туфельку. Но когда видел, что туфелька не подходила – прощался с ними. Примеряли туфельку и золушкины сёстры, но безуспешно. Тогда Золушка спросила:
Можно мне попробовать тоже?
Её сёстры рассмеялись. Но принц сказал:
Я буду примерять туфельку всем девушкам без исключения.
Туфелька свободно надевалась на золушкину ножку, как будто была сделана по ней. Тут же Золушка достала из кармана вторую туфельку, и все застыли в изумлении.
Проверка групповой работы. Защита алгоритма Слайды
5. Домашнее задание.
В гостях у сказок хорошо, а дома лучше.
Откройте дневники, запишем домашнее задание. С. 85 № 5, 6.
На листе формата А4 запишите составьте словесный и соответствующий алгоритм (укажите его тип) выполнения какой-либо работы и оформите свою работу (проявив творческие способности).
6. Рефлексия. Итог урока. Слайд
«Сказка ложь, да в ней намёк – добрым молодцам урок!» А какой урок нам сегодня преподали сказки?
Что нового мы узнали на уроке? (ответ)
– Чему научились?
Сегодня мы составляли алгоритмы к сюжетам сказок. А случаются ли в жизни ситуации, когда мы действуем по алгоритму? Приведите примеры
– Кому пока было трудновато?
– Кто или что вам помогло справиться?
– Кто доволен сегодня своей работой?
– Кто хотел бы что исправить? Что? Что для этого нужно сделать?
– Какую бы отметку вы себе поставили?
Я не сомневалась, что все вы знаете и любите сказки, каждый из вас получит оценку за практическую работу, и хотелось бы отметить наиболее активных участников урока (выставляются оценки).
Просмотр содержимого презентации
«презентация к уроку»
Презентация к уроку «В гостях у сказки с алгоритмами»
Цель урока:
- закрепить представление об алгоритме, схеме алгоритма, видах алгоритмов
- познакомить с алгоритмом с повторением (циклом)
- закрепить умения составлять и выполнять линейные и нелинейные алгоритмы, записывать и читать схемы алгоритмов, используя условные знаки.
Задачи урока:
1. Предметные: познакомить с новым видом алгоритмов, понимать запись алгоритмов, составлять линейные и нелинейные алгоритмы (с ветвлениями и циклами)
а) познавательные УУД:
-развитие внимания, мышления, зрительной памяти учащихся;
- извлекать знания из различных источников(текста, рисунков, схем, условных обозначений);
- умение ориентироваться в своей системе знаний: отличать новое от уже известного; у
б) коммуникативные УУД:
Учить детей контролировать свою речь (строить связной ответ) при выражении своей точки зрения по заданной тематике;
- развивать умение высказывать свои мысли и доказывать свою точку зрения;
- взаимодействовать друг с другом (слушать сравнивать и оценивать ответы других)
в) регулятивные УУД:
-составлять план решения учебной задачи;
- планировать последовательность шагов алгоритма для достижения цели;
3. Личностные:
- формирование умения рефлексивной самооценки, умения анализировать свои действия, управлять ими
- прививать учащимся умения общения и сотрудничества, опираясь на этические нормы, уважать мнение других.
Классная работа.
АЛГОРИТМ
Алгори́тм - последовательность, порядок действий исполнителя для достижения результата
- словесная,
- блок-схема
Название фигуры
Изображение
Обозначаемый шаг алгоритма
Овал
Ромб
Прямоугольник
Начало и конец
Принятие решения
Выполнение действия
18 +24 -15 х" width="640"
Используя данную программу действий,
найди значения Х и запиши их в таблицу.
Расположи ответы в порядке
убывания и расшифруй слово.
З К С А К А
начало
Достать ключ
Вставить ключ в замочную скважину
Повернуть ключ 2 раза
Вынуть ключ
конец
В гостях у сказки
с алгоритмами
Собери урожай
Войди в сад
Подойди к яблоне
Сорви яблоко
Положи яблоко в корзину
Собери урожай
Войди в сад
Подойди к яблоне
Сорви яблоко
Положи яблоко в корзину
Остались яблоки на яблоне?
Остались яблони с яблоками?
Начало
Встретить девушку
Примерить ей туфельку
Распрощаться с девушкой
Подошла?
Золушка найдена!
Конец
Собрать крупу
Перебрать крупу
Наносить воды
Почистить котёл
Помыть пол
Сказка - ложь, да в ней намёк
добрым молодцам - урок!
Определение 1.4. Под алгоритмизацией понимают процесс разработки алгоритма решения какой-либо задачи.
Для некоторых задач этот процесс достаточно прост, для других - требует определенных усилий, особенно в тех случаях, когда алгоритм должен удовлетворять наперед заданным условиям, например максимальному быстродействию решения задачи, минимальному требованию к объему памяти ЭВМ и др. В настоящем параграфе на примерах многих задач от простейших до относительно сложных изложены способы рационального составления алгоритмов. Задачи представлены в математической или почти в математической форме. При этом они подобраны так, что их решение не требует тех знаний, которые выходят за пределы курса математики общеобразовательных средних школ.
Опыт обучения программированию показывает, что студенты весьма часто пренебрегают составлением блок-схем алгоритмов. Желание быстрее написать программу порождает ощущение, что рисование блок-схемы как бы лишняя работа. Такой подход однако ошибочен и должен подавляться в самом начале обучения.
Составление блок-схемы до начала программирования очень часто позволяет обнаружить ошибки в решении задачи, тем самым уточнить алгоритм и в значительной степени избавиться от трудоемкого поиска ошибок при отладке программы. Практический опыт программирования свидетельствует о том, что большая доля времени, отведенного на составление программы, затрачивается программистами на обнаружение логических ошибок, а квалифицированными программистами считаются те из них, которые быстрее всего устраняют эти ошибки. В этой связи роль составления блок-схем алгоритмов чрезвычайно важна.
Кроме того, блок-схемы нужны для предоставления отчетности по разработкам, а также для ознакомления с ними заинтересованных лиц. Поэтому в дальнейшем для большинства рассматриваемых задач будут приведены либо блок-схемы алгоритмов, либо дана текстовая их форма, либо представлено и то и другое.
Теперь непосредственно перейдем к рассмотрению задач и конструированию алгоритмов их решения.
Задача 1.1. Даны два действительных числа а и Ь. Необходимо найти их сумму 5, разность Я, произведение Р и частное Н от деления а на Ь.
Алгоритм кажется очевидным: ввести в память ЭВМ числа а и Ь, выполнить вычисления 5 = а + Ь, Я = а - Ь, Р= а : Ь, Н = а/Ь и вывести на экран (принтер) полученные результаты. Однако такой алгоритм ошибочен для случая, когда Ь = 0. В этом случае чисто математически мы могли бы записать, что Н- а/Ь = со. Однако в компьютере операция деления на нуль не определена, вследствие чего на экране дисплея будет выведено сообщение «деление на нуль» и вычисление программы прервано. Поэтому проверка, равно ли Ь нулю, в алгоритме должна быть предусмотрена. Правильный алгоритм приведен на рис. 1.3. Ниже дана текстовая его форма.
Шаг 1. Ввести а , Ь.
Шаг 2. Вычислить Б = а + Ь, Я = а - Ь, Р= аЬ.
Шаг 3. Вывести Я, Р.
Шаг 4. Если Ь = 0, перейти к шагу 7.
Шаг 5. Вычислить Н = а/Ь .
Шаг 6. Вывести Н и перейти к шагу 8.
Шаг 7. Вывести Ь = 0, Н - СО.
Шаг 8. Остановиться.
Задача 1.2. Даны два действительных положительных числа а и Ь. Найти среднее арифметическое и среднее геометрическое этих чисел.
Как известно, среднее арифметическое чисел а, Ь определяется как?= {а + Ь)/ 2, а среднее геометрическое как С =у[аЬ. Поэтому блок-схема алгоритма представлена на рис. 1.4. Текстовая его форма будет такой.
Шаг 1. Ввести а, Ь.
Шаг 2. Вычислить?= (а + Ь)/ 2, С = 4аЬ.
Рис. 1.3.
числами а, Ь
Рис. 1.4.
Шаг 3. Вывести (7. Шаг 4. Остановиться.
В приведенном алгоритме записана операция среднего геометрического (7 = 4аЬ. Казалось бы, следовало вначале вычислить значение с=аЬ, а затем, используя, например, алгоритм Ньютона (см. рис. 1.1), вычислить (7. Однако в наборе стандартных программ компьютера имеется программа, вычисляющая квадратный корень из положительного числа. Поэтому при соответствующем обращении к этой программе она и вычислит (7.
Задача 1.3. Даны два действительных числа а и Ь. Определить, какое из чисел большее или они равны. Алгоритм решения задачи изображен на рис. 1.5.
Текстовая его форма такая.
Шаг 1. Ввести а , Ъ.
Шаг 2. Если а = Ь, перейти к шагу 6.
Шаг 3. Если а > Ь, перейти к шагу 5.
Шаг 4. Вывести Ъ> а и перейти к шагу 7. Шаг 5. Вывести а> Ь и перейти к шагу 7. Шаг 6. Вывести а = Ь.
Шаг 7. Остановиться.
Задача 1.4.
Вычислить значение функции 1 -х, если*
+ х 3 . если 2
- 1/х 2 , если 1
1 + х + х 2 , еслих > 3.
Алгоритм вычисления ? представлен на рис. 1.6. Текстовая его форма следующая.
Шаг 1. Ввести х
Шаг 2. Если х 1, перейти к шагу 8.
Шаг 3. Если х перейти к шагу 7.
Шаг 4. Если л:
Шаг 5. Вычислить ?= 1 +Х + * 2 и перейти к шагу 9.
Шаг 6. Вычислить ? = V1 + х 3 и перейти к шагу 9.
Шаг 7. Вычислить ?= 1/х 2 и перейти к шагу 9.
Шаг 8. Вычислить ?- 1 - х.
Шаг 9. Вывести х, ?.
Шаг 10. Остановиться.
Задача 1.5. Составить алгоритм вычисления корней квадратного уравнения ах 2 + Ьх + с = а, Ь, с ф 0, когда а ф 0, Ь ф0, с ф0.
Как известно, в зависимости от знака дискриминанта с1 = Ь 2 - 4 ас квадратное уравнение ах 2 + Ьх + с = Ос действительными коэффициентами а, Ь, сф 0 может иметь три типа корней: разные действительные корни, если с1> 0, равные действительные корни, если с!= 0, и комплексные сопряженные корни, если с! 0. Разные действительные корни вычисляются по формулам
Вывести х, У
~ь + 4 г,
х, =-, х 2 = -. Равные корни определяются так: х, =
2 а " 2 а
= х 2 = -. Комплексные сопряженные корни вычисляются так 2 а
- - мнимая часть
же, как и действительные, только представляются двойкой чисел -Ь . л!4
- ± /--, где знак / указывает на то, что 2а 2а
значения корня. В связи с изложенным в алгоритме вычисления корней на первом этапе должно быть предусмотрено вычисление значения дискриминанта и дальнейшая проверка его знака. Алгоритм с максимальной экономией вычислительных операций приведен на рис. 1.7. Ниже дана его текстовая форма.
Шаг 1. Ввести а , Ь , с.
Шаг 2. Вычислить с1 = Ь 2 - 4ас, к = а + а, к = -Ь/к.
Шаг 3. Если 0, перейти к шагу 7.
Шаг 4. Если 0, перейти к шагу 6.
Шаг 5. Положить х, = к и перейти к шагу 10.
Шаг 6. Вычислить g = 4(4, г = g/h, х х = к + г, х 2 = к - г и перейти к шагу 9.
Шаг 7. Вычислить g = у{4, г = g/h.
Шаг 8. Вывести: «Корни комплексные х, = /:+/>, х 2 = /:-/>» и перейти к шагу 11.
Шаг 9. Вывести: «Корни действительные» х, х 2 и перейти к шагу 11.
Шаг 10. Вывести: «Корни, равные х, = х 2 » х,.
Шаг 11. Остановиться.
Большинство приведенных алгоритмов содержат так называемые разветвления, т. е. места в блок-схемах, где вычисления направляются по разным путям. Эти места определяются блоками сравнения величин. Из каждого блока имеется два выхода, один из которых соответствует тому случаю, когда условие сравнения выполняется («да»), другой - случаю, когда оно не выполняется («нет»). Такие алгоритмы называются алгоритмами с разветвляющейся структурой.
Теперь рассмотрим алгоритмы, которые содержат фрагменты повторения вычислений - циклы. В зависимости от того, известно ли наперед число повторений некоторого участка алгоритма или нет, различают циклы арифметические и итерационные.
В арифметических циклах число повторений вычислений контролируется с помощью управляющей переменной, играющей роль счетчика циклов. При каждом очередном вычислении значение счетчика изменяется на заданную величину и сравнивается с установленным количеством повторений. Если эти величины совпадают, повторения прекращаются, т. е. осуществляется выход из цикла по счетчику. В противном случае повторения вычислений продолжаются. Если перед началом цикла значение счетчика превышает заданное число повторений, он не выполняется вообще. Возможен также принудительный выход из цикла по некоторому наперед заданному условию.
В циклах итерационного типа, в которых число повторений наперед неизвестно, их прекращение (выход из цикла) осуществляется при выполнении некоторого условия. Обычно это условие формулируется, например, так: выполнять повторения до тех пор, пока х где с - постоянная величина (константа), ах-увеличивается с каждым повторением (итерацией). В том случае, когда условие проверяется до начала повторений, циклы относят к группе циклов с предусловием, когда же эта проверка осуществляется после каждой очередной итерации, они классифицируются как циклы с постусловием. Для первой группы циклов, если х >с, повторения вычислений не будет вообще, для второй всегда выполнится хотя бы один цикл. Все арифметические циклы - это циклы с предусловием.
Задача 1.6. Дан ряд чисел х 15 х 2 ,..., х,-, ..., х п. Найти их сумму 5.
Так как сумма 5 = х, + х 2 + ... + х,- + ... + х п и суммирование чисел выполняется последовательно, т. е. к найденной сумме 5 М добавляется х,- число, то вычисление 5, = 5 М + х,- повторяется п - 1 раз, если положить 5 М =х х. Поэтому алгоритм вычисления суммы будет таким, как изображен на рис. 1.8. Текстовая его форма включает следующие действия.
Шаг 1. Ввести х, ..., х п, п.
Шаг 2. Положить 5=х,.
Шаг 3. Положить / = 2.
Шаг 4. Если /> п, перейти к шагу 7.
Шаг 5. Положить 5=5+ х,-.
Шаг 6. Положить / = / + 1 и вернуться к шагу 4.
Шаг 7. Вывести 5.
Шаг 8. Остановиться.
Рис. 1.8. Алгоритм вычисления суммы п чисел
В этом алгоритме роль счетчика циклов отводится переменной /, которая изменяется с шагом 1. Если бы требовалось вычисление суммы чисел х } , ..., х п через одно число, то очевидно, что шаг изменения переменной / должен быть взят равным 2, а начальное ее значение 3. Таким образом, в четвертом блоке схемы алгоритма следовало бы указать /= 3, а в седьмом / = /" + 2.
Задача 1.7. Составить алгоритм вычисления функции п («л-факториал»). Как известно, п - это произведение п натуральных чисел 1 2 3 ... п. При этом принимают, что 1! = 1. Поэтому вычисление значения п можно рассматривать как последовательное повторение операции умножения предшествующего значения факториала Т 7 на очередное натуральное число. Алгоритм вычисления п приведен на рис. 1.9.
Его текстовая форма такая.
Шаг 1. Ввести п.
Шаг 2. Положить Р= 1.
Шаг 3. Вычислить /= 2.
Шаг 4. Если / > п, перейти к шагу 7.
Шаг 5. Положить Г- Я.
Шаг 6. Положить /= /+ 1 и вернуться к шагу 4.
Шаг 7. Вывести Т 7 .
Шаг 8. Остановиться.
Аналогичным образом можно построить алгоритмы вычисления значений 2", а п, где а - вещественное, а п - целые числа.
Задача 1.8. Составить алгоритм вычисления выражения к = = ^2 + ^2~+ ^2 + ... + л/2 . Нетрудно видеть, что если в качестве
п корней
начального значения взять к = а/2 , то повторяющимся действием будет вычисление выражения V2 + к. Поэтому алгоритм решения этой задачи имеет вид, изображенный на рис. 1.10. Его текстовая форма такая.
Шаг 1. Ввести п.
Шаг 2. Вычислить к = а/2.
Шаг 3. Положить /= 2.
Шаг 4. Если /> п, перейти к шагу 7.
Шаг 5. Вычислить к = л/2 + к.
Шаг 6. Положить /"=/"+ 1 и вернуться к шагу 4. Шаг 7. Вывести к.
Шаг 8. Остановиться.
Задача 1.9. Составить алгоритм вычисления выражения S = = sin л: + sin 2 * ... + sin"*.
Если взять начальное значение суммы S = s"mx, то повторяющимся действием будет 5 + 5sin*. Алгоритм, вычисляющий указанную сумму, представен на рис. 1.11. Его текстовая форма такая.
Шаг 1. Ввести п, х.
Шаг 2. Вычислить 5 = sin*.
Шаг 3. Положить / = 2.
Шаг 4. Если /> п, перейти к шагу 7.
Шаг 5. Вычислить S =S + ^sinx.
Шаг 6. Положить / = / + 1 и вернуться к шагу 4. Шаг 7. Вывести S.
Шаг 8. Остановиться.
Задача 1.10. Составить алгоритм вычисления среднего квадратического п действительных чисел х у, х 2 , ..., х п.
Известно, что средним квадратическим п действительных
чисел является величина 5* = Л -(х? + х + ... + х 2 п. Поэтому ал-
горитм будет таким (рис. 1.12). Его текстовая форма включает следующие действия.
Шаг 1. Ввести Ху, ..., х„, п.
Шаг 2. Положить / = 1.
Шаг 3. Если /> п, перейти к шагу 7.
Шаг 4. Положить ^ = 0.
Шаг 5. Вычислить +х,-х г
Шаг 6. Положить /=/-+- 1 и вернуться к шагу 3.
Шаг 7. Вычислить =8 к /п.
Шаг 8. Вычислить =д/^7.
Шаг 9. Вывести Шаг 10. Остановиться.
Задача 1.11. Составить алгоритм вычисления числа сочетаний п чисел по т для п > т > 0.
Число сочетаний из п по т, обозначаемое С" ! , вычисляется
по известной формуле С"" =
. Казалось бы построение
(п - т)т
алгоритма не вызывает проблем: вычислить значения п,
- (п - т) , т, используя для этого алгоритм (см. рис. 1.9), а затем реализовать формулу для определения С”". Такой подход в общем требует выполнения п - 1 + (п - т - 1) + т - 1 = 2/7-3 циклов. Имеется возможность сконструировать алгоритм вычисления значения С;, который будет выполнять всего т циклов. Тогда, в худшем случае, когда т всего лишь на единицу меньше п, число циклов будет примерно в 2 раза меньше 2/7. Этот алгоритм основан на использовании рекуррентного сотношения для вычисления С"".
/ X 1 , . . . , X/; , И
Рис. 1.12.
п действительных чисел
С, и т. д.
Для построения алгоритма запишем общее выражение для вычисления С" ! , которое будем вычислять в цикле. Согласно рекуррентному соотношению при т = 0 число сочетаний С^ 1 = С 1 =
При т = і число со-
= п. При т = 1 число сочетаний С 2 п
и І +1 ^ I
четании С, =-
пи -1 У1 - 171 ^ щ і
Оно записывается так: С =
С"”, С п = п и позволяет вычислять сочетания последовательно С =п, С 2 = ---С" п,
С" п. Так как в итоге необходимо получить зна
чение С"" т то / должно изменяться от 1 до т - 1. Блок-схема алгоритма приведена на рис. 1.13. Его текстовая форма такая.
Шаг 1. Ввести п, т.
Шаг 2. Если п вывести «Повторить ввод, п и вернуться к шагу 1.
Шаг 3. Если п = 1, перейти к шагу 10.
Шаг 4. Если п = т, перейти к шагу 9.
Шаг 5. Положить С= п, /= 1.
Шаг 6. Если / > т - 1, перейти к шагу 11.
Шаг 7. Вычислить С =- --С.
Шаг 8. Положить /= /+ 1 и вернуться к шагу 6.
Шаг 9. Положить С= 1 и перейти к шагу 11.
Шаг 10. Положить С=п.
Шаг 11. Вывести С.
Шаг 12. Остановиться.
Заметим, что в приведенной блок-схеме предусмотрен контроль правильности ввода чисел т так, чтобы п> т.
Задача 1.12. Сконструировать алгоритм вычисления многочлена (полинома) Р п (х) степени п для некоторого действительного значения х
Используя традиционную форму представления многочлена р п (х) =а п х п + а п _ х х п ~ х + ... + а 2 х 2 + а х х + а 0 , алгоритм можно
было бы изобразить, как на рис. 1.14.
Ввести #о» 5 а п, х
|
У=УХ, Р =Р+а,у |
||
Рис. 1.14. Алгоритм вычисления полинома, представленного
в канонической форме
В этом алгоритме в цикле используются две операции умножения и одна операция сложения. Существует, однако, другой более быстрый способ вычисления значения многочлена. Он основан на использовании схемы Горнера, согласно которой полином представляется следующим образом:
Р»(х) = (...((а п х + а п _)х + а п _ 2)х + ... + а х)х + а 0 .
Например, для п = 4 он имеет такой вид:
Р„(х) =(((а п х + а ъ)х + а 2)х + а х)х + а 0 .
Алгоритм, вычисляющий полином по схеме Горнера, приведен на рис. 1.15. В цикле он выполняет всего одну операцию умножения.
Задача 1.13. Разработать алгоритм табулирования функции у = /(х) на интервале [а, Ь], а с шагом Ах.
Под табулированием функции обычно подразумевают составление таблицы значений функции в точках а, а + Ах, а + 2Ах, а + /Ах, а + пАх заданного интервала. Алгоритм решения этой задачи может быть построен как с использованием арифметического, так и итерационного циклов. Для того чтобы применить арифметический цикл, необходимо предварительно определить число точек табуляции п = --- . Затем организовать по-
вторение п раз вычисления значений функции в точках а + Ах, а + пАх и добавить к найденным ее значениям значение /(а). Алгоритм, построенный с использованием указанных замечаний, приведен на рис. 1.16.
Ввести а , Ь, Ах
Рис. 1.16. Алгоритм табулирования функции /(х ) с использованием
арифметического цикла
Его текстовая форма следующая. Шаг 1. Ввести а , Ь, Ах.
Шаг 2. Вычислить п = --- .
Шаг 3. Вычислить у = /(а ), положить х= а.
Шаг 4. Вывести а , у.
Шаг 5. Положить /= 1.
Шаг 6. Если /> я, перейти к шагу 10.
Шаг 7. Положить х = х + Ах, вычислить у = Дх).
Шаг 8. Вывести х, у.
Шаг 9. Положить /= /"+ 1 и вернуться к шагу 6.
Шаг 10. Остановиться.
Алгоритм решения задачи с применением итерационного цикла приведен на рис. 1.17.
В этом алгоритме шаги 7, 8 проверяют, совпадает ли последняя точка табуляции функции со значением конца интервала Ь.
Задача 1.14. Составить алгоритм поиска наибольшего общего делителя (НОД) двух целых чисел a, b и наименьшего общего кратного (НОК) этих чисел.
Как известно, НОД чисел a, b - такое наибольшее целое число, которое делит эти числа без остатка. Наименьшим общим кратным целых чисел а , b является целое число, которое делится на а и Ь. Если известен НОД, то НОК вычисляется по следующей формуле: НОК (а , b) = ab/Oj(a, b). Поэтому прежде чем вычислять НОК, необходимо найти НОД.
Существует несколько алгоритмов вычисления НОД. Приведем простейший из них, который принадлежит древнегреческому математику Евклиду. Он заметил, что НОД (а , b ) равен НОД ((а - b), Ь), где а > Ь. Поэтому суть его алгоритма сводится к последовательному вычитанию из большего числа меньшего до тех пор, пока эти числа станут равными между собой. Алгоритм приведен на рис. 1.18 и содержит цикл итерационного типа.
Текстовая форма алгоритма вычисления НОД, НОК следующая.
Шаг 1. Ввести а, Ь.
Шаг 2. Положить и = a, v = b.
Шаг 3. Если а = Ь, перейти к шагу 7.
Шаг 4. Если а> Ь, перейти к шагу 6.
Рис. 1.17.
итерационного цикла
Рис. 1.18. Алгоритм вычисления наибольшего общего делителя чисел а, Ь и наименьшего их кратного
Шаг 5. Положить х = а, а = Ь, Ь = х.
Шаг 6. Положить х = а - Ь, а = х и вернуться к шагу 3.
Шаг 7. Положить НОД = а.
Шаг 8. Вычислить НОК = и г/НОД.
Шаг 9. Вывести а , Ь, НОД, НОК. Шаг 10. Остановиться.
Задача 1.15. Разработать алгоритм вычисления значения цеп-
ной дроби У =---для х ф 0.
Как следует из записи дроби, последним в ней делителем яв-
ляется выражение С=х + -, значение которого при задан- ном х легко может быть найдено. Предпоследним делителем яв-
ляется выражение С = х +
А предшествую-
х щим ему делителем является выражение С =х + - , где С -
найденное перед этим значение делителя. Таким путем может
быть найдено значение делителя С =х + - , а затем значение дроби У = -.
Очевидно, что повторяющимся действием в этой задаче является поиск очередного делителя. Учитывая, что 2 = 2 1 , а 256 = 2 8 , всего необходимо найти восемь делителей. Исключая последний делитель, всего получаем семь повторяющихся действий. На основании изложенных рассуждений конструируем алгоритм, вычисляющий заданное выражение (рис. 1.19). Его текстовая форма такая.
Шаг 1. Ввести х.
Шаг 2. Положить а = хх, Ь = 256.
Шаг 3. Вычислить с = а + Ь/а.
Шаг 4. Положить і = 7.
Шаг 5. Если і 1, перейти к шагу 8.
Шаг 6. Вычислить b = 0,56, с = а + Ь/с.
Шаг 7. Положить і - і - и вернуться к шагу 5.
Шаг 8. Вычислить Y=x/C.
Шаг 9. Вывести у, х.
Шаг 10. Остановиться.
Задача 1.16. Дан ряд чисел а х, а 2 , ..., а„ ..., а п. Разработать алгоритм поиска наибольшего и наименьшего числа в этом ряду с указанием номера (индекса) его расположения.
Очевидный способ поиска наибольшего (наименьшего) числа в заданном ряду п чисел включает следующие действия. Взять первое число ряда и сказать, что оно наибольшее (наименьшее), а индекс его равен 1. Затем взять второе число ряда и сравнить с предполагаемым максимальным (минимальным) первым числом. Если второе число больше предполагаемого максимального (минимального) первого числа, заменить этим числом первое число и положить его индекс равным двум. Если же второе число окажется меньше первого числа, взять третье число ряда и сравнить с первым. Так следует действовать до тех пор, пока не будет выбрано последнее а п число. В результате на месте первого числа окажется наибольшее (наименьшее) число с указанным его номером в ряду чисел. Реализующий эти действия алгоритм приведен на рис. 1.20. Текстовая его форма следующая.
Шаг 1. Ввести а х, ..., а п, п.
Шаг 2. Положить max = а х, і - 1, min - а х, j - 1.
Шаг 3. Положить к = 2.
Шаг 4. Если а к max, перейти к шагу 6.
Шаг 5. Положить max = а к, і = к.
Шаг 6. Если а к > min, перейти к шагу 8.
Шаг 7. Положить min = а к, j = к.
Шаг 8. Положить к= к+ 1.
Шаг 9. Если к вернуться к шагу 4.
Шаг 10. Вывести max, /", min, у.
Шаг 11. Остановиться.
Задача 1.17. Дан ряд чисел а х, а 2 , ..., а„ ..., а п и число Ь. Сконструировать алгоритм поиска в ряду числа а к, равного Ь, и сообщения, найдено число или нет.
Рис. 1.20.
в последовательности чисел
Решение этой задачи сводится к последовательному сравнению чисел ряда а { , а 2 , ..., а п с числом Ь, выводу числа а к, совпадающего с Ь, и его индекса к или выводу сообщения, что необходимое число не обнаружено. Очевидный алгоритм ее решения приведен на рис. 1.21.
Ввести СЛи ...,7, Ь
Этот алгоритм в худшем случае, т. е. когда число не обнаружено, выполняет 2п сравнений. Вместе с тем есть алгоритм, который при п > 8 заметно сокращает это число, а следовательно, и время поиска. Улучшенный алгоритм приведен на рис. 1.22. Уменьшение количества сравнений достигается за счет исключения постоянных сравнений / с п, характерных для первого алгоритма. Выход из цикла осуществляется либо когда а , = Ь , либо когда на (п+ 1)-м повторении обнаружится число Ь, записанное в (п + 1)-й ячейке массива.
Последние две задачи относят к задачам обработки массивов - наборов данных одного вида - чисел или символов. В программировании различают массивы одномерные и многомерные. Одномерный массив образуют последовательные его элементы. Место элемента в массиве определяется его номером - индексом, представляющим собой положительное число. Рассмотренные последовательности чисел а ., а ъ
Ь являются одномерными массивами.
Двумерные массивы - это прямоугольные таблицы данных, состоящие из заданного количества строк и колонок (столбцов). В математике такие таблицы называются матрицами и весьма широко используются как непосредственно при математических вычислениях, так и в программировании. Элемент матрицы размещается на пересечении строки и столбца и идентифицируется двумя индексами: номером строки, например /, и номером столбца, например у. Если матрица содержит т строк и п столбцов, всего элементов этой матрицы тп и а ] - произвольный ее элемент. Матрица, содержащая т строк и т столбцов, называется прямоугольной.
В квадратной матрице выделяют главную и побочную диагонали. Матрица А = а ц размером т х п, т. е. содержащая т строк
и п столбцов, т = п, имеет вид:
|
Главную диагональ матрицы образуют элементы а и, а 22 , ..., а тп, т. е. элементы, лежащие на прямой, проведенной слева направо от элемента а п к элементу а тп.
Побочную диагональ образуют элементы матрицы а 1п, а 2п _ х, ..., а т1 , лежащие на прямой, проведенной от элемента а 1п к элементу а т{ , т. е. справа налево.
Элементы матрицы А, лежащие справа и вверху от главной диагонали, образуют верхнюю треугольную матрицу. Элементы, лежащие слева внизу от главной диагонали, образуют нижнюю треугольную матрицу.
Матрица называется симметричной, если элементы, симметричные относительно главной диагонали, равны между собой, т. е. а и = й / (.
Одной из важнейших задач обработки одномерных массивов является их сортировка - расположение элементов массивов в определенном порядке. Чаще всего рассматривается упорядочение элементов числовых массивов по возрастанию или убыванию. По статистическим данным, примерно 25 % времени работы ЭВМ расходуется на сортировку данных, потому что отсортированные данные обрабатывать значительно проще. Когда элементы массива отсортированы, их быстрее найти, обновить, исключить из массива и т. п.
Существует целый ряд алгоритмов сортировки. Среднее время их работы или временная сложность лежит в пределах от 0(п 2 / 4) до 0(ппп), где п - число элементов массива. К сожалению, нет алгоритма сортировки, который был бы наилучшим в любом случае.
Рассмотрим простейшую сортировку, называемую сортировкой вставками. Идея этой сортировки состоит в том, что очередной (сортируемый) элемент массива, упорядочиваемого, например, по возрастанию, сравнивается с предшествующими его элементами до тех пор, пока не встретится элемент, меньший или равный ему. Тогда все элементы, следующие за меньшим элементом, сдвигаются на одну позицию вправо, а очередной элемент ставится на освободившееся место за меньшим элементом. Если же в результате сравнения сортируемого элемента с предшествующими элементами массива меньший элемент не будет обнаружен, сортируемый элемент оставляют на старом месте и переходят к очередному элементу массива. Сравнения начинают со второго элемента массива и заканчивают последним его элементом.
Рассмотрим эту сортировку на массиве целых чисел
- 71 27 412 81 59 14 273 87, который требуется упорядочить по возрастанию. Первым сортируемым элементом массива является второй элемент - число 27. Образно говоря, «вынимаем» его из массива, т. е. освобождаем место для будущего сдвига чисел вправо, и сравниваем второй элемент (число 27) с первым элементом (число 71). Так как 27
- 27 71 412 81 59 14 273 87,
в которой часть массива 27, 71 предварительно отсортирована.
Теперь выбираем третий элемент массива - число 412. Запоминаем его и сравниваем с предшествующим элементом массива. Так как 412 > 71, а 71 > 21, оставляем число 412 на своем месте, т. е. получаем прежний массив
27 71 412 81 59 14 273 87.
Выбираем четвертый элемент массива - число 81. Запоминаем его и сравниваем с предшествующим элементом - числом 412. Так как 81
27 71 81 412 59 14 273 87.
Выбираем пятый элемент массива - число 59. Запоминаем это число и сравниваем с предшествующим элементом массива - числом 412. Так как 59 59, сдвигаем его на одну позицию вправо. Нетрудно видеть, что процесс сравнения и сдвига элементов закончится на числе 27. В результате получим
27 59 71 81 412 14 273 87.
Шестым элементом массива является число 14. Путем сравнения его с предшествующими элементами и сдвигов их вправо получим массив
14 27 59 71 81 412 273 87.
Выполнив описанные действия с седьмым и восьмым элементами массива, получим отсортированный список
14 27 59 71 81 87 273 412.
Задача 1.18. Разработать алгоритм сортировки вставками.
Согласно изложенному методу сортировки общим повторяющимся действием является выбор очередного сортируемого элемента и его запоминание. Элементы выбираются, начиная со второго и заканчивая последним п-м элементом массива. Эти действия составят внешний цикл алгоритма. Внутренний цикл алгоритма образуют действия сравнения и, если необходимо, сдвига элементов, а также его вставки в необходимую позицию массива. Поэтому алгоритм, реализуемый рассматриваемым методом, будет иметь такой вид (рис. 1.23). Его текстовая форма следующая.
Шаг 1. Ввести я, ..., а п, п.
Шаг 2. Положить / = 2.
Шаг 3. Положить к = я,
Шаг 4. Положить у = /"- 1.
Шаг 5. Если к > а р перейти к шагу 8.
Шаг 6. Если у
Шаг 7. Положить а ]+х = а р у = у - 1 и вернуться к шагу 5.
Шаг 8. Положить я /+1 = к, /= / + 1.
Шаг 9. Если / п, вернуться к шагу 3.
Шаг 10. Вывести я, ..., я„.
Шаг 11. Остановиться.
Проверка условия у > 0 в приведенной блок-схеме необходима для того, чтобы при сравнении сортируемого элемента к с предшествующими а р я-_, я, не выйти за пределы массива. Иначе алгоритм не будет определен. В заключение отметим, что сортировка вставками согласно достаточно эффективна для массивов с максимальным количеством элементов п 0(п 3/2), и быстрой сортировке, средняя сложность которой 0(1п(я)). Как правило, такая сортировка применяется для массивов с числом элементов п > 1000.
В тех случаях, когда в некотором массиве постоянно осуществляется поиск элементов, этот массив предварительно сортируется и в дальнейшем поиск осуществляется в упорядоченном
Рис. 1.23.
массиве. В качестве алгоритма поиска чаще всего используется так называемый бинарный поиск. Практика показывает, что такой подход существенно уменьшает средние временные затраты на поиск.
Суть бинарного поиска следующая. Пусть задан упорядоченный по возрастанию массив чисел а х, а 2 , а п а п и число Ь. Требуется найти элемент массива а к, равный Ь, или сообщить, что такого элемента в массиве нет. Обозначим первый индекс массива /, а последний и. Тогда индекс у числа а р стоящего примерно в середине массива, может быть найден по выражению у = |(/ + и)/ 2_|, где символы |_ ] определяют целую часть числа (/ + и)/ 2. Если
я- = Ь, процесс поиска завершен. Если же Ь то в силу упорядоченности массива я, ..., а п искомое число будет находиться в подмассиве а„ ..., а ] _ 1 . Когда же Ь > а р то по той же причине число следует искать в подмассиве я у+1 , ..., а п. Таким образом, в результате выбора числа а ] и сравнения его с числом Ь можно перейти к поиску в массиве с числом элементов, меньших в 2 раза, чем п. Далее процесс выбора элемента я. осуществляется в одном из подмассивов, сокращая поиск в массиве с числом элементов, меньших в 2 раза, чем в подмассиве. Этот процесс выбора а ] и деления очередного массива пополам продолжается до тех пор, пока не будет найдено заданное число либо установлено, что его в массиве нет. Описанный процесс продемонстрируем на поиске элемента Ь = 59 в следующем массиве
14 27 59 71 81 87 273 412 501.
Массив содержит девять элементов, поэтому у = |_(1 + 9)/2_| =
5. Элемент с индексом 5 - это а 5 = 81. Сравниваем его с Ь = 59. В результате переходим к поиску в массиве 14 27 59 71 (/= 1, и =у - 1 = 5 - 1 = 4). Теперь вычисляем индекс у = |_(1 + 4)/2_| = 2.
Элемент с индексом 2 - это а 2 = 27. Сравниваем его с Ь = 59. В результате переходим к поиску в массиве 59 71 (/=у+1 =
2+1 = 3, и = 4). Вычисляем индекс у = |_(3 + 4)/2_| = 3. Элемент
с индексом 3 - это я 3 = 59. Сравниваем его с Ь = 59 и устанавливаем, что это искомый элемент массива.
Теперь рассмотрим случай, когда элемент Ь= 12, т. е. он не принадлежит массиву. Первый индекс у = 5 и мы переходим к поиску в массиве 14 27 59 71 (/ = 1, и = 4). Второй индекс у = 2, что дает очередной массив поиска 14 27 (/= 1, и = 2). Третий индекс поиска у = 1(1 + 2)/2 I = 1 и мы переходим к массиву поиска 14
(/ = 1, и = 0). Однако в массиве нет элемента с индексом и = 0. Это означает, что мы проверили весь массив и не нашли элемента я; = Ь. Таким образом, можно сделать вывод, что признаком отсутствия элемента в массиве служит неравенство и
Задача 1.19. Составить алгоритм бинарного поиска.
Учитывая изложенное, можно предложить следующий алгоритм решения указанной задачи (рис. 1.24). Его текстовая форма приведена ниже.
Рис. 1.24.
Шаг 1. Ввести а х, а п, п, Ь.
Шаг 2. Положить / = 1, и = п.
Шаг 3. Если и перейти к шагу 9.
Шаг 4. Вычислить |_(/ + «)/2_|.
Шаг 5. Если а ] = Ь, перейти к шагу 8.
Шаг 6. Если а / положить и =у - 1 и вернуться к шагу 3.
Шаг 7. Положить / = у + 1 и вернуться к шагу 3.
Шаг 8. Вывести «Элемент найден», у = и перейти к шагу 10.
Шаг 9. Вывести «Элемент не найден».
Шаг 10. Остановиться.
Идея бинарного поиска используется и в других случаях, в частности при вычислении корней трансцендентных и алгебраических уравнений. Пусть задано трансцендентное уравнение, например е х - х - 2 = 0, и известно, что его корень принадлежит интервалу [а, Ь. Требуется найти значение этого корня.
В общем виде уравнение может быть записано как /(х) = 0, где Дх) - непрерывная функция, рассматриваемая на интервале [а, Ь]. Поскольку решение уравнения, т. е. его корень, х е [а, Ь] обращает уравнение в тождество, то левая часть равенства /(х) = 0 в точке х е а,Ь] должна быть равна нулю. С геометрической точки зрения это означает, что функция /(х) в точке х пересекает ось абсцисс. Эту точку пересечения и необходимо найти.
Для этого поступаем следующим образом. По выражению IV= (а + Ь)/2 находим координату IV середины отрезка [а, Ь. Если Дх) = 0, то корень уравнения х= IV найден. Если /(а )/(ВО > 0, т. е. /(а ) и /(ВО одного знака, корня на интервале нет (рис. 1.25), и мы переходим к его поиску на интервале , который вполовину короче исходного интервала [а, Ь ]. Если /(а )/(ВО а) и /(ВО разных знаков, корень находится на интервале [а, IV], и его поиск осуществляется на этом интервале, а интервал [ IV, Ь] забывается.
Таким образом, вычисляя выражение Ц^=(а+Ь)/2 и выполняя сравнение /(я) /(IV) > 0, мы сокращаем интервал поиска ровно вдвое. В результате после п таких действий получим интервал [а п, Ь п ], которому принадлежит корень уравнения, в 2" раз меньший исходного интервала [а, Ь, т. е. а п - Ь п = а - ^/2". Приняв в качестве точности вычисления корня а длину интервала |а п - Ь п, можно определить, что для получения этой точности необходимо сделать п = па - Ь |/е шагов. Описанный метод по-
Рис. 1.25.
иска корня получил название метода половинного деления, или дихотомии.
Задача 1.20. Разработать алгоритм уточнения корня уравнения /(х) = 0 методом дихотомии.
Метод предполагает, что задан интервал а, Ь, которому принадлежит корень, функция /(х) = 0 непрерывна и ограничена на этом интервале и f(a) f(b )
Шаг 1. Ввести а, Ь, е.
Шаг 2. Положить и = /(я), v = f(b).
Шаг 3. Вычислить х = а + , w = f(x).
Шаг 4. Если w = 0, перейти к шагу 10.
Шаг 5. Если uw> 0, перейти к шагу 7.
Шаг 6. Положить b = x, v=w и перейти к шагу 8.
Шаг 7. Положить а = х, u=w.
Шаг 8. Если а - Ь > с, вернуться к шагу 3.
Шаг 9. Положить х = а - Ь.
Шаг 10. Вывести х, s.
Шаг 11. Остановиться.
При решении различных задач часто приходится использовать значения элементарных функций, таких как sin (х), cos (х), log (х), In (х), е х и др. Для того чтобы облегчить процесс вычис-
и=/(а), у=/(6)
х = (а + Ь)/ 2, №=Ах)
Ь=х,у = 1Г
Рис. 1.26.
ления этих функций, в системной библиотеке компьютера хранятся заранее составленные программы вычисления их значений. Для их использования достаточно лишь упомянуть имя функции и указать ее аргумент. В свою очередь указанные программы составлены на основании формул разложения той или иной функции в ряд. Например, функция е х представляется сле-
дующим бесконечным рядом е х = 1 + X +-+
Для функций sin (х), cos (х) соответственно имеем:
. , V X X
В каждом из указанных разложений точность представления той или иной функции определяется числом членов ряда. Чем больше это число, тем точнее вычисляется функция при одном и том же х. Поэтому для вычисления значения функции с заданной точностью с поступают следующим образом. Вычисляют и суммируют члены ряда до тех пор, пока очередное слагаемое не станет по модулю меньше 8.
Звдача 1.21. Составить алгоритм вычисления функции зт(х) с точностью 8 при помощи разложения ее в ряд.
Из формулы, которая приближенно представляет функцию бш(х) в виде бесконечного ряда, следует, что алгоритм вычисления значения 8ш(х) с заданной точностью е будет включать повторяющиеся действия вычисления очередного члена ряда, суммирования членов ряда и изменения знака перед соответствующим членом ряда. Нетрудно видеть, что каждый очередной член ряда У п и может быть вычислен по рекуррентной формуле У п =
Например,
у хх2 _ * 3 у _у
- 1 2 1 (2 1+1) 3!’ 2 1
- 2л(2т ) 3!- 4-5 5!
Знаки членов ряда меняются поочередно, если начинать с У х.
Поэтому начальными установками алгоритма будут такие ?=х , 6’ = х, Z= хх, а = - 1. В цикле будем вычислять очередной
член ряда ? = --- и прибавлять его к предшествующей
2п(2п + 1)
сумме с соответствующим знаком. Блок-схема алгоритма приведена на рис. 1.27. Его текстовая форма дана ниже.
у =х, 8=х,
?-хх,а -~
Рис. 1.27.
Шаг 5. Вычислить 6’= 5 + у.
Шаг 6. Если у
Шаг 7. Положить а = -а, п = п + 1 и вернуться к шагу 4. Шаг 8. Вывести 5, х, е.
Шаг 9. Остановиться.
Задача 1.22. Составить алгоритм вычисления следа квадрат
а 2 а
а, Л а
|
... сі пп |
Шаг 1. Шаг 2. Шаг 3.
Ввести х, е.
Положить у = х, 5 = х, Z= хх, а = Положить п= 1.
Вычислить к= 2п, У =
к(к + 1)
а , а
ной матрицы А =
Как было сказано раньше, след матрицы - это сумма эле-
ментов ее главной диагонали, т. е. Я, - ^а и. Поэтому алгоритм
определения следа сводится к вычислению суммы Блок-схема этого алгоритма приведена на рис. 1.28.
Вместе с тем есть способ построить более эффективный алгоритм решения этой задачи. Он основан на вычислении адреса очередного диагонального элемента матрицы А не в двумерном, а в одномерном массиве.
Известно, что элементы двумерных и больших измерений массивов в памяти компьютера записываются линейно. Ниже в качестве примера приведена линейная запись элементов матрицы А с тремя строками и столбцами.
Через индексы строк и столбцов /, у номер любого элемента в линейном массиве вычисляется по формуле х = (/ - 1)я+/ Например, номер элемента а 22 определяется так (2 - 1)3 + 2 = 5. Таким образом, чтобы выбрать какой-либо элемент из линейного
Рис. 1.28.
массива, необходимо вычислять его номер по выражению А / "= (/- 1 )п + у, т. е. выполнить три арифметические операции.
В то же время можно видеть, что номер очередного диагонального элемента в линейном массиве отличается от номера предшествующего диагонального элемента на постоянную величину к = п + 1. Например, номер а 22 - 5 равен номеру а п - 1, т. е. 1 +4 = 5. Поэтому в линейном массиве очередной диагональный элемент определяется по номеру / = / + к. В результате его вычисление требует выполнить вместо трех всего одну арифметическую операцию, что в целом приводит к уменьшению объема вычислений и повышению быстродействия алгоритма. Блок-схема этого алгоритма приведена на рис. 1.29.
Задача 1.23. Разработать алгоритм вычисления суммы элементов побочной диагонали квадратной матрицы А.
В качестве примера рассмотрим матрицу с тремя строками и
тремя столбцами А =
Рис. 1.29. Эффективный алгоритм вычислени следа матрицы А
Через элементы побочной
диагонали этой матрицы для их выделения проведена прямая линия. Первый индекс диагональных элементов - это номер строки /, второй, как нетрудно видеть, вычисляется по выражению у = п + 1 - /", где к - п + 1. Поэтому блок-схема алгоритма, решающего эту задачу, будет иметь вид, представленный на рис. 1.30. Его текстовая форма приведена ниже.
Рис. 1.30. Блок-схема алгоритма вычисления суммы элементов побочной
диагонали квадратной матрицы А
Шаг 1. Ввести п, элементы матрицы А.
Шаг 2. Положить? = 0, / = 1, к= п + 1.
Шаг 3. Вычислить? р = + а 1к _ г
Шаг 4. Положить / = /" + 1.
Шаг 5. Если /п, вернуться к шагу 3.
Шаг 6. Вывести $ р.
Шаг 7. Остановиться.
Очевидно, что для решения этой задачи также можно построить более быстрый алгоритм, в основу которого положить выбор элементов из линейного массива.
Задача 1.24. Нарисовать блок-схему алгоритма, вычисляющего сумму элементов верхней треугольной матрицы А.
Рассмотрим матрицу А, состоящую из п строк и п столбцов.
|
С1 пп |
Нетрудно видеть, что первый индекс эле
мента верхней треугольной матрицы - это индекс строки /. Второй индекс определяется по выражению у = / + 1. Поэтому блок-схема алгоритма будет иметь вид, представленный на рис. 1.31. В алгоритме имеется два цикла: один внешний и второй внутренний. Такие циклы называются вложенными. Текстовая форма алгоритма приведена ниже.
Шаг 1. Ввести п, элементы матрицы А.
Шаг 2. Положить А т = 0, /"= 1.
Шаг 3. Положить у = / + 1.
Шаг 4. Вычислить А, = 5 Т + а ц.
Шаг 5. Положить у =у + 1.
Шаг 7. Положить /"=/"+ 1.
Шаг 9. Вывести А т.
Шаг 10. Остановиться.
Задача 1.25. Нарисовать блок-схему алгоритма получения транспонированной матрицы А, на месте исходной квадратной матрицы А.
Квадратная матрица А, называется транспонированной по отношению к заданной матрице А, если ее элементы получены обменом элементов, симметричных относительно главной диаго-
. Мы видим, что в ней
элементы я 12 и а 2{ , а п = а р Тогда для получения А,. в цикле необходимо запомнить элемент и = а 1р на место элемента а ] поставить элемент а р а на место элемента а м - элемент а 1} . Блок-схема алгоритма, решающего эту задачу, приведена ниже на рис. 1.32. Текстовая его форма такая.
Шаг 1. Ввести п, элементы матрицы А.
Шаг 2. Положить / = 1.
Шаг 3. Положить у = 1.
Шаг 4. Положить и =
« = а Р
Шаг 5. Положить у =у + 1.
Шаг 6. Если у п, вернуться к шагу 4.
Шаг 7. Положить /"=/"+ 1.
Шаг 8. Если /п, вернуться к шагу 3.
Шаг 9. Вывести А,.
Шаг 10. Остановиться.
В матричной алгебре и ее приложениях весьма часто приходится выполнять умножение матрицы А на вектор-столбец Ь и умножение матрицы А на матрицу В. Как выполняется операция умножения А на Ь , рассмотрим на примере матрицы
результате умножения мы получим вектор-столбец АЬ с элементами скалярных произведений строк матрицы А на столбец Ь. Первый элемент этого вектор-столбца
а х Ь = а и Ь х + а п Ь 2 + а п Ь 3 = ^ а и ь ] -
Второй его элемент
а 2 Ь = а 2 Ь + а 22^2 + «2з^з = У,«?/
Третий элемент столбца
«з Ь = а 31 Ь 1 + а 32 Ь 2 + Ь 3 = ? а у Ь } .
Рис. 1.32. Блок-схема алгоритма транспонирования квадратной матрицы А
Таким образом, чтобы выполнить умножение матрицы А на вектор Ь, необходимо последовательно умножить вектор строки А на столбец Ь. При этом умножение А на Ь имеет место только тогда, когда количество столбцов матрицы А равно количеству элементов вектора Ь.
Задача 1.26. Разработать алгоритм умножения матрицы А на вектор Ь. Очевидно, что в алгоритме должно циклически вычисляться скалярное произведение каждой вектор-строки матрицы А на вектор Ь и запоминаться как элемент результирующего вектора-столбца Л т. Блок-схема алгоритма приведена на рис. 1.33. Текстовая форма дана ниже.
Шаг 1. Ввести п, т, элементы Ли Ь.
Шаг 2. Положить /= 1.
Шаг 3. Положить у = 1, А* = 0.
Шаг 4. Вычислить А* = 5* + а^Ь г
Шаг 5. Положить у =у + 1.
Шаг 6. Если у п, вернуться к шагу 4.
Шаг 7. Положить А” = 5*.
Шаг 8. Положить /= /"+ 1.
Шаг 9. Если /т, вернуться к шагу 3.
Шаг 10. Вывести А"".
Шаг 11. Остановиться.
|
Умножение матрицы А = |
на матрицу В = |
|||||
возможно только тогда, когда число столбцов матрицы А равно числу строк матрицы В.
Умножение выполняют последовательно. Сначала матрицу А умножают на первый вектор-столбец В и получают вектор С,. Затем А умножают на второй вектор-столбец В и получают вектор С 2 . Этот процесс продолжают до исчерпания столбцов матрицы В. В результате получают матрицу С с количеством столбцов второй матрицы В.
Задача 1.27. Разработать алгоритм умножения матрицы А на матрицу В.
Очевидно, что в алгоритме как его фрагмент можно использовать алгоритм умножения матрицы на вектор. Блок-схема алгоритма приведена на рис. 1.34. На этой блок-схеме к -
количество столбцов матрицы В,
Шаг 1. Ввести п, т , к , элементы А, В.
Шаг 2. Положить д = 1.
Шаг 3. Положить /"= 1.
Шаг 4. Положить у = 1, 5* = 0.
Шаг 5. Вычислить 5* = Я к + а 1} Ь к.
Шаг 6. Положить у =у + 1.
Шаг 7. Если у
Шаг 8. Положить А," =
Шаг 9. Положить /"=/"+ 1.
Шаг 10. Если /"
Шаг 11. Положить д = д + 1.
Шаг 12. Если д вернуться к шагу 3.
Шаг 13. Вывести А™.
Шаг 14. Остановиться.
Обратим внимание на то, что в этом алгоритме имеется система из двух вложенных циклов. Предшествующая схема алгоритма имеет один вложенный цикл.
Задача 1.28. Разработать алгоритм решения системы п линейных уравнений с п неизвестными
|
+ а 1п х п |
||||
|
Н" ?/97 X ?) |
+ а 2п х п |
|||
|
+ а п2 х 2 |
+ а пп Х п |
методом исключения Гаусса.
Суть метода Гаусса состоит в том, что сначала исключается первое неизвестное х, из всех уравнений, кроме первого. Затем исключается второе неизвестное х 2 из всех уравнений, кроме первых двух. Последним исключается п - 1 неизвестное х„_, из последних двух уравнений. В результате получают систему уравнений треугольного вида
а" п х 1 + а[ 2 х 2 + ... + а п х п = Ь[ а 22 х 2 + ... +а 2 п х п = Ь 2
из которой сначала находят неизвестное х п = Ь" п 1а" пп, затем методом подстановки значения х п в предшествующее уравнение очередное неизвестное потом
х „-2 = (Ь "„-2 -а"ь--а" т х„)/а" т _.
и заканчивают этот процесс вычислением значения
Хі = (Ь[ -а" 22 х 2 -... -а" пп х п)/а" п.
Таким образом, метод содержит два этапа: последовательное исключение неизвестных и последовательное их вычисление. Рассмотрим технику исключения неизвестных на примере трех уравнений с тремя неизвестными. Для этого систему уравнений
ры-столбцы неизвестных и правых частей уравнений. Далее рас
а 2 а 2 2 а 23
смотрим расширенную матрицу А" =
В первом столбце матрицы А" найдем наибольший по модулю, не равный нулю элемент. Если ненулевого элемента в столбце нет, рассмотренная система уравнений не имеет решений. Если наибольший ненулевой элемент содержится в любой строке матрицы А", кроме первой, поменяем местами эту строку матрицы А" с первой ее строкой. Этими действиями осуществляется контроль совместности системы уравнений и уменьшается чувствительность метода к округлению чисел, сопровождающему вычисления на ЭВМ.
Для того чтобы исключить первое неизвестное х, из второго уравнения системы, вычислим множитель т 2 = а 2х /а п, умножим первую строку матрицы А" на этот множитель и вычтем результат умножения из второй строки А".
(я 21 - т 2 а и)х у - (а 22 - т 2 а п)х 2 - (а 23 - т 2 а хз)х 3 = Ь 2 - т 2 Ь х. Обозначив я 2! - т 2 а и =а" 2х = 0, будем иметь
Я 13 х 3 + я 23 х 3
а и Х 1 + а п Х 2 О + а" 22 х 2
«31* | + а 32 х 2
Для исключения неизвестного х { из третьего уравнения полученной системы вычислим множитель т 3 = а зх /а и, умножим этот множитель на первую строку матрицы А" и вычтем результат умножения из третьей строки.
Тогда ввиду того, что а м - т 3 а и = 0 и вводя соответствующие обозначения, получим систему
Я 13 х 3 + а 23 х 3
О Х + а 12 х 2 О + а" 22 х 2 О + я 32 х 2
в которой исключено неизвестное х, из всех остальных уравнений, кроме первого.
Теперь задача состоит в том, чтобы исключить неизвестное х 2 из третьего уравнения. Для этого поступим аналогичным образом. Найдем множитель т" 3 =а" 32 /о" 22 , умножим на него второе уравнение и вычтем результат умножения из третьего уравнения. В итоге получим
(«32 - ^з«22)*2 “(«33 - ^3«2з)*3 = ^3 - т Ъ ^2
Учитывая, что а" 32 - т" 3 а" 22 = 0 и обозначив а" 33 - т" 3 а" 23 =а 33 , Ь" 3 - т" 3 Ь" 2 = Ь 3 , придем к треугольной системе
из которой методом последовательной подстановки получим значения неизвестных
*3 =?з"Мз> *2 =(Ь" 2 -а" 23 х 3)/а 22 , х 1 ={Ь Х -я 13 х 3 -а п х 2)/а п.
Обобщая изложенное, можно сказать, что алгоритм должен выполнить п - 1 действие по исключению п - 1 неизвестных. Если к - номер исключаемого переменного, то необходимо в каждом из этих действий сделать от / = к + 1 до п вычитаний уравнений. При этом каждое вычитание осуществляется выполнением у = к + 1 до п арифметических действий. Кроме этого, при каждом исключении переменной необходимо найти максимальный элемент в соответствующем столбце матрицы А. И последнее, что нужно сделать, вычислить значения неизвестных х п, ..., х,. Таким образом, общая укрупненная блок-схема алгоритма представляется такой (рис. 1.35).
Теперь составим алгоритмы поиска максимального элемента, вычитания строк и вычисления значений переменных, которые на этой схеме представлены укрупненными блоками.
Поиск индекса максимального элемента в ряду чисел рассмотрен в задаче 1.16. В данном случае он ничем не отличается от метода, который изложен там. Полагаем, что максимальный элемент первый в столбце Ли 1= к. Затем в цикле сравниваем с этим элементом остальные элементы этого столбца и тем самым выделяем наибольший элемент и устанавливаем его индекс. Алгоритм поиска минимального элемента в столбце матрицы А приведен на рис. 1.36. Там же показан фрагмент проверки условий совместности системы уравнений. На рис. 1.37 показана блок-схема алгоритма вычитания строк.
Алгоритм определения значений переменных х п, х п _ х, ..., х, последовательно реализует формулы, по которым вычисляются эти переменные х п = Ь п /а пп, х я _, = {Ь п _ х - а п _ х х п)/а п _ х .... Его блок-схема приведена на рис. 1.38. Ниже приведена текстовая форма полного алгоритма.
Шаг 1. Ввести п, А, В.
Шаг 2. Положить к= 1.
Шаг 3. Положить 1= к, / = к + 1.
Шаг 4. Если |а 1к >а, к, положить / = 1.
Шаг 5. Положить / = / + 1, если / п, вернуться к шагу 4.
Рис. 1.35.
|
Система |
||
|
несовместна |
||
|
* &кр Я к/ Щр а и =г, 7=7 + 1 |
|
|
^=6*, = Ьі, |
|
Рис. 1.36.
и замены строк А"
Рис. 1.37.
Шаг 6. Если а 1к = 0, перейти к шагу 29.
Шаг 7. Если 1= к, перейти к шагу 12.
Шаг 8. Положить у = к.
Шаг 9. Положить I = а кр а к] = а /р а у = I-
Шаг 10. Положить у = у + 1, если / п, вернуться к шагу 9.
Шаг 11. Положить? = Ь к, Ь к = Ь„ Ь, = I-
Шаг 12. Положить /=? + 1.
Шаг 13. Вычислить т = а)к /а кк, положить а 1к = 0.
Шаг 14. Положить у = к + 1.
Шаг 15. Вычислить а 0 = а и - та 1к .
К выводу
Шаг 16. Положить у =у + 1, если / п, вернуться к шагу 15. Шаг 17. Вычислить Ь і = Ь; - т Ь к.
Шаг 18. Положить / = / + 1, если /" п, вернуться к шагу 13. Шаг 19. Положить к - к + 1, если к - 1, вернуться к шагу 3. Шаг 20. Вычислить х п = Ь п /а пп.
Шаг 21. Положить і = п - 1.
Шаг 22. Положить 5=0.
Шаг 23. Положитьу= / + 1.
Шаг 24. Вычислить 5=5+ а и х ] .
Шаг 25. Положить у = у + 1, если у = я, вернуться к шагу 24. Шаг 26. Вычислить х, = (6, - 5)/я„-.
Шаг 27. Положить / = /- 1, если /> 1, вернуться к шагу 22. Шаг 28. Вывести х, ..., л:, и перейти к шагу 30.
Шаг 29. Вывести «Система несовместна».
Шаг 30. Остановиться.
Задача 1.29. Сконструировать алгоритм записи последовательности чисел 1, 2, 3, ..., 49 в квадратную матрицу А с 7 строками и 7 столбцами по спирали (рис. 1.39).
Рис. 1.39.
Самое простое решение этой задачи следующее. Двигаясь по спирали, составить две последовательности индексов элементов матрицы А. В первую последовательность занести значение индексов строк 1, 1, 1, 1, 1, 1, 1, 2, 3, 4, 5, 6, 7, 7, 7, 7, 7, 7, 7, 7, 7, 6, 5, 4, 3, 2, ..., во вторую последовательность - значения индексов столбцов 1, 2, 3, 4, 5, 6, 7, 7, 7, 7, 7, 7, 7, 7, 7, 6, 5, 4, 3, 2, 1, 1, 1, 1, 1, 1, 1, ... . Затем организовать цикл от 1 до 49, в котором последовательно выбирать числа из двух последовательностей - индексы соответствующего элемента матрицы А и по этим индексам на место элемента матрицы а ] заносить значение управляющей переменной цикла к.
Пусть / - строчные индексы матрицы А, у - индексы ее столбцов, к - управляющая переменная цикла. Пусть далее 4 - к-е значение строчного индекса, а ] к - к-е значение ее столбцевого индекса. С учетом этих обозначений алгоритм будет иметь вид, показанный на рис. 1.40.
Рис. 1.40. Алгоритм записи чисел натурального ряда 1, ..., 49 в матрицу А
по спирали
Недостаток этого алгоритма заключается в том, что сначала необходимо составить последовательности индексов, отображающих движение по спирали, а затем программировать.
Можно предложить другой алгоритм, в котором записываются только начальные и конечные индексы сторон спирали. Например, для первых четырех ее сторон получим:
/= 1, у = от 1 до 7;
/" = от 2 до 7, У = 7;
/ = 7, у = от 6 до 1;
/ = от 7 до 2, у = 1.
Для остальных двух спиралей индексы найдем аналогичным путем, исходя из рисунка спирали.
Таким образом, согласно этому подходу для записи в матрицу А чисел одной спирали требуется выполнить четыре цикла: два в прямом направлении и два в обратном. Чтобы ограничиться использованием только этих четырех циклов, необходимо найти, как изменятся индексы от номера спирали. Тогда алгоритм будет содержать один внешний и четыре внутренних цикла, начальные и конечные индексы которых зависят от индексов внешнего цикла. Доработку этого алгоритма мы выносим в качестве самостоятельного упражнения.
Задача 1.30. Рассмотрим шахматную доску и два положения коня на ней (рис. 1.41). Возможные ходы коня показаны стрелками и пронумерованы. Конь слева (поле (1,2)), не выходя за пределы доски, может пойти только на три поля. Конь справа (поле(5,6)) может пойти на восемь полей, что является макси-
мальным количеством допустимых ходов коня из одного ПОЛЯ. Маршрутом коня называется последовательное перемещение коня по полям доски такое, что он не попадает на одно и то же поле дважды. Конечной точкой маршрута является поле, с которого нет допустимого хода либо по причине выхода коня за пределы доски, либо по причине повторного попадания на какое-либо поле маршрута. Составить алгоритм, строящий маршрут коня, возможно наибольшей длины.
Очевидно, что наибольшая длина маршрута - это 63 поля шахматной доски. Попытаться найти такой маршрут можно путем перебора всех маршрутов коня, начинающихся из всех 64 полей. Поэтому, кроме процедуры построения маршрута, алгоритм должен содержать цикл из 64 повторений задания исходного поля.
Для того чтобы построить маршрут коня, начинающийся с любого поля доски, кроме учета ограничений, обеспечивающих допустимый ход, необходимо определить стратегию выбора очередного хода. Возможной такой стратегией может быть первый допустимый ход коня, если просматривать его ходы по часовой стрелке (см. 2-е положение коня, рис. 1.41). В том случае, когда допустимого хода нет, маршрут считается законченным.
В свою очередь, допустимость хода по условию непопадания на уже пройденное поле маршрута может быть определена так. Запишем во все поля доски значение нуль, а дальнейшие ходы коня с некоторого поля будем нумеровать числами, на которые конь делает очередной ход. Тогда допустимым полем будет поле доски со значением нуль, а максимальное число натурального ряда в конце маршрута определит его длину.
Выход коня за пределы доски может фиксироваться путем обрамления доски двумя полями, в которые записано произвольное число больше нуля, например 66. На рис. 1.42 приведены исходные данные о доске и показано начало маршрута коня из поля (7, 8).
На основании изложенного алгоритм поиска лучшего маршрута коня должен включать следующие этапы:
- 1) инициализацию полей обрамления доски, т. е. запись в эти поля числа 66 или любого другого, например 99;
- 2) инициализацию начала цикла по всем маршрутам с указанием начальной длины маршрута / = -1 для выбора лучшего маршрута;
Рис. 1.42. Исходные данные о доске и начало маршрута коня
- 3) инициализацию полей доски, т. е. запись в эти поля числа 0;
- 4) построение маршрута коня, запоминание его длины и выделение лучшего текущего маршрута;
- 5) вывод лучшего маршрута и его длины.
Укрупненная блок-схема алгоритма поиска лучшего маршрута коня приведена на рис. 1.43.
На рис. 1.44 приведена блок-схема алгоритма инициализации верхнего обрамления доски с учетом того, что вся доска с обрамлением представляет собой квадратную матрицу /) = 11
с 12 столбцами и 12 строками, т. е. двумерный массив.
Аналогичный вид будет иметь блок-схема инициализации нижнего обрамления доски. Другими будут только начальные и конечные значения управляющей строки / 5 = 11, 1 Р = 12.
Что касается инициализации левого и правого краев доски, то в этом случае можно обойтись без вложенного цикла по у. Блок-схема этого алгоритма приведена на рис. 1.45. Соединенные последовательно блок-схемы инициализации верхнего, нижнего, а также левого и правого обрамлений доски образуют общую блок-схему инициализации обрамления доски.
Определение длины п маршрута
Запоминание лучшего маршрута и его длины / = /7
I*-:
Рис. 1.44. Блок-схема алгоритма инициа- Рис. 1.45. Блок-схема алгоритма
лизации верхнего обрамления доски инициализации левого и правого
обрамления доски
Блок-схема инициализации непосредственно шахматной доски реализует процедуру занесения в двумерный массив /) = dyW с индексами / 5 =3, 1 Р = 10, у 5 =3, ] р = 10 значений с1 1Г Она
легко может быть построена, в связи с этим не приводится.
Теперь рассмотрим, как может быть представлен алгоритм построения маршрута коня. Условимся, что последовательность полей, с которого начинается маршрут коня, будет задаваться с помощью двух индексов-строки / матрицы О и ее столбца у. Тогда согласно рис. 1.42 индексы всех полей, на которые может попасть конь, с произвольного поля (/, у) идя по часовой стрелке, будут следующими.
|
1 = 1 + 2 |
||
Таким образом, для исходного поля очередного маршрута и каждого допустимого поля (/,_/") необходимо организовать просмотр максимум 8 полей. Для этого следует организовать цикл переменной по к от 1 до 8. В свою очередь изменение индекса удобно вычислять как / = / + 4, у =у + у*. Для этого значения 4? Л необходимо представить двумя одномерными массивами 4 = (-2 -112 2 1-1 -2), у4 = (1 2 2 1-1-2-2 -1).
На основании изложенного построение маршрута может быть организовано следующим образом. Получив поле (/,у) начала очередного маршрута, установить его номер п= 1, положить т 1 и т р каждый длиной п 64. Затем приступить к выявлению первого допустимого поля в цикле по к. Если такое поле обнаружено, занести индексы /, у в массивы т { т р значение п = п + 1 - в и перейти к началу очередного цикла по к. Если же оно не обнаружено, изменить к = к + 1 и продолжить цикл.
В том случае, когда допустимое поле не будет обнаружено, следует перейти к замене полученного маршрута на лучший маршрут и вывести лучший маршрут и его длину. Блок-схема алгоритма построения маршрута приведена на рис. 1.46. Очевидно, что для хранения лучшего маршрута еще необходимы два массива индексов / и у - т п, т р длиной п
В заключение приведем укрупненную текстовую запись алгоритма поиска лучшего маршрута коня.
Шаг 1. Инициализировать обрамление доски.
Шаг 2. Положить / = -1.
Шаг 3. Установить /, у.
Шаг 4. Инициализировать доску.
Шаг 5. Положить п = 1, с1 (] = 1, к= 1.
Шаг 6. Если /:> 8, перейти к шагу 10.
Шаг 7. Положить / = / + / А, у = у + у*.
Шаг 8. Если ф о 0, положить к = к+ 1 и вернуться к шагу 6.
Шаг 9. Положить я = п + 1, т 1 = /, т у = у, к = 1 и вернуться к шагу 6.
Шаг 10. Если л > /, перейти к шагу 12.
Шаг 11. Заменить текущий маршрут (т; , т^) на лучший (т,„ т м).
Шаг 12. Положить /? = /?+ 1.
Шаг 13. Если И 64, вернуться к шагу 3.
Шаг 14. Вывести лучший маршрут и его длину /.
Шаг 15. Остановиться.
Задача 1.31. Рассмотрим еще одну задачу на шахматной доске. Требуется найти все варианты расстановки восьми ладей на доске так, чтобы они не били друг друга.
Тот, кто играет в шахматы, знает, что ладья бьет любую фигуру по вертикали и горизонтали. Поэтому ладьи не должны быть расположены на одной вертикали и горизонтали. Два варианта расположения фигур показаны на рис. 1.47.
Рис. 1.47. Возможные допустимые варианты расположения ладей на доске
В шахматной нотации первый вариант записывается как а! Ь2 сЗ 64 е5 Гб g7 Й8, второй - как а 8 Ь 7 с 6 ф е 4 Т 3 g 2 й,. Из этих
записей легко видеть, что любой допустимый вариант расстановки ладей определяется перестановкой первых восьми чисел натурального ряда. В связи с тем, что число перестановок Р п = 1 2 3 ... п = я!, в данном случае будем иметь Р% = I х х2-3-4-5-6-7-8 = 8! = 40 320 вариантов допустимых размещений ладей на доске. Для того чтобы получить все эти расстановки, необходимо сконструировать алгоритм построения всех перестановок п чисел натурального ряда. Известно несколько таких алгоритмов. Простейший из них рассмотрим на построении всех перестановок первых трех чисел натурального ряда 1, 2, 3.
Идея алгоритма состоит в последовательном вращении последовательности всех указанных чисел до тех пор, пока не будут получены все перестановки. Вращение начинают с первой перестановки 123 и продолжают до тех пор, пока не получат исходную перестановку. Таким образом, в данном случае будем иметь три перестановки. Очередная перестановка 123 1 будет повторять первоначальную перестановку. Чтобы фиксировать этот момент, необходимо все время сравнивать число вращаемых чисел (в данном случае 3) с последним числом перестановки и когда они совпадут, перейти к очередному действию алгоритма. Очередное действие состоит в проверке, равно ли число вращаемых чисел, в данном случае 3, двум. Если это так, все количество перестановок получено. Иначе уменьшается число вращаемых чисел на единицу и продолжается вращение, в данном случае первых двух чисел. Получаем перестановку 213. Сравниваем 2 с последним числом перестановки 3. Они не равны. Восстанавливаем число вращаемых чисел до 3 и вращаем перестановку 213. Получаем 132. Сравниваем число вращаемых чисел 3 с последним числом 2. Они по-прежнему не равны. Вращаем 132 и получаем 321. Дальнейшее вращение перестановки 321 дает 213 , т. е. перестановку, которая уже была получена в начале второго этапа вращений. Сравниваем число вращаемых чисел 3 с двойкой. Они не равны. Уменьшаем число вращаемых чисел до двух и вращаем первых два числа в перестановке 213. Получаем 123, сравниваем число вращаемых чисел 2 с последним числом вращаемых чисел 2. Они равны. Далее сравниваем число вращаемых чисел 2 с двойкой и заканчиваем построение перестановок. Все перестановки построены. Они приведены ниже. Повторяющиеся перестановки заключены в прямоугольники.
Пусть 1,2, ..., п - последовательность чисел натурального ряда; т - количество вращаемых чисел в перестановке; к - последнее число вращаемой перестановки. С учетом этих обозначений блок-схема алгоритма построения всех перестановок п чисел натурального ряда будет такой (рис. 1.48).
На рис. 1.49 изображены фрагменты алгоритма «сформировать перестановку 1, 2, ..., п» и «произвести вращение первых т чисел в последней перестановке», где Р, - /"-е число в перестановке.
Задача 1.32. Рассмотрим следующую задачу. На закрытом интервале [а , Ь задана унимодальная функция у = /(х), х е [а, Ь.
Требуется сконструировать алгоритм поиска точки х* е [а, Ь, которая доставляет наибольшее значение функции у*.
Прежде чем приступить к решению этой задачи, напомним, что функция унимодальна, если она одногорбая. Различные виды унимодальной функции представлены на рис. 1.50.
То обстоятельство, что унимодальная функция одногорбая, позволяет по двум различным точкам х 2 , х 2 е [а, Ь ] определить интервал а, Ь, которому принадлежит х*. Различные варианты соотношений /(х,) (х 2), /(х,) >/(х 2), /(х,) =/(х 2) выделяют свои подынтервалы [х, Ь], [а, х 2 ], [х, х 2 ], которым принадлежит х*. Все они меньше первоначального интервала [а, Ь. Для наглядности на рис. 1.51 эти подынтервалы заштрихованы.
Унимодальность функции у=/(х) и возможность вычислять ее в двух точках х, х 2 позволяют построить следующую процедуру поиска х* с определенной погрешностью?. Возьмем точку х = (а + Ь)/ 2, делящую интервал [а , Ь ] пополам. Сместимся влево
Рис. 1.48. Блок-схема алгоритма построения всех перестановок п чисел
натурального ряда
Рис. 1.49.
от нее и вправо на расстояние е/2, т. е. получим точки х, = = х - е/2, х 2 = х + е/2, где е - малое расстояние между этими точками, равное принятой погрешности вычисления х*. В точках х 1? х 2 вычислим значения функции у, у 2 . Если у, то х* находится в интервале [х |} Ь. Если у, >у 2 , то х* находится в интервале [а, х 2 . Если же у, = у 2 , то точка х - это значение х*, найденное с погрешностью е. В связи с этим процедуру считаем завершенной. В противном случае полагаем х, = а или х 2 = Ь и приступаем к делению пополам интервала [х, Ь] или [а, х 2 ] с дальнейшим получением изложенным способом точек х, х 2 , вычислением у, у 2 , сравнением их между собой и остановкой в случае у х = у 2 или
продолжением дальнейшего деления. Процесс завершаем в том случае, когда будет получен интервал
Заметим, что после первого деления мы переходим к оче-
редному интервалу длиной
Рис. 1.50. Унимодальные функции:
а - выпуклая; б - непрерывная негладкая; в - негладкая с разрывами
конечного ряда
а - Ь е
- -- + - , после второго перходим
к интервалу длиной
третьего деления - к интервалу длиной
а-Ь (2 3 -1)7
а - Ь 3
- -+ - с.
а - Ь 3
- - + -Є
а - Ь | 7
- - + - 8 -
є. Таким образом, после п деле-
ний исходного интервала [а , Ь ] будет получен интервал длиной а-Ь (2"-1)
є. Откуда при заданных значениях а, Ь, є мож-
но вычислить значение п, показывающее, сколько делений [а, Ь ] нужно выполнить, чтобы получить заданную точность.
Блок-схема алгоритма, реализующая эту процедуру, приведена на рис. 1.51. Описанный метод поиска наибольшего значения
Ввести а, Ь, с
Х -Х-е/2, Х2=Х+е/2
x*=x,y=f(x)
Вывести * * X ,у
Рис. 1.51. Блок-схема алгоритма поиска наибольшего значения унимодальной
функции методом половинного деления
унимодальной функции известен под названием метода половинного деления, или дихотомии. Существуют, однако, более эффективные методы решения этой задачи. Это методы золотого сечения и Фибоначчи.
Рассмотрим простейший из них - метод золотого сечения.
Согласно этому методу вначале вычисляются два значения функции х, х 2 , как и в методе дихотомии. Затем в полученном подинтервале [х, Ь] от точки х 2 вправо откладывается величина |х 2 - х, | и вычисляется значение функции в точке х 2 +|х 2 - х, |.
Если в результате первых двух вычислений функции в точках х, х 2 получен интервал неопределенности [а, х 2 ], от точки х, влево откладывается величина Х[ - х 2 и вычисляется функция в точке х, - | х, -х 2 |. Процесс продолжается до тех пор, пока не будет
достигнута заданная точность сокращения интервала. Схематично он показан на рис. 1.52.
Рис. 1.52.
методом золотого сечения
Метод получил название от известного с древности способа деления интервала а, Ь точкой с на две неравные части так, что отношение всей длины интервала к длине большей части равно отношению длины большей части к длине меньшей части. В данном случае интервал неопределенности [х, Ь ] или [а, х 2 ] делится точкой х, или х 2 именно в таком отношении.
По схематично описанной процедуре легко построить алгоритм вычисления наибольшего значения унимодальной функции, что и будет предложено в п. «Задачи для самостоятельного решения».
Урок информатики 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 : Напишите программу для создания орнамента
ТЕХНОЛОГИЧЕСКАЯ КАРТА КОНСТРУИРОВАНИЯ УРОКА
Тема урока – Алгоритмическая конструкция «Повторение»
Планируемые образовательные результаты
Предметные
Метапредметные
Личностные
получение представлений об алгоритмической конструкции «повторение(цикл)»; видах циклов, умений исполнять алгоритм содержащий цикл с заданным условием работы; умений составлять простые (короткие) алгоритмы с повторением для формального исполнителя с заданной системой команд;
умение выделять алгоритмы с повторением в различных процессах;
развитие алгоритмического мышления, необходимого для профессиональной деятельности в современном обществе
Словарь урока: алгоритм, повторение, циклический алгоритм, тело цикла.
Ресурсы урока: ПК подключенные к Интернет, мультимедийный проектор, экран, интерактивная доска, презентация, среда программирования Кумир.
ОРГАНИЗАЦИОННАЯ СТРУКТУРА УРОКА «ОТКРЫТИЯ» НОВОГО ЗНАНИЯ
Деятельность учителя
Деятельность обучающихся
Предметные
1 этап. Орг. момент
Здравствуйте, ребята! На каждом уроке мы с вами продвигаемся в открытиях новых знаний по информатике. С хорошим настроением начинаем работать. Я желаю вам успеха.
Дети рассаживаются по местам. Проверяют наличие принадлежностей.
Взаимодействие с учителем
Умение настраиваться на занятие
2 этап.
Актуализация знаний:
- Проверка домашней работы (у доски),
- Устное повторение
(пока идет работа у доски, затем сверка написанного на доске с шаблоном ответов)
Деятельность учителя
§ 2.4.2 РТ. №135(б), 138(б), 140
Ответь на вопросы:
Какая алгоритмическая конструкция называется ветвлением?
В каких формах может быть записано ветвление?
Какие команды используются для записи полной формы ветвления?
Какие команды используют для записи краткой формы ветвления?
Какие условия для организации ветвлений называют простыми? Составными?
Выполнение теста
Деятельность учащихся
Решают у доски
Отвечают на вопросы:
Конструкция, в которой выбор действий зависит от конкретного условия;
В полной и в краткой форме:
Если, то, иначе, все
Если, то, все.
Условия, состоящие из одной логической операции, называют простыми, а из нескольких – составными.
Знать: алгоритмические конструкции «следование» и «ветвление» .
Уметь составлять алгоритм ветвления
Поиск и выделение необходимой информации.
Умение с достаточной полнотой и точностью выражать свои мысли в соответствии с заданием.
Отличать верно выполненное задание от неверного.
3 этап.
Мотивация (создание проблемной ситуации)
Целеполагание
и планирование
- В строке без пробелов найди и удали понятия, не связанные с информатикой.
Удалив лишние понятия, вы получили ключевые понятия нашего урока.
Сформулируйте на их основе тему урока:
Так какова будет тема урока?
Тема урока:
Цели урока:
Узнать:
Познакомиться:
Научиться:
Удаляют: хромосома, суффикс, мел, глобус, числовой луч, теорема, вес, склонение, масштаб, перемещение
Повторение, циклический алгоритм, заданное условие работы.
Алгоритмическая конструкция «повторение».
Что такое «повторение» и почему его называют циклом?
С видами циклов;
Исполнять и составлять циклические алгоритмы с заданным условием продолжения работы.
Уметь форматировать символы (шрифт, размер, начертание, цвет) и абзацы (выравнивание, отступ первой строки, междустрочный интервал и др.).
Коммуникативные УУД:
Личностные УУД:
- формирование логического мышления
Регулятивные УУД:
Умение ставить учебную задачу, называть цель, формулировать тему в соответствии с нормами русского языка
4 этап. «Открытие» нового знания
(изучение новой темы)
Давайте узнаем, что такое «повторение» и почему его называют циклом?
Сделайте записи в тетрадях.
Познакомься с видами циклов (работа в паре)
Самопроверка с комментариями учителя:
Какие отличия вы увидели в записи 3-х циклических алгоритмов?
Вот первый алгоритм. Назовите его существенное отличие.
Как бы вы назвали цикл с таким условием?
Посмотрите на второй алгоритм, какое название вы ему придумали на основе анализа?
Посмотрите на третий алгоритм, какое название вы ему придумали на основе анализа?
Смотрят видео.
Записывают основное:
- повторение – это алгоритмическая конструкция действий, выполняемых многократно. Алгоритм с повторениями называют циклическим. Многократно повторяющиеся действия – телом цикла. Шаблон записи цикла нц тело цикла кц.
Работают в паре, выделяют существенные отличия в записях различных циклических алгоритмов.
Мы видим, что у этих алгоритмов разные условия окончания работы и немного отличается порядок записи.
Он будет выполняться пока условие не выполниться.
Цикл с заданным условием продолжения работы;
Цикл с заданным числом повторений;
Цикл с заданным условием окончания работы.
Получить понятие о циклическом алгоритме и его видах.
Коммуникативные УУД:
Развитие навыков общения со сверстниками и взрослыми в процессе деятельности.
Познавательные УУД:
- развитие познавательной активности
Личностные УУД:
- развитие внимания
- формирование навыков создания структурированного конспекта
5 этап. Включение нового знания в систему знаний (закрепление)
Самостоятельная работа + взаимопроверка;
- Компьютерный практикум
Научись выполнять алгоритм с заданным условием продолжения работы
Научись составлять алгоритмы с заданным условием продолжения работы для исполнителя Чертежник
Выполняют самостоятельно РТ. №151(а), проводят взаимопроверку
Работают в системе Кумир РТ. №150(а, в)
Закрепить понятие о цикле с заданным продолжением работы
Уметь составить алгоритм
Познавательные УУД:
- формирование знаниевой компоненты по теме урока
Коммуникативные УУД:
Развитие навыков общения со сверстниками и взрослыми в процессе деятельности.
Регулятивные УУД:
- умение использовать полученные знания на практике, развитие способности критической оценки собственной деятельности.
6 этап. Рефлексия и оценивание
Можете ли вы назвать тему урока?
Вам было легко или были трудности?
Что у вас получилось лучше всего и без ошибок?
Какое задание было самым интересным и почему?
Как бы вы оценили свою работу?
Отвечают на вопросы, подсчитывают баллы, выставляют оценки
7 этап. Домашнее задание
§ 2.4.3 С. 81- 84 РТ. №148, 151(в)
Задание творческого характера:
Приведите примеры циклического алгоритма из:
Повседневной жизни
Из литературного произведения
