Д. Кнут - Искусство программирования том 4 выпуск 4 - 2007 (1119377), страница 34
Текст из файла (страница 34)
Таким образом количество существенно различных деревьев, которые требуется рассмотреть, снижается (а) до 2 747275; (Ь) до 6834 708; (с) до 741167401. Арифметика с плавающей точкой для решения данной задачи ненадежна, но можно использовать подпрограммы для работы с рациональными числами из раздела 4.5.1; при этом никогда не приходится работать с целыми числами, превышающими по абсолютному значению 10э. 123.
(а) 2 284, но 2 284 = (1 + 2 х 3) х (4 + 5 х 67) — 89; (Ъ) 6964, но 6 964 = (1/.2) х х 34+ 5+ 6789: (с) 14786, но 14786 = — 1+ 2 х ( 3+4+5) х (6+ 789). [Если мы допустим использование знака "минус" слева от выражения, как это делал Дьюдеии, то получим 1361, 2758 и 85054 дополнительных решений упражнения 122 (а), (Ь) и (с), включая 19 более длинных выражений в случае (а), таких, как — (1 — 2) х х ((3 + 4) х (5 — (6 — 7) х 8) + 9), При таком расширении соглашений наименьшими непредставимыми числами нвляются: (а) 3802; (Ъ) 8312; (с) 17 722.] Общее количество представимых чисел (положительных, отрицательных и нуля) равно: (а) 27 666; (Ь) 136607; (с) 200765.
124. Числа Хортона-Страхлера возникли при изучении течения рек в работях К.Е. Ног~оп, ВиД. Свой бос. Атег., 56 (1945), 275 370; А.йв 81гаЫег, ВиИ. 6ео1. Яос. Ашег., 63 (1952), 1117-1142. Многие идеи по рисованию деревьев можно найти в классической статье 'йепиос, Еугойеэ, Запеу апб Апрж, Сошрисег Стар)исэ, 23, 3 (Зп!у 1989), 31-40.
сделано для эиълкиИапа1а.ого ОТВЕТЫ К УПРАЖНЕНИЯМ 139 7.2.1 Раздел 7.2.1.7 1. Вероятно, оно связано с гексаграммой 21 (ивыполнение вычислений" (псгппсЬ)пйп)) (йй); однако древние комментаторы в большей степени связывают эту гексаграмму с обеспечением законности, чем со взаимодействием электронов'и. 2. (а) Пусть первый нуклеотид в кодоне (Т, С, А, С) будет представлен соответственно элементами (ыь ь,ь1 1 ': ); второй нуклеотид аналогично представлен элементами (7-4 ее гт е ,'), а третий — (; ~ з") пз р":).
Наложим друг на друга все три представления. Таким образом, например, гексаграмма 34 представляет собой $3 = 1'.*+:.: + Н и тем самым является кодоном ТТС, который отображается на аминокислоту Р. При использовании такого соответствия гексаграммы с 34 по 54 включительно отображаются соответственно на значения (Р, С, Л, Я,ЪМ, В, $, —, Р, У, К, А, 7, Т, Ж, О, Ы, В, Ъ'„ Е, С). Кроме того, имеется три гексаграммы, отображающиеся на '-' — это гексаграммы 1, 9 и 41, а именно И, ва и И, которые в СЬ1п8 имеют названия озответственно "созидание", "укрощение" и "устранение излишнегез"; все они на удивление подходят для обозначения завершения белка.
(Ь) РассмотРим (6 6,6,4,4,4,4,4д,з,з з з з з з з з з 4 4) 2.3 х 10 способов пеРестановки 64 69 элементов массива генетического кода размером 4 х 4 х 4. Ровно 2402880402175789790003993681964551328451668718750185553920000000 вз 2.4 х 106з из иих содержат, как минимум, один отрезок из последовательности 21 различного элемента. (Использование принципа включения и исключении позволяет показать, что любое мультимножество ((п~ + 1) хы..., (и„+ 1) х„) с т различными элементами и и, = 0 имеет ровно и ~ " / п — к (и+1) ( )г! — ~(п+1 — й)й!(г — й)1аа У ~ ) Тпм ° ° ., и; П<4 4 <1 П1 Ы ° 1цс ис/ таких перестановок, где и = и, + ° + и„, а ае — количество неприводимых перестановок с й элементами (упражнение 7.2.1.2 — 100).) Таким образом, только одна из каждого миллиона перестановок может быть указана корректно. Однако имеется 4)~( 6 ) = 1 244 160 способов представления кодонов так, как зто сделано в части (а), и большинство из них соответствуют различным перестановкам аминокислот (за исключением обмена представления Т и С в третьей позиции).
И действительно, эмпирически около 31% всех 64 гексаграмм дают соответствующее отображение кодонов. Таким образом, конструкции в части (а) не дает оснований подозревать авторов 1 С1ип8 в каком-либо участии в разработке генетического кода. 3* Поскольку Рзз 10 = Раз + Раз+ Гзп+ Р46+ Рзп+ Г44+ Рз, миллионной стРофой является . Ответ на второй вопРос еще пРоще: Р64 — (Р + Рз+ Гю+ Рш+ Р16+ Рзт+ Рзо) = 314159 4. Одно из двух появлений Ътйуз в строке 4 должно быть 1ТФб; это может быть простой типографской опечаткой. Аналогично, 2мТЪз в строке 8 должно иметь вид 1ейо всей видимости, автор подразумевает мце одно значение слова "сгипсыпк" — раздавливать с хрустом. — Примеч. пер. сделано для тдгбрърлн$анаса.ого 140 ОТВЕТИ К УПРАЖНЕНИЯМ 32!УР. Однако Донноло несет ответственность за шесть случаев в строках 3 и 4, когда крайние справа буквы '!3 появляются дважды, в то время как перестановки с крайними справа буквами '13 отсутствуют.
5. Последняя перестановка должна быть, а не Ш, %%. 6. Б списке Мерсенна и-е значение т„соответствует и! только для 1 < и < 13 и 15 < и < 38. Мерсенн знал, что 14'. = 87178291200 ф ты = 8778291200, поскольку вставил '1' в личную копию книги (в настоящее время являющейся собственностью Б!Ы!оЗЬес!пе Маг!опа(е; ее факсимиле было опубликовано в 1975 году).
Однако остальные ошибки в его таблице не просто типографские, поскольку они распространяются на последующие значения, за исключением случая тзв, а именно: тзв = 39!+10 — 10'в; твв = 40тизв; тм = 41гию — 4 10зв — 14 10"; т„= ит„ для и =42,43,44,46,47,48,49,55,60и62;твв = 50твэ+10вв;ты = 51 50 твв.
При вычислении тзв = 9. 45 ты — 10вв+ 10зэ он, похоже, хотел УпРостить вычислении, поскольку легче выполнить умножения на 5 и 9, чем на 45. Однако он ошибся и выполнил умножение на 9 двалсдм. Большинство ошибок указывают на ненадежность метода умножения, который может зависеть от того, какие счеты использованы для вычислений: твз = 52гищ + 5 10в' — 2 10" + 10зв; твз = 53тзз — 4 10зв; тзв = = 54твз+10'в; твт = 57гизв+10зз+10зв; твз = 58тзт+10вт — 10зз+10зз+11.10зв; твэ = 59гпьв + 10вв + 10вэ — 10зв; изв1 = 61п1вв — 5 ' 10в', твз = 63твз + 10вз — 10тв; твв = 64твз+ 3, 10в1+ 10вт+ 2, 10зв 2, 10зз 10зз Оставшийся случай, тьв ж 10.912твв, непостижим. Это значенпе гяббтвв (шос(п!о 10'~), но эти цифры тоже ничего не говорят ни уму, ни сердцу.
Примечание: Атанасиус Кирхер (А1Ьапав!пз КпсЬег) явно копировал результаты Мерсенна, когда твбулировал и! для 1 < и < 50 на с. 157 своей книги Агв Майна Бс)енсй (1669), поскольку он повторил все ошибки Мерсенна. Однако Кирхер использовал значения 10гиы, твз,/10 и 10гивэ вместо ты, твв и твэ! вероятно, он пытался сделать последовательность растущей более равномерно. Неясно, кто первым вычислил точное значение 39!; в упражненип 1,2.5-4 описана история числа 1000!. 7. Базовыми перестановками являются 12345, 13254, 14523, 15432, 12453, 14235, 15324, 13542, 12534, И243, 13425, 14352. Но после этого мы находим, что все 60 из четных перестановок одновременно и живы и мертвы, поскачьку (9) отличается от (8) на четную перестановку. (Более того, если бы можно было как-то исправить ситуацию прн и = 5, то прн и = 6 половина живых перестановок стали бы нечетными.) 8.
Например, можно заменить (9) на а„аз .. а„1азаы а1ав... а„азат,..., а„|аз... а„-за1а„, где переходы осуществляются путем обмена местами двух конечных элементов слева и справа и циклического сдвига последовательности влево на один элемент. Такая модификация работает правильно, поскольку все перестановки имеют корректную четность, а живые и мертвые перестановки содержат а1 во всех возможных позициях (по сути, мы получили дуальную таблицу Симса (8!шв) для чередующейся группы, как в 7.2.1.2-(32); однако вместо (О, 1,..., и — 1) наши элементы нменованы как (и,и — 1,,1)).
сделано для юълкиИапаса.ого ОТВЕТЫ К УПРАЖНЕНИЯМ 141 Более простой способ генерации перестановок с корректными знаками был опубликован Э. Безу (Е, Вевопг) [Мешо1гев АсЫ. Йоуа(е !4ев Бс)епсев (Рапв, 1764), 292[: каждая перестановка ха1... а„~ множества (1,...,и — 1) дает и других, ха!... ... а„1а„~ а1... ан яа„а„ 9. (,1,т,т,г,в,т,т,а,т); яЛН, ПОжаЛуй, МЫ дОЛжНЫ СыаЗатЬ (Ч,л,т,т, о,г,т ". ~, '). Иргьнсчание! для порядковых номеров в уравнениях использовалась иная система; например, 'У означало 200. Кроме того, следует заметить, что (11) на самом деле представляет перевод работы вль-Самаваля (а1-Вашаа"в1) на современный арабский. Ахмад и Рашед основывались на копии Х1Ъ" века, в которой использовалось похожее, но более старое начертание цифр: (о* ~ т т 1 Э т т л ч). Сам вль-Самаввль мог использовать еще более древнее начертание. 10.
Если все 56 вариантов равновероятны, ответ равен 56Нье 258.2! как в задаче о собирании купонов (3.3.2-8). Однако (6,30, 20) случаев имеют вероятности соответственно (1/216,1/72,1/36). Таким образом, верным будет ответ (! — (1 — '! ) (! — '! ) (! — и ) ) !! 5466, что составляет около 42% от верхней границы 216ошв. [См. Р. Р)а)о!еФ, Р. Сага, апб 1. ТЬппошег, РЬсгеге Аррас' Магй., 39 (1992), 207-229.[ 11. В таблице приведены (е) = 20 сочетаний (Ь, с, б, В, С, Р) по три; кроме того, они находятся в лексикографнческом порядке, если считать Ь < с < д < В < С < О. Буква 1 (Е ) означает "переход от нижнего регистра к верхнему".
[См, А. Воппег, Яе1ессед ЪЪЬг(гз ог" Влшоп Ыи)( (Рнпсе1оп, 1985) „596-597.[ На рисунке есть две опечатки: в начале строки 6 '!Г должно быть 'Ь', а в конце строки 18 'с' должно быть 'гГ. Строка 1 была бы более согласованной с остальными, если бы имела вид но в этой строке переключение регистра, конечно же, не требуется. 12. Умножьте цикл Пуансо на 5 (шод7). 13. Прн наличип и различных букв лучше писать только и строк. а.
аа. ааа Ь. аЬ. ааЬ. аааЬ. ЬЬ. аЬЬ. ааЬЬ. аааЬЬ Тогда присванвание весов (а, Ь) = (1,4) дает числа от 1 до 11, как в (18). (Первая строка (16) также должна быть опущена.) Аналогично: для (а, а, а, Ь, Ь, с) мы можем неявно присвоить с вес 12 и добавить дополнительную строку с, ас. пас. апас. Ьс. аЬс. ааЬс. аааЬс. ЬЬс. а66с. аа66с. аааЬЬс.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
