Абрамов С.А., Гнездилова Г.Г., Капустина Е.Н., Селюн М.И. Задачи по программированию
Подождите немного. Документ загружается.
449. Даны действительные числа x
1
, y
1
, x
2
, y
2
, ..., x
6
, y
6
. Точки с
координатами (x
1
, y
1
), (x
2
, y
2
), (x
3
, y
3
) рассматриваются как вершины
первого треугольника, точки с координатами (x
4
, y
4
), (x
5
, y
5
), (x
6
, y
6
)—
второго треугольника. Выяснить, верно ли, что первый треугольник
целиком содержится во втором, и если да, определить площадь
области, принадлежащей внешнему треугольнику и не принадлежащей
внутреннему (на рис. 19 область заштрихована). (Определить
процедуру, позволяющую
выяснить, лежат ли две точки
в одной полуплоскости
относительно заданной
прямой (см. задачу 52
),
процедуру вычисления
расстояния между двумя
точками, а также процедуру
Рис. 19
вычисления площади треугольника по трем сторонам.)
450. Два треугольника заданы координатами своих вершин так,
как указано в предыдущей задаче. Выяснить, лежит ли какой-либо из
треугольников целиком внутри другого. Если да, построить стороны
треугольников и закрасить область, принадлежащую внешнему
треугольнику и не принадлежащую внутреннему(рис. 19). Построения
сторон и закраску области выполнить одним цветом. Если ни один из
треугольников не лежит целиком внутри другого, построить стороны
треугольников, используя для каждого треугольника свой цвет.
(Определить процедуру, позволяющую выяснить, лежат ли две точки в
одной полуплоскости относительно заданной прямой (см. задачу 52
), и
процедуру построения сторон треугольника по заданным координатам
вершин и номеру цвета.)
Рис. 20
451. Даны натуральные числа x
1
, y
1
, x
2
, y
2
, ..., x
6
, y
6
. Точки с
координатами (x
1
, y
1
), (x
2
, y
2
), (x
3
, y
3
) рассматриваются как три вершины
первого прямоугольника, точки с координатами (x
4
, y
4
), (x
5
, y
5
), (x
6
, y
6
)
– второго. Провести построения, аналогичные тем, которые были
описаны в предыдущей задаче в отношении треугольников.
Стороны прямоугольника считаются параллельными осям экрана (рис.
20
)
452. Представим себе, что в центре экрана сидит жучок,
который может перемещаться по прямой на указанное расстояние и
поворачиваться направо и налево. У жучка есть перо, которое может
оставлять след, повторяющий движение жучка. Если перо опущено,
след остается; если перо поднято, следа нет. Итак, жучок может
выполнять следующие приказы:
1) Forward – переместиться на заданное расстояние;
2) Left – повернуть налево на заданный угол;
3) Right – повернуть направо на заданный угол;
4) Pen Up – поднять перо;
5) Pen Down – опустить перо.
Реализовать процедуры Forward, Left, Right, Pen Up, Pen Down.
Процедуры должны взаимодействовать через глобальные переменные
xPos, yPos --координаты жучка на экране; Pen – признак, говорящий о
том, поднято перо или опущено; Angle -- угол, который образует
текущее направление перемещения жучка с осью абсцисс.
С помощью перечисленных процедур получить на экране:
а) Квадрат со стороной 75 единиц и центром, совпадающим с
центром экрана.
б) Прямоугольник с отношением сторон 1:2 и со срезанными
углами. Срезаются равнобедренные прямоугольные треугольники,
катеты которых имеют длину, равную 1/20 длины большей стороны
(рис. 21). Длина меньшей стороны – данная величина. Положение
прямоугольника на экране может быть выбрано произвольно.
Рис. 22
Рис. 21
в) Фигуру, составленную из пятнадцати квадратов, которая
изображена на рис. 22.
г) Четыре крупные цифры – текущий год; цифры должны быть
написаны по девятисегментному шаблону (как на почтовых
конвертах).
д) Те же цифры, что и в задании г), но написанные по
семисегментному шаблону (как на электронных часах).
е) Кривые Серпинского порядка 1 и 2, изображенные на рис. 23.
Рис. 23
453. Даны натуральные числа k, l, m, символы s
1, ... ,
s
30.
Вывести
данные cимволы в следующем виде:
…
s
1
…
s
16
…
∗
k пробелов b пробелов m пробелов
s
2
s
17
∗
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
s
15
s
30
∗
(Определить процедуру, обращение к которой дает вывод символа
t
после n пробелов.)
454. Дано натуральное число n; найти n!. Использовать
программу, включающую рекурсивную процедуру вычисления
n!. Чем
эта программа хуже нерекурсивной программы вычисления
n!?
455.Даны натуральные числа n, m; найти НОД(n, m).
Использовать программу, включающую рекурсивную процедуру
вычисления НОД, основанную на соотношении НОД(n, m) = НОД(m,
r
), где r – остаток от деления n на m (см. задачу 89). Чем эта программа
хуже нерекурсивной программы вычисления НОД(
n, m)?
456. Числа Фибоначчи u
0
, u
1
, u
2
, ... определяются следующим
образом: u
0
=0, u
1
=1, u
n
=u
n-1
+u
n-2
(n=2, 3, ... ) (см. задачу 144). Написать
программу вычисления
u
n
для данного неотрицательного целого n,
включающую рекурсивную процедуру, которая основана на
непосредственном использовании соотношения
u
n
=u
n-1
+u
n-2
. Доказать
по индукции, что при вычислении
u
n
(n=2, 3, ...) по этой программе
придется выполнить
u
n
-1 сложение чисел Фибоначчи. Итак, для
нерекурсивной программы количество сложений чисел Фибоначчи при
вычислении
u
n
для n=0, 1, ..., 10 есть соответственно 0, 0, 1, 2, 3, 4, 5, 6,
7, 8, а для рекурсивной – 0, 0, 1, 2, 4, 7, 12, 20, 30, 54. Ввиду последнего
обстоятельства никогда не следует пользоваться такого рода
рекурсивными процеду рами, основанными на непосредственном
применении соотношений вида
()
,...,,
1 knnn
xxFx
−−
= 2≥k .
457. Даны натуральные числа a, c, m. Получить f(m), где
+−−
≤≤
=
. случае противном в ))(1()(
,9 0 если ,
)(
nngnfng
nn
nf
=)(ng остаток от деления a
n+c
на 10.
Использовать программу, включающую рекурсивную
процедуру вычисления
f(n).
458. Даны неотрицательные целые числа n, m; вычислить A(n,
m
), где
>>−−
=≠−
=+
=
0 0, если )),1,(,1(
,0,0 если ),1,1(
,0 если ,1
),(
mnmnAnA
mnnA
nm
mnA
(это – так называемая функция Аккермана).
Использовать программу, включающую рекурсивную
процедуру.
459. Многие задачи, помещенные в §9, где речь идет о
вложенных циклах, могут решаться с привлечением процедур –
внутренние циклы могут быть заменены обращениями к должным
образом определенным процедурам. Например, для решения задачи
317
можно определить процедуру вычисления a
n
, для решения задачи
318
– процедуру вычисления
1
1
2
1
1
1
222
++
++
+
+
+ iiii
K и т. д.
Посмотреть задачи §9
и сказать, какие процедуры были бы полезны
для решения этих задач.
460*). Составить процедуру вычисления значения целого числа
по заданной строке символов, являющейся записью этого числа:
а) в десятичной системе счисления;