Абрамов С.А., Гнездилова Г.Г., Капустина Е.Н., Селюн М.И. Задачи по программированию

Подождите немного. Документ загружается.

Даны натуральные числа k, l, m (k ≤ l). Проверить, верно ли, что

для любого натурального числа из диапазона от k до l процесс

завершается не позднее, чем после m таких действий.

565. Рассмотрим некоторое натуральное число n (n > 1). Если

оно четно, то разделим его на 2, иначе умножим на 3 и прибавим 1.

Если полученное число не равно 1, то повторяется то же действие и т.

д., пока не получится 1. До настоящего времени неизвестно,

завершается ли этот процесс для любого n > 1.

Даны натуральные числа k, l, m ( lk ≤<1 ). Проверить, верно ли,

что для любого натурального n из диапазона от k до l процесс

завершается не позднее, чем после m таких действий.

566. Найти все простые несократимые дроби, заключенные

между 0 и 1, знаменатели которых не превышают 7 (дробь задается

двумя натуральными числами – числителем и знаменателем).

567. Дано натуральное число n. Выяснить, можно ли

представить n! в виде произведения трех последовательных целых

чисел.

568. Дано натуральное число m. Вставить между некоторыми

цифрами 1, 2, 3, 4, 5, 6, 7, 8, 9 записанными именно в таком порядке,

знаки +, – так, чтобы значением получившегося выражения было

число m. Например, если m=122, то подойдет следующая расстановка

знаков: 12 + 34 – 5 – 6 + 78 + 9. Если требуемая расстановка знаков

невозможна, то сообщить об этом.

569. Дано натуральное число n. Получить в порядке возрастания

n первых натуральных чисел, которые не делятся ни на какие простые

числа, кроме 2, 3 и 5.

570. Алгоритм Евклида (см. задачу 89) допускает

многочисленные обобщения. Например, вместе с НОД (f, g) можно

вычислять целые u и v такие, что fu + gv = НОД (f, g). Это дает

возможность находить некоторое целочисленное решение уравнения

вида kx + ly = m, где k, l, m – целые числа такие, что k и l одновременно

не равны 0, а m делится на d = НОД(|k|, |l|). Пусть |k|u + |l|v = d; тогда

|k|um/d + |l|vm/d = m и, как следствие этого, k(c

um/d) + l(c

vm/d) = m,

где 1±=

c (j = 1, 2). Укажем алгоритм нахождения целых чисел u и v,

удовлетворяющих fu+gv=НОД(f, g). Обозначим временно f через f

и g

через f

. Получаемые в процессе применения алгоритма Евклида

ненулевые остатки обозначим через f

, …, f

, частные от деления f

на

, f

на f

, …, f

n-1

на f

– через а

, а

, ..., а

;

....,....................

112

3221

2110

nnn

nnnn

faf

ffaf

−

−−−

здесь НОД(f

, f

) = f

. Пусть для некоторого 2−≤ ni вместе с числами

, f

i+1

известны соответствующие им множители p, q, s, t такие, что

p + f

q = f

, f

s + f

t = f

i+1

. Тогда, разделив f

на f

i+1

и получив частное

i+1

, и остаток f

i+2

, мы можем вычислить множители, соответствующие

i+2

: так как f

– a

i+1

= f

i+2

, то f

(pa

i+1

s) + f

(q–a

i+1

t) = f

i+2

Таким образом, для нахождения целых u и v таких, что

fu+ gv = НОД(f, g), надо применять к f и g алгоритм Евклида,

рассматривая на каждом шаге его примен ения, кроме тех двух чисел,

которые рассматривались и прежде, еще и соответствующие этим

числам множители p, q и s, t. На первом шаге в качестве множителей,

соответствую щих исходным числам f и g берутся 1,0 и 0,1. Выполнив

деление и получив частное a и некоторый остаток, надо, если остаток

не равен 0, вычислить по формулам p–as, q–at множители,

соответствую щие полученному остатку. Множители, соответствующие

последнему ненулевому остатку, дадут решение рассматриваемого

уравнения fu + gv = НОД(f, g).

а) Даны одновременно не равные 0 целые f и g. Найти

НОД(|f|, |g|) и целые u и v, такие, что fu + gv = НОД(|f|, |g|).

б) Даны целые k, l, m такие, что k и 1 одновременно не равны 0,

а m делится на НОД(|k|, |l|). Найти какое-нибудь целочисленное

решение уравнения kx + ly = m.

в) Заметим, что предложенный выше алгоритм поиска

множителей u и v можно изменить так, что число требуемых им

операций сократится почти в полтора раза: из двух чисел u и v

достаточно вычислить вместо НОД(f, g) только v, а затем определить u

по формуле u = (НОД(f, g) – gv)/f. Внести это усовершенствование в

программы, дающие решения заданий а), б).

571. Показать, что если х

, у

и х

, у

– два целочисленных

решения уравнения kx + ly = m, то х

– x

, y

– y

– целочисленное

решение уравнения kx + ly = 0. Вывести отсюда, что если

, – какое-

нибудь целочисленное решение уравнения kx + ly = m, то все

целочисленные решения этого уравнения описываются формулами

tkyytlxx

′

−=

′

+= , , где k

′

= k/НОД(k, l), l

′

= l/НОД(k, l)

...),2,1,0( ±±=t . Написать программу, которая позволяет проверить,

обладает ли уравнение kx + ly = m решением в целых неотрицательных

числах, и если обладает, то позволяет построить какое-то одно такое

решение.

572. Даны натуральное число k, одновременно не равные 0

целые числа n

, …, n

. Найти НОД(|n

|, …, |n

|) и целые u

, …, u

такие,

что u

+ … + u

= НОД(|n

|, …, |n

|) (см. задачу 333).

573. Даны натуральные взаимно простые числа n, p. Используя

алгоритм, описанный в задаче 570а, найти натуральное m такое, что,

во-первых, m < p и, во-вторых -nm при делении на р дает остаток 1.

574. Известная в теории чисел китайская теорема об остатках

утверждает следующее. Пусть p

, …,p

– попарно взаимно простые

натуральные числа; пусть v = р

...р

. Пусть а

, ..., а

, – такие целые

неотрицательные числа, что а

< p

, …, a

< p

. Тогда существует ровно

одно целое неотрицательное u < v, которое при делении на р

, дает

остаток а

, при делении на р

, дает остаток а

, …, при делении на р

дает остаток а

. (Процесс восстановления числа по его остаткам был

известен в Китае уже около 2000 лет назад, поэтому теорема и имеет

такое название.) Если даны р

, ..., р

, а

, ..., а

то на основании этой

теоремы число u может быть найдено последовательной проверкой

чисел 0, 1, ..., v – 1. Одн ако есть алгоритм значительно более быстрого

решения этой задачи, который мы сформулируем без доказательства

(имеет смысл попытаться самостоятельно найти доказательство).

Обозначим через v

)1( ri ≤≤ произведение всех р

, ..., р

кроме

, т.е. v

= р

…р

i-1

i+1

…р

= v/p

. Пусть числа w

)1( ri ≤≤ таковы, что

pw <≤1 и

wv при делении на р

дает остаток 1 (см. предыдущую

задачу). Тогда можно положить u равным остатку от деления

+ … + v

на v. Например, если р

, р

равно

соответственно 2, 3, 5, 7, а а

, а

равны соответственно 1, 2, 4, 3,

то получится u = 59. Проверка показывает, что u удовлетворяет

условию задачи: 753259 ⋅⋅⋅< ,

38741152193129259 +⋅=+⋅=+⋅=+⋅= .

Даны натуральные числа r, р

, ..., р

, целые неотрицательные

числа а

, …, а

, (p

, …, p

– попарно взаимно простые, а

< p

, …, a

). Найти u, удовлетворяющие сформулированным выше условиям.

575. Цепной дробью (конечной) называется выражение

...

где b

, ..., b

– натуральные числа. Для цепной дроби такого вида

используют краткую запись [b

, b

, ..., b

]. Каждое положительное,

меньшее единицы рациональное число s/t можно представить цепной

дробью. Пусть s, t – натуральные числа (s < t). После деления t на s с

остатком получается, что t = аs + r,

)0,0( sra <≤> , откуда

srastt

Полагаем b

= а, затем этим же способом преобразуем r/s и получаем

, и т.д. Видно, что b

, …, b

– это последовательность частных,

возникающих в процессе применения к s и t алгоритма Евклида (см.

задачу 89). Итак, пусть s/t = [b

, …, b

]. Дополнительно рассмотрим

цепные дроби [b

], [b

, b

], ..., [b

, …, b

k-1

], значения которых

называются подходящими дробями числа s/t. Обозначим несократимые

формы подходящих дробей через p

, ..., p

k-1

. Подходящие дроби

обладают следующими важными свойствами:

<− , i = 1, …, k – 1;

2) если для некоторой дроби u/v и подх одящей дроби

выполнено

−<− ,

то v>q

Свойства 1), 2) используются в решении разнообразных

практических задач, требующих подбора для данного рационального