Алгоритм, содержащий цикл и ветвление
Термин «алгоритм», впервые употребленный в современном значении. Лейбницем (1646–1716), является латинизированной формой имени великого персидского математика Мухаммеда бен Муссы аль-Хорезми (ок. 783 – ок. 850). Его книга «Об индийском счете» в XII в. была переведена на латинский язык и пользовалась широкой популярностью не одно столетие. Имя автора европейцы произносили как Алгоритми (Algorithmi), и со временем так стали называть в Европе всю систему десятичной арифметики.
Научное определение алгоритма дал А. Чёрч в 1930 году. В наше время понятие алгоритма является одним из основополагающих понятий вычислительной математики и информатики.
Алгоритм — это точное и полное описание последовательности действий над заданными объектами, позволяющее получить конечный результат.
Можно сказать, что алгоритм решения какой-либо задачи — это последовательность шагов реализации (или нахождения) этого решения, а процесс построения алгоритма (алгоритмизация) — разложение задачи на элементарные действия или операции.
Область математики, известная как теория алгоритмов, посвящена исследованию свойств, способов записи, области применения различных алгоритмов, а также созданию новых алгоритмов. Теория алгоритмов находит широкое применение в различных областях деятельности человека — в технике, производстве, медицине, образовании и т. д. Появление компьютера позволило решать чрезвычайно сложные, трудоемкие задачи.
Определение алгоритма для применения в области информатики нуждается в некотором уточнении. Во-первых, решение задач в информатике всегда связано с преобразованием информации, а значит, исходными данными и результатом работы алгоритма должна быть информация. Это может быть представлено в виде схемы.
Во-вторых, алгоритмы в информатике предназначены для реализации в виде компьютерных программ или для создания некоторой компьютерной технологии. Для выполнения алгоритма требуется конечный объем оперативной памяти и конечное время.
Основные требования, предъявляемые к алгоритмам:
Дискретность (прерывность): алгоритм должен представлять решение задачи в виде последовательности простых (или ранее определенных) этапов (шагов). Каждый шаг алгоритма формулируется в виде инструкций (команд).
Определенность (детерминированность; лат. determinate — определенность, точность): шаги (операции) алгоритма должны допускать однозначную трактовку и быть понятными для исполнителя алгоритма. Это свойство указывает на то, что любое действие в алгоритме должно быть строго определено и описано для каждого случая.
Массовость: алгоритм должен давать решение не только для конкретного набора значений, а для целого класса задач, который определяется диапазоном возможных исходных данных (область применимости алгоритма). Свойство массовости подразумевает использование переменных в качестве исходных данных алгоритма.
Результативность: алгоритм должен давать конкретный результат, т. е. должны быть рассмотрены все возможные ситуации и для каждой из них получен результат. Под результатом может пониматься и сообщение о том, что задача решения не имеет.
Конечность: количество шагов алгоритма должно быть конечным.
Эффективность: количество шагов и сами шаги алгоритма должны быть такими, чтобы решение могло быть найдено за конечное и, более того, приемлемое время.
Для оценки и сравнения алгоритмов существует много критериев. Чаще всего анализ алгоритма (или, как говорят, анализ сложности алгоритма) состоит в оценке временных затрат на решение задачи в зависимости от объема исходных данных. Используются также термины «временная сложность», «трудоемкость» алгоритма. Фактически эта оценка сводится к подсчету количества основных операций в алгоритме, поскольку каждая из них выполняется за заранее известное конечное время. Кроме временной сложности, должна оцениваться также емкостная сложность, т. е. увеличение затрат памяти в зависимости от размера исходных данных. Оценка сложности дает количественный критерий для сравнения алгоритмов, предназначенных для решения одной и той же задачи. Оптимальным (наилучшим) считается алгоритм, который невозможно значительно улучшить в плане временных и емкостных затрат.
Анализом сложности алгоритмов, исследованием классов задач, решаемых с помощью алгоритмов той или иной сложности, и многими другими теоретическими вопросами занимается специальная область информатики.
Алгоритмы можно представлять как некоторые структуры, состоящие из отдельных базовых элементов.
Логическая структура любого алгоритма может быть представлена комбинацией трех базовых структур:
- следование — образуется из последовательности действий, следующих одно за другим;
- ветвление (развилка) — обеспечивает в зависимости от результатов проверки условия (ДА или НЕТ) выбор одного из альтернативных путей алгоритма;
- цикл — обеспечивает многократное выполнение некоторой совокупности действий, которая называется телом цикла.
Для описания алгоритмов наиболее распространены следующие методы (языки):
Обычный язык. Изложение алгоритма ведется на обычном языке с разделением на последовательные шаги.
Блок-схемы. Графическое изображение алгоритма с помощью специальных значков-блоков.
Формальные алгоритмические языки (языки программирования). При записи алгоритмов используют строго определенный набор символов и составленных из них специальных зарезервированных слов. Имеют строгие правила построения языковых конструкций.
Псевдокод. Синтез алгоритмического и обычного языков. Элементы некоторого базового алгоритмического языка используются для строгой записи базовых структур алгоритма.
Словесный способ (запись на обычном языке) не имеет широкого распространения, т. к. таких описаний есть ряд недостатков:
- строго не формализуемы;
- достаточно многословны;
- могут допускать неоднозначность толкования отдельных предписаний;
- сложные задачи с анализом условий, с повторяющимися действиями трудно представляются в словесной или словесно-формульной форме.
Графический способ представления информации является более наглядным и компактным по сравнению со словесным. При графическом представлении алгоритм изображается в виде последовательности связанных между собой функциональных блоков, каждый из которых соответствует выполнению одного или нескольких действий. Такое графическое представление алгоритма называется блок-схемой. Определенному типу действия (ввод/вывод данных, проверка условия, вычисление выражения, начало и конец алгоритма и т. п.) соответствует определенная геометрическая фигура — блочный символ. Блоки соединяются между собой линиями переходов, которые определяют очередность выполнения действий.
| Название символа | Графическое изображение | Комментарии |
| Пуск/Останов (блоки начала и конца алгоритма) |  |
Указание на начало или конец алгоритма |
| Ввод/Вывод данных (блоки ввода, вывода |  |
Организация ввода/вывода в общем виде |
| Процесс (операторные блоки) |  |
Выполнение вычислительного действия или последовательности действий (можно объединять в один блок), которые изменяют значение, форму представления или размещение данных |
| Условие (условный блок) |  |
Выбор направления выполнения алгоритма. Если условие, записанное внутри ромба, выполняется, то управление передается по стрелке «да», в противном случае — по стрелке «нет». Таким образом, реализуется процесс изменения последовательности вычислений в зависимости от выполнения условия |
| Начало цикла с параметром |  |
Используется для организации циклических конструкций с известным количеством итераций (повторений) и известным шагом изменения параметра цикла. Внутри блока для параметра цикла указываются через запятую его начальное значение, конечное значение и шаг изменения. Цикл, для которого неизвестно количество повторений, записывается с помощью условного и операторных блоков |
| Предопределенный процесс |  |
Используется для указания обращений к вспомогательным алгоритмам, существующим автономно в виде некоторых самостоятельных модулей, и для обращения к библиотечным подпрограммам |
| Печать сообщений (документ) |  |
Вывод результатов на печать |
При составлении блок-схемы необходимо проверять выполнение следующих условий:
- из каждого прямоугольника и параллелограмма (кроме конца алгоритма) должна выходить только одна стрелка;
- в каждый прямоугольник и параллелограмм (кроме начала алгоритма) должна входить хотя бы одна стрелка;
- в каждый ромб должна входить хотя бы одна стрелка, а выходить из него — две стрелки, помеченные словами «ДА» и «НЕТ».
Псевдокод занимает промежуточное положение между естественным языком и языками программирования. В псевдокоде не приняты строгие синтаксические правила для записи команд, что отличает формальные языки программирования. Однако в псевдокоде есть некоторые конструкции, которые присущи формальным языкам, что облегчает переход от записи алгоритма на псевдокоде к записи алгоритма на языке программирования. Псевдокоды бывают разные. Рассмотрим учебный (школьный) алгоритмический язык АЯ.
Алфавит учебного алгоритмического языка является открытым. В него могут быть введены любые понятные всем символы: русские и латинские буквы, знаки математических операций, знаки отношений, специальные знаки и т. д. Кроме алфавита, в алгоритмической нотации определяются служебные слова, которые являются неделимыми. Служебные слова обычно выделяются жирным шрифтом или подчеркиванием. К служебным словам относятся:
| алг — заголовок алгоритма | нц — начало цикла | знач |
| нач — начало алгоритма | кц — конец цикла | и |
| кон — конец алгоритма | дано | или |
| арг — аргумент | надо | не |
| рез — результат | если | да |
| цел — целый | то | нет |
| сим — символьный | иначе | при |
| лит — литерный | всё | выбор |
| лог — логический | пока | утв |
| вещ — вещественный | для | ввод |
| таб — таблица | от | вывод |
| длин — длина | до |
Общий вид записи алгоритма на псевдокоде:
алг — название алгоритма (аргументы и результаты)
дано — условие применимости алгоритма
надо — цель выполнения алгоритма
нач — описание промежуточных величин
последовательность команд (тело алгоритма)
Часть алгоритма от слова алг до слова нач называется заголовком, а часть, заключенная между словами нач и кон, — телом алгоритма (исполняемой частью алгоритма).
В предложении алг после названия алгоритма в круглых скобках указываются характеристики (арг, рез) и тип значения (цел, вещ, сим, лит или лог) всех входных (аргументы) и выходных (результаты) переменных. При описании массивов (таблиц) используется служебное слово таб, дополненное именем массива и граничными парами по каждому индексу элементов массива.
Команды учебного языка:
1. Оператор присваивания, который обозначается «:=» и служит для вычисления выражений, стоящих справа, и присваивания их значений переменным, указанным в левой части. Например, если переменная а имела значение 5, то после выполнения оператора присваивания а := а + 1, значение переменной а изменится на 6.
2. Операторы ввода/вывода:
ввод (список имен переменных)
вывод (список вывода)
Список вывода может содержать комментарии, которые заключаются в кавычки.
3. Оператор ветвления (с использованием команды если. то… иначе…всё; выбор);
4. Операторы цикла (с использованием команд для, пока, до).
Запись алгоритма на псевдокоде:
Здесь в предложениях дано и надо после знака «|» записаны комментарии. Комментарии можно помещать в конце любой строки, они существенно облегчают понимание алгоритма.
При записи алгоритма в словесной форме, в виде блок-схемы или на псевдокоде допускается произвольное изображение команд. Вместе с тем такая запись позволяет понять человеку суть дела и исполнить алгоритм. Однако алгоритм, предназначенный для исполнения на компьютере, должен быть записан на строго формализованном языке. Такой язык называется языком программирования, а запись алгоритма на этом языке — компьютерной программой.
Для решения одной и той же задачи можно предложить несколько алгоритмов. Алгоритмы составляются с ориентацией на определенного исполнителя алгоритма. У каждого исполнителя имеется свой конечный набор команд, которые для него понятны и исполняемы. Этот набор называется системой команд исполнителя. Пользуясь системой команд, исполнитель может выполнить алгоритм формально, не вникая в содержание поставленной задачи. От исполнителя требуется только строгое выполнение последовательности действий, предусмотренной алгоритмом. Таким образом, в общем случае алгоритм претерпевает изменения по стадиям:
- первая стадия — алгоритм должен быть представлен в форме, понятной человеку, который его разрабатывает;
- вторая стадия — алгоритм должен быть представлен в форме, понятной исполнителю алгоритма (вторая стадия может отсутствовать, если исполнять алгоритм будет сам разработчик).
Примеры решения задач
Пример 1. Исполнитель Утроитель может выполнить только две команды, которым присвоены номера:
Первая команда уменьшает число на 1, вторая — увеличивает его втрое.
Написать набор команд (не более пяти) получения из числа 3 числа 16. В ответе указать только номера команд.
Ответ: 13311
Пример 2. Имеется Исполнитель алгоритма, который может передвигаться по числовой оси.
Система команд Исполнителя алгоритма:
1. «Вперед N» (Исполнитель алгоритма делает шаг вперед на N единиц).
2. «Назад M» (Исполнитель алгоритма делает шаг назад на M единиц).
Переменные N и M могут принимать любые целые положительные значения. Известно, что Исполнитель алгоритма выполнил программу из 50 команд, в которой команд «Назад 2» на 12 больше, чем команд «Вперед 3». Других команд в программе не было. Какой одной командой можно заменить эту программу, чтобы Исполнитель алгоритма оказался в той же точке, что и после выполнения программы?
1. Найдем, сколько было команд «Вперед», а сколько «Назад». Учитывая, что общее количество команд равно 50 и что команд «Назад» на 12 больше, чем команд «Вперед». Получим уравнение: x + (x + 12) = 50, где x — количество команд «Вперед». Тогда общее количество команд «Вперед»: x = 19, а количество команд «Назад»: 19 + 12 = 31.
2. Будем вести отсчет от начала числовой оси. Выполнив 19 раз команду «Вперед 3», Исполнитель алгоритма оказался бы на отметке числовой оси 57 (19 * 3 = 57). После выполнения 31 раз команды «Назад 2» (31 * 2 = 62) он оказался бы на отметке –5 (57 – 62 = –5).
3. Все эти команды можно заменить одной — «Назад 5».
Ответ: команда«Назад 5».
Пример 3. Черепашка является исполнителем для создания графических объектов на рабочем поле. При движении Черепашка оставляет след в виде линии. Черепашка может исполнять следующие команды:
| Название команды | Параметр | Действия исполнителя |
| вп | Число шагов | Продвигается в направлении головы на указанное число шагов |
| нд | Число шагов | Продвигается в направлении, противоположном направлению головы на указанное число шагов |
| пр | Число градусов | Поворачивается направо относительно направления, заданного головой черепашки |
| лв | Число градусов | Поворачивается налево относительно направления, заданного головой черепашки |
Для записи повторяющихся действий (цикла) используется команда Повтори. В этой команде два параметра: первый задает количество повторений (итераций), а второй — список команд которые должны повторяться (тело цикла); список заключается в квадратные скобки.
Записать для исполнителя Черепашка алгоритмы:
а) построения квадрата со стороной 100;
б) построения правильного шестиугольника со стороной 50.
в) построения изображения цифры 4, если голова Черепашки смотрит на север.
Ответ: а) Повтори 4 [вп 100 пр 90]; б) Повтори 6 [вп 50 пр 360/6]; в) вп 100; повтори [лв 135 вп 50].
Пример 4. Два игрока играют в следующую игру (это вариант восточной игры). Перед ними лежат три кучки камней, в первой из которых 2, во второй — 3, в третьей — 4 камня. У каждого игрока неограниченно много камней. Игроки ходят по очереди. Ход состоит в том, что игрок или удваивает число камней в одной из кучек, или добавляет по два камня в каждую из них. Выигрывает игрок, после хода которого либо в одной из кучек становится не менее 15 камней, либо общее число камней в трех кучках становится не менее 25. Кто выиграет при безошибочной игре обоих игроков — игрок, делающий первый ход, или игрок, делающий второй ход? Каким должен быть первый ход выигрывающего игрока? Ответ следует обосновать.
Решение. Удобнее всего составить таблицу возможных ходов обоих игроков. Заметим, что в каждом случае возможны всего четыре варианта хода. В таблице курсивом выделены случаи, которые сразу же приносят поражение игроку, делающему этот ход (например, когда камней в какой-либо кучке становится больше или равно 8, другой игрок непременно выигрывает следующим ходом, удваивая количество камней в этой кучке). Из таблицы видно, что при безошибочной игре обоих игроков первый всегда выиграет, если первым ходом сделает 4, 5, 6. У второго игрока в этом случае все ходы проигрышные.
| 1-й ход | 2-й ход | |||
| Начало | 1-й игрок | 2-й игрок | 1-й игрок | 2-й игрок |
| 2,3,4 | 4,3,4 | 8,3,4 | выигрыш | |
| 4,6,4 | 8,6,4 | выигрыш | ||
| 4,12,4 | выигрыш | |||
| 4,6,8 | выигрыш | |||
| 6,8,6 | выигрыш | |||
| 4,3,8 | выигрыш | |||
| 6,5,6 | 12,5,6 | выигрыш | ||
| 6,10,6 | выигрыш | |||
| 6,5,12 | выигрыш | |||
| 8,7,8 | выигрыш | |||
| 2,6,4 | 4,6,4 | 8,6,4 | выигрыш | |
| 4,12,4 | выигрыш | |||
| 4,6,8 | выигрыш | |||
| 6,8,6 | выигрыш | |||
| 2,12,4 | выигрыш | |||
| 2,6,8 | выигрыш | |||
| 4,8,6 | выигрыш | |||
| 2,3,8 | выигрыш | |||
| 4,5,6 | 8,5,6 | выигрыш | ||
| 4,10,6 | выигрыш | |||
| 4,5,12 | выигрыш | |||
| 6,7,8 | выигрыш | |||
Пример 5. Записано 7 строк, каждая из которых имеет свой номер. В нулевой строке после номера записана цифра 001. Каждая последующая строка содержит два повторения предыдущей строки и добавленной в конец большой буквы латинского алфавита (первая строка — A, вторая строка — B и т. д.). Ниже приведены первые три строкиєтой записи (в скобках указан номер строки):
Какой символ находится в последней строке на 250-м месте (считая слева направо)?
Примечание. Первые семь букв латинского алфавита: A, B, C, D, E, F, G.
Решение. Найдем длину каждой строки. Длина каждой следующей строки в два раза больше длины предыдущей плюс один символ, длина строк составит:
(6) 127*2+1=255 символов.
Так как задано 7 строк, а нумерация начинается с нулевой строки, последняя строка имеет номер 6 и содержит 255 символов. Последний символ в строке — F. Предпоследний элемент — E, далее идут символы D, C, B, A, 1 (по правилу формирования строк). Таким образом, 250-й символ — это 1.
Пример 6. Имеется фрагмент алгоритма, записанный на учебном алгоритмическом языке:
n := Длина(а)
b := Извлечь(а, k)
нц для i от 7 до n – 1
с := Извлечь(а, i)
b := Склеить(b, с)
Здесь переменные а, b, с — строкового типа; переменные n, i — целые.
В алгоритме используются следующие функции:
Длина(х) — возвращает количество символов в строке х. Имеет тип «целое».
Извлечь(х, i) — возвращает i-й символ слева в строке х. Имеет строковый тип.
Склеить(х, у) — возвращает строку, в которой находятся все символы строки х, а затем все символы строки у. Имеет строковый тип.
Какое значение примет переменная b после выполнения этого фрагмента алгоритма, если переменная а имела значение «ВОСКРЕСЕНЬЕ»?
Решение. Находим общее число символов в строке а, получим, что n = 11.
Выполняя команду b := Извлечь(а, k) при k = 2, получим, что b примет значение «О«.
В цикле последовательно, начиная с 7-го символа строки а и заканчивая предпоследним (n – 1), извлекаем символ из строки а и присоединяем к строке b.
В результате получим слово «ОСЕНЬ» (символы с номерами 2 + 7 + 8 + 9 + 10).
Ответ: «ОСЕНЬ«
Пример 7. Леонардо из Пизы, известный как Фибоначчи, был первым из великих математиков Европы позднего Средневековья. Числовой ряд, который называется его именем, получился в результате решения задачи о кроликах, которую Фибоначчи изложил в своей «Книге Абака», написанной в 1202 году. Он выглядит так:
1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144.
В этом ряду каждое следующее число, начиная с третьего, равно сумме двух предыдущих. Составить словесный алгоритм и блок-схему проверки принадлежности введенного числа n ряду Фибоначчи.
Решение. Словесный алгоритм:
- Ввести число n.
- Установить значение первых трех чисел Фибоначчи: 1, 1, 2 (сумма двух предыдущих чисел).
- Пока введенное число n больше очередного числа Фибоначчи, взять два последних числа Фибоначчи и получить из них новое число Фибоначчи.
- Если число Фибоначчи равно введенному n или было введено число n = 1, значит, что было введено число Фибоначчи, в противном случае — введенное число не является числом Фибоначчи.
Приведенный словесный алгоритм в пункте 1, 2 содержит начальные установки, в пункте 3 — цикл с условием, а пункт 4 — это вывод результата работы алгоритма.
F — текущее число ряда Фибоначчи;
F1 и F2 — два предыдущих числа ряда Фибоначчи для числа F;
n — число, для которого требуется определить, является ли оно числом из ряда Фибоначчи.
Использование основных алгоритмических конструкций: следование, ветвление, цикл
Логическая структура любого алгоритма может быть представлена комбинацией трех базовых структур: следование, ветвление, цикл.
Базовая структура СЛЕДОВАНИЕ указывает на то, что управление передается последовательно от одного действия к другому.
| Учебный алгоритмический язык | Язык блок-схем |
| действие 1 действие 2 … действие n |
 |
Использование исключительно этой структуры возможно лишь для достаточно простых задач, ход решения которых не меняется в зависимости от конкретных исходных данных и состоит в последовательном выполнении определенных операций.
В качестве примера рассмотрим решение простой задачи.
Пример. Найти y(x) = x2 + 3x + 5, используя только операции умножения и сложения.
Решение. На рис. приводятся два алгоритма, реализующие решение поставленной задачи.
Порядок вычисления y(x) в первом случае — обычный, а во втором — (x + 3) x + 5. Обе формулы эквивалентны, но в первом случае для вычисления необходимо 2 умножения, 2 сложения и 3 переменных (x, y, z), а во втором используются 1 умножение, 2 сложения и 2 переменные (x, y).
Приведенный пример показывает, что даже простые задачи могут решаться с помощью различных вариантов алгоритмов.
Обратите внимание, как в блоке следования используется оператор присваивания.
Операция присваивания — важнейшая операция во всех языках программирования. С помощью присваивания переменные получают новые значения: в левой части инструкции ставится идентификатор величины, а в правой части — выражение, значение которого можно определить.
В операторах присваивания используется либо привычный знак равенства, либо сочетание двоеточия и знака равенства «:=». Поскольку знак присваивания — это не знак равенства, возможны записи вида Х := Х + 1 или А := А – В. Нужно учитывать, что оператор присваивания будет выполняться только в том случае, если значения всех переменных правой части уже определены.
Базовая структура ВЕТВЛЕНИЕ (РАЗВИЛКА) используется в случае, когда выполнение программы может измениться в зависимости от результата проверки условия и пойти двумя разными (альтернативными) путями. Другими словами, условие является некоторым высказыванием (предикатом) и может быть истинным или ложным (принимать значение TRUE или FALSE). Каждый из путей ведет к общему выходу, так что работа алгоритма будет продолжаться независимо от того, какой путь будет выбран.
Различают две структуры этого типа — полную и неполную. В случае полной структуры, если условие выполняется (является истинным), вслед за ним выполняется действие 1, иначе — действие 2. В случае неполной структуры, если условие выполняется (является истинным), то вслед за ним выполняется действие 1, иначе ничего не происходит.
Важную роль в операторах ветвления играют содержащиеся в них условия. В простейшем случае условиями служат отношения между величинами. Условия с одним отношением называют простыми условными выражениями, или простыми условиями. В некоторых задачах необходимы более сложные условия, состоящие из нескольких простых, например условие А < X < С, т. е. Х < А и (Х >C) (возможна запись (Х < А) and (Х >C)). Объединение нескольких простых условий в одно образует составное условное выражение, или составное условие. Составные условия образуются с помощью логических операторов not (отрицание), and (логическое И), or (логическое ИЛИ), хоr (исключающее ИЛИ).
Структура ВЕТВЛЕНИЕ существует в четырех основных вариантах:
если — то (неполная структура);
если — то — иначе (полная структура);
выбор (неполный);
выбор — иначе (полный).
Циклы
Занятие 1. Циклические алгоритмы. Цикл с предусловием.
Очень многие алгоритмы, выполнение которых поручается компьютеру, по своей природе являются циклическими. И это не случайно, потому что человек обычно поручает машине рутинную работу, где нужно много считать, и счет производится по некоторым одинаковым правилам.
Определение . Цикл – это последовательность операторов, которая может выполняться более одного раза.
Определение . Циклический алгоритм – это алгоритм, содержащий один или несколько циклов.
Возьмем для примера задачу: найти сумму некоторого количества чисел, задаваемых пользователем.
Исходными данными в этом случае являются переменная N — количество чисел и сами эти числа. Значение очередного числа обозначим переменной Х. Результатом работы алгоритма станет сумма этих чисел, которую обозначим переменной S.
S = x 1 + x 2 + x 3 +. + x n
Допустимые значения переменной N должны удовлетворять условию n>0, так как количество слагаемых не может быть числом отрицательным.
Как же мы должны решать эту задачу? Сначала нужно запросить, сколько чисел нужно будет сложить и считать это число в переменную N. Затем нужно так организовать операторы, чтобы программа запрашивала очередное число и каждый раз складывала его с предыдущими; и повторяла эту группу операторов N раз.
На предыдущих занятиях при изучении оператора безусловного перехода мы знакомились с решением подобных задач. Но в языке Паскаль существуют более удобные конструкции для организации циклов:
• цикл с предусловием;
• цикл с постусловием;
• цикл со счетчиком.
Познакомимся с первым из них – оператором цикла с предусловием while .
Циклы с предусловием используются тогда, когда выполнение цикла связано с некоторым логическим условием. Оператор цикла с предусловием имеет две части: условие выполнения цикла и тело цикла.
При выполнении оператора while определенная группа операторов выполняется до тех пор, пока определенное в операторе while булево условие истинно. Если условие сразу ложно, то оператор не выполнится ни разу.
Общая форма записи следующая
На русском языке это звучит примерно так:
пока выполняется это условие делай
Вполне понятно, что операторные скобки ставят, чтобы отделить от остальной программы ту группу операторов, которую нужно повторить в цикле. Если в цикле нужно выполнить только один оператор, то операторные скобки не ставят.
При использовании цикла с предусловием надо помнить следующее:
1) значение условия выполнения цикла должно быть определено до начала цикла;
2) если значение условия истинно, то выполняется тело цикла, после чего повторяется проверка условия. Если условие ложно, то происходит выход из цикла;
3) хотя бы один из операторов, входящих в тело цикла, должен влиять на значение условия выполнения цикла, иначе цикл будет повторяться бесконечное число раз.
Вернемся к нашей задаче вычисления суммы чисел. При вычислении суммы используем следующий прием: вначале, когда еще не задано ни одно слагаемое, сумму полагают равной нулю (S:=0), а затем, получая очередное слагаемое, прибавляют его к сумме (S:=S+x) (см. программу ниже).
Очень важное значение в операторе цикла имеет так называемая переменная цикла. В нашей программе она называется i. С ее помощью мы обращаемся к пользователю за очередным числом (write (‘Введите ‘,i,’-ое число ’)) и считаем количество уже введенных чисел (i:=i+1), чтобы не запросить лишнее. Одновременно переменная цикла участвует в булевом выражении (i<=N).
Рассмотрите внимательно программу, решающую нашу задачу.
write (‘Сколько чисел для сложения? ‘);
write (‘ Введите ‘,i,’- е число ’);
write (‘Сумма введенных чисел равна ‘,s:5:2);
Хотелось бы, чтобы Вы смогли представить работу этой программы. Давайте попробуем вместе.
Пусть нам требуется сложить следующие числа: 5, 7, -4, 0, 8, 20. Посчитаем, сколько их всего – шесть. Это число мы введем, когда программа задаст вопрос: Сколько чисел для сложения? Теперь наша программа запросит ввести 1-ое число, т. к. на первом шаге переменная i равна 1. Мы введем число 5. Программа считает его в переменную х. Теперь число 5 сложим с числом 0 и результат присвоим переменной S (оператор S:=S+x). В этот момент S становится равной 5. Чтобы перейти к следующему числу, увеличим значение переменной i на 1 (оператор i:=i+1). Выполнение операторов тела цикла закончено. Теперь программа переходит опять к анализу условия вхождения в цикл (i<=N). Переменная цикла i=2, переменная N=6, поэтому значение логического условия 2<=6 равно True. Значит снова выполняется тело цикла:
write (‘Введите ‘,i,’-ое число ’);
Итак, мы сложили два числа и переходим опять к проверке условия. Ответим на вопрос: 3
write (‘Введите ‘,i,’-ое число ’);
Аналогично, мы сложим и остальные числа. Но когда же операторы цикла выполнятся последний раз и остановится работа цикла? Когда сложим последнее число. Проверим это.
write (‘Введите ‘,i,’-ое число ’);
В этом примере известно заранее количество повторений — N раз. Но чаще всего этот вид цикла используется тогда, когда количество повторений заранее не известно и зависит от выполнения какого-либо условия. Рассмотрим еще один пример.
Отвлечемся от цифр и вспомним окружающую жизнь. Сколько циклических алгоритмов можно увидеть вокруг, если внимательно посмотреть на события: чередование времен года, посещения магазинов, школы или секции, получение за контрольные оценок и др. Попробуем записать их.
Например, рассмотрите следующие циклические алгоритмы
а) Пока не сдал выпускные экзамены делай
б) Пока есть желание, возможность и здоровье делай
посещай занятия спортом
Задание . Выберите самостоятельно сказку из предложенных (или придумайте другой циклический алгоритм из жизни или произведений известных авторов) и напишите программы, с помощью которых можно в шутливой форме проверить знания первоклассников.
а) “Репка”. “Дед тянет-потянет, вытянуть не может. Позвал бабку. Бабка за дедку , дедка за репку, тянут потянут, вытянуть не могут. Позвала бабка внучку. И вытянули репку”.
б) “Курочка ряба”. “Снесла курочка яичко. Дед бил, бил, не разбил. Баба била, била, не разбила. Мышка бежала, хвостиком задела, яичко упало и разбилось”.
в) “Колобок”. “. Катится колобок по лесу. От зайца ушел, от медведя ушел, от волка ушел. Встретил лису, она его и съела”.
г) “Волк и лиса”. “. Сидит волк у проруби, хвост в воду опустил и приговаривает: “Ловись, ловись, рыбка, большая и маленькая”. Пришла за водой баба. Прогнала волка.
д) “Горшочек каши”. “. Варит горшок кашу, варит. Каша из дома на улицу потекла. Не знает мать девочки, что надо горшочку сказать. Пришла девочка, сказала: “Горшочек, не вари”. Перестал горшок кашу варить”.
Цикл с предусловием.
Продолжим изучение цикла с предусловием на примере решения следующей задачи.
Задача . Найти сумму чисел в непустой последовательности.
Рассмотрим алгоритм решения. Пусть нам дана такая последовательность чисел:
3, -4, 0, 5, 19, -20, 6, 2
Для работы нам нужно организовать обращение к каждому элементу последовательности. Нетрудно догадаться, что это будет происходить через порядковый номер каждого члена последовательности. Пронумеруем эти числа:
1 2 3 4 5 6 7 8
3, -4, 0, 5, 19, -20, 6, 2
Получилось, что всего у нас чисел восемь, на первом месте стоит число 3, на втором — число (-4), на третьем — число 0 и т.д. Тогда переменная цикла i будет пробегать числа от 1 до 8, становясь на каждом шаге больше на 1 и запрашивая каждый раз очередное число. Поэтому общая схема цикла будет выглядеть так:
write (‘Введите ‘,i,’-ое число’);
Здесь N — количество чисел последовательности (в нашем случае 8), х — член последовательности, i — порядковый номер очередного члена последовательности. Просмотрим, как будет работать этот цикл.
write (‘Введите ‘, i ,’-ое число’);
write (‘Введите ‘, i ,’-ое число’);
write (‘Введите ‘, i ,’-ое число’);
write (‘Введите ‘, i ,’-ое число’);
Итак, у нас уже организован цикл считывания чисел. Осталось только вписать в тело цикла оператор, который бы суммировал все эти числа. Для этого опишем переменную Summa в разделе описания переменных и присвоим ей нулевое значение перед выполнением цикла. Тогда при каждом шаге нашего цикла значение этой переменной должно быть изменено на х. Это произойдет при выполнении оператора
Summa := Summa + x ;
Если Вам не совсем понятно, что происходит при выполнении этого оператора, Вам нужно вспомнить, как происходит присваивание значение переменной: сначала вычисляется значение выражения в правой части (в нашем случае Summa+x, т.е, значение переменной Summa увеличиваем на х), а затем присваиваем это значение переменной с именем, записанным в левой части (Summa). Таким образом, в переменной Summa собирается сумма всех считанных чисел.
Задание . Напишите полный текст программы, находящей сумму N чисел последовательности. Дополните программу нахождением среднего арифметического этих чисел.
Примечание . Средним арифметическим чисел называется сумма этих чисел, деленная на их количество.
Задачи для самостоятельного решения
1. Построить и записать в виде программы алгоритм вычисления суммы квадратов десяти произвольных чисел, водимых с клавиатуры в процессе выполнения программы.
2. Вводятся 15 чисел. Определить, сколько среди целых чисел.
3. Вывести все чётные числа начиная с числа N и до числа M. Числа N и M задает пользователь.
4. Составить программу, проверяющую, является ли последовательность из 10 целых чисел, вводимых с клавиатуры, возрастающей.
5. Составить программу, печатающую все делители целого числа в порядке возрастания.
6. Составить программу нахождения суммы чётных чисел, находящихся в промежутке от 26 до 88.
7. Найти наибольший общий делитель двух натуральных чисел a и b.
8. Спортсмен в первый день пробежал 10 км. Каждый следующий день он увеличивал норму на 10% от нормы предыдущего дня.
а) Определить через сколько дней спортсмен пробежит суммарный путь более 100 км.
б) Определить через сколько дней спортсмен будет пробегать более 20 км.
в) Какой путь пробежит спортсмен на 7-й день.
9. Вводятся 14 чисел. Определить, сколько среди них положительных (включая 0) и сколько отрицательных. (Числа вводятся в одну переменную в цикле)
10. Запросите 16 чисел и выведите на экран для каждого, делится ли оно нацело на 11. Спросите у пользователя, сколько нужно проанализировать чисел, а затем запросите эти числа и сделайте для каждого вывод, является ли оно четным или отрицательным.
12. Найдите сумму следующей последовательности
а 1 +а 2 -а 3 +а 4 -. +а n , где n — количество элементов, задаваемых пользователем.
13. Составить программу, печатающую все делители целого числа в порядке убывания.
14. Вывести на экран числа, кратные К из промежутка [А,В]. Числа А, В, К задает пользователь.
15. Запросите у пользователя положительное число А и найдите сумму всех натуральных чисел из промежутка [1, А].
Занятие 2. Цикл с предусловием в графике.
Задача . Построить множество концентрических окружностей (с общим центром), удовлетворяющих следующим условиям:
а) радиус следующей окружности на m меньше предыдущей;
б) процесс построения должен завершиться, когда радиус меньшей окружности станет меньше или равным данному числу а.
Итак, для решения задачи в программе мы должны запросить у пользователя значения переменных m и а, затем инициализировать графический режим и в цикле выполнять построение окружностей, меняя при этом радиус. Для наиболее красочного построения окружностей применим процедуру установки текущего цвета с применением случайных чисел.
write (‘Введите шаг изменения радиуса окружностей ‘);
write (‘Введите радиус большей окружности ‘);
write (‘Введите радиус меньшей окружности ‘);
write (‘Введите координаты центра ‘);
InitGraph (DV, DM, ‘..\BGI’);
Примечание . Здесь применена процедура Randomise, которая инициализирует генератор случайных чисел. Значения же случайных чисел можно получить с помощью функции Random (Х), где Х — параметр, указывающий диапазон значений случайного числа. Оно изменяется в пределах [0,Х[. Результат в этом случае будет типа Word. Если параметр Х не задан, то результат буде типа real в пределах [0.0,1.0[.
Задачи для самостоятельного решения
1. Составить программу, перемещающую отрезок заданной длины слева направо. Имитация движения осуществляется закраской цветом фона линии на предыдущем шаге и построением ее по новой координате Х на следующем шаге.
2. Составить программу, перемещающую отрезок заданной длины сверху вниз.
3. Составить программу, перемещающую отрезок заданной длины из левого верхнего угла в правый нижний, постепенно его увеличивая.
4. Нарисовать веер, состоящий из секторов круга, разукрашенных разным цветом.
5. Нарисовать окружность, меняющую цвет заданное число раз.
6. Изобразить движущуюся окружность заданного радиуса и цвета.
7. Изобразить движение выбранной Вами фигуры.
8. Изобразить движение грузовика.
9. Используя процедуру очистки экрана, постройте изображение надувающегося мыльного пузыря, который должен лопнуть, когда его радиус станет в 3 раза больше первоначального.
10. Нарисуйте последовательность вложенных квадратов с общим центром в центре экрана так, чтобы расстояние между сторонами уменьшалось до тех пор, пока не стало меньше трех точек.
11. Составьте программу “Растущая ель”. Рост ели имитируется добавлением к нижнему основанию треугольника (кроне ели) линии на одну точку шире основания как слева, так и справа. К основанию ствола добавляется прямая линия. Программа прекращает работу при увеличении высоты дерева вдвое.
12. Составьте программу “Рост лиственного дерева”. Рост кроны изображается добавлением окружностей.
13. Нарисуйте действующую модель часов с кукушкой. Часы должны тикать, кукушка куковать.
14. Нарисуйте движение маятника.
15. Нарисуйте движение фигуры, используя уже имеющийся файл с программой из темы “Операторы графики”.
Занятие 3. Контрольная работа
1. Запишите конструкцию цикла с предусловием. В каких случаях применяется цикл с предусловием?
2. Запишите правильную структуру последовательности операторов:
Сколько раз будет повторен цикл и какими будут значения переменных a, b, s после его завершения?
3. Запишите правильную структуру последовательности операторов. Какими будут значения переменных а и b после выполнения операторов:
4. Запишите правильную структуру последовательности операторов. Определите значение переменной s после их выполнения.
b) s:=0; i:=0; while i>1 do begin s:=s+100 Div i; Dec(i) End;
5. Дана последовательность операторов, вычисляющих факториал f числа n, которая содержит пять ошибок. Найдите эти ошибки, предварительно записав операторы в правильном виде.
Примечание . Факториалом натурального числа называется произведение всех натуральных чисел от 1 до этого числа,
т.е. n !=1*2*3*. *( n -2)*( n -1)* n
6. Найдите и исправьте ошибки в следующем фрагменте программы, определяющей для заданного натурального числа n число, записанное цифрами числа n в обратном порядке.
7. Ниже представлен фрагмент программы вычисления количества цифр в заданном натуральном числе. Найдите и исправьте в нем ошибки.
8. Каким условиям должны удовлетворять значения переменной k, чтобы следующие циклы были бесконечны:
while k<>0 do k:=1+k;
while k<>0 do k:=k-2;
Подготовьтесь объяснить учителю их решения.
Занятие 4. Цикл с постусловием repeat.
Вы уже умеете организовать цикл при помощи оператора while. Напомним, что при выполнении этого оператора компьютер вычисляет значение условия. Если условие истинно, то исполнительная часть оператора while будет выполняться до тех пор, пока это условие не примет значение False. Если значение условия есть False в самом начале, то исполнительная часть оператора while вообще не будет выполняться.
Иногда при решении задач возникает необходимость выполнить тело цикла хотя бы один раз, а потом исследовать условие повторять ли его еще раз. Эту задачу выполнит другой вид цикла Repeat.
repeat повторяй
u ntil ; до тех пор, пока условие не будет верным
Есть небольшое отличие в организации цикла repeat по сравнению с while: для выполнения в цикле repeat нескольких операторов не следует помещать эти операторы в операторные скобки begin . end. Зарезервированные слова repeat и until действуют как операторные скобки.
Конструкция repeat . until работает аналогично циклу while. Различие заключается в том, что цикл while проверяет условие до выполнения действий, в то время как repeat проверяет условие после выполнения действий. это гарантирует хотя бы одно выполнение действий до завершения цикла.
a) repeat b) repeat
read (Number); i := i+1;
Sum := Sum+Number; writeln (Sqr(i))
until Number=-1 until Number=-1
Задача . Определить, является ли введенное число простым.
Алгоритм решения этой задачи будет следующий. При помощи операции mod проводим проверку всех целых чисел от 2 до введенного числа Number . Мы проверяем является ли очередное проверяемое число делителем нашего числа (значит, остаток от деления введенного числа на проверяемое число равен нулю). Если такой делитель найден, значит, цикл досрочно завершает свою работу на некотором i-том шаге. Если делитель не найден, значит цикл проверил все числа и значение переменной цикла i будет равно конечному значению, т.е. Number. Поэтому, после записи цикла следует анализ значения переменной i и выводится соответствующее сообщение.
Примечание . Напомним, что простым называется число, которое не имеет делителей кроме 1 и самого себя.
Цикл не может продолжаться бесконечно, так как любое число всегда делится само на себя.
writeln (‘Какое число должно быть проверено? ‘);
until Number mod i = 0;
writeln (Number,’ является простым ‘)
writeln (Number,’ делится на ‘,i);
При построении циклов нужно быть очень аккуратным: следить за отсутствием ошибок как в фазе входа в цикл, так и в фазе завершения цикла.
Задание . Выберите две задачи, решенных Вами с помощью цикла с предусловием, и решите их с помощью цикла с постусловием.
Задачи для самостоятельного решения
1. Составьте программу для определения N!-M!
2. Запросить имя пользователя и напечатать «Привет, Вася!» 10 раз. (если Вася – имя пользователя)
3. Программа должна вычислять произведение двух чисел и спрашивать завершать программу или нет, если нет то продолжать запрашивать данные вычислять произведение и печатать его.
4. Вывести на печать все трёхзначные натуральные числа, сумма цифр которых равна заданному числу N. (Операции div и mod не использовать.)
5. Составить программу, печатающую все простые числа, не превосходящие данного числа.
6. Население города увеличивается на 3% каждый год. В 1983 году население города составляло 65000. Напишите программу, которая выведет на экран предсказываемую численность населения города в каждом году вплоть до 1999г.
7. Найдите все натуральные числа от 1 до 1000, кратные 3.
8. Составить программу планирования закупки товара в магазине на сумму, не превышающую заданную величину.
9. Составить программу запроса пароля пока не будет введен пароль верно. В программе предусмотреть счетчик неправильных вводов пароля.
10. Произведение N первых нечетных чисел равно р. Сколько сомножителей взято?
11. Числа Фибоначчи (f n ) определяются формулами:
f 0 =f 1 =1; f n =f n-1 +f n-2 при n=2,3.
а) определения f — 40-е число Фибоначчи;
б) поиска f — первого числа Фибоначчи, большего m (m>1);
в) вычисления S — суммы всех чисел Фибоначчи, которые не превосходят 1000.
12. Самостоятельно придумать и решить задачу на применение цикла с постусловием.
Занятие 5. Работа с клавиатурой. Стандартные процедуры read и readLn. Стандартные функции readKey и KeyPressed; их применение в циклах.
Это занятие мы посвятим вопросам программированию обменов с клавиатурой компьютера. Турбо Паскаль содержит несколько простых и ясных средств, которые позволяют организовать эффективное управление программы посредством клавиатуры.
Самая простая и часто применяемая техника организации приема информации основывается на использовании уже знакомых Bам процедур read и readln. Расширим знания о них. Эти процедуры работают со стандартным входным файлом, который отождествлен с “консолью”, т. е. с клавиатурой и экраном дисплея. На практике это означает, что информация, введенная с клавиатуры, помимо обработки процедурами, будет отображаться на экране.
Удобством указанных процедур является автоматическое преобразование ими вводимой цепочки символов в значение заданного типа. Так, если в разделе описания переменных имеется описание вида
то выполнение оператора readln (Chislo) будет происходить следующим образом. Программа будет приостановлена в ожидании ввода с клавиатуры символов, изображающих целое число. После ввода этих изображений они будут автоматически преобразованы в соответствующие двоичные значения и присвоены переменной Chislo. Аналогично организован прием значений действительного, символьного и строкового типа. Если read(readln) не может выполнить преобразования, то генерируется ошибка № 106 – Invalid numeric format (Неверный формат числовых данных) и выполнение программы прекращается. Это является стандартной реакцией, которую выполняет программа, взявшая на себя обработку ошибок. Мы вернемся еще к обработке ошибок, вызванных некорректным вводом, в теме “Процедуры и функции”, где научимся правильно составлять и использовать вспомогательные подпрограммы. А пока приведем пример применения этих процедур ввода при организации циклов.
write (‘Для остановки программы наберите “Стоп“‘);
write (‘Для продолжения – любую клавишу ‘);
until (Stop=‘Стоп‘) or (Stop =‘стоп‘);
Примечание . Здесь использованы следующие процедуры:
GoToXY (X, Y:Byte) — перемещает курсор к элементу экрана с заданными координатами, учитывая, что размер экрана в текстовом режиме 25 строк по 80 символов.
TextBackGround (Color : Byte) – задает цвет фона .
TextColor (Color : Byte) – задает цвет символов.
Однако, несмотря на простоту и удобство, стандартные процедуры read и readln не обеспечивают всеж потребностей, возникающих при работе с клавиатурой. Их важнейший недостаток в том, что вместе с приемом символов они выполняют их отображение на экран (так называемое “эхо на монитор”). В большинстве случаев это либо не нужно, либо недопустимо. Например, если программа реализует некоторый оконный интерфейс, то вывод вводимых символов испортит изображение. Кроме того, они рассчитаны только на ввод относительно небольшого подмножества символов (буквы, цифры, знаки препинания) и частичного использования специальных клавиш (например, Backspace для отмены только что введенного символа). Эти процедуры не могут распознать нажатие функциональных или редактирующих клавиш и их сочетаний с управляющими клавишами Ctrl, Alt, Shift. В силу указанных причин процедуры read и readln редко используются в серьезных программах.
Стандартная функция readKey
Более универсальным средством взаимодействия с клавиатурой является стандартная функция readKey из системного модуля Crt. Функция вызывается без параметров, возвращает значение символьного типа и работает следующим образом. Организуется задержка выполнения с ожиданием нажатия клавиши. После того, как нажатие произведено, функция завершает работу, возвращая код нажатой клавиши. Полученное значение можно использовать далее в программе. Тривиальный пример работы с функцией readKey, не требующий комментариев, может выглядеть так:
write (‘ Введите букву — ‘);
writeln (‘ Вы ввели букву — ‘, Sym);
Примечание . Здесь использована процедура Exit, которая позволяет досрочно выйти из программы. Применение этой процедуры является плохим стилем программирования.
Функция readKey не отображает введенный символ на экран, благодаря чему она широко используется для организации управления в различных диалоговых программах. В дополнение к этому readKey позволяет отслеживать нажатие более широкого множества клавиш, опознавая функциональные и редактирующие клавиши и их сочетания с управляющими клавишами Ctrl, Alt, Shift.
Если говорить более подробно, функция readKey исходит из того, что все множество клавиш и их сочетаний с управляющими клавишами разбито на два подмножества, которые обычно называют основным и расширенным наборами.
В основной набор входят клавиши букв, цифр, разделителей и знаков препинания, их комбинации с клавишей Shift (или, что то же самое, при включенном переключателе CapsLock), а также клавиши Tab, BackSpace, Enter и Esc. Если нажата одна из перечисленных клавиш, то readKey возвратит обычный ASCII-код соответствующего символа.
В расширенном наборе содержатся некоторые (не все) клавиши из основного набора в комбинации с клавишами Ctrl и Alt, а также функциональные и редактирующие клавиши. Если нажимается одна из клавиш расширенного набора, то функция readKey возвращает символ с кодом 0 (его представление в программе – chr(0) или #0). В этом случае повторное обращение к readKey вернет код клавиши из расширенного набора.
Коды клавиш из основного и расширенного наборов в виде, удобном для включения в Турбо Паскаль-программы, приведены в приложении.
Схема использования функции readKey для общего случая может выглядеть так:
write (‘ Нажмите клавишу ‘);
#8 : writeln (‘ Вы нажали BackSpace‘);
#9 : writeln (‘Вы нажали Tab ‘);
#13 : writeln (‘Вы нажали Enter ‘);
#27 : writeln (‘Вы нажали Esc ‘);
writeln (‘Вы ввели символ ‘, Sym );
Sym := readKey;
writeln (‘Вы нажали клавишу с кодом ‘, Ord (Sym)));
Большинство прикладных диалоговых программ использует описанную технику взаимодействия с клавиатурой. Однако встречаются случаи, когда возможностей функции readKey оказывается недостаточно. На самом деле функция readKey воспринимает нажатия не всех клавиш: достаточно попробовать, запустив вышеприведенную программу, нажать клавиши F11, F12, ввести комбинацию Alt+Esc и т.д. Тому, кто желает более детально изучить работу этой функции, предлагаем самостоятельно найти в книгах по Турбо Паскалю этот материал. А мы ограничимся вышесказанным.
Стандартная функция KeyPressed
Второй базовой функцией взаимодействия с клавиатурой является функция KeyPressed. В отличие от readKey, она предназначена не для приема кода нажатой клавиши, а для простой проверки, была ли нажата какая-либо клавиша. Эта функция вызывается без параметров и возвращает значение булевого типа: True, если было нажатие, и False в противном случае.
Важно понять, что KeyPressed не производит никаких действий с кодом нажатой клавиши, но код может быть далее прочитан функцией readKey, например,
C оотношение этих функций станет более понятным, если рассмотреть их внутреннюю организацию несколько подробнее. В системной области DOS имеется небольшой буфер, в который операционная система помещает коды нажатых клавиш. буфер организован в виде очереди, причем помещение кодов производится в ее хвост, а считывание из головы. Таким образом, каждое обращение к функции readKey извлекает из головы очереди один содержащийся там код. Если буфер пуст, то организуется задержка выполнения до тех пор, пока в нем не появится код ( появление кода соответствует нажатию клавиши). Если же к моменту вызова readKey нажатие уже произошло, то есть буфер содержит хотя бы один код, то никакой задержки не будет. Буфер очень невелик и рассчитан на хранение максимум 15 кодов, что соответствует 15 нажатиям. Кстати говоря, иногда встречается такая ситуация, когда та или иная программа “не успевает” выбирать коды клавиш из буфера (то есть нажатия производятся чаще). Ситуация переполнения буфера индицируется звуковым сигналом, после чего коды вновь нажимаемых клавиш будут пропадать.
Функция KeyPressed не извлекает код из буфера, а только проверяет , пуста ли очередь, и возвращает соответствующее булево значение. Более подробно рассмотрение системных аспектов работы с клавиатурой смотрите в соответствующей литературе.
Используя полученные знания решите выбранные с учителем задачи из нижеприведенного перечня.
1. Составьте программу движения круга вверх, вниз, влево, вправо в зависимости от нажатия клавиш управления курсором.
2. Составьте программу движения заданного слова сверху вниз и обратно, для остановки движения запрограммируйте нажатие какой-либо клавиши.
3. Составьте программу движения человечка, для остановки движения запрограммируйте нажатие какой-либо клавиши..
4. Составьте программу движения маятника, для остановки движения запрограммируйте нажатие какой-либо клавиши.
5. Составьте программу движения бегущей строки.
6. Составьте программу вывода слова на экран и поочередное мерцание его букв.
7. Составьте программу падания букв из введенного слова.
8. Составьте программу случайного вывода звездочек разного цвета на экран, для вывода запрограммируйте нажатие какой-либо клавиши.
9. Составьте программу рисования надувающихся пузырей и их лопания по достижению заданного радиуса.
10. Составить программу для вывода на экран бегущей надписи, например: «Для остановки нажми Ctrl+Stop».
11. Самостоятельно придумайте и решите задачу с применением знаний этого занятия.
Занятие 6. Цикл со счетчиком.
Циклы со счетчиком составляют такой класс, в которых выполнение исполнительной части должно повторяться заранее определенное число раз. Циклы со счетчиком используются довольно часто, и поэтому в языке Паскаль для этих целей имеется специальная конструкция.
Можно, конечно, циклы со счетчиком моделировать при помощи операторов while и Repeat, но структура цикла со счетчиком проще.
Общая форма записи цикла со счетчиком
for i := A to B do for i := A downto B do
Здесь переменная i — управляющая переменная или переменная цикла,
А — начальное значение переменной цикла,
В — конечное значение переменной цикла.
При переходе к обработке оператора цикла for управляющей переменной присваивается заданное начальное значение. Затем в цикле выполняется исполнительный оператор (или составной оператор). каждый раз при выполнении исполнительного оператора управляющая переменная увеличивается на 1 (для for. to) или уменьшается на 1 (для for. downto). Цикл завершается при достижении управляющей переменной своего конечного значения.
1) for i := 1 to ListSize do
2) for Dlina := 15 downto 1 do
3) for x := 1 to 10 do
for y := 1 to 10 do
4) for Range := Number+1 to Multi*3 do
При использовании цикла for компьютер выполняет за программиста черновую работу по инициализации управляющей переменной и по ее увеличению (уменьшению) при каждом повторении цикла. Единственное ограничение заключается в том, что тип управляющей переменной не должен быть real. Переменная цикла не должна изменяться какими-либо операторами внутри цикла. К ней можно обращаться и использовать в вычислениях, но нельзя присваивать новое значение. Присваивания могут выполняться только механизмом самого цикла. Таким образом, следующий цикл является некорректным:
for i := 1 to 10 do
Управляющая переменная должна описываться, как и любая другая переменная. Обычно переменная цикла имеет тип integer, но позднее Вы рассмотрите другие типы данных, которые могут указываться в цикле for.
Внимание ! Следует помнить, что управляющая переменная не может быть типа real.
Исполнительная часть цикла может быть либо простым, либо составным оператором. Если начальное значение цикла for . to больше конечного значения, то никакие операции не выполнятся. Таким образом, следующий оператор не приведет ни к каким действиям
for j := 1 to 0 do
Однако цикл, представленный в такой форме, распечатает целые числа от единицы до десяти:
for j := 1 to 10 do
Как можно догадаться, следующий цикл выполняет счет в обратном порядке
for j := 10 downto 1 do
Часто исполнительная часть одного из циклов For является новым оператором цикла For. Структуры такого рода называются вложенными циклами. При завершении внутреннего цикла управляющая переменная внешнего цикла увеличивается. Повторение этих действий будет продолжаться до вавершения внешнего цикла. Приведенный ниже вложенный цикл печатает пары чисел, начиная от (1,1), (1,2). и кончая (10,10):
for х := 1 to 10 do
for у := 1 to 10 do
Задание . Выполните две, уже решенные Вами задачи с помощью других видов цикла, используя цикл со счетчиком.
Занятие 7-8. Самостоятельное решение задач.
Выберите с учителем задачи для решения из предложенного ниже списка.
1. Найдите количество точек с целочисленными координатами попадающих в круг радиуса R.
2. Составить программу, которая распечатывает на экране таблицу умножения.
3. Найдите все трёхзначные числа, равные сумме кубов своих цифр. Учтите, что abc=100a+10b+c
4. Составить программу вывода всех трёхзначных чисел, сумма цифр которых равна данному целому числу. Программа должна печатать именно числа, а не набор цифр.
5. Имитировать на экране работу электронных часов.
6. Напишите программу отгадывания буквы.
7. Задано n троек чисел a,b,c. Определить, сколько из предложенных троек можно использовать для построения треугольника, если a,b,c — длины его сторон. (Известно, что .)
8. Найти сумму целых положительных чисел, больших 20, меньших 100 и кратных 3.
9. Укажите все целые числа, которые увеличатся на 20%, если их цифры записать в обратном порядке.
10.Составьте программу взвешивания продавцом 2,5 кг муки.
11. Составить программу, в которой среди двухзначных чисел печатаются те числа, которые равны сумме своих цифр.
12. Замените буквы цифрами так, чтобы равенство ФАКТ+ФАКТ=НАУКА стало верным. Одинаковым буквам должны соответствовать одинаковые цифры, разным — разные.
13. Написать программу для создания на экране зигзага, бегущего снизу вверх звездочками.
14. В бригаде, работающей на уборке сена, имеется N косилок. Первая из них работала m ч., а каждай следующая на 10 мин. больше, чем предыдущая. Сколько часов проработала вся бригада?
15. В компьютер вводятся по очереди данные о росте N учащихся класса. Определить средний рост учащихся класса.
16. Составьте программу вычисления степени числа а с натуральным показателем n.
17. Каждая бактерия делится на две в течение одной минуты. В начальный момент имеется одна бактерия. Составьте программу, которая рассчитает количество бактерий на заданное Вами целое значение момента времени.
18. Дана последовательность из N целых чисел. Определить произведение максимального и минимального элементов этой последовательности.
19. Для двух последовательностей из N и M элементов соответственно найти произведение максимального элемента первой последовательности и минимального элемента второй последовательности.
20. Дано целое n>0 и последовательность из n действительных чисел, среди которых есть хотя бы одно отрицательное число. Найти величину наибольшего из отрицательных чисел этой последовательности.
Проверьте себя, ответив на вопросы:
1. Что называется циклом? Приведите пример.
2. Какой алгоритм называется циклическим? Приведите примеры.
3. Какие виды циклов Вы знаете? Почему они имеют такие названия?
4. В теле какого цикла не нужно ставить операторные скобки, даже если выполняется составной оператор?
5. Каким должно быть условие, чтобы тело цикла w hile ни разу не выполнилось? Почему?
6. Каким должно быть условие, чтобы тело цикла r epeat выполнилось один раз? Почему?
7. Каким должно быть условие, чтобы тело цикла for ни разу не выполнилось? Почему?
8. Чему равен шаг изменения параметра цикла в операторе for?
9. Укажите отличительные особенности каждой из конструкций циклов.
10. Будет ли выполняться циклическая часть программы, если логическое выражение в конструкции REPEAT истинно с самого начала?
11. Что такое стоп-код? Когда его применяют?
12. Какие условия предъявляются к переменной цикла?
13. Какого типа должна быть переменная цикла?
14. Может ли переменная цикла использоваться в вычислениях?
15. Что называется шагом? Что означает выражение “шаг равен пяти”?
16. Что происходит на каждом шаге выполнения тела цикла при выполнении оператора Summa:=Summa+Chislo?
17. Какой цикл Вы применяете чаще? Каковы его достоинства и недостатки?
18. Функция R eadKey и ее применение в программах.
19. Функция KeyPressed и ее применение в программах.
20. Какие клавиши входят в основной набор?
21. Какие клавиши входят в расширенный набор? Как обратится к этим клавишам в программе?
22. Что обозначает слово downto в операторе цикла f or?
Циклические алгоритмы. Циклы с предусловием и постусловием.
«Циклические алгоритмы. Циклы с предусловием и постусловием».
Предмет: Информатика и ИКТ
Тема урока: «Циклические алгоритмы. Циклы с предусловием и постусловием»
Тип урока: Изучение нового материала
образовательные: Познакомиться с понятием «Циклы с предусловие и постусловием». Закрепить знания учеников об алгоритме.
развивающие: Воспитать трудолюбие, самостоятельность, культуру речи и общения.
воспитательные : Развивать мышление, память, речь и другие психические процессы.
Познавательные УУД: формируют и развивают компетентность в области использования ИКТ
Регулятивные УУД: умеют соотносить свои действия с планируемыми результатами.
Коммуникативные УУД: умеют работать индивидуально и в группе.
Личностные УУД: понимают значимость подготовки в области информатики и ИКТ в условиях
развития информационного общества.
Средства обучения: проектор, персональный компьютер, специализированное программное обеспечение (среда программирования «PascalABC»).
1. Организация начала урока
Здравствуйте. Сегодня я, буду вести уроки «Информатики и ИКТ». Приветствую обучающихся, проверяю их готовность к уроку. Обучающиеся приветствуют друг друга.
2. Проверка выполнения домашнего задания
Спрашиваю у них пройденный материал.
1. Что такое линейный алгоритм?
Линейный алгоритм или следование – это тип алгоритма, в котором последовательность действий не меняется в его процессе выполнения. Алгоритм, в котором команды выполняются в порядке их записи, то есть последовательно друг за другом, называется линейным.
2. Как реализуется линейный алгоритм?
В программе линейный алгоритм реализуется последовательным размещением операторов.
Например, линейным является следующий алгоритм посадки дерева:
1) выкопать в земле ямку;
2) опустить в ямку саженец;
3) засыпать ямку с саженцем землей;
4) полить саженец водой.
3. Какая форма организации действий называется ветвлением?
Форма организации действий, при которой в зависимости от выполнения или невыполнения некоторого условия совершается либо одна, либо другая последовательность действий, называется ветвлением.
4. Как оформляют алгоритм ветвления?
Логику принятия решения можно описать так:
• ЕСЛИ хочешь быть здоров, ТО закаляйся, ИНАЧЕ валяйся весь день на диване;
• ЕСЛИ низко ласточки летают, ТО будет дождь, ИНАЧЕ дождя не будет;
• ЕСЛИ уроки выучены, ТО иди гулять, ИНАЧЕ учи уроки.
3. Изучение нового материала
Тема наших уроков будет: «Циклические алгоритмы. Цикл с предусловием «Пока». Цикл с постусловием «До»».
• Целью нашего урока является: «знакомство с понятием цикла и развитие умения решать различные задачи по данной теме».
Давайте теперь запишем что же такое цикл?
Цикл — форма организации действий, при которой одна и та же последовательность действий совершается несколько раз до тех пор, пока выполняется какое — либо условие.
Циклический алгоритм – это алгоритм, содержащий один или несколько циклов.
Алгоритмическая структура «цикл» может быть зафиксирована различными способами:
• графически — с помощью блок-схемы;
• на языке программирования, например на языке Паскаль с использованием специальных инструкций, реализующих циклы различного типа.
Сегодня мы познакомимся с циклами с предусловием и постусловием.
Циклы с предусловием используются тогда, когда выполнение цикла связано с некоторым логическим условием. Оператор цикла с предусловием имеет две части: условие выполнения цикла и тело цикла.
На русском языке это звучит примерно так:
пока выполняется это условие, делай
от начала
группа операторов
до конца;
При использовании цикла с предусловием надо помнить следующее:
1. значение условия выполнения цикла должно быть определено до начала цикла;
2. если значение условия истинно, то выполняется тело цикла, после чего повторяется проверка условия. Если условие ложно, то происходит выход из цикла;
3. хотя бы один из операторов, входящих в тело цикла, должен влиять на значение условия выполнения цикла, иначе цикл будет повторяться бесконечное число раз.
При выполнении оператора while определенная группа операторов выполняется до тех пор, пока определенное в операторе while булево условие истинно. Если условие сразу ложно, то оператор не выполнится ни разу.
Операторные скобки ставят, чтобы отделить от остальной программы ту группу операторов, которую нужно повторить в цикле. Если в цикле нужно выполнить только один оператор, то операторные скобки не ставят.
Выполняется данный оператор так: сначала условие, стоящее после слова WHILE, проверяется на истинность. Если оно имеет значение TRUE, то выполняется оператор, стоящий после слова DO, затем условие проверяется вновь и т.д. Как только на очередном шаге условие не выполняется (значение выражения становится равным FALSE), то выполнение оператора цикла прекращается.
Если выполняемый оператор не изменяет значения переменных, входящих в условие, то условие всегда будет истинным, и цикл будет выполняться вечно, при этом говорят, что программа зацикливается. Если же при первой проверке условия оно сразу оказывается ложным, то оператор цикла не выполняется вообще.
Если в цикле нам необходимо выполнять больше, чем один оператор, то применяется составной оператор, т.е. несколько операторов заключаются в операторные скобки BEGIN … END.
При построении программ со структурой цикла WHILE:
1) начальное значение логического выражения должно быть определено перед вхождением в цикл, т.е. перед WHILE;
2) последовательность выполняемых операторов в теле цикла должна быть логически связанной и содержать хотя бы один оператор, изменяющий значение параметра цикла, иначе цикл будет продолжаться бесконечно;
3) логическое выражение в заголовке цикла WHILE, чтобы цикл закончился, должно принять значение FALSE.
Работа оператора While
Давайте рассмотрим первый пример:
В блок-схеме таблица умножения на 3 выглядит так:
Попробуйте сами составить таблицу умножения на 1, 2, 4, 5, 6, 7, 8 и 9. Как она будет выглядеть в виде блок-схемы? (ученики составляют таблицу умножения в виде блок-схемы).
Теперь давайте рассмотрим особенности этого цикла и запишем к себе:
Давайте теперь попробуем самостоятельно решить задачу в Turbo Pascal .
Решение задачи о выводе 10 целых чисел на экран с использованием цикла While … do :
Для решения данной задачи, давайте вспомним, что такое натуральный ряд чисел?
Натуральным рядом называется ряд из целых чисел начиная с 1. То есть, 1, 2, 3,…, и до какого-то числа N .
Решене данной задачи:
writeln(‘ Василисе ‘,v,’ лет ‘);
Следующая задача, которую Вам предстоит самим решить дома, запишите задачу:
• Начав тренировки, лыжник в первый день пробегал 10 км. Каждый следующий день он увеличивал длину пробега на 10% от предыдущего дня. Определить в какой день он пробежит больше 20 км, в какой день суммарный пробег за все дни превысит 100км.
Давайте разберем, сколько переменных у нас будет и какого они типа? Переменных у нас всего 2, одна будет у нас для вычисления дневного пробега больше 20 км, а другая будет вычислять в какой день суммарный пробег за все дни превысит 100 км. Какого типа будут переменные? Дневной пробег будет типа integer (то есть целое числа), а вторая real (то есть вещественное число или число с запятой), так как у нас имеется 10%, то если его перевести в число, мы получаем 0,1. У нас будет в программе иметься два цикла, первый цикл для определения дня когда лыжник пробежит больше 20 км, а второй для нахождения дня, когда суммарный пробег за все дни превысит 100 км.
Теперь познакомимся со следующей разновидность циклов — это циклы с постусловием.
Вы уже умеете организовать цикл при помощи оператора while. Напомним, что при выполнении этого оператора компьютер проверяет значение условия. Если условие истинно, то исполнительная часть оператора while будет повторяться до тех пор, пока это условие не примет значение False. Если значение условия есть False в самом начале, то тело цикла while вообще не будет выполняться.
Иногда при решении задач возникает необходимость выполнить тело цикла хотя бы один раз, а потом, проверив условие, определить, повторять ли тело цикла еще раз. Эту задачу выполнит другой вид цикла – цикл Repeat.
Есть небольшое отличие в организации цикла repeat по сравнению с while: для выполнения в цикле repeat нескольких операторов не следует помещать эти операторы в операторные скобки begin . end. Зарезервированные слова repeat и until действуют как операторные скобки.
Конструкция repeat . until работает аналогично циклу while. Различие заключается в том, что цикл while проверяет условие до выполнения действий, в то время как repeat проверяет условие после выполнения действий. Это гарантирует хотя бы одно выполнение действий до завершения цикла.
Данная конструкция читается так:
Рассмотрим работу цикла с постусловием:
Особенности цикла с постусловием:
Решим туже самую задачу теперь с помощью цикла с постусловием:
Сравним цикл с пред и постусловием:
Как я уже говорила:
Есть небольшое отличие в организации цикла repeat по сравнению с while: для выполнения в цикле repeat нескольких операторов не следует помещать эти операторы в операторные скобки begin . end. Зарезервированные слова repeat и until действуют как операторные скобки.
Конструкция repeat . until работает аналогично циклу while. Различие заключается в том, что цикл while проверяет условие до выполнения действий, в то время как repeat проверяет условие после выполнения действий. Это гарантирует хотя бы одно выполнение действий до завершения цикла.
А так же есть и общее в этих циклах:
- До цикла задается начальное значение переменных,
входящих в условие. Условие — выражение булевскоготипа. - В теле цикла значение переменных, входящих в условие, должны обязательно изменять свое значение, иначе возникнет ситуация «зависания».
Для решения следующей задачи следует вспомнить геометрическую прогрессию.
А теперь сама задача:
Все увидели задачу, которую нужно решить с использованием цикла с постусловием. Вы все видите, что имеется блок-схема, составленная с использованием цикла с предусловием. Давайте ее разберем детально, а затем я дам задание. Все мы видим, что блок-схема имеет начало, затем происходит ввод данных, где i =7, так как это сын под номером 7, так как он забрал два последних изумруда из сундука отца, поэтому мы q даем значение равное двум. Так как первый сын взял половину того, что было в сундуке, значит разность геометрической прогрессии равна двум, то есть r мы присваиваем значение равное двум. Как раз буква r и показывает разность геометрической прогрессии. Условие у нас будет тем, что пока у нас i >1 мы выполняем следующею последовательность действий, то есть i := i -1, то есть это действие показывает, что номер следующего сына уменьшается на единицу. Затем мы вычисляем итый член прогрессии выполняя действие: q = q * r . Данная последовательность из двух действий будет выполняться до тех пор, пока условие i >1 не станет ложной, после чего произойдет вывод сколько всего изумрудов было в сундуке и программа закончится.
Теперь давайте вы самостоятельно попробуете составить блок-схему для цикла с предусловием и самостоятельно напишите программу для решения данной задачи на языке Паскаль с использованием программы PascalABC .
Теперь подсказка для решения задачи:
Само решение на языке Pascal :
А теперь выполните самостоятельно:
4. Подведение итогов
Вам понравился урок?
Выставление оценок и озвучивание их ученикам.
Спасибо за участие и активную деятельность. До новых встреч.
5. Домашнее задание
Домашним заданием будет повторить что такое цикл, что такое цикл с пост и предусловием, а так же синтаксис их написания на языке программирования Паскаль. Затем, дома решить задачу про лыжника с помощью цикла с пост и предусловием и принести мне написанные программу в тетради с ответами на поставленные в задаче вопросы.
ЛогоМир
Актуальность программы состоит в том, что она предоставляет возможность учащимся программировать максимально легко и просто. KTurtle великолепно подходит для обучения детей основам математики, геометрии и программирования. Также программа адаптирована для реализации в условиях временного ограничения занятий в очной (контактной) форме и включает все необходимые инструменты электронного обучения.
Новизна программы состоит в том, что она адаптирована для возрастной категории детей младшего школьного возраста. В ходе занятий учащиеся шаг за шагом осваивают основные алгоритмические конструкции и одновременно обретают навыки работы за компьютером. Особое внимание уделяется практической работе.
Педагогическая целесообразность. Программирование на компьютере подразумевает описание некоторой проблемы на определенном языке и последующее многократное моделирование с целью проверки модели и решения проблемы. Эффективное описание проблемы для моделирования требует развитого объектного мышления.
Правильно организованное обучение с использованием среды программирования развивает алгоритмическое и логическое мышление в естественной для этого обстановке, дает опыт работы с разными моделями; знакомит с общими принципами и методами программирования, что позволяет учащимся адаптировать приобретенные навыки при освоении других программных сред.
Отличительная особенность программы заключается в том, что данная программа, являясь как самостоятельной единицей, так и продолжением ДООП «ИНФОзнайка», знакомит учащихся с ещё одной прикладной программой операционной системы Linux .