Д. Кнут - Искусство программирования том 2 (3-е издание) - 2001 (Часть 2) (1119454), страница 76
Текст из файла (страница 76)
27 (1992), 169-172. 19. Если т > и или т < 1, то найдем такое а 6 Р, что т ж а (по модулю Ь); искомое представление будет представлением т' = (т — а)/6, за которым следует а. Заметим, что т > а принадлежит иитераалу 1 < н!' < т; т < 1 принадлежит т < гл' < и, позтому алгоритм конт«ен. ]При Ь = 2 решения иет. Представление будет единстаенным тогда и только тогда, когда 0 6 Р; неоднозначное представление появится, например, когда Р = (-3, -1,7), Ь т 3, так как (а)з = (3773а)л.
Нетрудно показать, что при 6 > 3 имеется точно 2л решающих множеств Р, в которых ]а] < Ь для всех а 6 Р. Далее, множество Р = (О, 1, 2 — ««Ь", 3 — «зЬ",, Ь вЂ” 2 — «л-«Ь", 6 — 1 — 6" ] порождает единственное представление для всех Ь > 3 и и > 1„где любое «, есть О или 1.
См. )лгос, 1ЕЕЕ Яушр. Сотр. Ап«Ь. 4 (1978), 1-9; ХАСМ 29 (1982), 1131-1143.] 20. (а) 0,111... = 1.888 ... = 18.««! ... = 18!.еьл .. = = 18«ел«л!, „! ... имеет девять сс! ! л«2 , „ !23«ле гг! представлений. (Ь) Р— дробная часть,ала! ..., .которая всегда принимает значения между -1/9 и +71/9. Пусть х имеет десять или более Р— десятичных представлений. Тогда для достаточно большого Ь число 10"'х имеет десять представлений, отличающихся цифрами, которые расположены левее десятичной точки; 10 х = и! + /! = = псе + /со, где любое /! есть Р— дробная часть, Ввиду единственности предстааления целых чисел числа н, различны, скажем, и! « пле! следовательно, !!!о — и! > 9, но зто число принадлежит интервалу /! — /ло > 9 > 71/9 — ( — 1/9).
Таким образом, мы пришли к протиаоречию, что и доказывает справедливость утверждения. (с) «Тюбое число вида О.а! а!..., где любое а есть — 1 нли 8, раино 1.а',а! ... при а' = а! + 9 (более того, оно имеет ещ«6 представлений 18.а!'а!... и т. д.). 21. Такое представление люжно получить, используя метод, аналогичный предложенному в тексте раздела для перевода в уравновешенную троичную систему счисления. В отличие от систем, рассмотренных в упр. 20, нуль может быть представлен бесчисленным колпчеством способов, которые получаются а результате умножения на степень десЯть «Уммы —.' + 2 л>с(-41.') 10 " (илн из такого же пРедставлении, но с противоположными знаками цифр).
Представлениями единицы служат 1.-' — -', -' + -'', 5 — 3« — -, 5 — 4« + —., 50 — 45 — 3- — -, 50 — 45 — 4- + -* и др., где Л! ! ! ! ! ! ° ! ! ' ! л ! ! ! 2 ! (х4$)(10 '+10 +. ). ]АММ 57 (1950), 90 — 93] 22. Полагая, что имеется приближение Ь„...Ь,Ье с погрепсностью Л.'ль Ь«10" — х > 10 ', где С > О, покажем, как уменьшить ошибку примерно в 10 ' раз. (Процесс может быть начат с любого приближения, для которого 2 „", Ь«10 > х; далее через конечное количество нтерапнй ошибка станет меньше «.) Просто выбираем т > и настолько большим, чтобы десятичное представление числа -10 а имело единицу в позиции 10 ' и не имело единица позициях 10 '»', 10 '+~, ..., 10". Тогда 10~а+(некоторая подходящая сумма степеней 10 между 10 и 10") + 2 " 6»10» ш 2 " 6»10 — 10 '.
23. Пусть множество Ь = (2»>, а»Ь " [ а» б Р) замкнуто (как в упр, 18), следовательно, оио измеримо. Так как ЬЯ = (,),,(а + Я), имеем Ьд(Я) = р(ЬЯ) < х„,ер 1»(а + Я) = 2, р д(Я) = ьи(Я), и поэтому должно быть справедливо р((а+ Я) г1 (а'+ Я)) = О, если а 14 а' б Р. Тогда множество Т вЂ” множество меры иулгч если 0 б 17, так как множество Т явлвется объединением множеств вида Ь (и + ((а + Я) с (а' + Я))), а зе а', каждое из которых — меры нуль. С другой стороны, как отмечал К. А, Брэкк (К. А.
Втэке). каждое вещественное число (в системе счисления, рассмотренной в упр, 21) имеет бесконечное количество представлений. [Множество Т ие может быть пустым, поэтому вещественные числа не могут быть записаны как счетное объединение замкнутых, разомкнутых и граничных множеств (см. АММ 84 (1977), 827-828; более детальный анализ приводится в работе Регйолзей, АММ 97 (1990), 408-411). Если множество 17 состоит из элементов, меньших Ь, то множество представлений чисел по основанию Ь и цифры из множества В имеют меру нуль.
Есэи множество 17 состоит из элементов, больших, чем Ь, и из вещественных чисел, то оно имеет бесконечную меру.) 24. (2а 10» + а' [ 0 < а < 5,0 < а' < 2) или (5а' 10 + а [ 0 < а < 5,0 < а' < 2) для Ь > О. [Р. Л. Грэхэм (11. Е. Огайат) показал, что не существует другого множества целых цифр, удовлетворяющих этим свойствам.
Эндрю Одлыжко (Апбгеи Огйузйо) доказал, что ограничение в рассмотрении множеств целых чисел излишне в толь смысле, что если два наименьших элемента множества 17 являются 0 и 1, то все цифры должшя быть целыми. Доказательства. Пусть Я = (2 св а»Ь [ а» б 17) — множество "дробных частей" н пусть Х = ((а„... ав)ь [ а» б 17) — множество "полных чисел". Тогда [О .. со) = Ц,ех(х+ Я) и (х+Я) О(х +Я) при х ~ х' б Х имеет льеру нуль. Получим (О .. 1) С Я и докажем индукцией по гп, что (т..т+1) С х, + Я для некоторого х б Х. Пусть х 6 Х таково, что для любого е > Омара (т..
т+в) О(х,„+Я) положительна, Тогда х < т их, должно быть целым независимо от величины перекрытия множеством х1„1+Я множества х +Я, Если х > О, то из того, что (гл — х ., т -х + 1) ОЯ имеет положительную мерл, по индукции следует, что эта мера равна 1 и (т ..т+ 1) Я х + Я, так кзк множество Я замкнутое. При х =.0 и (т .. т + 1) Я Я мы должны получить т < х' < т + 1 для любого х' б Х, гдв (тп .. г' ) С Я; ио тогда 1+ Я перекрывает х' + Я.
(См. Ргос. Е,оп»)ол МаГЬ. Яос. (3) 18 (1978), 581-595.)) При.«ечаиие. Если снять ограничение 0 6 )у, возник«сил много других достаточно интересных ситуаций, в частности (1,2,3,4,5,6,7,8,9,10), (1,2,3,4,5,51,52,53,54,55) и (2,3,4,5,6,52,53,54,55,56). Если же допустить наличие отрицательных цифр, то при помощи метода, описанного в упр. 19, можно найти много других решений задачи, а также множества, содержащие иеобычиыв числа наподобие ( — 1, О, 1, 2, 3, 4, 5, 6, 7, 18), которые ие удовлетворяют оговореииылл условиям, Появляются предпосылки для поиска изящных решений для множеств с отрицательными цифралш.
25. Положительное число, представление которого по основанию Ь содержит пл последовательных цифр (Ь вЂ” 1), расположенных справа от разделяющей точки, должно иметь вид с/Ь" + (6 — д)/Ь"е«, где с и и — неотрицательные целые числа и 0 < 9 < 1, Поэтому, если и/и имеет такой вид, значит, равенство 6 чьи = 6 си+Ь и-дивыполнено.
Следовательно, ди есть целое число, кратное Ь . Однако 0 < ди < и < 6«. (При 0 < а < 6 — 1 могут встречаться произвольно длинные ряды цифр ааааа, например, в представлении чисел а/(Ь вЂ” 1).) 26. Доказательство достаточности получается иепосредственныл» обобщением на случай основания Ь обычного доказательства. Доказательство необходимости разбивается на две части. Если для некоторого и число 9 +1 больше 2 б„с»6», то для малых е число 6,+» — г не допускает такого представления. Если,9 +» <»ит»<„с»д» для всех и, но равенство выполняется не всегда, то можно показать, что для некоторого х существуют два представления (см.
ТгалзасВопв оГ гйе ГЬоуа1 Яос1егу оГ Сапа»(а, вегнн 1П, 46 (1852), 45-55). 27. Доказательство выполняется индукцней по и. Если и четно, то должно быть ее > О и искомый результат получается по индукции, так как п1'2 имеет единственное представление такого типа. Если и нечетно, то должно быть ее = О и задача сводится к представлению числа -(и-1)/2. Если зто последнее равно либо О„либо 1, то, очевидно, существует только один способ решения задачи. В противном случае по индукции доказывается, что число имеет единственное представление.
[Отсюда следует, что любое положительное целое число имеет ровно дев таких представления с убывающим порядком ео > е~ > . > еп одно — с.четным ц другое— с нечетным й[ 28. Доказательство может быть выполнено, как и в упр. 27. Обратите внимание, что а ч- Ь» представляет собой произведение 1+ 1 и некоторого комплексного целого числа тогда и только тогда, когда а+ Ь четное.
Такое представление неявно связано с "кривой дракона", описанной в ответе к упр. 18. 29. Достаточно доказать, что любую совокупность [Т»,Т„Тм, ..), удовлетворяющую свойству В, можно получить с помощью "стягивания" некоторой совокупности (Я», Яц Ям где Яе = (О, 1,..., Ь вЂ” 1), н что все элементы множеств Яц Я»,... кратны 6. ПРи доказательстве последнего УтвеРждениЯ можно считать, что 1 б То и сУществУет наименьший элемент Ь > 1, такой, что Ь Ф Те.
Инлукцией по и докажем, что если пЬ ф То, то н6+ 1, пЬ+ 2,..., гй+ Ь вЂ” 1 ие принадлежат никакому из лщожеств Т: если же пЬ б Те, то же самое верно и для чисел цЬ+ 1,..., иЬ+ Ь вЂ” 1. Тогда искомой совокупностью будет Я! = (гй [ пЬ б То), 8» = Тц Яз = Т» и и д,, откуда следует результат. Если пЬ ф То, то пЬ = 1о+ 1» +, где Гм Гм ... кратны 6. Следовательно, го < пЬ кратно Ь, По индукции (Фе+ 6) + Ф» +1» + ° есть представление числа пЬ+ 6 при О < 6 < Ь, поэтому пЬ+ Ь ф Тз для любого у. Если нЬ б Те и О < lс < Ь, то Ге+1»+.. Равенство 11 = гй+ 6 не может выполняться для у > 1, иначе пЬ+Ь имело бы два представления (6-6)+ +(пЬ+6)+ ° ы (гй)+ +6+ . ° . По индукции Го шог( Ь = Ь. Из представления пЬ ж (Го — Ь) + 1» + следует Ге — — пЬ+ 6.
[См. Меин Аг»1пеГ тоог И'»з)гвш)е (3) 4 (1956), 15 — 17. Конечный результат получен Р. А. Мак-Мехоном (Р. А. ЬбасМайоп), Сош61пасогу Апа(уз)з 1 (1915), 217-223,[ ЗО. (а) Пусть А, — множество чисел и, в представлении которых не содержится Ьг", тогда согласно свойству единственности и б А, тогда и только тогда, когда и + Ь, ф А;. Следовательно, и б А, тогда н только тогда, когда и + 26»6» б А. Г1 А». Пусть т— количество целых чисел и б А, ОА», таких, что О < и < 2ЬГЬ», Значит, в том же интервале найдется ровно т целых чисел, принадлежащих Ам но не принадлежащих А», и ровно гп, не принадлежащих ни А„ни А»; поэтому 4п» = 26ГЬ», Следовательно, Ьг и Ь» не могут быть нечетными одновременно. Однако одно из ннх, разумеется, нечетно, так как нечетные числа допускают представление в бинарном базисе.
(Ь) Согласно п. (а) можно так перенумеровать числа 6, чтобы 6о было нечетным, а Ьм 6», ...— четными. Тогда ряд 1Ьм ~6», °, должен также образовывать базис и эту процедуру можно повторить. (с) Если имеется бинарный базис, то для представления числа ш2" (для больших п) при достаточно больших Й необходимо получить и положительные, и отрицательные гГ». Доказательство обратного утверждения приводится в следующем алгоритме. 81.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
