Математика. Настоящий учебник посвящен системе Mathematica прикладному пакету компьютерной алгебры, при помощи которого можно решать любые задачи, в которых в той или иной форме встречается математика
 Скачать 4.43 Mb.
|
|
a/(b/(c/d)) различных? Суммы и произведения вычисляются при помощи внутренних команд Sum и Product, с итераторами обычного формата. Sum[a, {i,m,n}] сумма n P i=m a i Product[a, {i,m,n}] произведение n Q i=m a i 1.2. Найдите сумму всех n-значных чисел Решение. Породив таблицу первых 10 таких сумм Table[Sum[i, {i,10^(n-1),10^n-1}],{n,1,10}] мы увидим следующий ответ 45, 4905, 494550, 49495500, 4949955000, 494999550000, 49499995500000, 4949999955000000, 494999999550000000, 49499999995500000000, где количество идущих подряд девяток на единицу меньше, чем количе- ство нулей. После того как этот ответ написан, он становится очевидным. Если Вы предпочитаете видеть не всю таблицу сразу, а отдельные суммы, которые возникают на экране по мере их вычисления, можно напечатать, например, For[n=1,n<=10,n++,Print[Sum[i, {i,10^(n-1),10^n-1}]]] Максимум и минимум конечной последовательности или конечного спис- ка чисел ищутся при помощи команд Max и Min. Max[m,n] максимум m и n Min[m,n] минимум m и n Пусть 2s натуральных чисел расположены в порядке возрастания: 0 < n 1 < n 2 . . . < n 2s −1 < n 2s . 1.3. Разбейте эти числа на пары так, чтобы сумма произведений пар была максимальна. 1.4. Разбейте эти числа на пары так, чтобы сумма произведений пар была минимальна. 1.5. Разбейте эти числа на пары так, чтобы произведение сумм пар было максимально. 1.6. Разбейте эти числа на пары так, чтобы произведение сумм пар было минимально. Указание. Проведите небольшой компьютерный эксперимент. После то- го, как ответ известен, он легко доказывается индукцией. 265 1.7. Найдите все наборы из m натуральных чисел ≤ n, для которых их сумма равна изх произведению. 2. Вычисление степеней. 67,68 Следующая функция служит для образования степеней. x^y Power[x,y] потенцирование Обратите внимание, что потенцирование использует правую группировку! 2.1. Проверьте, как истолковывается выражение l^m^n. В связи высказы- ванием популярного музыканта, приведенным в сноске следующего разде- ла, вычислите 2^2^7 и (2^2)^7. 2.2. Дайте рекуррентное определение функции степени x n Решение. Напрашивающееся определение для того, кто делал вид, что учился математике, но при этом никогда не интересовался программирова- нием, и ничего не вычислял сам, такое: power[x ,0]:=1; power[x ,n ]:=power[x,n-1]*x Будучи правильным с логической точки зрения в вычислительном смыс- ле это определение абсолютно чудовищно. Почему? Подобное определе- ние становится совершенно бесполезным при вычислении чего-нибудь столь крошечного, как 2 100000 . Для вычислении x n по этому определению требу- ется около n − 1 умножений, в то время как еще древние египтяне знали, что при вычислении x n можно обойтись количеством умножений поряд- ка log 2 (n). Следующий способ вычисления степени называется бинарным или египетским алгоритмом: x n = (x n/2 ) 2 , если n четно, x n −1 x, если n нечетно. Непродолжительное размышление убедит вас в том, что 100000 умножений это чуть меньше, чем 2 100000 умножений. Так, выполняя 10 9 умножений в секунду, мы произведем 100000 умножений за время, меньшее зернистости контроля времени системой Windows (1 миллисекунда). Тогда как 2 100000 ≈ 10 30103 умножений не может быть выполнено никогда. 2.3. А теперь определите функцию x n еще раз, при помощи египетского алгоритма. 67 O ye powers! (for powers ye are, and great ones too) c Laurence Sterne, Tristram Shandy 68 If all computers of earth were to focus simply on writing down as many digits as possible for the next century, they would write down far less than 2 2 7 digits. c A.Granville, It is easy to determine whether a given integer is prime. — Bull. Amer. Math. Soc., 2004, vol.42, N.1, p.3–38. 266 Решение. Ну, хотя бы, так: power[x ,0]:=1; power[x ,n ]:=If[EvenQ[n],power[x,n/2]^2,power[x,n-1]*x] Хотя, вероятно, в естественных условиях мы воспользовались бы не услов- ным оператором, а определением с условием: power[x ,0]:=x; power[x ,n ]:=power[x,n/2]^2 /; EvenQ[n] power[x ,n ]:=power[x,n-1]*x /; OddQ[n] Конечно, по факту эти определения работают за одинаковое время (но все еще раз в пять медленнее, чем встроенная функция Power использующая профессиональные алгоритмы). Вычисление степеней можно реализовывать и иначе. Еще один чрезвы- чайно популярный алгоритм вычисления степени, известный очень давно, но систематически исследованный только де Жонкьером в самом конце XIX века, это метод простого множителя: x n = (x n −1 )x, n простое, (x p ) m , n = pm, где p наименьший простой делитель n. 2.4. Определите функцию x n при помощи метода простого множителя и сравните скорость ее работы со скоростью функции основанной на египет- ском алгоритме. 2.5. Найдите случаи, когда метод простого множителя требует меньше умножений, чем египетский алгоритм. Ответ. Первый случай, когда метод простого множителя лучше, чем еги- петский алгоритм, это вычисление x 15 , которое требует шести умножений по египетскому алгоритму x, x 2 , x 3 , x 6 , x 7 , x 14 , x 15 , и только пять умножений по методу простого множителя: x, x 2 , x 3 , x 6 , x 12 , x 15 . Впрочем, x n можно вычислять и многими другими способами, например, вычисление x 15 при помощи описанного в книге Кнута дерева степеней тоже дает пять умножений: x, x 2 , x 3 , x 5 , x 10 , x 15 . Первый случай, для которого дерево степеней более эффективно, чем метод простого множителя, это вычисление x 23 . При этом используется только шесть умножений: x, x 2 , x 3 , x 5 , x 10 , x 13 , x 23 , 267 в то время как метод простого множителя требует семь умножений: x, x 2 , x 4 , x 5 , x 10 , x 11 , x 22 , x 23 . Хармс определил функцию, несколько первых значений которой таковы: 1, 2 2 , 3 3 3 , 4 4 44 , 5 5 55 5 , . . . 2.6. Дайте рекуррентное определение функции Хармса. Сколько значений этой функции Вам удастся вычислить? 3. Извлечение цифр. 69 В настоящем параграфе мы начнем отраба- тывать технику вычислений с цифрами. Это на непросвещенный взгляд чисто схоластическое занятие имеет по крайней мере два важных прило- жения. Во-первых, числовые последовательности обычно удобнее всего по- рождать именно через последовательности цифр. Во-вторых, большинство эффективных современных алгоритмов работы с многозначными числами имитирует вычисления с многочленами и основано на разбиении чисел на блоки цифр. IntegerDigits[n] список цифр числа n FromDigits[ {a1,...,an}] преобразование списка цифр в число DigitCount[n,b,d] кратность цифры d в числе n IntegerExponent[n] количество нулей в конце n 3.1. Как узнать, сколько цифр содержит число n? Чему равна сумма его цифр? Какая цифра стоит у него в старшем/младшем разряде? Ответ. Проще всего так: Length[IntegerDigits[n]], Total[IntegerDigits[n]], First[IntegerDigits[n]], Last[IntegerDigits[n]], 3.2. Задайте число 9 . . . 9, состоящее из n девяток. 3.3. Задайте число 123 . . . 123, где группа цифр 123 повторяется n раз. Решение. По-хорошему это делается, например, так FromDigits[Flatten[Table[ {1,2,3},{n}]]] Функция выравнивания Flatten убирает лишний уровень вложенности в получающемся при исполнении Table списке {{1,2,3},...{1,2,3}}. Можно, конечно, и без затей Sum[123*1000^(i-1), {i,1,n}] 69 Учитель сказал, что я совсем не знаю математики и поставил мне в дневник какую- то цифру. c Николай Фоменко 268 но для больших n это гораздо менее эффективно с вычислительной точки зрения. Кроме того, возможности применения команды FromDigits гораз- до шире. 3.4. Задайте число 10001 . . . 10001, состоящее из n единиц, разделенных группами по три нуля. Указание. Используйте Join, чтобы добавить в список последнюю еди- ницу. 3.5. Задайте число 1234 . . . 9991000, состоящее из выписанных подряд чисел от 1 до 1000. Указание. Обратите внимание, что наивное FromDigits[Range[1000]] дает неправильный результат! Используйте IntegerDigits и Flatten. Еще одной внутренней командой является DigitCount[n]], которая по- казывает количество цифр, входящих в запись числа n, в следующем по- рядке: 1,2,3,4,5,6,7,8,9,0. 3.6. Определите функцию, которая показывает количество цифр, входя- щих в разложение числа n, в обычном порядке 0,1,2,3,4,5,6,7,8,9. Решение. Конечно, можно просто циклически переставить кратности, возвращаемые DigitCount: dc1[n ]:=RotateRight[DigitCount[n]] С другой стороны, такую функцию легко задать и обращаясь непосред- ственно к IntegerDigits: dc2[n ]:=Table[Count[IntegerDigits[n],i], {i,0,9}] 3.7. Каких чисел среди натуральных чисел ≤ 10 n больше: тех в деся- тичной записи которых встречается 1 или тех, в записи которых она не встречается? А теперь определите функцию, вычисляющую количество тех чисел ≤ 10 n , в записи которых не встречается 1, и посчитайте первые 10 ее значений. 3.8. Имеется 9! = 362880 девятизначных чисел, состоящих из попарно различных цифр 1, . . . , 9. Сколько из них являются полными квадратами? Указание. Что легче выбрать, девятизначные числа, являющиеся полны- ми квадратами, или квадраты пятизначных чисел, состоящие из различных цифр? Ответ. Вот эти числа 139854276 152843769 157326849 215384976 245893761 254817369 326597184 361874529 375468129 382945761 385297641 412739856 523814769 529874361 537219684 549386721 587432169 589324176 597362481 615387249 627953481 653927184 672935481 697435281 714653289 735982641 743816529 842973156 847159236 923187456 Поскольку литература по теории чисел и Computer Science никем не ре- дактируется, большинство многозначных чисел в книгах по этим наукам 269 воспроизведено с опечатками. Таким образом, при ссылке на любые чис- ленные данные их приходится проверять заново. В предположении, что опечатка затронула лишь одну цифру, часто приходится генерировать спис- ки чисел, отличающихся от исходного лишь в одной позиции. 3.9. Напишите программу, которая порождает список чисел той же раз- рядности, отличающихся от исходного в одной цифре. Решение. Например, при помощи Replace Part: replacedigit[n ]:=Map[FromDigits[ ReplacePart[IntegerDigits[n],#[[2]],#[[1]]]]&, Complement[Flatten[Outer[List, Range[Length[IntegerDigits[n]]],Range[0,9]],1], {{1,0}}]] 3.10. Напишите программу, которая порождает список чисел той же раз- рядности, отличающихся от исходного в двух цифрах. 3.11. Проверьте, что заменяя в четырехзначном числе не более двух цифр, из него всегда можно получить простое число. Верно ли то же самое для пятизначных чисел? 3.12. Из цифр 1, 2, 3, 4, 5, 6, 7, 8, 9 составлены всевозможные числа, не содержащиеся повторяющихся цифр. Найти их сумму. 4. Манипуляция с цифрами. 70 Билет с номером abcdef называется счастливым по петербургски, если a + b + c = d + e + f, т.е. сумма первых трех цифр равна сумме трех последних цифр. Тот же билет называется счастливым по московски, если a + c + e = b + d + f, т.е. сумма цифр, расположенных на нечетных местах равна сумме цифр на четных местах. 4.1. Найдите количество счастливых билетов. 4.2. Найдите количество дважды счастливых билетов (т.е. таких, которые одновременно являются счастливыми по петербургски и по московски). Ответ. Не пытайтесь вывести на экран список номеров счастливых биле- тов: количество счастливых билетов равно 55252, а дважды счастливых — 6700. Следующие задачи взяты из классического сборника задач московских математических кружков 71 . Впрочем, его авторы вряд ли предполагали, что эти задачи будут решаться с использованием компьютера! 70 Recreational Number Theory is that part of Number Theory that is too difficult to study seriously. c H. W. Lenstra, Jr. — AMS-MAA Invited talk, 2002 Annual meeting, San Diego, Jan. 8, 2002. 71 Д.О.Шклярский, Н.Н.Ченцов, И.М.Яглом, Избранные задачи и теоремы элемен- тарной математики. Ч.I. Арифметика и алгебра. — М., ГИТТЛ, 1954, с.1–455. 270 4.3. Найдите все натуральные числа, которые при зачеркивании последней цифры уменьшаются в целое число раз. Ответ. Очевидно, что число, заканчивающееся на 0 при отбрасывании последней цифры уменьшается в 10 раз. С другой стороны, если последняя цифра не равна нулю, то при ее отбрасывании число уменьшается больше, чем в 10 раз. Теперь вычисляя Select[Range[10,10000],Last[IntegerDigits[#]]!= 0&& Mod[#,FromDigits[Most[IntegerDigits[#]]]]==0&] мы получим следующие числа 11, 12, 13, 14, 15, 16, 17, 18, 19, 22, 24, 26, 28, 33, 36, 39, 44, 48, 55, 66, 77, 88, 99. Теперь секундное размышление убеж- дает нас, что каждое число, уменьшающееся при отбрасывании последней цифры в m > 10 раз, обязано быть двузначным, так что мы действительно нашли все такие числа. 4.4. Существует ли натуральное число x такое, что его произведения на 2,3,4,5,6 записываются теми же цифрами, что само x, но в другом порядке? Ответ. Условие, что x и y имеют один и тот же набор цифр выражается как Sort[IntegerDigits[x]]==Sort[IntegerDigits[y]] Теперь по аналогии с предыдущей задачей совсем легко написать код, вы- бирающий числа, удовлетворяющие этому условию. Вот наименьший такой пример x = 142857, 2x = 285714, 3x = 428571, 4x = 571428, 5x = 714285, 6x = 857142. Понятно, что пририсовывая к этому примеру любое количество нулей мы получим число, обладающее таким же свойством. Стоит отметить, что это свойство числа 142857 известно много тысячелетий. Каким образом? Дело в том, что это число представляет собой в точности период десятичной дроби, которой записывается 1/7. Вычисляя Table[N[i/7], {i,1,6}] мы получим следующий знакомый ответ: 0.142857, 0.285714, 0.428571, 0.571429, 0.714286, 0.857143 Вас, конечно, не смущают последние цифры трех последних чисел, полу- чающиеся в результате так называемого округления. Поиск дальнейших примеров является весьма хлопотным делом, занима- ющим на бытовом компьютере несколько минут. Среди семизначных чисел кроме 1428570 возникает еще ровно один пример, а именно, x = 1429857, 2x = 2859714, 3x = 4289571, 4x = 5719428, 5x = 7149285, 6x = 8579142. 4.5. Существуют ли числа, которые при перестановке первой цифры в конец увеличиваются в три раза? 271 Ответ. Два таких числа, а именно, 142857 и 285714 были найдены нами в предыдущей задаче. Выполняя следующий код, Select[Range[10^6], FromDigits[RotateLeft[IntegerDigits[#]]]==3*#&] мы видим, что это единственные шестизначные числа, обладающие таким свойством. С другой стороны, совершенно ясно, что повторяя ту же группу цифр при помощи команды FromDigits[Flatten[Table[ {1,4,2,8,5,7},{n}]]] мы получим дальнейшие числа, обладающие тем же свойством. 4.6. Найдите все числа n ≤ 10 6 , которые при вычеркивании одной цифры уменьшаются в 9 раз. Ответ. Исполнение кода Select[Range[10^6],MemberQ[ Table[9*FromDigits[Drop[IntegerDigits[#], {i}]], {i,1,Length[IntegerDigits[#]]}],#]&] показывает, что имеется 87 таких чисел 45, 135, 225, 315, 405, 450, 675, 1125, . . . 4.7. Найдите все числа n ≤ 10 6 , которые при вычеркивании одной циф- ры уменьшаются в 9 раз и обладают тем дополнительным свойством, что получившееся число снова делится на 9. Ответ. Нужно лишь внести в предыдущий код дополнительный тест Mod[Total[IntegerDigits[#]],9]==0&, выбирающий из списка чисел, по- лучающихся из x вычеркиванием одной цифры, те, сумма которых делится на 9. При этом найдется 18 таких чисел, из которых ровно 7 заканчиваются на 5: 405, 2025, 6075, 10125, 30375, 50625, 70875, а все остальные получаются из них дорисовыванием нулей в конце. 4.8. Для данного натурального n найдите все пары натуральных чисел таких, что l + m = n и m получается из l вычеркиванием одной цифры. 4.9. Найдите все числа, для которых квадрат заканчивается на само это число — последняя цифра 6= 0. 5. Палиндромы. 72 В настоящем разделе мы обсудим операцию реверсии, состоящую в пе- реворачивании списка цифр числа. Иными словами, если исходное число x записывается как a 1 . . . a n , то реверсированное число rev(x) = a n . . . a 1 состоит из тех же цифр в обратном порядке. Обратите внимание, что чис- ло реверсированное к реверсированному, вообще говоря, не обязано совпа- дать с исходным. Казалось бы, реверсированные числа представляют со- бой чистую игру ума, но в действительности в докомпьютерную эпоху они очень широко использовались для вычисления произведения не начиная с 72 I'm guided by the beauty of our weapons. c Leonard Cohen — AMS-MAA Invited talk, 2002 Annual meeting, San Diego, Jan. 8, 2002. 272 младшего разряда, как при обычном школьном “умножении столбиком”, а начиная со старшего разряда, как это принято в теории приближенных вычислений 73 5.1. Определите функцию, которая сопоставляет числу реверсированное к нему число. Ответ. Ну, конечно, это rev[n ]:=FromDigits[Reverse[IntegerDigits[n]]] 5.2. Найдите все числа ≤ 10 7 , которые в 4 раза меньше своего реверсиро- ванного. Ответ. Вычисляя Select[Range[10^7],FromDigits[Reverse[IntegerDigits[#]]]==4*#&] мы видим, что таких чисел ровно 4, а именно 2178, 21978, 219978, 2199978, причем все они получаются врисовыванием девяток внутрь первого из них. 5.3. Найдите все числа ≤ 10 7 , которые в 9 раз меньше своего реверсиро- ванного. Ответ. В данном случае ответ таков: 1089, 10989, 109989, 1099989. |