Учебник. А. Ю. Босова Москва бином. Лаборатория знаний 2016 11 класс Базовый уровень Учебник
 Скачать 4.61 Mb.
|
|
Глава 2. алгоритмы и программирование Пример 4. Определим значение переменной s, полученное в результате выполнения следующей программы: var s, k, d: integer; begin s:=0; d:=10; for k:=5 to 10 do s:=s+d; writeln(s) end. Построим трассировочную таблицу второго вида, отражая в каждой строке результат группы действий. Группу действий огра- ничим контрольной точкой: выполнение алгоритма продолжается до контрольной точки и приостанавливается после выполнения отмеченной ею строки. Будем считать, что контрольная точка (КТ) поставлена на строке s := s + d. Результат в КТ k s d Начальные значения – 0 10 1 5 10 2 6 20 3 7 30 4 8 40 5 9 50 6 10 60 Итак, в результате работы программы переменная приняла значение s = 60. Каким должно быть значение d, чтобы в результате работы про граммы переменная приняла значение s = 186? Существует ли та кое значение d, что в результате работы программы переменная примет значение s = 212? 95 Запись алгоритмов на языках программирования §7 Пример 5. Определим значение переменной s, полученное в результате выполнения следующей программы: var s, i, j: integer; begin s:=0; for i:=1 to 3 do for j:=3 downto i do s:=s + i + j; writeln(s) end. Трассировочная таблица может иметь вид: Результат в КТ i j s Начальные значения – – 0 1 1 3 4 2 2 7 3 1 9 4 2 3 14 5 2 18 6 3 3 24 Результат: 24 Пример 6. Выясним, для чего предназначена следующая про- грамма: var n: integer; nd: string; begin writeln('Введите натуральное число'); read(n); nd:=''; while n<>0 do begin if n mod 2=1 then nd:='1'+nd else nd:='0'+nd; n:=n div 2 end; writeln(nd); end. 96 Глава 2. алгоритмы и программирование Прежде всего, обратим внимание на то, что в ней кроме пе- ременной n целого типа используется строка nd, для которой символ «+» обозначает операцию сцепления строк. Начальное значение n вводится с клавиатуры, поэтому зададим его по сво- ему усмотрению, например n = 12. Результат в КТ nd n Начальные значения '' 12 1 '0' 6 2 '00' 3 3 '100' 1 4 '1100' 0 Результат: 1100 Выполните программу для n = 25. Какую задачу, по вашему мне нию, решает эта программа? 7.4. Другие приёмы анализа программ Трассировочная таблица — наглядный, но не универсальный инструмент анализа программ. Например, её затруднительно стро- ить, если в алгоритме много шагов. Пример 7. Требуется выяснить, какое число будет напечатано в результате выполнения следующей программы: var n, s: integer; begin n:=0; s:=400; while s<2992 do begin s:=s+12; n:=n+2 end; write(n) end. 97 Запись алгоритмов на языках программирования §7 Трассировочная таблица для этой программы будет содержать не одну сотню строк. Попробуем проанализировать программу иначе. 1. Выясним, какую функцию выполняет каждая из переменных, задействованных в программе. Начальное значение переменной s = 400. При каждом выпол- нении тела цикла к значению s прибавляется число 12. Начальное значение переменной n = 0. При каждом выпол- нении тела цикла значение переменной увеличивается на 2: n = 2, если тело цикла выполнено 1 раз; n = 4 — если 2 раза; n = 6 — если 3 раза и т. д. Таким образом, искомое значение n — это 2 ∙ k, где k — число выполнений тела цикла. 2. Выясним, при каком условии произойдёт выход из цикла. Цикл выполняется, пока s < 2992. Следовательно, цикл за- вершится при достижении s значения, равного или большего 2992. 3. Выясним, сколько раз выполнится тело цикла, вычислив зна- чение выражения: (2992 – 400)/12 = 216. После того как тело цикла выполнится 216 раз, значение переменной s будет рав- но 2992, что является условием выхода из цикла. При этом n = 2 ∙ 216 = 432. Выясните, каким будет результат работы программы, если в ней условие выхода из цикла будет изменено на: 1) s < 2990; 2) s <= 2992; 3) s <= 300. Пример 8. Получив на вход некоторое натуральное число x, эта программа выводит два числа — m и n. var x, m, n: integer; begin readln(x); m:=0; n:=1; while x>0 do begin m:=m+1; n:=n*(x mod 10); x:=x div 10; end; writeln(m); write(n) end. 98 Глава 2. алгоритмы и программирование Известно, что при некотором значении x были выведены чи- сла 5 и 25. Выясним, сколько существует разных значений x, при вводе которых может быть получен такой результат. Выясним, какие именно данные накапливаются в переменных. Начальное значение переменной x задаётся пользователем. Тип этой переменной integer, следовательно, она не может пре- вышать 32 767. В цикле значение переменной x изменяется по правилу, заданному командой: x:=x div 10 При таком преобразовании значение переменной x уменьша- ется в 10 раз и дробная часть результата отбрасывается. Можно сказать, что при каждом выполнении тела цикла от значения переменной x «отсекается» одна цифра справа. Начальное значение переменной m = 0. При каждом выпол- нении цикла значение переменной m увеличивается на единицу. Можно сказать, что в m подсчитывается количество цифр, «от- сечённых» от x. Начальное значение переменной n = 1. В цикле значение пе- ременной n изменяется по правилу, заданному командой: n:=n*(x mod 10) Здесь x mod 10 — не что иное, как последняя цифра чи- сла x. Таким образом, в переменной n накапливается произведе- ние цифр числа x, взятых справа налево. Выход из цикла осуществляется при x <= 0, т. е. когда все значащие цифры этого числа будут рассмотрены. Следовательно, если на экран первой выводится цифра 5, то исходное число пятизначное. Второе число указывает на то, что 25 — это произведение всех цифр исходного числа x. Рассмотрим варианты пятизначных чисел, произведение цифр которых равно 25. Например, 11551, 51151 и т. д. Очевидно, в записи любого из таких чисел должны быть две пятёрки и три единицы. Применение известной вам формулы из комбинатори- ки позволяет вычислить число разных чисел, удовлетворяющих такому условию, — это 10. О какой формуле идёт речь? Приведите эту формулу и выполните соответствующие вычисления. Укажите наибольшее и наименьшее числа, удовлетворяющие условию задачи. Выпишите все числа, удовлетворяющие условию задачи. 99 Запись алгоритмов на языках программирования §7 СамОе ГлаВнОе Компьютерную программу можно считать последовательно- стью строк символов некоторого алфавита. Современные системы программирования и языки допускают использование визуаль- ных элементов (окон, иконок и др.) для построения программ, в частности для создания интерфейса пользователя. Тем не менее основная, алгоритмическая, часть любой программы строится с использованием символьных средств. В основной школе вы познакомились со школьным алгорит- мическим языком КуМир и языком программирования Pascal (Паскаль). В 11 классе мы продолжаем работать с языком Pascal. Компьютер оперирует только одним видом данных — от- дельными битами, или двоичными цифрами. Задачи, решаемые с помощью компьютера, оперируют данными, имеющими форму чисел, символов, текстов и более сложных структур. Алгоритмы для обработки этих данных создаются с учётом их структуры — множества элементов данных и множества связей между ними. Различают простые и сложные структуры данных. Простые структуры данных не могут быть разделены на составные части больше, чем бит. К ним относятся числовые, символьные, ло- гические и другие данные. Простые структуры данных служат основой для построения сложных структур данных — массивов, списков, графов, деревьев и др. Для анализа свойств алгоритма и проверки его соответствия решаемой задаче используются трассировочные таблицы. В них фиксируется пошаговое исполнение алгоритма (программы), что позволяет наглядно представлять значения переменных, изменя- ющиеся при его выполнении. Используются трассировочные таб- лицы двух видов: 1) таблицы, каждая строка которых отражает результат одного действия; 2) таблицы, каждая строка которых отражает результат выпол- нения группы действий. Вопросы и задания 1. Что такое язык программирования? Опишите состав и ин- терфейс среды разработки программ на используемом вами языке программирования. 2. Приведите примеры структур данных, используемых в язы- ке программирования Pascal. 100 Глава 2. алгоритмы и программирование 3. Кратко охарактеризуйте основные элементы языка програм- мирования Pascal. 4. Опишите структуру программы на языке Pascal. 5. Для чего предназначены трассировочные таблицы? 6. Вещественные числа x, y, z являются исходными данными для следующего алгоритма: 1) переменной m присвоить значение x; 2) сравнить значения m и y: если y больше m, переменной m присвоить значение y; 3) сравнить значения m и z: если z больше m, переменной m присвоить значение z. Выясните, какую задачу решает этот алгоритм. Запишите его на языке программирования Pascal. Решите аналогич- ную задачу для чисел x, y, z и w. 7. Определите значение переменной n, которое будет получено в результате выполнения следующей программы: var s, n: integer; begin s:=0; n:=1; while sqr(s+2)<125 do begin n:=n*2; s:=s+2; end; writeln(n) end. 8. Определите значение переменной s, которое будет получено в результате выполнения следующей программы: var s, i, j: integer; begin s:=0; for i:=1 to 3 do for j:=i to 4 do s:=s+2*i-j; writeln (s) end. 101 Запись алгоритмов на языках программирования §7 9. Требуется выяснить, какое число будет выведено в результа- те выполнения следующей программы: var n, s: integer; begin n:=0; s:=1000; while s>=100 do begin s:=s-2; n:=n+1 end; write(n) end. 10. Получив на вход число x, приведённая ниже программа вы- водит два числа — m и n. var x, m, n: integer; begin readln(x); m:=0; n:=0; while x>0 do begin if n m:=m+1; x:=x div 10; end; writeln(m); write(n) end. Известно, что при некотором значении x были выведены числа 4 и 8. Укажите наибольшее и наименьшее из таких чисел x. Сколько всего существует таких x? 11. Напишите программу, выводящую на экран все чётные трёх- значные числа. 12. Напишите программу, подсчитывающую сумму квадратов всех чисел от 1 до n. 13. Напишите программу, позволяющую определить, входит ли заданная цифра в некоторое целое неотрицательное число. 14. Разработайте программу перевода десятичного натурального числа n в троичную систему счисления. 102 Глава 2. алгоритмы и программирование 15. Разработайте программу, которая выводит сообщение «Да», если точка с координатами (x, y) принадлежит закрашенной области, и «Нет» в противном случае. 16. Шифр кодового замка является двузначным числом. Бурати- но забыл код, но помнит, что сумма цифр этого числа, сло- женная с их произведением, равна самому числу. Напишите все возможные варианты кода, чтобы Буратино смог быстрее открыть замок. Решите задачу методом перебора. § 8 Структурированные типы данных. массивы Мы повторили основные приёмы работы с простыми типами данных. Из элементов простых типов в языке Pascal можно обра- зовывать составные типы данных (структуры данных). Примером таких структур являются одномерные массивы. массив — это поименованная совокупность однотипных элементов, упорядоченных по индексам, определяющим положение элемента в массиве. 8.1. Общие сведения об одномерных массивах Массив в языке Pascal — это набор однотипных данных, при- чём количество этих данных фиксировано и определяется при описании массива. Все переменные, входящие в массив, имеют одно и то же имя — имя массива, а различаются они по индек- су — номеру (месту) в массиве. 103 Структурированные типы данных. массивы §8 Описание массива выглядит так: array [<тип индекса>] of <тип компонент> Здесь: • array и of — служебные слова («массив» и «из»); • <тип индекса> — описание индексации компонент (элементов) массива; • <тип компонент> — тип величин, составляющих массив. Например: • var day: array [1..365] of integer — 365 целочисленных эле- ментов пронумерованы от 1 до 365; • var tem: array [1..12] of real — 12 вещественных элементов пронумерованы от 1 до 12; • var ocenka: array [2..5] of integer — 4 целочисленных эле- мента пронумерованы от 2 до 5; • const n = 10; var slovo: array [1..n] of string — n строковых величин пронумерованы от 1 до n. Вспомним основные приёмы работы с массивами. Пример 1. Имеются сведения о количестве ежедневных осад- ков в течение июня месяца в некотором регионе. Требуется найти среднее количество осадков и вывести таблицу, в которой для каждого дня месяца указать количество осадков в этот день и его отклонение от среднемесячного значения. Для решения этой задачи данные о количестве ежедневных осадков в течение месяца будут просмотрены дважды: 1) при поиске среднего значения; 2) при расчёте отклонения. Для решения задачи нам понадобится массив из 30 вещест- венных чисел. Назовём его osad. В программе будет два цикла. В первом цикле мы будем вводить значения элементов массива и сразу же подсчитывать их сумму — по завершении цикла мы получим сумму осадков, выпавших в течение месяца. Во втором цикле мы будем выводить строки таблицы и вычислять значения отклонений. При работе с элементами массива будем пользоваться пере- менной osad[i]; значение индекса i при этом будет изменяться от 1 до 30 с шагом 1. Для вычисления среднего значения задей- ствуем вещественную переменную sred, присвоив ей начальное значение 0 и последовательно накапливая в ней сумму осадков, выпавших в течение месяца. Разделив по завершении цикла 104 Глава 2. алгоритмы и программирование полученное значение на 30, вычислим требуемое среднемесячное количество осадков и присвоим результат этой же переменной. Program osadki; var osad: array [1..30] of real; sred: real; i: integer; begin sred:=0; writeln('Введите количество осадков по дням'); for i:=1 to 30 do begin write(i, ' июня: '); readln(osad[i]); sred:=sred + osad[i] end; sred:=sred/30; writeln('День Количество осадков Отклонение'); for i:=1 to 30 do writeln(i:3, osad[i]:15:3, osad[i] - sred:12:2) end. Найдите в Интернете информацию о количестве ежедневных осадков, выпавших в течение месяца, в вашем регионе. Исполь зуя эти данные, выполните программу в среде программирования Pascal. Выполните аналогичные расчёты с помощью электронных таблиц. Чаще всего массив обрабатывается в цикле for. Но при работе с массивами можно использовать и другие циклы. Пример 2. Имеется массив символов. Требуется вывести на экран элементы данного массива в обратном порядке. Элементами массива символов могут быть любые символы, имеющиеся на клавиатуре, причём каждому элементу соответству- ет именно один символ. Если в качестве элементов нашего масси- ва рассматривать последовательности букв, образующие некоторое слово или фразу на естественном языке, то, решив поставленную задачу, мы научимся строить «перевёртыши» слов. Будем рассматривать слова и фразы не более чем из 20 сим- волов, задав соответствующую размерность массива: simbol: array [1..20] of char; 105 Структурированные типы данных. массивы §8 Если какое-то слово или фраза будут короче, то часть массива окажется не занятой, но это не повлияет на работу программы. Договоримся признаком конца слова считать точку — ввод сим- волов продолжается, пока не введена точка; после ввода точки ввод символов прекращается. program slova; var simbol: array [1..20] of char; i, n: integer; begin writeln('Введите слово - цепочку символов — с точкой в конце'); i:=0; repeat i:=i+1; read(simbol[i]); until simbol[i]='.'; n:=i-1; writeln('Перевёрнутое слово: '); for i:=n downto 1 do write(simbol[i]); end. Запустите программу в среде программирования Pascal. Модифицируйте программу так, чтобы в начале её работы поль зователю задавался вопрос о количестве символов, которые он бу дет вводить. Какой цикл при этом лучше использовать? Как изменить программу, чтобы она выводила на экран в обрат ном порядке элементы целочисленного массива? К типовым задачам обработки одномерных массивов, решае- мым в процессе их однократного просмотра, относятся: • задачи поиска элементов с заданными свойствами, в том чи- сле максимумов и минимумов; • проверка соответствия элементов массива некоторому условию (подсчёт количества или суммы элементов, удовлетворяющих некоторому условию; проверка соответствия всех элементов массива некоторому условию; проверка массива на упорядо- ченность и др.); • задачи на удаление и вставку элементов массива; • задачи на перестановку всех элементов массива в обратном порядке и т. д. |