Дубровский О.И., Лихачев Е.Р. и др.Задачи по программированию. Часть 1. Базовые алгоритмические конструкции: Практикум
Подождите немного. Документ загружается.
11
3.27. Написать программу нахождения наименьшего общего кратного (НОК)
двух заданных неотрицательных целых чисел.
Указание:
(,)
(,)
nm
НОКnm
НОД nm
⋅
=
. Для нахождения НОД использовать алгоритм Евклида.
3.28. Написать программу, проверяющую , являются ли два данных числа вза-
имно простыми.
Указание: Два числа называются взаимно простыми , если их наибольший общий делитель
равен 1. Для нахождения НОД использовать алгоритм Евклида.
3.29. Даны натуральные числа m и n . Найти такие натуральные p и q, не
имеющие общих делителей , что
pm
qn
=
.
3.30. Найти первое число Фибоначчи, большее заданного числа m , а также
номер n этого числа Фибоначчи.
Указание к 3.30 – 3.32: Числа Фибоначчи
n
f
определяются формулами
0 1
f=f=1
;
21 −−
+
=
nnn
fff (
n2,3, …
=
).
3.31. Вычислить сумму всех чисел Фибоначчи, которые не превосходят за-
данное число m .
3.32. Вводится последовательность целых чисел, оканчивающаяся нулем , и
состоящая более, чем из одного ненулевого элемента. Вычислить сумму тех из
них , порядковые номера которых – числа Фибоначчи.
3.33. Определите, для какого наибольшего числа n можно вычислить n!, поль-
зуясь типом integer.
3.34. Определите, для какого наибольшего числа n можно вычислить
1
k
n
2
k
(-2)
(k!)
=
∑
,
если для для хранения значений слагаемых и суммы используется тип real, а
для k и n – тип longint.
3.35. Составить программу для определения «машинного эпсилон» .
Указание: Машинное эпсилон – это такое минимальное, не равное нулю число , после прибав-
ления которого к единице компьютер все еще выдает результат , отличный от 1.
3.36. Составить программу для определения числа десятичных знаков , выде-
ляемых для представления действительного числа.
3.37. Вводится последовательность символов , имеющая следующий вид :
d
1
±d
2
±…± d
n
(d
i
– цифры, n > 1), оканчивающаяся точкой . Вычислить значение
этой алгебраической суммы.
3.38. Составить программу для вычисления
m
x
(x ≥ 0) с заданной точностью
ε. Для получения последовательных приближений y
i
использовать следующие
соотношения :
y
1
=
x+m1
2
−
,
y
i
=
i-1
m-1
i-1
1x
((m1)y+)
my
−, i = 2, 3,…
где x – заданное действительное число, m – заданное натуральное число.
3.39. Составить программу нахождения суммы ряда с заданной точностью ε:
12
337921
...()
......
...()
n
x13x135x1357x132n1x
x
23245246724689242n2n1
+
⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅−⋅
+++++++
⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅+
Для оценки правильности результата предусмотреть вычисление по контроль-
ной формуле: arcsinx.
Указание к 3.39 – 3.43: Вычисление суммы заканчивается, если модуль очередного слагаемо -
го оказывается меньше заданной точности ε. Причем для этих рядов (при | x | < 1) абсо-
лютная величина суммы всех отброшенных членов ряда при этом оказывается меньше ε.
3.40. Составить программу нахождения суммы ряда с заданной точностью ε:
23
...()
......
...
i
225253i4
xxxx
669693i
⋅⋅⋅−
−+−±
⋅⋅⋅
m
Для оценки правильности результата предусмотреть вычисление по контроль-
ной формуле:
3
31x3
+−
.
3.41. Составить программу нахождения суммы ряда с заданной точностью ε:
3521
()()()
......
!!!()!
i
x(2x)x4xx6xx2ix
2462i
−
++++
−+−±
m
Для оценки правильности результата предусмотреть вычисление по контроль-
ной формуле: sinx – cosx + 1.
3.42. Составить программу нахождения суммы ряда с заданной точностью ε:
2462
......
!!!!!!!()!
i
11111111
xxxx
122436i2i
+−+++−±+
m
Для оценки правильности результата предусмотреть вычисление по контроль-
ной формуле: 2 –
2
x
e
−
– cosx.
3.43. Составить программу нахождения суммы ряда с заданной точностью ε:
23
......
!!!!!!!()!
i
11111111
xxxx
122436i2i
−−−+−−±−
m
Для оценки правильности результата предусмотреть вычисление по контроль-
ной формуле: cos
x
–
x
e
−
3.44. Составить программу для решения уравнения
2
cos
ln
x
1x
ex
101x
−
+−
+
= 0
на отрезке [0,2] с точностью ε = 10
-4
методом деления отрезка пополам .
Указание к 3.44 - 3.48: Метод деления отрезка пополам состоит в последовательном при-
ближении к корню за счет уменьшения отрезка, на котором находится корень . Каждое но -
вое приближение x находится как середина текущего отрезка. Концы текущего отрезка
выбираются из условия противоположности знака f(x) на его концах. Вычисление заканчи-
вается, когда длина отрезка станет меньше заданной точности ε.
3.45. Составить программу для решения уравнения
3
0,072xarctgx
−+ = 0
13
на отрезке [0,2] с точностью ε = 10
-4
методом деления отрезка пополам .
3.46. Составить программу для решения уравнения
5
0,49
cos()
30x
xx
7x
−++−
= 0
на отрезке [0,2] с точностью ε = 10
-4
методом деления отрезка пополам .
3.47. Составить программу для решения уравнения
3
arccosln()
2
x0,577x10,01x
3
+++−
= 0
на отрезке [0,2] с точностью ε = 10
-4
методом деления отрезка пополам .
3.48. Составить программу для решения уравнения
5
1
(ln)
x
4
exxx
9
−
−++−
= 0
на отрезке [0,2] с точностью ε = 10
-4
методом деления отрезка пополам .
3.49. Составить программу для определения локального максимума функции
f(x) =
x
1e0,5x
−
−−
Указание к 3.49, 3.50: Значения аргумента должны составлять возрастающую арифмети-
ческую прогрессию с заданным начальным членом 0,1 и разностью 0,1.
3.50. Составить программу для определения локального минимума функции
f(x) =
x
ex
−
Вложенные циклы
3.51. Составить программу, которая решает следующий числовой ребус :
охохо
+ ахаха
= ахахах.
3.52. Составить программу для графического изображения делимости чисел
от 1 до n (n – исходное данное). В каждой строке надо выводить число и столь-
ко плюсов , сколько делителей у этого числа. Например, если исходное данное –
число 4 , то на экране должно быть выведено:
1+
2++
3++
4+++.
3.53. Два двузначных числа, записанных одно за другим , образуют четырех -
значное число, которое делится на их произведение. Найти такие числа.
3.54. Старинная задача. Определить , сколько можно купить быков , коров и
телят, если плата за быка – 10 рублей , за корову – 5 рублей , за теленка – 50 ко-
пеек, а на 100 рублей надо купить 100 голов скота.
3.55. Получить все совершенные числа, меньшие заданного натурального п.
14
Указание: Совершенным называется натуральное число , равное сумме всех своих делителей
( исключая само число ). Например : 28 = 1 + 2 + 4 + 7 + 14.
3.56. Найти все простые несократимые дроби, меньшие 1 , знаменатели кото-
рых не превышают 9 (дробь задается двумя натуральными числами – числите-
лем и знаменателем ).
3.57. Составить программу возведения заданного числа в третью степень, ис-
пользуя следующую закономерность :
.
29
27
25
23
21
5
;191715134
;11973
;532
;11
3
3
3
3
3
+
+
+
+
=
+++=
++=
+=
=
3.58. Установлено, что если дата лежит в диапазоне от 1582 до 4902 гг., то в
этом случае номер дня недели (воскресенье имеет номер 0, понедельник – 1, … ,
суббота – 6) равен остатку от деления на 7 значения выражения
[]
yc
2.6m0.2dy2c
44
−++++−
, где d – номер дня в месяце; m – номер ме-
сяца в году (нумерация начинается с марта); y – число, состоящее из двух
младших цифр года; c – число, состоящее из двух старших цифр года;
[
]
x
озна-
чает целую часть числа x . Составить программу, вычисляющую количество
пятниц, приходящихся на 13-е число, с 2001 по 2010 гг.
3.59. Вывести на экран последовательность символов : AABABC…AB..YZ.
3.60. Вывести на экран последовательность символов : ZYYXXX…AA..AA.
3.61. Вывести на экран таблицу символов следующего вида:
ABC…Z
ZBC…Z
ZZC…Z
ZZZ…Z
3.62. Вывести на экран таблицу символов следующего вида:
100...00
020...00
…
000...09
3.63. Вывести на экран таблицу символов следующего вида:
999...99
088...88
…
000...01
3.64. Вывести на экран таблицу символов следующего вида:
0123456789
1234567890
…
9012345678
15
3.65. Найти минимальное число, которое представляется суммой четырёх
квадратов натуральных чисел не единственным образом .
3.66. Найти все простые делители заданного натурального числа n .
3.67. Составить программу, которая представляет заданное натуральное число
при помощи римских цифр. При этом 1000 обозначается M ; 500 обозначается D ,
100 – C, 50 – L, 10 – X, 1 – I.
3.68. Найти k- е простое число в арифметической прогрессии 11, 21, 31, 41, 51,
61,…
3.69. Дано натуральное число n ≥ 2. Составить программу разложения этого
числа на простые множители:
а) простой множитель p должен быть выведен k раз, где k – натуральное
число такое , что n делится на p ·k и не делится на p · (k+1);
б) каждый простой множитель должен быть выведен ровно 1 раз.
3.70. Найти наименьшее натуральное число n , представимое двумя различны-
ми способами в виде суммы кубов двух натуральных чисел х
3
+y
3
(х ≥ у).
3.71. Составить программу нахождения основных троек Пифагоровых чисел
a, b и c, используя следующие формулы
a = u·v;
22
uv
b
2
−
=
;
22
uv
c
2
+
=
,
где u и v – взаимно простые нечетные натуральные числа и u > v.
Указание: Пифагоровыми числами называется тройка натуральных чисел, удовлетворяю -
щих равенству a
2
+ b
2
= c
2
.
3.72. Составить программу, вычисляющую цифровой корень заданного нату-
рального числа.
Указание: Если сложить все цифры какого - либо числа , затем все цифры найденной суммы и
т .д., в итоге получится цифра, которая и называется цифровым корнем данного числа.
3.73. В данном натуральном числе переставить цифры таким образом , чтобы
образовалось наименьшее число, записанное этими же цифрами.
3.74. Дано натуральное k . Определить k-ю цифру последовательности
12345678910111213… , в которой выписаны подряд все натуральные числа.
3.75. Дано натуральное k . Определить k-ю цифру последовательности
149162536… , в которой выписаны подряд квадраты всех натуральных чисел.
3.76. Дано натуральное k . Определить k-ю цифру последовательности
1123581321… , в которой выписаны подряд все числа Фибоначчи.
3.77. Заданное натуральное число n представить в виде суммы различных чи-
сел Фибоначчи. Определить количество слагаемых в этой сумме.
3.78. Группа параллельно соединенных сопротивлений , изображенная на рис.
4а, задается неотрицательными числами r
1
, r
2
,..., r
i
, – значениями сопротивле-
ний . Последовательное соединение ряда таких групп, показанное на рис. 4б, за-
дается так: сначала идут значения сопротивлений , входящих в первую группу,
затем – некоторое отрицательное число, затем – значения сопротивлений , вхо-
дящих во вторую
группу, затем – не-
которое отрица-
тельное число и т.
д. После значения
Рис.
4
16
последнего сопротивления последней группы идут два отрицательных числа.
Составить программу расчета сопротивления соединения.
3.79. Cоставить программу расчета сопротивления параллельного соединения
последовательных групп (рис. 5), предполагая , аналогично предыдущей задаче,
что каждая группа задается рядом
значений сопротивлений , за которым
идет отрицательное число, а вслед за
значением последнего сопротивле -
ния последней группы идут два от -
рицательных числа.
3.80. Прямоугольное хоккейное поле размера axb освещено n рядами ламп, по
m ламп в ряду, расположенных на высоте h от поверхности льда. Расстояние
между рядами ламп равно а /(n–1), расстояние между лампами в ряду – b/(m–1).
Определить освещенность хоккейного поля в точке, расстояния от которой до
бортов соответственно равны а
i
, b
i
(а
i
≤ а, b
i
≤ b). Мощность ламп – 200 Вт,
к.п.д. ламп – 1 %.
4. Использование подпрограмм
4.1. Составить программу для вычисления значения следующего выражения
при заданных x, a, b, c:
(())((/)/)/
(())
axbxcxaxbxcx
t
axbxcx
++−++
=
++
При решении задачи определить и использовать функцию .
4.2. Составить программу для вычисления значения следующего выражения
при заданных x, y, a, b:
2222
2424
sin()cos()()
()sin()cos()
xaxayb1
t
xa1ybyb
−++−−
=
+−++−
При решении задачи определить и использовать функцию .
4.3. Составить программу для вычисления значения следующего выражения
при заданных x, a, b:
222
3
2
3
()4()
0,5(0,50,5)(0,25)
ababbaatgba
t
xxxtgx
+−−
=
+−−
При решении задачи определить и использовать функцию .
4.4. В программе определить две переменные перечисляемого типа – одну
для названия страны , другую – для названия континента. Написать функцию ,
которая по заданной стране определяет континент, на котором находится стра-
на. Определить для двух стран, находятся ли они на разных континентах .
4.5. Найти все пары дружественных чисел, лежащих в заданном диапазоне.
Определить и использовать в программе функцию для нахождения суммы де-
лителей натурального числа.
Указание: Два натуральных числа называются дружественными , если каждое из них равно
сумме всех делителей другого , кроме самого этого числа.
Рис.
5
17
4.6. Для заданного натурального n найти первые n автоморфных чисел. На-
писать и использовать в программе логическую функцию , определяющую , яв-
ляется ли число автоморфным.
Указание: Число называется автоморфным, если квадрат этого числа заканчивается этим
же числом.
4.7. Найти все числа – палиндромы (см . 1.19) в заданном диапазоне от n до
m, которые при возведении в квадрат так же дают палиндром . Определить и ис-
пользовать в программе необходимые функции.
4.8. Составить программу, вычисляющую наибольший общий делитель n за-
данных чисел. Определить и использовать в программе функцию для нахожде-
ния НОД двух чисел, использующую алгоритм Евклида (см . 3.25).
4.9. Составить программу, вычисляющую наименьшее общее кратное n за-
данных чисел. Определить и использовать в программе функцию для нахожде-
ния НОД двух чисел, использующую алгоритм Евклида.
4.10. Найти и вывести в порядке возрастания все несократимые дроби, заклю -
чённые между 0 и 1. Для решения задачи определить и использовать в про-
грамме функцию для нахождения НОД двух чисел, использующую алгоритм
Евклида.
4.11. Даны два целых числа a и b (b ≠ 0). Описать процедуру, приводящую
дробь a/b к несократимому виду c/d и использовать ее для приведения дроби
1 + 1/2 + 1/3 + … + 1/20
к несократимому виду.
4.12. Написать и использовать в программе процедуру сложения двух дробей ,
результатом которой является несократимая правильная дробь. Использовать
функцию для нахождения НОД двух чисел, использующую алгоритм Евклида.
4.13. Дано натуральное число n . Выяснить , имеются ли среди чисел n, n+1,...,
2n близнецы. Определить и использовать в программе логическую функцию ,
определяющую , является ли число простым.
Указание: Близнецами называются простые числа , разность между которыми равна двум.
4.14. Составить программу, определяющую количество сверхпростых чисел в
натуральном ряду чисел, не превышающих 1000. Определить и использовать в
программе необходимые функции.
Указание: Сверхпростым называется число , если оно простое, и число , полученное из него
записью цифр в обратном порядке, тоже будет простым.
4.15. Среди простых чисел, не превосходящих заданного n , найти такое, в
двоичной записи которого максимальное число единиц. Написать и использо-
вать в программе логическую функцию , определяющую , является ли число
простым, а также функцию для определения количества единиц в двоичной за-
писи натурального числа.
4.16. Найти натуральные числа из заданного диапазона, у которых количество
делителей является произведением двух простых чисел. Определить и исполь-
зовать в программе функцию , определяющую количество делителей натураль-
ного числа, а также логическую функцию , определяющую , является ли число
простым.
4.17. Составить программу для вычисления значения следующего выражения
при заданном a :
18
26
3
7
aa1
13a
−+
++
.
Корни у =
k
x
вычислять с точностью ε = 0.0001 по итерационной формуле,
приведенной в 3.38. Определить и использовать в программе соответствующую
функцию .
4.18. Используя вспомогательную функцию нахождения sin(x) в виде разло-
жения в ряд
sin(x) =
35721
......
!!!()!
i
xxxx
x
3572i1
+
−+−+±
+
m
,
(процесс суммирования остановить , если очередное слагаемое станет меньше
0.001), вычислить для заданного N выражение:
...
sin(sinsin)(sinsinsin)(sinsin...sin)
1111
11212312N
++++
++++++
.
4.19. Используя вспомогательную функцию нахождения cos(x) в виде разло-
жения в ряд
cos(x) =
2462
......
!!!()!
i
xxxx
1
2462i
−+−+±
m
,
(процесс суммирования остановить , если очередное слагаемое станет меньше
0.001), вычислить для заданного N выражение:
cos(x)+cos(cos(x))+… +cos(cos(… cos(x)… )).
(N раз)
4.20 На прямой находятся три положительных заряда, величины q
1
, q
2
, q
3
,
так, как показано на рис. 6. Определить расстояния
от заряда q
1
до точек, в которых равнодействующая
сил отталкивания зарядами q
1
, q
2
, q
3
некоторого чет-
вертого положительного заряда равна нулю . Опре-
делить и использовать необходимые функции и про-
цедуры.
Литература
1. Бабушкина И . А . Практикум по Турбо Паскалю / И . А. Бабушкина, Н . А.
Бушмелева, С . М . Окулов , С . Ю . Черных . – М .: АБФ , 1998. – 384 с.
2. Сборник задач по базовой компьютерной подготовке / В . С . Зубов [и др.]. –
М .: Изд - во МЭИ , 1998. – 178 с.
3. Программирование на языке Паскаль: Учеб . пособие для студ . вузов , обуч .
по направлению подгот . бакалавров и магистров "Информатика и вычисл . тех -
ника" и по направлениям подгот. дипломир. специалистов "Информатика и вы-
числ. техника" и "Информ. системы" : Задачник / О .Ф . Ускова [и др.]. – СПб.:
Питер , 2002. – 333 с.: ил.
4. Пильщиков В . Н . Сборник упражнений по языку Паскаль / В . Н . Пильщи-
ков . – М .: Наука, 1989. – 160 с.
5. Абрамов С . А. Задачи по программированию / С . А. Абрамов , Г . Г . Гнез-
дилова, Е . Н . Капустина, М . И . Селюн. – М .: Наука, 1988. – 224 с.
Рис.
6
19
Составители: Дубровский Олег Игоревич
Лихачев Евгений Робертович
Курганский Сергей Иванович
Редактор Тихомирова О . А .