Д. Кнут - Искусство программирования том 1 (1119450), страница 25
Текст из файла (страница 25)
Из формулы (14) можно вывести много важных фактов. Прежде всего, отметим, что 12 — это оп2рицательное число (-0.61803...), модуль которого меньше единицы. Поэтому с увеличением и последовательность ) р") убывает. Фактически величина ф /~/5 всегда настолько мала, что можно принять 3. [35) Напишите программу, которая вычисляет и выдает на печать числа Фибоначчи от Г, до Гшоо в десятичном виде. (В предыдущем упражнении был определен порядок чисел, с которыми придется иметь дело.) 4.
[14] Найдите все и, для которых Г = и. 5. [80] Найднге все и, для которых Г = иг. 6. [НМ10] Докажите тождество (5). Т, [15) Если и не является простым числом, то и Г„не является простым числом (за одним исключением). Докажите это утверждение и найдите исключение. 8. [15) Во многих случавх удобно определить Г для ошрицашеаьных и. Предположим, что Г+г = Г +г+ Г„для всех целых и. Проанализируйте эту возможность и ответьте на следующие вопросы. Чему равны Г г и Г г? Можно ли простым способом выразить Г „ через Г? 9. [Мдд] Используя соглашения из упр.
8, определите, выполняются ли соотношения (4), (б), (14) и (15) при любых целых значениях нижних индексов. 10. [15) Выясните, будет ли значение 4"1'г/5 больше или меньше Г„. 11. [Мдд] Покажите, что ег» = Г„й+ Г г и 4'" = Г 5 + Г» г для оеех целых и. э 12, [Мдб) Последовательность Фибоначчи "второго порядка" определяется соотноше пнями Уо = О, Гг = 1, Уп~-г = у'»~-г + у» + Г». Выразите У„через Г и Г„.еь [Укаеаипе. Воспользуйтесь производящими функциями.) ь 13.
[Мдд) Выразите следующие последовательности с помощью чисел Фибоначчи (г, в и с — заданные константы): а) ао = г, аг = е; а»+г = а»+г + а, и > О; Ь) Ьо=О,Ьгж1; Ь»+г=Ь»,.г+Ь +с,и>О. 14. [Мдд) Пусть ги — фиксированное положительное целое число.
Найдите а„, если а»+г = а„тг + а + (") при и > О аг=1; ао — — О, 15. [Мйд] Пусть 1(и) и д(и) — произвольные функции и пусть для п > О а„.~.г = а»+г + а„ + 1(и); Ь е-г = Ь»ог + Ь + д(и); с ч-г = с ч.г+с»+х1(и)+уд(и) ао = О, Ь =О, со = О, аг =1, Ь =1, сг —— 1, Выразите с, через х, у, а„, Ь„и Г„. ь 16. [МЯО) Чигла Фибоначчи неявно присутствуют в треугольнике Паскаля. Покажите, что сумма биномиальных коэффициентов является числом Фибоначчи. 17. [М84) Используя соглашения из упр. 8, докажите следующее обобщение равенства (4): У'~-ьГ -г — Г Г ° = ( — 1)"Г -»-ьГь 18. [80) Всегда ли Гг + Ггт, бУдет числом Фибоначчи? ь 19. [Мй?) Чему равен сов 35'? 20.
[М15] Выразите сумму Я,", Гь с помощью чисел Фибоначчи. 21. [Мдб] Чему равна сумма 2 " Гех~? ь 22. [М80] Покажите, что ~~» (»)Гме» является числом Фибоначчи. 23. [М88] Обобщая предыдущее упражнение, покажите, что 2» ("„)Г»Г,", Г „» всегда является числом Фибоначчи. 24. [НМ80] Вычислите определитель порядка н х и: 1 — 1 0 0 ...
0 О 0 1 1 -1 0 ... 0 0 0 0 1 1 -1 ... 0 0 0 0 0 О 0 ... 1 1 — 1 0 0 0 0 ... 0 1 1 26. [М81] Покажите, что 2"Г = 2 ~ ~( )5»" » «ае ь 26, [М80] Используя предыдущее упражнение, покажите, что Г, ж Ь»о т»т~ (по модулю р), если р — нечетное простое число. 2 т. [М80] Используя предыдущее упражнение, покажите, что если р — простое число, не равное 5, то либо Гр т, либо Г .тт (но не оба) кратно р, 28. [М81] Чему равно Г„ег — фГ«? ь 29.
[М88] (Фибономиальиме когффит»иеншм.) Эдуард Люка определил величины и') Äà -т...Г»ет тт ('Г -»+ ) ()= я/я ûû »...Г» 11'», Гт по аналогии с биномиальными коэффициентами. (а) Составьте таблицу значений (») для 0 < я < и < 6. (Ъ) Покатките, что (,") всегда является целым числом, поскольку ь 30. [М88] (Д. Джарден (11. Загт)еп) и Т.
Моцкин (Т. Мосзрйп).) Последовательность то-х степеней чисел Фибоначчи удовлетворяет рекуррентному соотношению, в котором каждый член зависит от предыдущих пг + 1 членов. Покажите, что ( — 1)П ~~ 1Г ~ = О, если гл>О ('тп 1 — „+» —— , е » Например, при та = 3 получаем тождество Ä— 2Г„»т — 2Г„ег + Г«гег = О. г г г 31.
[М80] Покажите, что Гг фщи»11 = 1 — ф г" и Гг +»фшо01 = ф г" 32. [М84] Остаток от деления одного числа Фибоначчи на другое равен ш число Фибоначчи. Покажите, что по модулю Г« Г «е»»з ЗЗ. [НМ84] Пусть з = я/2+ т)пф. Покажите, что з!ппз/з1вз = т' "Г„. Г», (-1)'+'Г 1)«Г ц тт+«Г если т шот) 4 = 0; есзи тп гпог) 4 = 1; если тп шог) 4 = 2; если тл шот) 4 = 3. в 34. [М94] (Система чисел Фибоначчи.) Пусть запись Ь » т означает, что?с > т+2.
Покажите, что для любого положительного целого и существует единственное представление и = Р», + Р», + + Г»„, где?сг »?сг » » |с, » О. Зб. (М94] (Сисгпема фи-чисел.) 1'ассмотрим действительные числа, записанные с помощью цифр 0 и 1 по основанию ф (например, (100.1)4 = фг+ф '). Покажите, что существует бесконечное множество способов такого представления числа 1, например 1 = (.11)4 = (.011111... )4. Но если потребовать, чтобы две единицы подряд не встречалось и чтобы зто представление не заканчивалось бесконечной последовательностью 01010101..., то для каждого неотрицательного числа будет существовать единственное представление. Каким будет представление для целых чисел? ь Зб.
(Муй] (Строки Фибоначчи.) Пусть Я» = "а", Яг = "6" и В„ег = Я„~.»Я, и > О, Другими словами, Б .~г образуется путем помещения 5 справа от К,.»ь Имеем 5г = «Ьа", Яс = "Ьаб", 5г = "ЬаЬ6а" и т. д. Очевидно, что в строке бь содержится Р„букв. Исследуйте свойства 5„. (Где встречаются две буквы подряд? Можете ли вы предсказать, какой будет Ь-я буква Я»? Какова плотность буквы Ь? И т.
д.) ь 3?. (Муб] (Р. Ю. Гаскел (Н. Е. Са»1се11) и М. Дж. Виниган (М. Л, %Ып16вп).) Двое играют в следующую игру. Имеется и фишек; первый игрок берет любое количество фишек (но только не все сразу). После этого момента игроки ходят по очереди, причем каждый из них берет одну или несколько фишек, но не более чем двукратное количества фишек, еалтмх предыдущим игроком. Выигрывает тот, кто заберет последнюю фишку. (Рассмотрим эту игру на конкретном примере.
Пусть п = 11. Игрок А взял 3 фишки; значит, игрок В может забрать до б фишек, но он берет 1. Остается? фишек. Игрок А может взять 1 или 2 фишки; он берет 2. Теперь игрок В может взять до 4 фишек; он берет 1. Остается 4 фишки. На этот раз игрок А берет 1 фишку; теперь игрок В должен взять по меньшей мере одну фишку, поэтому на сведующем ходе игрок А выигрывает.) Сколько фишек следует взять первому игроку в начале игры, если первоначально имеется 1 000 фишек? 9?ивннс9 жюнгчг, 38. (Уб] Напишите такую компьютерную программу игры, описанной в предыдущем упражнении, чтобы она велась оптимальным образом. 39. [М24] Найдите выражение в замкнутой форме для аь при условии, что ае = О, аг — — 1 и аь»г = аь ы + ба„для и > О. 40, [Мйб] Найдите решение рекуррентных соотношения /(1) = 0; у(п) са гшп гаах(1+?(Ь),2+ у(п — 6)) для п > 1 е<»<л ь 41. [Мйб] (Юрий Матиясевич (гиг1 МаНувееи!сй), 1990.) Пусть у(х) = (х+ ф '].
Докажите, что если и = Р», + + Е»„— это представление числа и в системе чисел фибоначчи (см. упр. 34), то Р»с<т + + Р»„~.г = г'(фп). Найдите аналогичную формулу для Р», г + + В»„ 42. [Мйб] (Д, А. Кларнер (О. А. К1»гпег).) Покажите, что если т и и — неотрицательные целые числа, то существует единственная последовательность индексов /сг » /сг » ~ Ь„ такая, что т = Г», +С»г+ +Г»„, П = Уме»+Г»г,.! +"-+Р»„ЕЬ (Заметим, что Ь могут быть отрицательными, а г — -нулем.) 1.2.9.
Производящие функции Каждый раз, когда необходимо получить информацию о последовательности чисел (ао) = ао, амат,..., можно рассмотреть бесконечную сумму от "параметра" х С(х) =по+а~э+ото~+.. = ~а„х" о>о А теперь можно заняться исследованием свойств функции С. Данная функция характерна тем, что с ее помощью можно представить всю последовательность. Это очень важно, особенно если последовательность (а„) была определена методом индукции (т. е. если а„определяется через ао, аы..., а„~). Более того, с помощью методов дифференциального исчисления по функции С(х) можно восстановить все члены последовательности ао, аы ...
(при условии, что бесконечный ряд (1) сходится для некоторого ненулевого х). С(г) называется проозоодтцей функцией для последовательности ао, ам аз,.... Использование производящих функций открывает новые горизонты методов н приемов и существенно расширяет наши возможности при решении задач. Как уже упоминалось в предыдущем разделе, А. де Муавр ввел производящие функции, чтобы решить линейные рекуррентные соотношения в общем виде.
Джеймс Стирлинг применил теорию де Муавра для решения более сложных рекуррентных соотношений и показал, как применять для этого не только арифметические операции, но также дифференцирование и интегрирование (МеСЬодпэ 1ИГегепг1а)1з (Ьоп<$оп, 1730), Ргороз111оп 15]. Через несколько лет Л. Эйлер нашел новые способы использования производящих функций, например, при исследовании разбиений [Сотгпепсагй Агасси. Бей Реп 13 (1741), 64 — 93; Хоч' Соттепй Асас(.
Яс1 Реп 3 (1750), 125 — 169). Дальнейшее развитие эти методы получили в классическом труде Пьера С. Лапласа (Р1егге Я. Ьар1асе) ТЬеоНе Апа)у11дпе с(еэ РгоЬа1лШез (Рана, 1812). Очень важен вопрос о сходимости бесконечного ряда (1). В любом учебнике по теории бесконечных рядов доказываются следующие утверждения. а) Если ряд (1) сходится для некоторого г = хо, то он сходится для всех х, таких, что )х) ( )хо!. Ь) Этот ряд сходится для некоторого х ф 0 тогда и только тогда, когда последовательность (~/~ао0 ограничена. (Если это условие не выполняется, то можно получить сходящийся ряд для последовательности (а„/и!) нли другой последовательности, связанной с исходной.) С другой стороны, во время работы с производящими функциями не всегда стоит беспокоиться о сходимости приведенного ряда, так как часто мы только исследуем возможные подходы к решению конкретной задачи.
Найдя решение некоторым способом, каким бы нестрогим оно ни было, мы сможем обосновать его независимым образом. Например, в предыдущем разделе для вывода формулы (14) мы воспользовалнсь производящей функцией. После того как данное равенство получено, уже не составляет труда доказать его по индукции и можно даже не упоминать, что оно было найдено с помощью производящей функции. Более того, можно показать, что большинство операций (еслн не все), выполняемых над производящими функциями, можно строго обосновать, не затрагивая вопроса о сходимости ряда. Например, см. работу Е. Т. Вец, Тгапк Атег. МагЬ.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
