Абрамов С.А., Гнездилова Г.Г., Капустина Е.Н., Селюн М.И. Задачи по программированию
Подождите немного. Документ загружается.
числа хорошего приближения в виде дроби со сравнительно
небольшим знаменателем. Примером может служить задача расчета
зубчатой передачи, состоящей из двух шестерен. Передаточное число
должно быть близко к заданному значению, и при этом число зубьев
каждой из шестерен не может превышать некоторой у казанной
границы. Для решения такого рода задач полезны следующие
соотношения для числителей и знаменателей подходящих дробей:
p
1
=1; p
2
= b
2
; p
n
= b
n
p
n-1
+ p
n-2
, n = 3, 4, ..., k –1
q
1
=b
1
; q
2
= b
1
b
2
+1; q
n
= b
n
q
n-1
+q
n-2
, n = 3, 4, … k – 1 *).
*) Доказательство этих соотношений и свойств 1), 2) можно найти,
например, в книге [50].
Написать программы выполнения следующих заданий. Даны
натуральные s, t (s < t)
а) Получить все подходящие дроби числа s/t (указать их
числители и знаменатели).
б) Считая, что дополнительно дано натуральное k, выяснить,
существуют ли такие подходящие дроби числа s/t, числители и
знаменатели которых меньше k. Если такие подходящие дроби
существуют, то построить последнюю по порядку (указать ее
числитель и знаменатель), а также указать модуль разности числа r/s и
найденной подходящей дроби.
576. Даны натуральные числа a
1
,…, a
10
. Предположим, что
имеются 10 гирь весом a
1
,…, a
10
. Обозначим через c
k
число способов,
которыми можно составить вес k, т.е. c
k
– это число решений уравнения
a
1
x
1
+…+a
10
x
10
= k, где x
i
может принимать значение 0 или 1 (i = 1,…,
10). Получить c
0
,…, c
10
.
577. Даны натуральные числа a
1
,…, a
10
. Предположим, что
имеются 10 видов монет достоинством a
1
,…, a
10
. Обозначим через
b
k
число способов, которыми можно выплатить сумму k, т.е. b
k
–это число
решений уравнения a
1
x
1
+…+a
10
x
10
= k, где x
i
может принимать целые
неотрицательные значения. Получить b
0
,…, b
20
.
578. Дано натуральное число n. Как наименьшим количеством
монет можно выплатить n копеек? Предполагается, что в достаточно
большом количестве имеются монеты достоинством в 1, 2, 3, 5, 10, 15,
20 и 50 коп.
579. Дано натуральное число n (n ≥5). Получить все пятерки
натуральных чисел x
1
, x
2
, x
3
, x
4
, x
5
такие, что x
1
≥ x
2
≥ x
3
≥ x
4
≥ x
5
и x
1
+…+
x
5
= n.
580. Дано натуральное число n (n ≤99). Получить все способы
выплаты суммы n с помощью монет достоинством 1, 5, 10 и 20 коп.
§ 16. Системы счисления
581.Получить последовательность d
k
, d
k-1
, …,d
0
десятичных
цифр числа 2
200
, т.е. такую целочисленную последовательность, в
которой каждый член d
i
удовлетворяет условию 90 ≤≤
i
d и,
дополнительно, d
k
.
10
k
+ d
k-1
.
10
k-1
+ … + d
0
=2
200
.
582. Получить последовательность d
-1
, d
-2
, …, d
-k
десятичных
цифр числа 2
-200
, т.е. такую целочисленную последовательность, в
которой каждый член d
i
удовлетворяет условию 90 ≤≤
i
d и,
дополнительно, d
-1
.
10
-1
+ d
-2
.
10
-2
+ … + d
-k
.
10
-k
=2
-200
.
583. Получить последовательность d
k
, d
k-1
, …, d
0
десятичных
цифр числа 100!, т.е. такую целочисленную последовательность, в
которой каждый член d
i
удовлетворяет условию 90 ≤≤
i
d и,
дополнительно, d
k
.
10
k
+ d
k-1
.
10
k-1
+ … + d
0
=100!.
584. Получить последовательность d
k
, d
k-1
, …, d
0
десятичных
цифр числа:
a) 100!+2
100
;
b) 100!–2
100
,
т.е. получить такую целочисленную последовательность, в которой
каждый член d
i
удовлетворяет условию 90 ≤≤
i
d и, дополнительно,
d
k
.
10
k
+ d
k-1
.
10
k-1
+ … + d
0
равно 100!+2
100
или соответственно 100!–2
100
.
585. Дано натуральное число p. Получить двоичное
представление числа p в виде последовательности a
0
,…, a
n
нулей и
единиц такой, что
01
2...2 aaap
n
n
+⋅++⋅= (a
n
≠0).
586. Даны натуральные числа p и q (q≥ 2). Получить q-ичное
представление числа p в виде такой последовательности a
0
,…, a
n
целых
неотрицательных чисел что a
i
< q (i=0,…, n) и p=a
n
q
n
+…+ a
1
q+a
0
(a
n
≠0)
587. Даны действительное число x и натуральное число q (0≤ x
<1, q≥ 2). Получить пять цифр q-ичного представления числа x, т.е.
получить последовательность целых неотрицательных a
-1
,…, a
-5
такую,
что x=a
-1
q
-1
+…+ a
-5
q
-5
+r, 10 −≤≤ qa
i
, r < q
-5
.
588. Дано натуральное число p. Получить последовательность
a
0
,…a
n
, каждый член которой равен –1, 0 или 1, такую что
01
3...3 aaap
n
n
+⋅++⋅= (a
n
≠0).
589. Даны натуральное число n, целые числа a
0
,…, a
n
, такие,
что каждое a
i
равно нулю или единице и a
n
≠0. Последовательность
a
0
,…, a
n
задает двоичное представление некоторого целого числа
01
2...2 aaap
n
n
+⋅++⋅= . Получить последовательность нулей и
единиц, задающую двоичное представление:
a) числа p+1;
b) числа p–1;
c) числа 3p.
590. Получить все меньшие 10
6
натуральные числа, которые
являются палиндромами (см. задачу 563) как в десятичной так и в
двоичной системах.
591. Дано натуральное число m. Найти такое натуральное n, что
двоичная запись n получается из двоичной записи m изменением
порядка цифр на обратный (m задано в десятичной системе, и n надо
также получить в десятичной системе, например, для m=6 получается
n=3).
592. Дано натуральное число n. Требуется получить
последовательность, которая состоит из нулей и семерок и образует
десятичную запись некоторого натурального числа, делящегося на n.
(Воспользоваться тем, что в числовой последовательности 7, 77,
777, … обязательно найдутся два члена, дающие при делении на n
один и тот же остаток.)
593. Дано натуральное число m (m<27). Получить все
трехзначные натуральные числа, сумма цифр которых равна m.
594. Получить все шестизначные счастливые номера. (Про
целое число n, удовлетворяющее условию 0≤ n ≤ 999999, говорят, что
оно представляет собой счастливый номер, если сумма трех его первых
цифр равна сумме трех его последних цифр; если в числе меньше
шести цифр, то недостающие начальные цифры считаются нулями ).
595. Даны взаимно простые натуральные числа p, q (p<q). Найти
периодическую и непериодическую части (две последовательности
однозначных неотрицательных чисел, разделенных числом –1)
десятичной дроби, равной p/q.
596. Получить все четырехзначные числа в записи которых нет
двух одинаковых цифр.
597. Даны натуральные числа n, m, неотрицательные целые
числа a
m
, a
m-1
,…, a
0
такие, что a
m
a
m-1
…a
0
– запись n в некоторой
системе счисления (среди a
m
, a
m-1
,…, a
0
могут быть и числа, большие
девяти, – это будет означать, что основание системы счисления
заведомо больше десяти). Требуется определить основание
использованной системы счисления.
598. Даны натуральное число n, действительные числа a
1
,…, a
n
(a
i
≠0, i=1,…, n). Знаки чисел в каждой из троек a
i
, a
i+1
, a
i+2
(i=1,…, n–2)
могут образовать одну из следующих комбинаций: + + +, + + –, + – +,
+ – –, – + +, – + –, – – +, – – –. Получить целые b
0
,…,b
7
, равные
количествам вхождений в последовательность a
1
,…, a
n
указанных
троек a
i
, a
i+1
, a
i+2
, с той или иной комбинацией знаков.
599. В последовательности действительных чисел a
0
, a
1
,…, a
10
выбрать последовательность
k
iii
aaa ...,,,
21
(0≤ i
1
< i
2
<…< i
k
≤10), для
которой значение sin(
k
iii
aaa +++ ...
21
) является наибольшим.
(Перебрать все подпоследовательности данной последовательности
путем рассмотрения всех последовательностей b
0
, b
1
,…, b
10
из нулей и
единиц: a
i
входит в подпоследовательность, если b
i
=1. Использовать
решение задачи 589а.)
600. Дано натуральное число n; представить его в двоично-
десятичной системе счисления. Последнее означает, что надо получить
последовательность двоичных цифр – нулей и единиц; при этом
первые четыре двоичные цифры дают запись (в виде двоичного числа)
первой (старшей) десятичной цифры числа n, следующие четыре
двоичные цифры – запись второй десятичной цифры числа n и т.д.
Таким образом, общее число двоичных цифр должно делиться на
четыре. Примеры: если n =93, то двоично-десятичная запись n есть
10010011; если n=607, то – 011000000111 и т.д.
601. Даны натуральное число m, двоичные цифры b
1
,…, b
4m
.
Рассматривая последовательность b
1
,…, b
4m
как запись некоторого