Математика. Настоящий учебник посвящен системе Mathematica прикладному пакету компьютерной алгебры, при помощи которого можно решать любые задачи, в которых в той или иной форме встречается математика
 Скачать 4.43 Mb.
|
|
5.4. Может ли число быть в 2, 3, 5, 6, 7 или 8 раз своего реверсированного? Число n, совпадающее со своим реверсированным, называется палин- дромическим или, коротко, палиндромом. Иными словами, палиндро- мическое число a 1 . . . a n читается одинаково слева направо и справа налево. 5.5. Задайте тест, который проверяет, является ли число палиндромом. Ответ. Функция rev уже определена, поэтому: palinQ[n ]:=TrueQ[rev[n]==n] 5.6. Ясно, что 11 0 = 1, 11 1 = 11, 11 2 = 121, 11 3 = 1331, 11 4 = 14641 (бином Ньютона). Дальше из-за переноса разрядов симметрия нарушается, например, 11 5 = 161051. Есть ли среди степеней 11 еще палиндромы? Следующие обобщения этой задачи объясняют, что происходит при ре- шении уравнений rev(x m ) = rev(x) m 5.7. Проверьте, что квадрат и куб числа 111 являются палиндромами, а остальные степени не являются. 5.8. Квадраты чисел 1111, 11111, 111111, 1111111, 11111111, 111111111 являются палиндромами, а остальные степени не являются. 5.9. Квадраты чисел 11 . . . 11 состоящих более, чем из 10 единиц, не явля- ются палиндромами. Ответ. Они заканчиваются цифрами 987654321, а начинаются цифрами 12345679. 73 Я.С.Безикович, Приближенные вычисления. — ГИТТЛ, Л.–М., 1941, 290с.; см. с.60–64. 273 Следующая задача предлагалась на вологодской областной олимпиаде 1994 года по программированию 74 5.10. Найдите палиндромы ≤ 10 5 , квадраты которых тоже являются па- линдромами. Ответ. Кроме 1, 2 и 3, уже изученных нами чисел 11, 111, 1111, 11111, состоящих их одних 1, и еще двух очевидных вариаций на тему 11 2 = 121, а именно, 22 2 = 484 и 121 2 = 14641, имеется еще ровно 12 примеров: 101 2 = 10201 202 2 = 40804 212 2 = 44944 1001 2 = 1002001 2002 2 = 4008004 10001 2 = 100020001 10101 2 = 102030201 10201 2 = 104060401 11011 2 = 121242121 11211 2 = 125686521 20002 2 = 400080004 20102 2 = 404090404 Этот ответ носит общий характер. Сумма квадратов цифр такого палин- дрома не превосходит 9. Таким образом, палиндром с m > 1 разрядами может содержать только 0, 1 и 2. • При четном m палиндром либо соддержит не более 8 единиц, либо начинается и заканчивается двойкой, а все остальные цифры нули. • При нечетном m палиндром либо соддержит не более 9 единиц, либо в середине стоит двойка и он содержит не более 4 единиц, либо он начина- ется и заканчивается двойкой, все остальные цифры, кроме, быть может, средней, нули, а средняя цифра может равняться единице. 5.11. Найдите палиндромы ≤ 10 5 , кубы которых тоже являются палин- дромами. Ответ. Кроме 1, 2, 7 3 = 343 и уже изученных нами чисел 11 и 111 имеется ровно пять примеров 101 3 = 1030301, 1001 3 = 1003003001, 10001 3 = 1000300030001, 10101 3 = 1030607060301, 11011 3 = 1334996994331 Чуть позже мы объясним этот ответ. 5.12. Найдите палиндромические простые p ≤ 10000. 5.13. Найдите первые двести пар (p, rev(p)), где как число p, так и ревер- сированное к нему число rev(p) оба простые, причем p < rev(p). 5.14. Найдите все простые < 10 6 такие, что каждая циклическая переста- новка цифр в них снова дает простое. Ответ. Мы не будем приводить соответствующий код, а ограничимся ча- стью ответа. Имеется четыре группы трехзначных простых с этим свой- ством: 113, 131, 311, 197, 719, 971, 199, 919, 991, 337, 373, 733, 74 А.С.Сипин, А,И.Дунаев, Областные олимпиады по информатике. — Изд-во Русь, Вологда, 1995, с.1–95. 274 Обратите внимание, что те из них, которые имеют две одинаковых цифры, остаются простыми вообще при любой перестановке цифр! Имеется две группы четырехзначных 1193, 1931, 3119, 9311, 3779, 7937, 7793, 9377, и для группы пятизначных чисел: 11939, 19391, 39119, 91193, 93911, 19937, 37199, 71993, 93719, 99371. Авторы не хотят лишать читателей удовольствия самостоятельно найти шестизначные числа с этим свойством. В следующей задаче предлагается решить уравнение rev(x 2 ) = rev(x) 2 5.15. Пусть (a 1 . . . a m ) 2 = b 1 . . . b n . Найдите все числа ≤ 10000, для кото- рых (a m . . . a 1 ) 2 = b n . . . b 1 Указание. Ясно, что дорисовывание нулей в конце числа не меняет этого свойства, поэтому рассматривайте только приведенные решения, последняя цифра которых 6= 0. 5.16. Решите уравнение rev(x 3 ) = rev(x) 3 Ответ. Кроме 7 все приведенные решения этого уравнения являются ре- шениями предыдущего и, кроме 2, все состоят их фрагментов вида 1 и 11, разделенных нулями и фрагментов вида 111 отделенных с каждой стороны по крайней мере двумя нулями. Приведем список всех приведенных реше- ний меньших миллиона: 1, 2, 7, 11, 101, 111, 1001, 1011, 1101, 10001, 10011, 10101, 11001, 11011, 100001, 100011, 100101, 100111, 101001, 101011, 101101, 110001, 110011, 110101, 111001. 5.17. Решите уравнение rev(x 4 ) = rev(x) 4 Ответ. Единственными приведенными решениями этого уравнения явля- ются числа 1, 11, 101, 1001, 10001, . . . Все остальные решения получаются из этих дописыванием нулей. 5.18. Решите уравнение rev(x 5 ) = rev(x) 5 Ответ. Единственным приведенным решением этого уравнения является 1. Интересно, что множество решений каждого из этих уравнений содержится в множестве решений предыдущего. Следующая простенькая задача предлагалась в 2000 году в качестве уте- шительной на уральском четвертьфинале студенческой олимпиады по про- граммированию. 5.19. При повороте на π цифры 0, 1 и 8 не меняются, цифры 6 и 9 переходят друг в друга, а все остальные цифры становятся бессмысленными. Среди двузначных чисел при вращении на π не меняются 11, 69, 88 и 96. Найдите все n-значные числа, которые не меняются при таком вращении. 5.20. Существуют ли простые числа, кроме состоящих из одних единиц, которые не меняются при вращении на π? 275 6. Закон старшего разряда. 75 Сейчас произойдет нечто совершенно удивительное. Казалось бы, у слу- чайного числа все должно быть случайно, в том числе и первая цифра. 6.1. Исследуйте поведение первой цифры чисел 2 n , n ∈ N. Решение. Следующий код вычисляет, сколько раз каждая из цифр 1,2, . . . ,9 встречается как первая цифра среди первых n степеней двойки: firstdigit[n ]:=Table[Count[ Table[First[IntegerDigits[2^m]], {m,1,n}], i], {i,1,9}] Ответ потрясает воображение. То, что среди первых цифр первых 10 сте- пеней двойки встречается три единицы, кажется случайностью. Однако, взгляд на первые цифры первых 100 степеней 30, 17, 13, 10, 7, 7, 6, 5, 5 делает закономерности в распределении цифр очевидными. При рассмот- рении первых цифр первой 1000 степеней 301, 176, 125, 97, 79, 69, 56, 52, 45 подозрения переходят в уверенность. Оказывается, дальше распределение первых цифр практически не меняется. Вот как расположены первые циф- ры в нескольких последовательных отрезках по 10000 степеней: 1 − 10000 3010 1761 1249 970 791 670 579 512 458 10001 − 20000 3010 1762 1249 969 793 669 579 512 457 20001 − 30000 3010 1760 1250 969 791 670 581 511 458 30001 − 40000 3011 1761 1249 969 792 668 581 511 458 40001 − 50000 3010 1760 1251 969 791 670 580 512 457 50001 − 60000 3010 1762 1248 969 793 670 579 512 457 60001 − 70000 3011 1760 1250 969 791 670 580 511 458 70001 − 80000 3010 1763 1248 969 793 668 580 512 457 80001 − 90000 3010 1760 1250 969 792 671 579 512 457 90001 − 100000 3010 1762 1248 970 792 669 579 511 459 Не пытайтесь повторить этот “смертельный” номер! Вычисление этой таб- лицы на стандартном ноутбуке может занять значительное время. Если Вы думаете, что это характерно именно для степеней 2, Вас ждет следующий сюрприз. 6.2. Исследуйте поведение первой цифры чисел 3 n , n ∈ N. Ответ. Cреди первых цифр первых 10 степеней тройки цифра 2 встре- чается три раза, 3 3 = 27, 3 5 = 243, 3 7 = 2187, а цифра 1 — всего один 75 Но, желаньем подстрекаем Их сюрпризом удивить, Не давай, подлец, быка им В виде опыта доить! c Алексей Константинович Толстой, Мудрость жизни 276 раз, 3 9 = 19683. Однако, дальше все постепенно становится на свои места. Вот распределение первых цифр среди первых 100 степеней, первой 1000 степеней и первых 10000 степеней: 28, 19, 12, 8, 9, 7, 7, 5, 5; 300, 177, 123, 98, 79, 66, 59, 52, 46; 3007, 1764, 1247, 968, 792, 669, 582, 513, 458. Обратите внимание, что из-за аномального поведения в первом десятке цифра 1 все еще встречается чуть реже, а 2 — чуть чаще, чем должны. 6.3. Исследуйте поведение первой цифры чисел m n , где n ∈ N, а m не является степенью 10. Теперь Вы, конечно, больше не думаете, что этот закон применим только к степеням? 6.4. Исследуйте поведение первой цифры чисел Фибоначчи F n , где n ∈ N. Ответ. Да в точности то же самое. Вот распределение первых 100, 1000 и 10000 чисел Фибоначчи по первой цифре: 30, 18, 13, 9, 8, 6, 5, 7, 4 301, 177, 125, 96, 80, 67, 56, 53, 45 3011, 1762, 1250, 968, 792, 668, 580, 513, 456 6.5. Исследуйте поведение первой цифры факториала n!, где n ∈ N. Конечно, такое точное совпадение ответов для разных классов чисел не может быть случайным. И действительно, закон Ньюкомба, известный также как закон старшего разряда, утверждает, что цифра d встре- чается в качестве ведущей с вероятностью log 10 (1 + 1/d). Вот значения логарифма с точностью до 6 значащих цифр: 0.301030, 0.176091, 0.124939, 0.0969100, 0.0791812, 0.0669468, 0.0579919, 0.0511525, 0.0457575 Как отмечает В.И. Арнольд, это объясняет многие реально наблюдае- мые явления, связанные с экспоненциальным ростом, например, почему численность населения примерно одной страны из трех начинается с 1. То же относится к основным физическим постоянным — в любой системе еди- ниц! 76 76 Ну, как не воскликнуть: “I do not know as much as God, but I know as much as God did at my age!” c Milton Shulman 277 § 2. Рациональные числа Уровень научного образования во всех странах мира неуклонно снижается, а Россия в этом общемировом процессе, как и в других, отстает. Например, некоторые наши школьники до сих пор сво- бодно складывают дроби, тогда как все американские студенты и 80% школьных учителей давно уже думают, что 1/2 + 1/3 = 2/5. В.И.Арнольд, Что такое математика? В данном параграфе мы обсуждаем основы вычислений с рациональны- ми числами. Поле Q рациональных чисел является полем частных кольца Z целых чисел и, таким образом, с одной стороны вычисления в нем сводят- ся к вычислениям с целыми числами, а, с другой стороны, интерпретация в терминах дробей позволяет гораздо проще проводить многие вычисления с целыми числами. 1. Числитель и знаменатель. 77 Рациональное число x представляется как частное двух целых чисел m/n, n 6= 0, при этом автоматически производятся все сокращения, ко- торые система в состоянии найти. Numerator[x] числитель x Denominator[x] знаменатель x Таким образом, Numerator[m/n] и Denominator[m/n] возвращают не m и n, а m/ gcd(m, n) и n/ gcd(m, n), причем знак относится к числителю. 1.1. Как известно, многие школьники сокращают правильные дроби, за- черкивая одинаковую цифру в числителе и знаменателе. Например, за- черкивая 6 в 26/65 мы получаем 2/5. Найдите все правильные дроби со знаменателями < 1000, которые можно сокращать таким образом. Ответ. Вот все такие дроби с двузначными числителями и знаменателями: 16 64 = 1 4 , 19 95 = 1 5 , 26 65 = 2 5 , 49 98 = 4 8 . Вот такие дроби с двузначным числителем и трехзначным знаменателем: 13 325 = 1 25 27 756 = 2 56 34 136 = 4 16 34 238 = 4 28 39 195 = 3 15 39 975 = 3 75 49 196 = 4 16 49 294 = 4 14 49 392 = 4 32 59 295 = 5 25 67 268 = 7 28 67 469 = 7 49 79 395 = 7 35 83 332 = 8 32 96 192 = 6 12 97 194 = 7 14 97 291 = 7 21 98 196 = 8 16 98 294 = 8 24 98 392 = 8 32 77 Can you do Division? Divide a loaf by a knife — what's the answer to that? c Lewis Carroll, Through the looking glass 278 Что касается дробей с трехзначными числителями и знаменателями, то их уже довольно много. Кроме тривиальных примеров 101/202, 101/303, 102/204, 103/206, встречается и несколько более интересные примеры, ска- жем, 133/931 = 13/91. Как известно, многие школьники складывают дроби складывая их чис- лители и знаменатели. Однако, хороший школьник знает, что так можно складывать только несократимые дроби. А именно, дробь a b u c d = a + c b + d называется медиантой дробей a/b и c/d. 1.2. Задайте медианту двух дробей. Решение. Если ровно двух, то проще всего так: medianta[x ,y ]:=(Numerator[x]+Numerator[y])/ (Denominator[x]+Denominator[y]) Однако, следует иметь в виду, что из-за возможных сокращений медианта не ассоциативна. Поэтому в природных условиях мы бы, скорее всего, определили медианту так: medianta[x ]:=Total[Numerator[ {x}]]/Total[Denominator[{x}]] В 1816 году английский геолог Джон Фарей расположил все (несокра- тимые) дроби 0 ≤ l/m ≤ 1 со знаменателем m ≤ n в порядке возрастания и высказал предположение, что каждый член этой последовательности яв- ляется медиантой двух соседних. Получающаяся так последовательность дробей называется последовательностью Фарея порядка n. 1.3. Напишите команду, порождающую последовательность Фарея и убе- дитесь в справедливости гипотезы Фарея. Решение. Ну, например, так: farey[n ]:=Union[Flatten[Table[i/j, {j,1,n},{i,0,j}],1]] Теперь вычисление Do[Print[farey[n]], {n,1,6}] Вернет нам ответ {0,1} {0,1/2,1} {0,1/3,1/2,2/3,1} {0,1/4,1/3,1/2,2/3,3/4,1} {0,1/5,1/4,1/3,2/5,1/2,3/5,2/3,3/4,4/5,1} {0,1/6,1/5,1/4,1/3,2/5,1/2,3/5,2/3,3/4,4/5,5/6,1} Разумеется, 0 истолковывается как 0/1. 2. Гармонические числа. 279 Из курса анализа хорошо известен гармонический ряд: 1 + 1 2 + 1 3 + 1 4 + 1 5 + . . . Его частичные суммы называются гармоническими числами: H n = 1 + 1 2 + 1 3 + . . . + 1 n . Вот несколько первых гармонических чисел: H 1 = 1, H 2 = 3 2 , H 3 = 11 6 , H 4 = 25 12 , H 5 = 137 60 , H 6 = 49 20 , H 7 = 363 140 , H 8 = 761 280 , H 9 = 7129 2520 , H 10 = 7381 2520 . По самому определению n-е гармоническое число рационально. Являясь дискретным аналогом логарифма, гармонические числа настолько часто возникают в комбинаторных задачах и при анализе алгоритмов, что в си- стему встроена специальная функция HarmonicNumber для их быстрого вы- числения. HarmonicNumber[n] n-е гармоническое число EulerGamma константа Эйлера Следующее упражнение основано на том, что знаменатель H n являет- ся делителем lcm(2, . . . , n) — и, тем более, n!. Таким образом, все числа lcm(2, . . . , n)H n — и, тем более, n!H n — целые. 2.1. Убедитесь, что при n > 1 число H n не может быть целым. Указание. Посмотрите на числа lcm(2, . . . , n)H n , все они нечетны. Это значит, что входящая в знаменатель H n степень 2 никогда не сокращается. 2.2. Вычислите таблицу первых 100 гармонических чисел. Найдите те простые, на которые в них происходит сокращение. Посмотрим теперь на числители гармонических чисел. Числитель H 2 делится на 3, но не на 3 2 . Зато числитель H 4 делится на 5 2 , числитель H 6 — на 7 2 , а числитель H 10 — на 11 2 . Вообще, теорема Вольстенхольма утверждает, что для любого простого p > 3 числитель H p −1 делится на p 2 2.3. Проверьте теорему Вольстенхольма для первой тысячи простых. Решение. Можно так. Apply[And,Table[TrueQ[ Mod[Numerator[HarmonicNumber[Prime[i]-1]],Prime[i]^2]==0], {i,3,1002}]] Если мы интересуемся только целыми частями, n-е гармоническое чис- ло довольно точно аппроксимирует ln(n) — или, в зависимости от точки зрения, аппроксимируется ln(n). 280 2.4. Оцените разницу ln(n) и H n для n ≤ 1000. Убедитесь, что всегда ln(n) < H n < ln(n) + 1. В действительности существует предел H n − ln(n) при n −→ ∞. Этот предел обозначается γ и называется константой Эйлера. Вычисление N[EulerGamma,50] дает первые 50 знаков константы Эйлера: 0.57721 56649 01532 86060 65120 90082 40243 10421 59335 93992. Однако, если нас интересуют знаки после запятой, то для небольших значе- ний n (порядка миллионов или миллиардов) даже ln(n)+γ все еще является не очень хорошим приближением к H n . Следующая формула для H n H n = ln(n) + γ + 1 2n − 1 12n 2 + ε 120n 4 где 0 ≤ ε ≤ n, позволяет получить гораздо лучшее приближение. Как доказал Эйлер, ряд ∞ X i=1 1 p i , где p i обозначает i-е простое число, расходится. 2.5. Сравните два следующих кода: N[Sum[1/Prime[i], {i,1,PrimePi[10^n]}]] Sum[N[1/Prime[i]], {i,1,PrimePi[10^n]}] В чем их отличие? Какой из них дает более надежный результат? Ка- кой дольше вычисляется? А теперь проведите эксперимент для небольших значений n, скажем, n = 5, 6, 7. Если гармонический ряд расходится логарифмически, то этот ряд рас- ходится еще гораздо медленнее, примерно как ln(ln(n))! Иными словами, никто никогда не видел — и в течение ближайшего столетия скорее всего и не увидит — никаких его значений, больших чем 7. 2.6. Пронаблюдайте динамику частичных сумм ряда ∞ X i=1 1 p при небольших n, скажем n = m10 4 , 1 ≤ m ≤ 10. При каком n эта сумма превзойдет 3? 3. Десятичные дроби. 78 В данном разделе мы изучим запись рациональных чисел так называе- мыми бесконечными десятичными дробями. Как хорошо известно, никаких бесконечных десятичных дробей не существует. То есть, конечно, они су- ществуют как последовательности цифр, но вот только ни складывать, ни 78 In the Middle Age, in Germany, if you wanted to learn addition and multiplication, you could go to any university. But if you wanted to learn division, you could only do it in one place, Heidelberg. c Israel Gelfand 281 умножать их никто не умеет, поэтому вся излагаемая в школьном курсе математики “теория” вещественных чисел, основанная на использовании бесконечных десятичных дробей, абсолютно бессмысленна. Что, однако, существует, это конечные десятичные дроби и периодиче- ские десятичные дроби, которыми выражаются рациональные числа. Опе- рации над конечными дестяичными дробями сразу сводятся к операциям над целыми числами. В настоящем параграфе мы постараемся придать смысл операциям над периодическими дробями. Дело это называется тео- рией сравнений и обычно изучается не в школьном курсе арифметики, а в университетском курсе теории чисел. Например, в школьном курсе нико- гда не доказывается, что рациональное число записывается периодической дробью. В действительности этот факт составляет содержание теоремы Эйлера, которая, кроме того, утверждает, что период несократимой дроби со знаменателем n не превосходит φ(n), где φ некоторая арифметическая функция, называемая функцией Эйлера. В следующем параграфе мы обсудим, как работают команды RealDig- its и FromDigits для приближенных вещественных чисел. Однако для рациональных чисел их использование имеет некоторую специфику. RealDigits[x] предпериод и период рационального числа x FromDigits[ {list,m}] восстановление числа по списку цифр Говорят, что число x изображается периодической десятичной дробью, если найдется такое натуральное l, что 10 l x − x выражается конечной де- сятичной дробью. Это значит, что начиная с некоторого места эта дробь состоит из бесконечно повторяющегося блока цифр длины l. Наименьшее такое l называется длиной периода, а сам повторяющийся фрагмент длины l — периодом этой дроби. Однако десятичная запись числа не обязана начинаться с периода, ему может предшествовать предпериод. Дробь, начинающаяся сразу с периода, называется чисто периодической. Например, дробь 5/12 = 0.416666666 . . . имеет предпериод длины 2, и период — длины 1. Как мы уже знаем из предыдущей главы, дробь 1/7 = 0.14285714285714285714 . . . является чисто периодической и имеет период 142857 длины 6. Разложение рационального числа x в конечную/периодическую десятич- ную дробь получается применением к нему команды RealDigits[x]. Ответ имеет следующий формат. • Для числа x = m/n, в знаменатель которого входят только степени 2 и 5, ответ имеет вид {{x1, . . . ,xk},r}, где x 1 , . . . , x k предпериод (кроме начальных нулей), а r — десятичная экспонента. Иными словами, 10 r · 0.x 1 . . . x k • Для любого другого рационального числа x = m/n ответ имеет вид {{x1, . . . ,xk,{y1, . . . ,yl}},r}, где x 1 , . . . , x k и r имеют тот же смысл, что и раньше, а y 1 , . . . , y l период десятичной записи x. 282 3.1. Убедитесь, что длина периода несократимой дроби m/n равна наи- меньшему l, для которого найдется такое натуральное k, что знаменатель n этой дроби делит 10 k (10 l − 1). 3.2. В условиях предыдущей задачи убедитесь, что длина предпериода m/n равна наименьшему k такому, что n делит 10 k (10 l − 1). 3.3. Убедитесь, что длина предпериода и периода правильной дроби m/n не превосходит φ(n). Когда здесь достигается равенство? 4. Египетские дроби. 79 Древние египтяне представляли рациональное число как сумму целого и нескольких различных дробей с числителем рав- ным 1. Такие выражения принято называть египетскими дробями. Вот первые интересные примеры египетского разложения правильных дробей: 3 7 = 1 3 + 1 11 + 1 231 , 5 7 = 1 2 + 1 5 + 1 70 , 6 7 = 1 2 + 1 3 + 1 42 . Следующая задача содержится в знаменитом папирусе Райнда 80 , храня- щемся в Британском музее. 4.1. Найдите натуральное n такое, что 2 73 = 1 60 + 1 219 + 1 292 + 1 n . Каждое рациональное число может быть бесконечным числом способов записано как египетская дробь, но для любого m среди этих записей лишь конечное число состоит ровно из m слагаемых 81 . Сейчас мы попробуем опи- сать несколько алгоритмов разложения рационального числа в египетскую дробь. Проще всего реализовать жадный алгоритм 82 . Так называется алго- ритм, выбирающий на каждом шаге наибольшее слагаемое, которое может войти в египетскую дробь. Для реализации этого алгоритма нам понадобится важная вспомогатель- ная функция, сопоставляющая списку его список разностей. 4.2. Определите функцию, которая по списку длины n порождает список длины n − 1, состоящий из попарных разностей соседних членов исходного списка. Решение. Вот совсем топорное решение: differences[x ]:=Table[x[[i]]-x[[i+1]], {i,1,Length[x]-1}] 79 Человек не хуже муравья может переносить тяжести в 20 раз больше собственного веса. Но за большее количество раз, и страшно матерясь. c Николай Фоменко 80 A.B.Chace, H.P.Manning, R.C.Archibald, The Rhind mathematical papyrus. vol.I. — Berlin, 1929. 81 I.Stewart. The riddle of the vanishing camel. Scientific American, June 1992, p.122–124. 82 S.Wagon. Mathematica in Action — Springer-Verlag, 1999. 283 Зная, что арифметические операции распределяются по спискам, можно дать гораздо более изящную конструкцию: differences[x ]:=Most[x]-Rest[x] Из общих соображений кажется, что этот код улучшить невозможно, но в действительности следующее определение еще лучше и исполняется чуть быстрее: differences[x ]:=Apply[Subtract,Partition[x,2,1], {1}] 4.3. Определите функцию, которая сопоставляет рациональному числу x его разность с наибольшим египетским слагаемым. Решение. Если число целое или его числитель равен 1, то остаток равен 0, если оно рациональное вне отрезка [0, 1], то нужно вычесть целую часть. Остается понять, что в случае, когда x ∈ (0, 1) из него нужно вычесть 1/ d1/xe. Все это можно резюмировать так: greedypart[x ]:=Which[IntegerQ[x],0,Numerator[x]==1,0, x<0||x>1,x-Floor[x],True,x-1/Ceiling[1/x]] При предыдущих условиях Ceiling[1/x] совпадает с 1+Floor[1/x] или, что то же самое с 1+Quotient[1,x] 4.4. Закончите программу разложения рационального числа в египетскую дробь по жадному алгоритму. Решение. Ну, например, так: greedylist[x ]:=Most[FixedPointList[greedypart,x]] greedyegypt[x ]:=differences[greedylist[x]] К сожалению, даже в случае небольших числителей и знаменателей жад- ный алгоритм часто дает очень плохие разложения. Так, уже 17 19 = 1 2 + 1 3 + 1 17 + 1 388 + 1 375972 выглядит подозрительно, а при разложении 31/311 получаются знаменате- ли, содержащие больше 500 цифр! Хватать все, что подвернется под руку, не всегда является лучшей стратегией. Имеется много других алгоритмов, которые дают более короткие разложения с гораздо меньшими знаменате- лями. Часто выгоднее предполагать, что знаменатели с самого начала быст- ро растут. Вот два классических алгоритма такого рода, гарантирующие, кроме того, единственность представления 83 4.5. Алгоритм Фибоначчи: любое рациональное число 0 < x < 1 един- ственным образом представляется в виде x = 1 n 1 + 1 n 2 + . . . + 1 n s , 83 по поводу доказательства см. С.Б.Гашков, В.Н.Чубариков. Арифметика, алгорит- мы, сложность вычислений, 2-е изд. – М: ”Высшая школа”, 2000. 320 c. 284 где n 1 ≥ 2 и n i+1 > n 2 i − n i для всех i. Реализуйте алгоритм Фибоначчи. 4.6. Алгоритм Остроградского: любое рациональное число 0 < x < 1 единственным образом представляется в виде x = 1 n 1 + 1 n 1 n 2 + . . . + 1 n 1 n 2 . . . n s , где n 1 ≥ 2 и n i+1 ≥ n i для всех i. Реализуйте алгоритм Остроградского. |