554.Дано натуральное число n. Получить все пифагоровы тройки натуральных чисел, каждое из которых не превосходит n, т. е. все такие тройки натуральных чисел a, b, c, что a2 + b2 = c2(a £ b £ c £ n).
555.Треугольником Паскаля называется числовой треугольник
1 1
1 2 1
1 3 3 1
1 4 6 4 1
. . . . . . . . . . . . . . . . .
в котором по краям стоят единицы, а каждое число внутри равно сумме двух стоящих над ним в ближайшей строке сверху.
Дано натуральное n. Получить первые n строк треугольника Паскаля.
556.Для чисел Фибоначчи u0, u1, .... (см. задачу 144) справедлива формула Бине
k
1 ƒ 1+ 5 [
1 ƒ 1- 5 [
k
|
|| ||
|
uk= |[
- |
2 J [
, k = 0, 1, ....
2 J
Так как
1- 5
2
< 1, то для больших k выполнено приближенное
равенство
k
1 ƒ 1+ 5 [
||
|
uk» | .
[ 2 J
k
1 ƒ 1+ 5 [
||
|
Вычислить и округлить до целого все числа |
[ 2 J
(k = 0, 1, ..., 15). Вычислить u0, u1, ..., u15
по формулам
u0= 0; u1 = 1; uk
= uk -1 + uk -2
(k = 2, 3, …) и сравнить результаты.
557.Дано натуральное число n (n ³ 2). Найти все меньшие n простые числа, используя решето Эратосфена. Решетом Эратосфена называют следующий способ. Выпишем подряд все целые числа от 2 до n. Первое простое число 2. Подчеркнем его, а все большие числа, кратные 2, зачеркнем. Первое из оставшихся чисел 3. Подчеркнём, его как простое, а все большие числа, кратные 3, зачеркнем. Первое число из оставшихся теперь 5, так как 4 уже зачеркнуто. Подчеркнем его как простое, а все большие числа, кратные 5, зачеркнем и т. д.:
3,4,5,6,7,8,9,10,
558.Дано натуральное число n. С помощью решета Эратосфена (см. предыдущую задачу) найти четверки меньших n простых чисел, принадлежащих одному десятку (например, 11, 13, 17, 19).
559.Дано натуральное число n. Найти все меньшие n числа Мерсена. (Простое число называется числом Мерсена, если оно может быть представлено в виде 2p – 1, где р – тоже простое число.)
560.Два натуральных числа называют дружественными, если каждое из них равно сумме всех делителей другого, кроме самого этого числа. Найти все пары дружественных чисел, лежащих в диапазоне от 200 до 300.
561.Дано натуральное число n. Среди чисел 1, ..., n найти все такие, запись которых совпадает с последними цифрами записи их квадрата (как, например, 62 = 36, 252= 625 и т. д.).
562.Натуральное число из n цифр является числом Армстронга, если сумма его цифр, возведенных в n-ю степень, равна самому числу
(как, например, 153 = 13 + 53+ 33). Получить все числа Армстронга, состоящие из двух, трех и четырех цифр.
563.Назовем натуральное число палиндромом, если его запись читается одинаково с начала и с конца (как, например, 4884, 393, 1).
а) Найти все меньшие 100 натуральные числа, которые при возведении в квадрат дают палиндром.
б) Найти все меньшие 100 числа – палиндромы, которые при возведении в квадрат также дают палиндромы.
564.Рассмотрим некоторое натуральное число n. Если это не палиндром, то изменим порядок его цифр на обратный и сложим исходное число с получившимся. Если сумма не палиндром, то над ней повторяется то же действие и т. д., пока не получится палиндром. До настоящего времени неизвестно, завершается ли этот процесс для любого натурального n.
Даны натуральные числа k, l, m (k £ l). Проверить, верно ли, что для любого натурального числа из диапазона от k до l процесс завершается не позднее, чем после m таких действий.
565.Рассмотрим некоторое натуральное число n (n > 1). Если оно четно, то разделим его на 2, иначе умножим на 3 и прибавим 1. Если полученное число не равно 1, то повторяется то же действие и т. д., пока не получится 1. До настоящего времени неизвестно, завершается ли этот процесс для любого n > 1.
Даны натуральные числа k, l, m (1 < k £ l ). Проверить, верно ли, что для любого натурального 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(c1um/d) + l(c2vm/d) = m, где c j = ±1 (j = 1, 2). Укажем алгоритм нахождения целых чисел u и v, удовлетворяющих fu+gv=НОД(f, g). Обозначим временно f через f0 и g через f1. Получаемые в процессе применения алгоритма Евклида ненулевые остатки обозначим через f2, …, fn, частные от деления f0 на f1, fl на f2, …, fn-1 на fn – через а1, а2, ..., аn:
f0 = a1 f1 + f2 ,
f1 = a2 f2 + f3 ,
........................,
fn-2 = an-1 fn-1 + fn ,
fn-1= an fn;
здесь НОД(f0, f1) = fn. Пусть для некоторого i £ n - 2
вместе с числами
fi, fi+1известны соответствующие им множители p, q, s, t такие, что f0p + f1q = fi, f0s + f1t = fi+1. Тогда, разделив fi на fi+1и получив частное ai+1, и остаток fi+2, мы можем вычислить множители, соответствующие fi+2: так как fi – ai+1fi+1= fi+2, то f0(pai+1s) + f1(q–ai+1t) = fi+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.Показать, что если х1, у1и х2, у2– два целочисленных решения уравнения kx + ly = m, то х1– x2, y1– y2– целочисленное
решение уравнения kx + ly = 0. Вывести отсюда, что если
x, y
– какое-
нибудь целочисленное решение уравнения kx + ly = m, то все целочисленные решения этого уравнения описываются формулами x = x + l¢t, y = y - k ¢t , где k ¢ = k/НОД(k, l), l¢= l/НОД(k, l)
t = (0, ± 1, ± 2, ...) . Написать программу, которая позволяет проверить, обладает ли уравнение kx + ly = m решением в целых неотрицательных числах, и если обладает, то позволяет построить какое-то одно такое решение.
572.Даны натуральное число k, одновременно не равные 0 целые числа n1, …, nk. Найти НОД(|n1|, …, |nk|) и целые u1, …, uk такие, что u1n1 + … + uknk = НОД(|n1|, …, |nk|) (см. задачу 333).
573.Даны натуральные взаимно простые числа n, p. Используя алгоритм, описанный в задаче 570а, найти натуральное m такое, что, во-первых, m < p и, во-вторых -nm при делении на р дает остаток 1.
574.Известная в теории чисел китайская теорема об остатках утверждает следующее. Пусть p1, …,pr – попарно взаимно простые натуральные числа; пусть v = р1...рr. Пусть а1, ..., аr, – такие целые неотрицательные числа, что а1 < p1, …, ar < pr. Тогда существует ровно одно целое неотрицательное u < v, которое при делении на р1, дает остаток а1, при делении на р2, дает остаток а2, …, при делении на рr, дает остаток аr. (Процесс восстановления числа по его остаткам был известен в Китае уже около 2000 лет назад, поэтому теорема и имеет такое название.) Если даны р1, ..., рr, а1, ..., аr то на основании этой теоремы число u может быть найдено последовательной проверкой чисел 0, 1, ..., v – 1. Однако есть алгоритм значительно более быстрого решения этой задачи, который мы сформулируем без доказательства (имеет смысл попытаться самостоятельно найти доказательство).
Обозначим через vi(1 £ i £ r) произведение всех рi, ..., рr кроме
рi, т.е. vi= р1…рi-1рi+1…рr = v/pi. Пусть числа wi (1 £ i £ r) таковы, что
1 £ wi< pi
и viwiпри делении на рi дает остаток 1 (см. предыдущую
задачу). Тогда можно положить u равным остатку от деления
v1w1a1+ … + vrwrarна v. Например, если р1, р2, р3, р4 равно соответственно 2, 3, 5, 7, а а1, а2, а3, а4 равны соответственно 1, 2, 4, 3, то получится u = 59. Проверка показывает, что u удовлетворяет условию задачи: 59 < 2 × 3 × 5 × 7 ,
Даны натуральные числа r, р1, ..., рr, целые неотрицательные числа а1, …, аr, (p1, …, pr – попарно взаимно простые, а1 < p1, …, ar < pr ). Найти u, удовлетворяющие сформулированным выше условиям.
575.Цепной дробью (конечной) называется выражение
b1+
1
b2+
...
bk
где b1, ..., bk– натуральные числа. Для цепной дроби такого вида используют краткую запись [b1, b2, ..., bk]. Каждое положительное, меньшее единицы рациональное число s/t можно представить цепной дробью. Пусть s, t – натуральные числа (s < t). После деления t на s с
остатком получается, что t = аs + r, (a > 0,
s = 1 = 1 .
0 £ r < s) , откуда
t t s
a + r s
Полагаем b1= а, затем этим же способом преобразуем r/s и получаем b2, и т.д. Видно, что b1, …, bk– это последовательность частных, возникающих в процессе применения к s и t алгоритма Евклида (см.
задачу 89). Итак, пусть s/t = [b1, …, bk]. Дополнительно рассмотрим цепные дроби [b1], [b1, b2], ..., [b1, …, bk-1], значения которых называются подходящими дробями числа s/t. Обозначим несократимые формы подходящих дробей через p1/q1, ..., pk-1/qk-1. Подходящие дроби обладают следующими важными свойствами:
s - pi
< 1 , i = 1, …, k – 1;
q
1) 2
t qi i
2) если для некоторой дроби u/v и подходящей дроби pi
qi
выполнено
s - u
< s - pi ,
t v t qi
то v>qi.
Свойства 1), 2) используются в решении разнообразных практических задач, требующих подбора для данного рационального
числа хорошего приближения в виде дроби со сравнительно небольшим знаменателем. Примером может служить задача расчета зубчатой передачи, состоящей из двух шестерен. Передаточное число должно быть близко к заданному значению, и при этом число зубьев каждой из шестерен не может превышать некоторой указанной границы. Для решения такого рода задач полезны следующие соотношения для числителей и знаменателей подходящих дробей: p1=1; p2= b2; pn= bnpn-1+ pn-2, n = 3, 4, ..., k –1
q1=b1; q2= b1b2+1; qn= bnqn-1+qn-2, n = 3, 4, … k – 1 *).
*) Доказательство этих соотношений и свойств 1), 2) можно найти, например, в книге [50].
Написать программы выполнения следующих заданий. Даны натуральные s, t (s < t)
а) Получить все подходящие дроби числа s/t (указать их числители и знаменатели).
б) Считая, что дополнительно дано натуральное k, выяснить, существуют ли такие подходящие дроби числа s/t, числители и знаменатели которых меньше k. Если такие подходящие дроби существуют, то построить последнюю по порядку (указать ее числитель и знаменатель), а также указать модуль разности числа r/s и найденной подходящей дроби.
576.Даны натуральные числа a1,…, a10. Предположим, что имеются 10 гирь весом a1,…, a10. Обозначим через ckчисло способов, которыми можно составить вес k, т.е. ck– это число решений уравнения a1x1+…+a10x10= k, где xiможет принимать значение 0 или 1 (i = 1,…, 10). Получить c0,…, c10.
577.Даны натуральные числа a1,…, a10. Предположим, что имеются 10 видов монет достоинством a1,…, a10. Обозначим через bkчисло способов, которыми можно выплатить сумму k, т.е. bk–это число
решений уравнения a1x1+…+a10x10= k, где xiможет принимать целые неотрицательные значения. Получить b0,…, b20.
578.Дано натуральное число n. Как наименьшим количеством монет можно выплатить n копеек? Предполагается, что в достаточно большом количестве имеются монеты достоинством в 1, 2, 3, 5, 10, 15, 20 и 50 коп.
579.Дано натуральное число n (n ³ 5). Получить все пятерки натуральных чисел x1, x2, x3, x4, x5такие, что x1³ x2³ x3³ x4³ x5и x1+…+ x5= n.
580.Дано натуральное число n (n £ 99). Получить все способы
выплаты суммы n с помощью монет достоинством 1, 5, 10 и 20 коп.
§ 16. Системы счисления
581.Получить последовательность dk, dk-1, …,d0 десятичных цифр числа 2200, т.е. такую целочисленную последовательность, в которой каждый член di удовлетворяет условию 0 £ di£ 9 и, дополнительно, dk.10k + dk-1.10k-1+ … + d0=2200.
582.Получить последовательность d-1, d-2, …, d-kдесятичных цифр числа 2-200, т.е. такую целочисленную последовательность, в которой каждый член di удовлетворяет условию 0 £ di£ 9 и, дополнительно, d-1.10-1+ d-2.10-2+ … + d-k.10-k=2-200.
583.Получить последовательность dk, dk-1, …, d0 десятичных цифр числа 100!, т.е. такую целочисленную последовательность, в которой каждый член di удовлетворяет условию 0 £ di£ 9 и, дополнительно, dk.10k + dk-1.10k-1+ … + d0=100!.
т.е. получить такую целочисленную последовательность, в которой каждый член di удовлетворяет условию 0 £ di£ 9 и, дополнительно, dk.10k + dk-1.10k-1+ … + d0 равно 100!+2100или соответственно 100!–2100.
585.Дано натуральное число p. Получить двоичное
n
представление числа p в виде последовательности a0,…, an нулей и
единиц такой, что
p = an× 2
+ ... + a1× 2 + a0
(an¹0).
586.Даны натуральные числа p и q (q³ 2). Получить q-ичное представление числа p в виде такой последовательности a0,…, an целых неотрицательных чисел что ai < q (i=0,…, n) и p=anqn+…+ a1 q+a0 (an¹0)
587.Даны действительное число x и натуральное число q (0£ x
<1, q³ 2). Получить пять цифр q-ичного представления числа x, т.е.
получить последовательность целых неотрицательных a-1,…, a-5такую,
i
что x=a-1q-1+…+ a-5q-5+r, 0 £ a
£ q - 1, r < q-5.
588.Дано натуральное число p. Получить последовательность
a0,…an , каждый член которой равен –1, 0 или 1, такую что
n
p = an× 3
+ ... + a1× 3 + a0
(an¹0).
589.Даны натуральное число n, целые числа a0,…, an , такие, что каждое ai равно нулю или единице и an¹0. Последовательность a0,…, an задает двоичное представление некоторого целого числа
n
p = an× 2
+ ... + a1× 2 + a0. Получить последовательность нулей и
единиц, задающую двоичное представление:
a) числа p+1;
b) числа p–1;
c) числа 3p.
590.Получить все меньшие 106 натуральные числа, которые являются палиндромами (см. задачу 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, неотрицательные целые числа am, am-1,…, a0 такие, что am am-1…a0– запись n в некоторой
системе счисления (среди am, am-1,…, a0 могут быть и числа, большие девяти, – это будет означать, что основание системы счисления заведомо больше десяти). Требуется определить основание использованной системы счисления.
598.Даны натуральное число n, действительные числа a1,…, an (ai¹0, i=1,…, n). Знаки чисел в каждой из троек ai, ai+1, ai+2 (i=1,…, n–2) могут образовать одну из следующих комбинаций: + + +, + + –, + – +,
+ – –, – + +, – + –, – – +, – – –. Получить целые b0,…,b7, равные количествам вхождений в последовательность a1,…, an указанных троек ai, ai+1, ai+2, с той или иной комбинацией знаков.
599.В последовательности действительных чисел a0, a1,…, a10
выбрать последовательность
ai1
, ai2
, ..., a
i
k
(0£ i1< i2<…< ik£10), для
i
которой значение sin( a
+ ai2
+ ... + a
i
k
) является наибольшим.
(Перебрать все подпоследовательности данной последовательности
путем рассмотрения всех последовательностей b0, b1,…, b10 из нулей и единиц: ai входит в подпоследовательность, если bi=1. Использовать решение задачи 589а.)
600.Дано натуральное число n; представить его в двоично- десятичной системе счисления. Последнее означает, что надо получить последовательность двоичных цифр – нулей и единиц; при этом первые четыре двоичные цифры дают запись (в виде двоичного числа) первой (старшей) десятичной цифры числа n, следующие четыре двоичные цифры – запись второй десятичной цифры числа n и т.д.
Таким образом, общее число двоичных цифр должно делиться на четыре. Примеры: если n =93, то двоично-десятичная запись n есть 10010011; если n=607, то – 011000000111 и т.д.
601.Даны натуральное число m, двоичные цифры b1,…, b4m .
Рассматривая последовательность b1,…, b4m как запись некоторого
натурального n в двоично-десятичной системе (см. предыдущую задачу), найти натуральное n в десятичной системе.
602.Доказать, что любое натуральное число n можно единственным способом представить с помощью некоторых целых неотрицательных d0,…, ds в виде ds(s+1)!+ ds-1s!+…+ d12!+ d0 при условии, что 0 £ di £ i+1, i=0, …, s, ds¹0.
Дано натуральное число n; найти соответствующие ds, ds-1, …,
d0.
603.В качестве основания позиционной системы может быть
взято отрицательное целое число. Например, можно рассмотреть систему с основанием –10. Любое целое n единственным образом представляется в виде суммы as (–10)s+ as-1(–10)s-1+…+ a1(–10)+a0, где 0 £ ai £ 9, i =0, …, s. Из сказанного следует, что любое целое n записывается в системе с основанием –10 в виде целого числа без знака as as-1, …, a1a0.
Дано целое число n. Построить представление n в системе с основанием –10, т.е. найти соответствующие as, as-1, …, a0.
604.Рассмотрим последовательность натуральных чисел w0, w1,
…, образованную по следующему закону: w0=1, w1=2, wk= wk-1+ wk-2(k=2, 3, …). Эта последовательность – сдвинутая последовательность чисел Фибоначчи (см. задачу 144) w0=u2, w1=u3, w2=u4.
Последовательность w0, w1, …, – это 1, 2, 3, 5, 8, 13, 21, … Доказать, что любое натуральное n можно единственным способом представить с помощью некоторых неотрицательных целых b0,…, bt в виде btwt+ bt-1wt-1+…+ b0w0 при условии, что 0 £ bi £ 1, i=0, …, t, bt¹ 0. При этом две единицы не могут стоять рядом: если bi=1, то bi+1=0 (i=0,…, t–2).
Дано целое неотрицательное число n; найти соответствующие
bt, bt-1, …, b0.
605.«Римские цифры».
а) Проверить, правильна ли запись числа римскими цифрами.
б) Записать данное число из диапазона от 1 до 1999 римскими цифрами.
в) Перевести число, записанное римскими цифрами, в десятичную систему.
§ 17. Геометрия
606.Даны действительные положительные числа a, b, c, d.
Выяснить, можно ли построить четырехугольник с такими длинами сторон.
607.Дано действительное число j
(0 < j < p ) . Из точки (1, 1)
под углом j к прямой x=1 выпущен световой луч (рис. 29, а – 29, b).
Найти точку оси ординат, в которой луч падает на эту ось.
Еслиj < p / 4 , то луч сначала отразится по закону «угол падения равен углу отражения» от оси абсцисс.
y
j
1 x
y
1
j
1 x б
a
Рис. 29
608.Даны действительные числа x1, y1, x2, y2(x1¹x2), которые определяют две точки A(x1, y1) и B(x2, y2). На оси абсцисс найти такую точку, сумма расстояний от которой до точек A и B – наименьшая для всех точек этой оси.
609.Даны действительные числа x, y. Вычислить расстояние от точки плоскости с координатами (x, y) до границы квадрата *) с вершинами:
*) То есть минимум расстояний от данной точки до точек границы квадрата.
610.Даны натуральное число n, целые числа x1, y1, x2, y2, …, xn, yn. Известно, что точки p1, …, pn с координатами (x1, y1), (x2, y2), …, (xn,
yn) попарно различны. Пусть точка pi удалена от начала координат на расстояние ri (i=1, …, n). Пусть R = max(r1, …, rn).
а) Среди точек p1, …, pn выбрать какую-нибудь одну pi, для которой ri=R; указать координаты выбранной точки и расстояние от этой точки до начала координат.
б) Среди точек pi, (1 £ i £ n)для которых ri=R, выбрать те, которые обладают наименьшей абсциссой. Если таких точек больше одной, то выбрать из них точку, которая имеет наибольшую ординату. Указать номер выбранной точки.
611.Даны действительные числа a1, …, a50. Эти числа определяют 25 интервалов числовой оси: (a1, a2), (a3, a4), …, (a49, a50).
а) Имеют ли все данные интервалы общие точки? Если да, то указать какую-нибудь из этих точек.
б) Является ли интервалом объединение данных интервалов?
Если да, то указать концы этого интервала.
в) Указать число i (1 £ i £ 25) такое, что объединение данных интервалов можно представить в виде i непересекающихся интервалов.
г) Имеются ли точки числовой оси, принадлежащие по крайней мере трем каким-нибудь из данных интервалов? Если да, то указать какую-нибудь из этих точек.
Выяснить, есть ли на плоскости точка, принадлежащая всем кругам c1,
…, c15, где сiимеет центр с координатами xi, yiи радиус ri (i=1, …, 15).
613.Даны действительные числа x1, y1, x2, y2, …, x15, y15, которые рассматриваются как координаты (x1, y1), (x2, y2), …, (x15, y15) точек на плоскости. Выяснить, верно ли, что для каждой из этих пятнадцати точек найдется другая, такая, что все оставшиеся тринадцать точек лежат по одну сторону от прямой, проходящей через эти две точки.
614.Даны целые числа x1, y1, x2, y2, …, xn, yn. Выяснить, найдутся ли среди точек с координатами (x1, y1), (x2, y2), …, (xn, yn) четыре таких, которые являются вершинами квадрата.
615.Даны целые числа x1, y1, x2, y2, x3, y3. Известно, что точки с координатами (x1, y1), (x2, y2), (x3, y3) являются тремя вершинами некоторого прямоугольника. Найти координаты четвертой вершины.
616.Прямая на плоскости может быть задана уравнением ax+by+c=0, где a и b одновременно не равны нулю. Будем рассматривать прямые только с целыми коэффициентами a, b, c. Пусть даны коэффициенты нескольких прямых: a1, b1, c1, a2, b2, c2, …, an, bn, cn.
a) Определить, имеются ли среди этих прямых совпадающие или параллельные.
б) Определить, имеются ли три прямые, пересекающиеся в одной точке.
в) Определить, находятся ли данные прямые в общем положении. (Прямые находятся в общем положении, если все они различны, никакие две из них не параллельны и никакие три не пересекаются в одной точке.)
617.Окружность на плоскости может быть задана координатами x, y ее центра и радиусом r. Пусть даны соответствующие характеристики нескольких окружностей: x1, y1, r1, x2, y2, r2, …, xn, yn, rn
а) Определить, имеются ли среди этих окружностей три попарно пересекающиеся.
б) Найти среди этих окружностей все уединенные окружности, т. е. такие, которые не имеют общих точек ни с одной из остальных окружностей, не лежат целиком внутри и не заключают внутри себя какой-либо из остальных окружностей.
618.Рассматриваются три луча, проведенные в плоскости из точки О. Углы между соседними лучами равны 2 p /3. На лучах
выбраны точки А1, А2, А3, и из этих точек как из центров проведены окружности, проходящие через точку О. Считая данными расстояния А1О, А2О, А3О, вычислить площадь фигуры, изображенной на рис. 30, а. Для вычисления разбить фигуру на части так, как показано на рис. 30, б.
А1
А3 А2
б
а
Рис.30
619.Эта задача является обобщением предыдущей.
Рассматривается n лучей, проведенных в плоскости из точки О (n ³ 2).
Углы между соседними лучами равны 2 p /n. Вновь на лучах выбираются точки А1, …, Аnи проводятся соответствующие окружности. Считая данными расстояния А1О, А2О, …, АnО, вычислить площадь фигуры, аналогичной описанной в предыдущей задаче.
620.Медианой множества, состоящего из четного числа точек плоскости, никакие три из которых не лежат на одной прямой, называется прямая, соединяющая две точки множества, с обеих сторон от которой лежит равное число точек.
Даны действительные числа x1, y1, x2, y2, …, xn, yn(n—нечетное число). Найти число медиан множества точек с координатами (x1, y1), (x2, y2), …, (xn, yn) в предположении, что никакие три точки этого множества не лежат на одной прямой.
621.Даны действительные числа a, b, c, d. Выяснить, можно ли прямоугольник со сторонами a, b целиком уместить в прямоугольнике со сторонами c, d (в отличие от задачи 55, здесь не обязательна взаимная параллельность сторон).
622.Даны действительные числа a1, b1, c1, a2, b2, c2, …, an, bn, cn.
Эта последовательность определяет на плоскости n квадратов со сторонами, параллельными осям: ai, bi – координаты центра квадрата, ci– длина его стороны (i =1, …, n). Определить площадь фигуры, образованной всеми квадратами (рис. 31).
Здесь может оказаться полезным предварительное решение следующей задачи.
Стороны двух прямоугольников параллельны координатным осям. Каждый из прямоугольников задан четырьмя действительными числами – двумя абсциссами и двумя ординатами. Представить ту часть первого прямоугольника, которая не покрывается вторым прямоугольником, в виде объединения нескольких прямоугольников, не накладывающихся друг на друга.
Рис. 31
623.Даны действительные числа x, y. В треугольнике,
вершинами которого служат точки (0, 0), (0, 1), (x, y), найти точку (для
определения ее координат разрешается использовать методы приближенных вычислений), сумма расстояний от которой до вершин треугольника минимальна. Известно (теорема Штейнера), что для
треугольника с углами, не превосходящими 2 p /3 (т. е. 120°), эта точка
совпадает с точкой Торричелли, т. е. точкой, из которой все стороны треугольника видны под углом 2 p /3. Если же в треугольнике имеется угол, больший 2 p /3, то решением задачи будет вершина этого угла.
624.Даны действительные числа x1, y1, x2, y2, …, xn, yn.
Известно, что точки p1, p2, …, pn с координатами (x1, y1), (x2, y2), …, (xn,
а) Верно ли, что ломаная не имеет самопересечений?
б) В предположении, что ломаная не имеет самопересечений, выяснить, является ли n-угольник p1 p2…pn выпуклым.
625.Даны действительные числа x1, y1, x2, y2, …, xn, yn.
Известно, что точки p1, p2, …, pn с координатами (x1, y1), (x2, y2), …, (xn,
yn) попарно различны. Найти выпуклый многоугольник с вершинами в некоторых из точек p1, p2, …, pn, который содержит все точки p1, p2, …, pn. Многоугольник должен быть представлен последовательностью вершин.
626.Сетью называется совокупность точек (узлов), некоторые из которых соединены между собой стрелками. Сети, состоящие из n узлов, можно сопоставить две квадратные матрицы порядка n: матрицу соединений и матрицу связей.
Элемент матрицы соединений aij равен 1, если сеть содержит
стрелку, ведущую из узла i в узел j, и 0 в
противном случае. Элемент bijматрицы связей равен 1, если из узла i можно попасть в узел j, двигаясь по стрелкам, и 0 в противном случае. Так, для сети,
1 3
5 6
2 4
Рис. 32
изображенной на рис.32, матрицы соединений и связей имеют вид
J0
|
|0
|0
|
|0
|0
|
|[0
0]
|
|
,
0|
|
0|
1|
|
0|]
J0 0 1 1
|
|0
1|.
|0
0|
|0
|
1|
|
|[0
0|]
|0 0 1
|
1 1]
|
0 |
|
Дана матрица соединений некоторой сети из n узлов; получить матрицу связей этой сети.
627.Линия называется уникурсальной, если ее можно начертить, не отрывая 2
карандаша от бумаги и не проходя два раза 1
одно и тоже звено. Доказать, что линия
4
6 5
Рис. 33
уникурсальна тогда и только тогда, когда число тех ее узлов, из которых выходит нечетное число звеньев, не превосходит двух. Линии, содержащей n узлов, можно сопоставить квадратную матрицу порядка
n – матрицу соединений, элемент aij которой равен 1, если узел i соединен с узлом j некоторым звеном, не содержащим других вершин, и 0 в противном случае (i, j=1, …, n). Для линии, изображенной на рис. 33, матрица соединений имеет вид
J0 1
|
|1
|0
|
|0
|1
|
|[1
0 0 1
1]
|
|
.
0|
|
1|
1|
|
0|]
Дана матрица соединений для линии с n узлами. Выяснить, является ли линия уникурсальной, и если является, то получить последовательность номеров узлов, которые будут пройдены во время требуемого вычерчивания.
§18. Сортировка массивов и файлов *)
*) В задачах 628 – 648 этого параграфа существенно, что данные рассматриваются в программе как массив; в задачах 649 – 657 рассматриваются файлы, и это усложняет некоторые алгоритмы.
628.Рассмотрим массив целых или действительных чисел a1,…,an. Пусть требуется представить элементы этого массива так, чтобы после перестановки они были упорядочены по неубыванию: a1£ a2£…£ an. Эта задача называется задачей сортировки или упорядочения массива (эту же задачу можно рассматривать применительно к упорядочению по невозрастанию: a1³ a2³…³ an; если числа попарно различны, то можно говорить об убывании и о возрастании). Для решения этой задачи можно воспользоваться, например, следующими алгоритмами:
а) Найти элемент массива, имеющий наименьшее значение, переставить его с первым элементом, затем проделать то же самое, начав со второго элемента и т.д. (Сортировка выбором.)
б) Последовательным просмотром чисел a1, …, an найти наименьшее i такое, что ai>ai+1. Поменять местами ai и ai+1, возобновить просмотр с элемента ai+1 и т.д. Тем самым наибольшее число передвинется на последнее место. Следующие просмотры начинать опять сначала, уменьшая на единицу количество просматриваемых элементов. Массив будет упорядочен после просмотра, в котором участвовали только первый и второй элементы.(Сортировка обменами.)
в) Просматривать последовательно a2, …, an и каждый новый элемент ai вставлять на подходящее место в уже упорядоченную совокупность a1, …, ai-1. Это место определяется последовательным
сравнением ai с упорядоченными элементами a1, …, ai-1. (Сортировка простыми вставками.)
629.Исследовать число сравнений и число перемещений (т. е. перестановок с одного места на другое) элементов a1, …, an в процессе применения описанных в предыдущей задаче алгоритмов. Показать, что число перемещений для алгоритма сортировки выбором ограничено некоторой линейной функцией от n. В это же время и число сравнений для алгоритма сортировки выбором, и обе указанные характеристики для алгоритмов сортировки обменами и сортировки простыми вставками в некоторых случаях (например, когда исходный массив таков, что a1>a2>…>an) являются квадратичными функциями от n.
630.Из утверждения предыдущей задачи следует, что алгоритм сортировки выбором выгодно отличается от алгоритмов сортировки
обменами и сортировки простыми вставками в тех случаях, когда перемещение элемента оказывается существенно более сложным делом, чем сравнение элементов. Использовать это при выполнении следующих заданий.
Дана действительная матрица размера n´m; упорядочить
(переставить) строки матрицы:
а) по неубыванию значений первых элементов строк; б) по невозрастанию сумм элементов строк;
в) по неубыванию значений наименьших элементов строк; г) по невозрастанию значений наибольших элементов строк.
В заданиях б), в), г) разрешается дополнительно определить числовой массив a1,…,an.
631.Пусть дан упорядоченный по неубыванию массив целых или действительных чисел a1£ a2£…£ an и пусть дано некоторое число b (соответственно целое или действительное), для которого нужно
найти такое место среди чисел a1,…,an, чтобы после вставки числа b на это место упорядоченность не нарушилась. Если вследствие равенства между собой некоторых элементов массива число b можно вставлять на разные места, то требуется определить ближайшее к началу массива место. Эта задача называется задачей поиска места элемента. Для b имеется n+1 возможность: b£ a1, a1<b£ a2, …, an-1<b£ an, an<b, и решением задачи поиска места элемента b будет соответственно одно из чисел 1, …, n+1. Для решения задачи полезен алгоритм, который называется алгоритмом деления пополам: взять первоначально 1 и n+1 в качестве границ поиска места элемента; далее, до тех пор, пока границы не совпадут, шаг за шагом сдвигать эти границы следующим образом: сравнить b с as, где s – целая часть среднего арифметического границ; если as<b, то заменить прежнюю нижнюю границу на s + 1, а верхнюю оставить без изменения, иначе оставить без изменения нижнюю границу, а верхнюю заменить на s; когда границы совпадут,
став равными некоторому числу t, выполнение вышеописанного алгоритма закончится с результатом t. (Число сравнений, требуемых этим алгоритмом, не превосходит [log2(n+1)]+1.)
а) Даны действительные числа a1, …, an, b1, …, bm(a1£ a2£…£
an). Получить натуральные числа k1, …, kmтакие, что ki– это решение задачи поиска места bi среди a1, …, an (i =1, …, m). Применить алгоритм деления пополам.
б) Таблица выигрышей денежной лотереи представлена массивом выигравших номеров a1,…, an и массивом выигрышей в рублях p1,…, pn (pi– это выигрыш, выпавший на номер ai (i=1,…, n)). Определить суммарный выигрыш, выпавший на билеты с номерами b1,
…, bm. Применить алгоритм деления пополам.
в) Пусть место некоторого числа b среди упорядоченных по неубыванию a1, …, an выбирается как наиболее удаленное от начала последовательности место, на которое можно вставить это число, не
нарушая этим упорядоченности по неубыванию. Внести изменение в описание алгоритма деления пополам и соответственно дать новое решение задания а), сформулированного выше.
632.Даны действительные числа a1,…, an, p, натуральное число k (a1£ a2£…£ an, k£ n). Удалить из a1, …, an элемент с номером k (т. е. ak) и вставить элемент, равный p, так, чтобы не нарушилась упорядоченность.
633.Алгоритм упорядочения простыми вставками (см. алгоритм в) в задаче 628) можно изменить следующим образом. Место, на которое надо вставить ai в уже упорядоченную совокупность a1, …, ai- 1, определяется алгоритмом деления пополам (см. задачу 631).
Получится новый алгоритм сортировки, который называется алгоритмом сортировки бинарными вставками (слова “бинарная вставка” следует понимать как “вставка делением пополам”). Этот
алгоритм требует всего около nlog2 n сравнений элементов. Написать программу, реализующую этот алгоритм.
634.Даны целые числа a1, …, an. Получить в порядке возрастания все различные числа, входящие в a1, …, an. Здесь удобно воспользоваться алгоритмом сортировки вставками (если n велико, то лучше применить бинарные вставки; если n сравнительно мало, скажем, n<50, то можно обойтись и простыми вставками). В процессе сортировки следует отбрасывать элементы, уже встречавшиеся раньше. Если в результате поиска места ai в упорядоченной совокупности a1, …, ak (k<i) обнаружится, что среди a1, …, ak есть элемент, равный ai, то следует перейти к рассмотрению ai+1 без изменения a1, …, ak.
cp, d1£ d2£…£ dq). Внести единую упорядоченность в c1,…,cp, d1,…,dq,
получив f1, f2, …, fp+ q такие, что f1£ f2£…£ fp+ q. Число сравнений не должно превосходить p+q.
636.Алгоритм фон Неймана упорядочения массива a1, ..., anпо неубыванию (алгоритм сортировки слияниями) основан на многократных слияниях уже упорядоченных групп элементов массива (см. предыдущую задачу). Вначале весь массив рассматривается как совокупность упорядоченных групп по одному элементу в каждой.
Слиянием соседних групп получаем упорядоченные группы, каждая из которых содержит два элемента (кроме, может быть, последней группы, которой не нашлось парной). Далее, упорядоченные группы укрупняются тем же способом и т. д. Здесь приходится оперировать не только с массивом a1, …, an, но и с вспомогательным массивом b1, …, bn (первоначальные значения его элементов не играют роли). Рис. 34 демонстрирует два последовательных этапа укрупнения: массивы a1,
…, an, и b1, …, bn представлены в виде отрезков, которые разбиты на
части, изображающие упорядоченные группы. Число упорядоченных групп убывает, следовательно, настанет такой момент, когда в массиве a1, …, an, или b1, …, bn будет содержаться только одна упорядоченная группа. А это означает, что массив упорядочен. Для слияния двух упорядоченных групп, содержащих соответственно p и q элементов, достаточно произвести p + q сравнений. Следовательно, для одного этапа укрупнения достаточно произвести не более n сравнений.
Столько же требуется на одном этапе и перемещений. Можно показать, что алгоритм фон Неймана требует в целом приблизительно n log2n сравнений и столько же перемещений. Из рассмотренных до сих пор алгоритмов только алгоритм сортировки бинарными вставками требовал столь небольшого числа сравнений. Однако алгоритм фон Неймана выгодно отличается от последнего алгоритма тем, что требует меньше перемещений элементов a1, …, an (хотя и требует дополнительного массива b1, …, bn).
Написать программу, реализующую алгоритм фон Неймана.
Рис.34
637.Пусть дан массив a1, …, an. Требуется переставить a1, …, an так, чтобы вначале в массиве шла группа элементов, больших того элемента, который в исходном массиве располагался на первом месте, затем – сам этот элемент, потом – группа элементов, меньших или равных ему. Число сравнений и перемещений, каждое в отдельности, не должно превышать n – 1.
638.На преобразовании массива, описанном в предыдущей задаче, основывается следующий рекурсивный алгоритм сортировки (так называемая быстрая сортировка). Если массив содержит не более
одного элемента, то он упорядочен. Иначе применяем к нему преобразование, описанное в предыдущей задаче, и определяем результат применения алгоритма быстрой сортировки к a1, …, an следующим образом: вначале идет первая группа элементов, упорядоченная с помощью алгоритма быстрой сортировки, затем без изменения тот элемент, который разделял первую и вторую группы элементов, затем вторая группа элементов, упорядоченная с помощью алгоритма быстрой сортировки. Этот алгоритм не использует дополнительного массива и требует в среднем приблизительно nlog2 n сравнений и столько же перемещений элементов. Правда, это лишь среднее число: в худшем случае число сравнений может достигать n(n – 1)/2; кроме того, алгоритм быстрой сортировки содержит рекурсии.
639.На преобразовании массива, описанном в задаче 637, основывается также следующий алгоритм поиска значения k-го по величине элемента массива a1, …, an (т. е. того элемента, который бы занял место с номером k после упорядочения массива). Пусть в результате преобразования, описанного в задаче 637, первый элемент занял p-е место; если k = p, то поиск закончен; если k < p, то надо перейти к поиску k-го по величине элемента в начальной группе элементов, содержащей p – 1 элемент (задача упростилась, так как p – 1 < n); если же k > p, то надо перейти к поиску (k – p)-го по величине э
2
решение уравнения kx + ly = 0. Вывести отсюда, что если
1
...
s - pi
2) если для некоторой дроби u/v и подходящей дроби pi
t v t qi
1
А1
Рис. 31
5 6
4
Рис.34