Учебник. А. Ю. Босова Москва бином. Лаборатория знаний 2016 11 класс Базовый уровень Учебник

• Название: А. Ю. Босова Москва бином. Лаборатория знаний 2016 11 класс Базовый уровень Учебник
• Анкор: Учебник
• Дата: 24.03.2022
• Размер: 4.61 Mb.
• Имя файла: bosova_uch_11_.pdf
• Тип: Учебник; #412962
• страница: 10 из 21

Глава 2. алгоритмы и программирование
Сортировка — один из наиболее распространённых процессов современной обработки данных. Под сортировкой (упорядочением) массива понимают перераспределение значений его элементов в некотором определённом порядке.
Вопросы и задания
1. Приведите примеры задач поиска информации в больших массивах данных.
2. Почему важно уметь решать задачи, связанные с обработкой массивов, путём однократного просмотра массива?
3. Программист написал программу суммирования элементов массива, но допустил в ней ошибку.
Program summa;
const n=10;
var a: array [1..n] of integer; s, i: integer;
begin
s:=0;
for i:=1 to n do
begin
readln(a[i]);
s:=s+i
end;
writeln('s=', s)
end.
1) Что получится в результате выполнения этой программы, если в качестве элементов массива ввести числа: 1, –2, 3,
–4, 5, –6, 7, –8, 9, –10?
2) Придумайте пример такого массива, обработка которого с помощью этой программы приводила бы к правильному результату.
3) Найдите ошибку, допущенную программистом.
4. Программист написал программу нахождения произведения элементов массива, но допустил в ней ошибку.
Program proizv;
const n=10;
var a: array [1..n] of integer; p, i: integer;
begin
p:=0;
for i:=1 to n do

117
Структурированные типы данных. массивы
§8
begin
readln(a[i]);
p:=p*a[i]
end;
writeln('p=', p)'
end.
1) Что получится в результате выполнения этой программы, если в качестве элементов массива ввести числа: 1, –2, 3,
–4, 5, –6, 7, –8, 9, –10?
2) Придумайте пример такого массива, обработка которого с помощью этой программы приводила бы к правильному результату.
3) Найдите ошибку, допущенную программистом.
5. На блок-схеме представлен алгоритм одновременного поиска максимального и минимального значений элементов мас сива:
Реализуйте этот алгоритм на языке программирования и вы- полните программу для массива из задания 6.

118
Глава 2. алгоритмы и программирование
6. Имеется одномерный целочисленный массив из семи элемен- тов:
i
1 2
3 4
5 6
7
a[i]
10 12 5
8 4
15 20
Каким будет результат преобразования массива по следую- щему алгоритму?
for i:=k+1 to n do
a[i-1]:=a[i];
7. Имеется ли разница между операциями вставки в массив элемента на место с индексом k и замены значения элемен- та массива с индексом k? Обоснуйте свой ответ.
8. Имеется одномерный целочисленный массив из семи элемен- тов:
i
1 2
3 4
5 6
7
a[i]
10 12 5
8 4
15 20
Каким будет результат преобразования массива по следую- щему алгоритму?
for i:=1 to n div 2 do
begin
r:=a[i];
a[i]:=a[n-i+1];
a[n-i+1]:=r
end;
9. Дана программа:
const n=5;
const a: array[1..n] of integer=(1,2,6,4,6);
var i, max1, max2: integer;
begin
max1:=a[1];
max2:=a[2];
for i:=2 to n do
if a[i]>max1
then begin max2:=max1; max1:=a[i]; end
else if a[i]>max2 then max2:=a[i];
writeln('max1=', max1, ', max2=', max2);
end.

119
Структурное программирование
§9
Что получится в результате выполнения этой программы?
Какую задачу решает эта программа?
10. Дано натуральное десятичное число n <= 32 000. Напишите программу, в которой:
1) из цифр данного числа формируется одномерный цело- численный массив;
2) определяются наибольшая и наименьшая цифры данного числа;
3) находятся сумма и произведение цифр, образующих дан- ное число.
11. Требуется упорядочить по весу в порядке неубывания n не- прозрачных банок с чаем, имея в своём распоряжении толь- ко чашечные весы без гирь. Опишите возможный алгоритм решения этой задачи.
§ 9
Структурное программирование
9.1. Общее представление
о структурном программировании
Программирование как род занятий и сфера деятельности интенсивно развивается со второй половины прошлого века. За это время сложились определённые технологии, способствующие повышению производительности труда программистов, в том числе сокращению числа ошибок, упрощению отладки, моди- фикации и сопровождения программного обеспечения. Особенно это важно при разработке больших и сложных программных комплексов, осуществляемой усилиями целых коллективов про- граммистов.
Одна из таких технологий — структурное программирова- ние — была разработана ещё в начале 70-х годов прошлого века и связана с именем выдающегося нидерландского ученого Эдсгера
Дейкстры (1930–2002).
Структурное программирование — технология разработки про­
граммного обеспечения, в основе которой лежит представление программы в виде иерархической структуры логически целостных фрагментов (блоков).

120
Глава 2. алгоритмы и программирование
Перечислим некоторые принципы структурного программиро- вания.
1. Любая программа строится из трёх базовых управляющих конструкций: последовательность, ветвление, цикл.
2. В программе базовые управляющие конструкции могут быть вложены друг в друга произвольным образом.
3. Повторяющиеся фрагменты программы можно оформить в виде подпрограмм (процедур и функций). В виде подпрограмм можно оформить логически целостные фрагменты программы, даже если они не повторяются.
4. Все перечисленные конструкции должны иметь один вход и один выход.
5. Разработка программы ведётся пошагово, методом «сверху вниз».
О методе разработки алгоритма «сверху вниз» вы получили представление в курсе информатики основной школы. Напомним его ключевые моменты на примере разработки некоторой про- граммы.
Сначала пишется короткий текст основной программы. В ней вместо каждого логически целостного фрагмента вставляется вы- зов подпрограммы, которая будет выполнять этот фрагмент. Вме- сто настоящих, работающих, подпрограмм в программу вставля- ются так называемые заглушки. Как правило, они удовлетворяют требованиям интерфейса заменяемого фрагмента, но не выполня- ют его функций.
На следующем шаге следует убедиться, что подпрограммы вызываются в правильной последовательности, т. е. верна общая структура программы.
После этого подпрограммы-заглушки последовательно заменя- ются на полнофункциональные, причём разработка каждой под- программы ведётся тем же методом, что и основной программы.
На каждом этапе проверяется, что уже созданная программа пра- вильно работает по отношению к подпрограммам более низкого уровня.
Разработка заканчивается тогда, когда ни на одном уровне не останется ни одной заглушки. Полученная программа проверяется и отлаживается.
Такая последовательность гарантирует, что на каждом этапе разработки программист будет иметь дело с обозримым и понят- ным ему множеством фрагментов, осознавая, что общая структура всех более высоких уровней программы верна.

121
Структурное программирование
§9
9.2. Вспомогательный алгоритм
Пример 1.
Применим метод
рис. 2.11. Отрезок AB
«сверху вниз» для разработки алго- ритма нахождения периметра тре- угольника, заданного координатами своих вершин.
Пусть XA, XB, YA, YB, XC,
YC — координаты вершин треуголь- ника АВС. Его периметр — сумма длин отрезков АВ, ВС и АС.
Из курса геометрии вам известна формула для вычисления длины от- резка AB по координатам его концов
(рис. 2.11):
d
XA XB
YA YB




(
)
(
)
2 2
Действия по вычислению длины отрезка представляют собой логически целостный фрагмент, который целесообразно оформить в виде вспомогательного алгоритма.
Вспомогательный алгоритм — это алгоритм, целиком используе­
мый в составе другого алгоритма.
На рисунке 2.12 представлены:
1) блок-схема алгоритма вычисления периметра треуголь- ника, предполагающая вызов вспомогательного алгоритма
Отрезок;
2) блок-схема вспомогательного алгоритма Отрезок.
При вызове вспомогательного алгоритма указываются его па- раметры (входные данные и результаты). Параметрами вспомо- гательного алгоритма Отрезок являются величины X1, Y1, X2,
Y2, D. Это формальные параметры, они используются при опи- сании алгоритма. При конкретном обращении к вспомогательно- му алгоритму формальные параметры заменяются фактическими параметрами, т. е. именно теми величинами, для которых будет исполнен вспомогательный алгоритм. Типы, количество и поря- док следования формальных и фактических параметров должны совпадать.

122
Глава 2. алгоритмы и программирование
рис. 2.12. Алгоритм вычисления периметра треугольника и вспомога- тельный алгоритм Отрезок
Команда вызова вспомогательного алгоритма исполняется сле- дующим образом:
1) формальные входные данные вспомогательного алгоритма за- меняются значениями фактических входных данных, указан- ных в команде вызова вспомогательного алгоритма;
2) для заданных входных данных исполняются команды вспо- могательного алгоритма;
3) полученные результаты присваиваются переменным с именами фактических результатов;
4) осуществляется переход к следующей команде основного ал- горитма.
Каким будет результат работы алгоритма при следующих исходных данных: XA = 1, XB = 2, XC = 3, YA = 1, YB = 3, YC = 1.

123
Структурное программирование
§9
9.3. рекурсивные алгоритмы
Алгоритм называется рекурсивным, если на каком­либо шаге он прямо или косвенно обращается сам к себе.
Пример 2. Как известно, факториал натурального числа n определяется следующим образом: n! = 1 ∙ 2 ∙ 3 ∙ ... ∙ n; 0! считается равным единице (0! = 1).
Иначе это можно записать так:
F(n) = 1 при n ≤ 1;
F(n) = F(n →– 1) ∙ n при n > 1.
В определении факториала через рекурсию имеется условие
n ≤ 1, при достижении которого вызов рекурсии прекращается.
В рекурсивном определении должно присутствовать ограничение
(граничное условие), при выходе на которое дальнейшая инициация рекурсивных обращений прекращается.
Пример 3. Определим функцию S(n), вычисляющую сумму цифр в заданном натуральном числе n:
S(n) = n при n < 10;
S(n) = S(n div 10) + n mod 10 при n ≥ 10.
Самостоятельно определите функцию K(n), которая возвращает ко­
личество цифр заданного натурального числа n.
Пример 4. Алгоритм вычисления значения функции F(n), где
n — натуральное число, задан следующими соотношениями:
F(n) = 1 при n ≤ 2;
F(n) = F(n –→ 1) + 3 ∙ F(n →– 2) при n > 2.
Требуется выяснить, чему равно значение функции F(7).
По условию, F(1) = F(2) = 1.
F(3) = F(2) + 3 ∙ F(1) = 1 + 3 ∙ 1 = 4.
F(4) = F(3) + 3 ∙ F(2) = 4 + 3 ∙ 1 = 7.
F(5) = F(4) + 3 ∙ F(3) = 7 + 3 ∙ 4 = 19.
F(6) = F(5) + 3 ∙ F(4) = 19 + 3 ∙ 7 = 40.
F(7) = F(6) + 3 ∙ F(5) = 40 + 3 ∙ 19 = 97.

124
Глава 2. алгоритмы и программирование
Подобные вычисления можно проводить в уме, а их резуль- таты фиксировать в таблице:
n
1 2
3 4
5 6
7
F(n)
1 1
4 7
19 40 97
Пример 5. Исполнитель Плюс имеет следующую систему команд:
1) прибавь 1;
2) прибавь 2;
3) прибавь 4.
С помощью первой из них исполни- тель увеличивает число на экране на 1, с помощью второй — на 2, с помощью третьей — на 4. Про- грамма для исполнителя Плюс — это последовательность команд.
Выясним, сколько разных программ, преобразующих число 20 в число 30, можно составить для этого исполнителя.
Количество программ, с помощью которых можно получить некоторое число n, будем рассматривать как функцию K(n).
Число, меньшее 20, при заданных начальных условиях и си- стеме команд исполнителя Плюс получить невозможно. Следова- тельно, при n < 20 К(n) = 0.
Для начального числа 20 количество программ равно 1: сущест вует только одна пустая программа, не содержащая ни одной команды. Можем записать: К(n) = 1 при n = 20.
Любое число n > 20 может быть получено из чисел n – 1,
n – 2 и n – 4 одной из трёх команд, входящих в систему команд исполнителя — «прибавь 1», «прибавь 2» и «прибавь 4» соот- ветственно. При этом каждая программа получения из исходно- го числа чисел n – 1, n – 2 и n – 4 удлинится на одну команду и будет приводить к числу n. Следовательно, К(n) = К(n – 1) +
+ К(n – 2) + К(n – 4).
Запишем все соотношения, определяющие функцию К(n):
К(n) = 0 при n < 20;
К(n) = 1 при n = 20;
К(n) = К(n – 1) + К(n – 2) + К(n – 4) при n > 20.
Заполним по этой формуле таблицу для всех значений n от
20 до 30:
n
20 21 22 23 24 25 26 27 28 29 30
K(n)
1 1
2 3
6 10 18 31 55 96 169

125
Структурное программирование
§9
Итак, существует 169 различных программ, с помощью ко- торых исполнитель Плюс может преобразовать число 20 в 30.
Любой объект, который частично определяется через самого себя, называется рекурсивным. Нас окружает множество рекурсивных объектов. Приведём примеры только некоторых из них.
1. Матрёшка — русская деревянная игрушка в виде расписной куклы, внутри которой находятся подобные ей куклы меньшего размера.
2. Два зеркала, поставленные друг напротив друга, — в них обра­
зуются два коридора из затухающих отражений. Это, например, можно наблюдать в спальном железнодорожном вагоне.
3. Примером рекурсивной структуры является замечательное сти­
хотворение Р. Бернса «Дом, который построил Джек» в переводе
С. Маршака.

126
Глава 2. алгоритмы и программирование
4. Рекурсивную природу имеют геометрические фракталы. На ри­
сунке представлено построение одного из геометрических фрак­
талов — треугольника Серпинского. Чтобы его получить, нужно взять равносторонний треугольник с внутренней областью, прове­
сти в нём средние линии и «выкинуть» центральный из четырёх образовавшихся маленьких треугольников. Дальше эти же дейст­
вия нужно повторить с каждым из оставшихся трёх треугольников, и т. д.
9.4. Запись вспомогательных алгоритмов
на языке Pascal
Запись вспомогательных алгоритмов в языках программиро- вания осуществляется с помощью подпрограмм. В Паскале раз- личают два вида подпрограмм: процедуры и функции.
Процедура — подпрограмма, имеющая произвольное количество входных и выходных данных.
Описание процедуры имеет вид:
procedure <имя_процедуры>(<описание параметров-значений>;
var: <описание параметров-переменных>);
begin
<операторы>
end;
В заголовке процедуры после её имени приводится перечень формальных параметров и их типов. Для вызова процедуры до- статочно указать её имя со списком фактических параметров.
При этом между фактическими и формальными параметрами должно быть полное соответствие по количеству, порядку следо- вания и типу.
Пример 6. Запишем на языке Pascal программу нахождения периметра треугольника, заданного координатами его вершин.
Вспомогательный алгоритм оформим с помощью процедуры.

127
Структурное программирование
§9
program perimetr;
var xa,ya,xb,yb,xc,yc,d,p: real;
procedure otrezok(x1,y1, x2,y2: real; var d: real);
begin
d:=sqrt(sqr(x1-x2)+sqr(y1-y2));
end;
begin
p:=0;
writeln('Ввод координат концов отрезка:');
writeln('xa, ya');
read(xa,ya);
writeln('xb, yb');
read(xb,yb);
writeln('xc, yc');
read(xc,yc);
otrezok(xa,ya,xb,yb,d);
p:=p+d;
otrezok(xa,ya,xc,yc,d);
p:=p+d;
otrezok(xc,yc,xb,yb,d);
p:=p+d;
writeln('p=',p)
end.
Выполните программу на компьютере.
Подумайте, каким образом можно модифицировать программу, чтобы вычислять с её помощью периметр n­угольника. Каким обра­
зом при решении этой задачи можно использовать массивы?
функция — подпрограмма, имеющая единственный результат, запи­
сываемый в ячейку памяти, имя которой совпадает с именем функ­
ции.
Описание функции имеет вид:
function <имя_функции>(<описание входных данных>):
<тип_функции>);
begin
<операторы>
end;
В заголовке функции после её имени приводится описание входных данных — указывается перечень формальных параметров

128
Глава 2. алгоритмы и программирование
и их типов. Там же указывается тип самой функции, т. е. тип результата. В блоке функции обязательно должен присутствовать оператор
<имя_функции> := <результат>;
Для вызова функции достаточно указать её имя со списком фактических параметров в любом выражении, в условиях (после слов if, while, until) или в операторе write главной программы.
Пример 7. Запишем на языке Pascal программу нахождения периметра треугольника, заданного координатами его вершин.
Вспомогательный алгоритм оформим с помощью функции.
program perimetr;
var xa,ya,xb,yb,xc,yc,p: real;
function d(x1,y1, x2,y2: real): real;
begin
d:=sqrt(sqr(x1-x2)+sqr(y1-y2));
end;
begin
writeln('Ввод координат концов отрезка:');
writeln('xa, ya');
read(xa,ya);
writeln('xb, yb');
read(xb,yb);
writeln('xc, yc');
read(xc,yc);
p:=p+d(xa,ya,xb,yb)+d(xa,ya,xc,yc)+d(xc,yc,xb,yb);
writeln('p=',p)
end.
Выполните программу на компьютере.
На основе этой программы напишите функцию, вычисляющую площадь треугольника по целочисленным координатам его вершин.
Используйте эту функцию для вычисления площади n­угольника.
СамОе ГлаВнОе
Структурное программирование — технология разработки про- граммного обеспечения, в основе которой лежит представление программы в виде иерархической структуры логически целостных фрагментов (блоков).

129
Структурное программирование
§9
Основные принципы структурного программирования заклю- чаются в том, что:
1) любая программа строится из трёх базовых управляющих кон- струкций: последовательность, ветвление, цикл;
2) в программе базовые управляющие конструкции могут быть вложены друг в друга произвольным образом;
3) повторяющиеся фрагменты программы можно оформить в виде подпрограмм (процедур и функций). В виде подпрограмм можно оформить логически целостные фрагменты программы, даже если они не повторяются;
4) все перечисленные конструкции должны иметь один вход и один выход;
5) разработка программы ведётся пошагово, методом «сверху вниз».
Вспомогательный алгоритм — это алгоритм, целиком исполь- зуемый в составе другого алгоритма.
Алгоритм называется рекурсивным, если на каком-либо шаге он прямо или косвенно обращается сам к себе.
Запись вспомогательных алгоритмов в языках программиро- вания осуществляется с помощью подпрограмм. В Паскале раз- личают два вида подпрограмм: процедуры и функции.
Вопросы и задания
1. В чём заключается сущность структурного программирова- ния? Какие преимущества обеспечивает эта технология?
2. Какой алгоритм называется вспомогательным?
3. Вспомните, в чём состоит суть метода последовательно- го построения (уточнения) алгоритма. Как он называется иначе?
4. Опишите основные шаги разработки программы методом
«сверху вниз».
5. Дан прямоугольный параллелепипед,
длины рёбер которого равны a, b и c. Требуется определить периметр треугольника, образованного диаго- налями его граней. Какой алгоритм целесообразно использовать при ре- шении этой задачи в качестве вспо- могательного?

130