Д. Кнут - Искусство программирования том 2 (3-е издание) - 2001 (Часть 2) (1119454), страница 39
Текст из файла (страница 39)
[М49] Справедливо ли и(п) < 2ц"1 "1«1 дзя всех натуральных чисел и? (Если справедливо, то получим нижнюю границу 1(2" — 1) > и — 1+ [!Зп]; см. (17) н (49).) 30. [80] В цепочке со слеясеннем н емчнтаннем вместо правила (2) имеется правило а, = а«ш аю Воображаемый компьютер, описанный в тексте раздела, оснащается новой операцией — 599, (На практике зто соответствует тому, что при вычислении ее используются и умножение, и деление.) Найдите такую цепочну для некоторого и, имеющую менее 1(п) шагов. 31.
[М45] (Д. Г. Лехмер (П. Н, 1л1ипег).) Исследуйте залачу минимизации «9+ (г — 9) в аддитивиой цепочке (1), где 9 — число простых шагсе, в которых а, = а; «+ 1, при данном малом патожительном весе с. (Эта задача ближе к реальности для многих вычислений х", если умножение иа г проще, чем общее умножение; см. приложения в разделе 4.б,2.) 32. [МУО] (Э. Ч, Яо (А. С.
тао), Ф. Ф. Яо (Р. Р. гас) и Р. Л. Грэхем (Н, 1. Стейшн).) Назначим "'цену" о а«для каждого шага а, = о + а«аддитивной цепочки (1). Покажите, что бинарный метод "слева направо" приводит к цепочне минимальной общей стоимости для всех натуральных и. ЗЗ. [15] Сколько алдитивиых цепочек длиной 9 имеет (52) в качестве приведенного ориентироваяиого графа? 34. [М58] Бинарная аддитивная цепочка для и = 2'«+... + 2", когда ее » е«> О, представляет собой 1, 2, 2««-«« 2««-«« + 1 2««-«э + 2«« - г 2««- « + 2«« -«« + 1 и Это соответствуег методу "$ и Х", описанному в начале этого раздела, в то время как алгоритм А соответствует аддитивной цепочке, полученной посредством сортировки двух последовательностей — (1, 2, 4,..., 2'«) и (2"-' + 2", 2"-«+ 2*'-' + 2",..., и) — в порядке возрастания.
Докажите или опровергните следующее: каждая из этих аддитивиых цепочек дувльиа по отношению к другой. 36. [М27] Как много адаптивных цепочек без шагов, которые ие используются, эквивалентны каждой из вддитивиых цепочек, обсуждавшихся в упр. 34, если ес > е«+ 1? ° 39. [35[ (Э. Г. Штраус(Е, С. Всгане).) Найдитеспособвычисленняобобщеиногомоненсма хг'кэт... я" за не более чем 2Л(шах(пм пэ,...,и )) + 2 — т — 1 операций умножения. * В оригинале — «ЬаЬу эсер«н «с1ове эсер«соответственно. — Прим.
нерее. 37. [НМЯ0] (Э. Ч. Яо.) Пусть 1(пп,,,, и ) — длина наикратчайшей адаптивной цепочка, которая содержит т чисел п1 « .. и . Докажите, чта Цпп.,.,п, ) < Л(п ) + тЛ(п )/ЛЛ(п )+О(Л(т~ )ЛЛЛ(п )/ЛЛ(п ) ), тем самым обобщая (25), 38. [М47] Чему равно асимптотическое значение 1(1,4,9,..., т~) — т при т -+ аа в обозначениях из упр. 37? > 39. [МЯ3] (Х. Оливос (1.
Ойуав), 1979.) Пусть 1([вы из,...,и ]) — минимальное количества умножений, требующихся для вычисления маиаиома х"' х"~... х,"„в смысле упр. 36, где каждое и; — натуральное. Докажите, чта зта задача эквивалентна задаче из упр. 37, показав, чта 1([п,, пз,,п,„]) = 1(вы им...,и ) + т — 1. [Указанию Обобщите ориентированный граф, построив рассмотренный граф с более чем одной исходной вершиной.] ° 40. [МЯ1] (Х. Оливос.) Обобщая метод множителя н теорему Е, докажите, что 1(т1т + . + т~т) < ((тп..., т,) + 1(пы, п~) + 1 — 1, гле 1(пп..., т) определено в упр, 37. 41.
[М40] (П. Дании (Р. Пщупеу), Б. Леон (В. 1еавй) и Р. Сети (К. Бе0и).) Пусть С— связный граф с и вершинами (1,..., и) и т ребрами, гле ребра объединяют нз с аз лля 1 < у < т, Докажите, чта1(1,2,...,24",24"'+2""'+1,,2"" +2"" +1) = Ап+т+й лля всех достаточна больших А, гле й — минимальное число вершин в накрытии вершин лля О (т. е. множество, содержащее либо и;, либо аз для 1 < У < т). 42. [М30] Справедлива ли 1(2" — 1) < и — 1+1(п) для всех катуральных и? Всегда ли выполняется равенство? Выполняется ля 1(п) ж 1а(п)? 4.б.4. Вычисление полнноыов Так как нам известен эффективный метод вычисления полинома специального ви- да х", рассмотрим общую задачу вычисления полинома и-й степени и(х) = и„т" + и„1х" ' + ° ° + и1х+ иа, па Ф О, (1) для определенных значений х.
Такая задача часто возникает на практике. Затем сконцентрируем внимание на минимизации числа операций, требуемых для вычисления полиномов на компьютере, в идеальном случае предполагая, что все арифмш'ические операции точны. Чаще всего полиномы вычисляются с использованием арифметики с плавающей точкой, которая не является точной, и различные схемы для оценки обычно дают различные ответы.
Численный анализ достигаемой точности зависит от коэффициентов рассматриваемого полинома, но в данной книге он не проводится; читателю следует внимательно исследовать точность любых вычислений, полученных с использованием арифметики с плавающей точкой. В большинстве случаев будут описаны методы, вполне удовлетворительные с точки зрения численного анализа, но будет также рассмотрено достаточно много плохих примеров. [См. работу у1еЬЬ М(1!ег, ЯСОМР 4 (1975), 105-107, в которой приведены обзор литературы по устойчивости быстрых вычислений полинома и доказательство, что определенные виды численной устойчивости не могут быть гарантированными для некоторых семейств быстродействующих алгоритмов,) Во всем этом разделе будем считать переменную х просто числом.
Но важно помнить, что большинство рассматриваемых методов действительны также, когда переменные являются более сложными объектами, такими как числа с многократной точностью, полиномы и матрицы. В подобных случаях эффективная формула приводит даже к большему выигрышу, в особенности, когда можно уменьшать количество операций умножения.
Начинающий программист, скорее всего, вычислит полипом (1) способом, который прямо соответствует его традиционному виду: сначала вычислит и„х", затем— и„1х" ', ..., и1х и наконец суммирует все члены (1). Но даже если использовать эффективные методы из раздела 4.6.3 для вычисления степеней х этими методами, результирующее вычисление излишне медленно, кроме случая, когда почти все коэффициенты иь равны нулю. Если ие все коэффициенты равны нулю, то очевидной альтернативой должно быть вычисление (1) справа налево посредством вычисления значений х" и иьх~ + -. + ие для Й = 1, ..., и. Такой процесс включает 2п — 1 операций умножения и и операций сложения и, возможно, потребует дополнительных команд для сохранения промежуточных результатов в памяти и их извлечения из памяти.
Правило Горнера. Одной из первых забот начинающего программиста обычно является изучение элегантного способа перестройки этих вычислений следующим образом: и(х) = (,(и„х+ и„1)х+ .. )х+ив (2) (иачать с и„, умножить на х, добавить и„м умножить на, х,, умножить иа х, добавить ие). Эту модель вычисления обычно называют "правило Горнера" (либо "схема Горнера".— Прим. ред.). Мы уже знаем, как его использовать в связи с заменой основания системы счисления в разделе 4,4. Полный процесс требует и умножений и и сложений минус одно сложение для каждого нулевого коэффициента. Кроме того, нет необходимости запоминать промежуточные результаты, так как каждая величина, появляющаяся в процессе вычислений, немедленно используется после ее получения.
В. Дж. Горнер (Ж. С. Ногпег) предложил зто правило в начале 19 века (Рп()оворЫса1 2гапяасг1опв, Воуа1 Яос(егу о( Ьопбоп 109 (1819), 308-3351 в связи с процедурой вычисления корней полииома. Известность последнего метода (см. 3. 1. Соо!Ы8е, Майешабся оГ Сгеаг Ата1еигя (Ох(огб, 1949), глава 15) объясняет то обстоятельство, что имя Горнера связывается с формулой (2), но в действительности Исаак Ньютон использовал такую же идею более чем на Г50 лет раньше.
Например, в общеизвестной работе Пе Апа1уя( рег Юоиабопея Хпбп1свэ, написанной в 1669 году, Ньютон записал у -4 х у:+ 5 х у; — 12 х у:+17 для полииома у4-4уз+5уз -12у+17, что поясняет, почему позже метод приобрел известность как метод Ньютона нахождения корня. Тут ясно видно идею формулы (2), так как он часто обозначал группирование горизонтальными линиями и двоеточием, а ие круглыми скобками. Ньютон использовал эту идею на протяжении нескольких лет в неопубликованных заметках. (См, Тйе Майетаг1са1 Рарегз оГ 1заас №и 1оп, е61геб Ьу П. Т. ЖЫгееЫе, 1 (1967), 490, 531; 2 (1968), 222.) Независимо метод, эквивалентный правилу Горнера, фактически использовался в 13 веке китайцем Чин Чи Шао (СЫ1п СЫи 8пао) [см. У. М1капп', Тйе Пете)артель ог'Майеша11св т Сйп1а аш1 Ларка (1913), 73-771, Предложим несколько обобщений правила Гориера.
Сначала рассмотрим вычисление и(г), когда х — комплексное число, в то время как коэффициенты иь— действительные числа. В частности, когда г = ем = сову+ лейлу, псин»лосс и(г) является, по сусцеству, двумя рядами Фурье (на самом деле--сумлсами. — Прим. род.) (ио+иссоэу+ ° -+и„соопд) + с(и»в»с»у+ -+и»ялнд).
Комплексное сложение и умножение, очевидно, может быть сведено к последона- тельностн обычных операций над вещественными числами. 1 сложения 2 сложений 2 умножений 4 умножений, 2 сложений 3 умножений, 5 сложений требует требует требует требует вещественное + комплексное комплексное + комплексное вещественное х комплексное комплексное х комплексное (См, упр. 41.
Вычитание рассматривается здесь как эквивалент сложения.) Следовательно, правило Горнера (2) использует каждые 4н — 2 умножений и Зп — 2 сложений или Зн — 1 умножений и бп — 5 сложений для вычисления и(г), когда г = х + су — комплексное число. В действительности без 2п — 4 шсожений можно обойтись, так как каждый раз выполняется умножение на то же число г. Предлагаем альтернативную процедуру вычисления и(х + су): г=х+х, г=г +у; ,г 1<1 <н. (3) Ьс =и -с, ас =и„, а» Ь» с + га» сс Ь/ и»» га» и(х) = ( ° ° (иг(»/г1х + иг1»/г1-г)х + ) + исс + (( ° (и»(»/г1 — сх " иг(»/гр-г)х + ' )х +и") х' г г г В правиле второго порядка используются и+ 1 умножение и и сложений (слс.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
