Учебник. А. Ю. Босова Москва бином. Лаборатория знаний 2016 11 класс Базовый уровень Учебник
 Скачать 4.61 Mb.
|
|
Глава 2. алгоритмы и программирование рис. 2.7. Ветвящаяся алгоритмическая конструкция Выясните, какую задачу решает этот алгоритм. К какой последо вательной алгоритмической конструкции сводится эта ветвящаяся конструкция при: 1) х = –10; 2) х = 2; 3) х = 10? 6.3. циклическая алгоритмическая конструкция Алгоритм реализован с использованием циклической алгоритми- ческой конструкции, если некая группа подряд идущих шагов ал горитма может выполняться многократно в зависимости от входных данных. Любая циклическая алгоритмическая конструкция содержит в себе элементы ветвящейся алгоритмической конструкции. 81 алгоритмические структуры §6 Циклическая структура (цикл) обеспечивает многократное выполнение одних и тех же команд. Существует несколько раз- новидностей циклических структур: цикл с предусловием (цикл- пока), цикл с постусловием (цикл-до), цикл с параметром. Лю- бая циклическая структура состоит из двух частей — заголовка и тела цикла. Последовательность команд, повторяющуюся при выполнении цикла, называют телом цикла. Заголовок определяет количество повторений тела цикла. На рисунке 2.8 представлены блок-схемы цикла с предусловием и цикла с параметром. рис. 2.8. Блок-схемы циклов Пример 4. Исполнитель Редактор получает на вход строку цифр и преобразует её. Редактор может выполнять две команды, в которых параметры v и w обозначают цепочки цифр. Команда нашлось (v) проверяет, встречается ли цепочка v в строке исполнителя Редактор. Если она встречается, то команда возвращает логическое значение «истина», в противном случае возвращает значение «ложь». Строка при этом не изменяется. Команда заменить (v, w) заменяет в строке первое слева вхо- ждение цепочки v на цепочку w. Дана программа для исполнителя Редактор: НАЧАЛО ПОКА нашлось (333) ИЛИ нашлось (22) ЕСЛИ нашлось (333) ТО заменить (333, 2) ИНАЧЕ заменить (22, 3) КОНЕЦ ЕСЛИ КОНЕЦ ПОКА КОНЕЦ 82 Глава 2. алгоритмы и программирование Выясним, какая строка получится в результате применения приведённой выше программы к строке, состоящей из N подряд идущих цифр 3 при: 1) N = 21; 2) N = 25. Пусть N = 21. Исполнитель Редактор начинает работать со строкой, состоящей из одних только цифр 3: первые три циф- ры 3 сразу же заменяются цифрой 2, следующие три цифры 3 тоже заменяются цифрой 2, полученные две цифры 2 заменяются цифрой 3. После этого мы фактически возвращаемся к исходной задаче, которую должны решить для строки из 16 (21 – 3 – 3 + 1) подряд идущих троек: 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 ... 2 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 ... 2 2 3 3 3 3 3 3 3 3 3 3 3 3 ... 3 3 3 3 3 3 3 3 3 3 3 3 3 ... Можно сказать, что при каждом повторении описанных выше действий из последовательности вычёркивается по пять цифр 3: 21[3] → 16[3] → 11[3] → 6[3] → 1[3] или 3. Пусть N = 25. Тогда: 25[3] → 20[3] → 15[3] → 10[3] → 5[3] → 1[2]2[3] или 233. Итак, можно вычёркивать из последовательности по пять цифр 3, но только при условии, что в ней есть шесть и более идущих подряд троек. Самостоятельно определите, какая строчка получится в результате применения приведённой выше программы к строке, состоящей из 22, 23 и 24 подряд идущих цифр 3. Таким образом, можно сформулировать следующее правило преобразования строки из N подряд идущих цифр 3, соответст- вующее приведённому выше алгоритму: 1) если N mod 5 = 0, то N := 5, иначе N := N mod 5; 2) исполнить исходный алгоритм для строки, состоящей из N подряд идущих цифр 3. 83 алгоритмические структуры §6 Определите, какая строчка получится в результате применения приведённой выше программы к строке, состоящей из 2017, 12 345 подряд идущих цифр 3. Определите, какая строчка получится в результате применения приведённой выше программы к строке, состоящей из 2015, 12 347 подряд идущих цифр 2. Пример 5. Алгоритмы, реализованные через циклическую алгоритмическую конструкцию, представлены блок-схемами на рисунке 2.9. рис. 2.9. Циклическая алгоритмическая конструкция 84 Глава 2. алгоритмы и программирование Известно, что X, A, B, S — целые положительные числа. Выясните, какую задачу решает каждый из алгоритмов на рисунке 2.9. Известно, что при некотором Х результатом работы и первого, и второго алгоритмов является число 3. Укажите все значения Х, при которых возможен такой результат. СамОе ГлаВнОе Вне зависимости от выбранной формы записи элементарные шаги алгоритма объединяются в алгоритмические конструкции (структуры): последовательные, ветвящиеся, циклические, вспомо- гательные и рекурсивные. Для записи любого алгоритма достаточ- но трёх основных алгоритмических структур: последовательной, ветвящейся, циклической. Алгоритм реализован через последовательную алгоритмиче- скую конструкцию, если все команды алгоритма выполняются один раз, причём в том порядке, в котором они записаны в тек- сте программы. Алгоритм реализован через ветвящуюся алгоритмическую конструкцию, если от входных данных зависит, какие команды алгоритма будут выполняться. Алгоритм реализован с использованием циклической алгорит- мической конструкции, если некая группа подряд идущих ша- гов алгоритма может выполняться многократно в зависимости от входных данных. Вопросы и задания 1. Какая алгоритмическая конструкция называется последова- тельной? 2. Петя приглашён в гости к однокласснику Васе, живущему в квартире № 362 шестнадцатиэтажного десятиподъездного дома. Петя забыл, в каком подъезде и на каком этаже живёт Вася, но знает, что в доме на каждой лестничной площадке по 4 квартиры. Помогите Пете узнать, в каком подъезде и на каком этаже находится нужная ему квар тира. 3. Какая алгоритмическая конструкция называется ветвящей- ся? Как она связана с последовательной? 4. Как на блок-схемах изображается полное ветвление? Непол- ное ветвление? 5. Автомат по продаже напитков имеет только две кнопки (A и B), но должен продавать 4 напитка: горячий кофе, горячий чай, холодный яблочный сок и холодную газировку. Пред- ставьте в форме блок-схемы алгоритм работы такого автомата. 85 Запись алгоритмов на языках программирования §7 6. Разработайте и составьте в словесной форме инструкцию для школьного охранника: в какой последовательности и что он должен проверять (наличие пропуска, соответствие фотогра- фии, есть ли сменная обувь и т. п.) и как реагировать на выявленные нарушения (вызвать милицию, отправить до- мой, сделать замечание, но пропустить, и т. д.). 7. Какая алгоритмическая конструкция называется цикличе- ской? Как она связана с ветвящейся? 8. Водитель автобуса, в котором К мест, продаёт билеты и по одному пропускает пассажиров в автобус. Он должен завер- шить посадку и уехать либо когда в автобус войдут все же- лающие, либо когда все места будут заняты. Составьте алго- ритм действий водителя. 9. Исполнитель Редактор получает на вход строку цифр и преоб- разует её. Редактор может выполнять две команды. Команда нашлось (v) проверяет, встречается ли цепочка v в строке, поданной на вход исполнителя. Команда заменить (v, w) за- меняет в строке первое слева вхождение цепочки v на це- почку w. Дана программа для исполнителя Редактор: НАЧАЛО ПОКА нашлось (33) ИЛИ нашлось (22) ЕСЛИ нашлось (33) ТО заменить (33, 2) ИНАЧЕ заменить (22, 3) КОНЕЦ ЕСЛИ КОНЕЦ ПОКА КОНЕЦ Какая строка получится в результате применения приведён- ной выше программы к строке, состоящей из: 1) 500 идущих подряд цифр 3; 2) 500 идущих подряд цифр 2; 3) 300 идущих подряд цифр 3 и следующих за ними 200 идущих подряд цифр 2. § 7 Запись алгоритмов на языках программирования Язык программирования — формальная знаковая система, предназначенная для записи компьютерных программ. 86 Глава 2. алгоритмы и программирование Компьютерную программу можно считать последовательно- стью строк символов некоторого алфавита. Современные системы программирования допускают использование визуальных элемен- тов (окон, иконок и др.) для построения программ, в частности для создания интерфейса пользователя. Такое программирование называют визуальным. Тем не менее основная, алгоритмическая часть любой программы строится с использованием символьных средств. В основной школе вы познакомились со школьным алгорит- мическим языком КуМир и языком программирования Pascal (Паскаль). В 11 классе мы продолжим работать с языком Pascal. Желательно установить среду программирования на ваш домашний компьютер. Все алгоритмы, представленные в этом учебнике на языке Pascal, вы можете записывать и на любом другом интересующем вас языке программирования. Среда программирования Сайт с программным обеспечением Pascal ABC.Net http://pascalabc.net Компилятор Free Pascal http://freepascal.org Среда разработки Lazarus с компилятором Free Pascal http://lazarus.freepascal.org Интерпретатор Python http://python.org 7.1. Структурная организация данных Информация, представленная в виде, пригодном для автома- тизированной обработки, называется данными. Компьютер опе- рирует только одним видом данных — отдельными битами, или двоичными цифрами. Причём он работает с этими данными в соответствии с неизменным набором алгоритмов, которые опре- деляются системой команд центрального процессора. Задачи, которые решаются с помощью компьютера, редко вы- ражаются на языке битов. Как правило, данные имеют форму чисел, символов, текстов и более сложных структур. Алгоритмы, создаваемые для обработки этих данных, учитывают их струк- туру. 87 Запись алгоритмов на языках программирования §7 Под структурой данных в общем случае понимают множество эле ментов данных и множество связей между ними. Различают простые и сложные структуры данных. Простые структуры данных не могут быть разделены на составные части больше, чем бит. К ним относятся числовые, символьные, логические и другие данные. Простые структуры данных служат основой для построения сложных структур дан- ных — массивов, списков, графов, деревьев и др. В языках программирования понятие «структуры данных» тесно связано с понятием «типы данных». Любые данные, т. е. константы, переменные, значения функций или выражения, ха- рактеризуются своими типами. Информация по каждому типу однозначно определяет: 1) множество допустимых значений, которые может иметь тот или иной объект описываемого типа; 2) множество допустимых операций, которые применимы к объ- екту описываемого типа; 3) объём выделенной памяти для хранения данных указанного типа. Некоторые простые типы данных языка Pascal приведены на рис. 2.10. рис. 2.10. Некоторые простые типы данных языка Pascal 88 Глава 2. алгоритмы и программирование 7.2. некоторые сведения о языке программирования Pascal Основными элементами языка Pascal являются: • алфавит языка (латинские буквы, арабские цифры, специаль- ные символы); • служебные слова, значение которых в языке программирова- ния строго определено; • постоянные и переменные величины; • знаки операций (табл. 2.2); • стандартные функции; • выражения; • операторы (языковые конструкции, с помощью которых в программах записываются действия, выполняемые над дан- ными в процессе решения задачи). Все величины имеют имена (идентификаторы), формируемые по определённым правилам: • имя может состоять из буквы или последовательности букв латин ского алфавита, цифр и символа подчёркивания, но начинаться такая последовательность должна с буквы или символа подчёр кивания; • желательно, чтобы имя отражало смысл величины; • имя не должно совпадать ни с одним из зарезервированных слов. Таблица 2.2 Операции в языке Pascal Арифметические операции Операции отношения + Сложение = Равно – Вычитание <> Не равно * Умножение > Больше / Деление < Меньше div Целочисленное деление <= Меньше или равно mod Остаток от целочисленного деления >= Больше или равно 89 Запись алгоритмов на языках программирования §7 Логические операции Строковые операции not Логическое отрицание + Сцепление (присоединение) and Логическое И or Логическое ИЛИ xor Исключающее ИЛИ Выражение — это формула, по которой вычисляется значение. Выражение может состоять из операндов (констант, переменных, стандартных функций), знаков операций и круглых скобок. Выра- жения записываются в строку; знаки операций не пропускаются. Порядок выполнения операций определяется скобками и прио- ритетом операций (табл. 2.3). Операции одинакового приоритета выполняются слева направо, если порядок выполнения не задан явно круглыми скобками. Вычисление выражения с вложенными скобками начинается с внутренних скобок. Таблица 2.3 Приоритет операций в языке Pascal Приоритет Операция 1 not 2 *, /, div, mod, and 3 +, –, or, xor 4 =, <>, >, <, >=, <= Программа на языке Pascal имеет следующую структуру: program <имя программы>; Заголовок программы var <переменные с указанием типов>; const <постоянные с указанием типов>; Блок описания ис- пользуемых данных begin <последовательность команд>; end. Блок описания дей- ствий по преобразо- ванию данных (про- граммный блок) Окончание табл. 2.2 90 Глава 2. алгоритмы и программирование Обязательными в ней являются два раздела: описания данных и описания действий, которые над этими данными необходимо выполнить. Данные, обрабатываемые компьютером, хранятся в памяти. С точки зрения языка Pascal она разделена на секции, называ- емые переменными. Каждая переменная имеет имя, тип и зна- чение; значения переменных могут меняться в ходе выполнения программы. Блок описания действий начинается со слова begin, а закан- чивается словом end и знаком точки. Действия представляются операторами (табл. 2.4). Операторы языка Pascal разделяются точкой с запятой. Операторы бывают простые и составные (за- ключённые в операторные скобки begin … end). Таблица 2.4 Основные операторы языка Pascal Название Общий вид Присваивание a:=b Ввод с клавиатуры read(a) Вывод на экран write(a) Условный if <условие> then <оператор 1> else <оператор 2> Цикл с предусловием while <условие> do <тело цикла (операторы)> Цикл с постусловием repeat <тело цикла (операторы)> until <условие> Цикл с увеличиваю- щимся параметром for <целочисленная переменная>:=<начальное значение> to <конечное значение> do <тело цикла (операторы)> Цикл с уменьшаю- щимся параметром for <целочисленная переменная>:=<начальное значение> downto <конечное значение> do <тело цикла (операторы)> 91 Запись алгоритмов на языках программирования §7 Пример 1. В начале этой главы мы обсуждали алгоритмы нахождения простых чисел. Напишем программу, проверяющую, является ли заданное натуральное число n простым. Самый простой путь решения этой задачи — проверить, имеет ли данное число n (n >= 2) делители в интервале [2; n – 1]. Если делители есть, число n — составное, если — нет, то — простое. В программе будем использовать логическую переменную flag: • если flag = true, то n — простое число; • если flag = false, то n — составное число (если у числа n есть делители, то «флаг выключаем» с помощью оператора присваивания flag := false). var n, i: longint; flag: boolean; begin writeln('Введите n'); read(n); flag:=true; for i:=2 to n-1 do if n mod i = 0 then flag:=false; if flag then writeln('Да') else writeln('Нет') end. В этой программе мы проверяли, нет ли у числа n делителей из интервала [2; n – 1]. Но если n = a · b, то меньшее из чисел a, b не больше n (в противном случае оба числа были бы больше n , а следовательно, их произведение было бы больше n). Кроме того, из делимости числа n на a автоматически следует, что n де лится и на n/a. Усовершенствуйте приведённую выше программу с учётом этих соображений. Проверку, является ли заданное натуральное число n >= 2 простым, мы осуществили методом перебора всех возможных его делителей. Метод перебора используется для решения достаточно широкого круга задач. Пример 2. Применим метод перебора для поиска наибольшего общего делителя (НОД) двух натуральных чисел a и b. Начнём перебор с d — наименьшего из чисел a и b. Это первый, очевидный кандидат на роль их наибольшего общего 92 Глава 2. алгоритмы и программирование делителя. И далее, пока не найдём d, на которое оба числа де- лятся нацело, будем уменьшать его на единицу. Как только такое деление произойдёт, останавливаем уменьшение d. Полученное значение d и будет наибольшим общим делителем чисел a и b. var a, b, d: integer; begin write('Введите два числа: '); readln(a, b); if athen d:=a else d:=b; while (a mod d <> 0) or (b mod d <> 0) do d:=d - 1; write('НОД = ', d) end. 7.3. анализ программ с помощью трассировочных таблиц Для анализа свойств алгоритма и проверки его соответствия решаемой задаче используются трассировочные таблицы. В них фиксируется пошаговое исполнение алгоритма (программы), что позволяет наглядно представлять значения переменных, изменя- ющиеся при его выполнении. Поэтому трассировочные таблицы иначе называют таблицами значений. Используются трассировочные таблицы двух видов: 1) таблицы, каждая строка которых отражает результат одного действия; 2) таблицы, каждая строка которых отражает результат выпол- нения группы действий. Пример 3. Определим значения переменных a и b, получен- ные в результате выполнения следующей программы: var a, b: integer; begin a:=5; b:=1; while b<=a do begin b:=b + 1; 93 Запись алгоритмов на языках программирования §7 a:=a - 1; end; writeln(a); writeln(b) end. Составим трассировочную таблицу первого вида. В её заголов- ке поместим имена всех переменных, используемых в програм- ме. В отдельном столбце будем записывать команды и условия, имеющиеся в программе. Каждая строка таблицы соответствует одному шагу алгоритма. Чтобы не загромождать таблицу, будем записывать в каждой строке только то значение переменной, ко- торое получено на соответствующем шаге. № шага Команда или условие Значение выражения a b 1 a:=5 5 5 2 b:=1 1 1 3 b<=a да 4 b:=b+1 2 2 5 a:=a-1 5 4 6 b<=a да 7 b:=b+1 3 3 8 a:=a-1 3 3 9 b<=a да 10 b:=b+1 4 4 11 a:=a-1 2 2 12 b<=a нет 13 writeln(a) 2 14 writeln(b) 4 Из таблицы видно, что в результате работы переменные при- няли значения: a = 2 и b = 4. |