Об упражнении, появившемся в томе TAOCP "Заметки об упражнениях" - PullRequest
Новая
       19

Об упражнении, появившемся в томе TAOCP "Заметки об упражнениях"

7 голосов
/ 05 октября 2009

В TAOCP, том 1, в разделе «Примечания к упражнениям», есть вопрос, который выглядит примерно так:

"Докажите, что 13 ^ 3 = 2197. Обобщите ваш ответ. (Это ужасная проблема, которую автор пытался избежать)."

Вопросы:

  1. Как бы вы могли доказать это? (Прямое умножение является одним из способов, другим способом может быть использование формулы (a + b) ^ 3). Требует ли решение использования какого-либо метода, который позволит нам сделать какое-то обобщение?

  2. Какое здесь обобщение?

  3. Почему это ужасная проблема?

  4. Какие еще похожие ужасные проблемы вам известны?

Ценю любые ответы.

P.S. Я извиняюсь, если из вышеизложенного изложения проблемы выглядело, как домашнее задание, но это не так. Попросите людей не отмечать это как домашнее задание, чтобы больше людей могли дать ответы.

Ответы [ 3 ]

3 голосов
/ 05 октября 2009

Я предполагаю, что он намекает на то, чтобы доказать это, начиная с аксиом Пеано . Затем строит целые числа и продолжает формально показывать, что 13 ^ 3 = 2197 является естественным логическим выводом, вытекающим из определения возведения в степень.

Мы можем обобщить, чтобы показать, что для заданных a и b существует некоторое целое число c, то есть a ^ b.

Это ужасная проблема, потому что большинству людей она неинтересна.

Подобные проблемы можно найти в курсе по анализу (наряду с некоторыми гораздо более интересными).

1 голос
/ 08 января 2013

Я изначально считал это следующим образом:
n 3 = n * n * n
log n (n 3 ) = log n (n * n * n)
log n (n 3 ) = log n (n) + log n (n) + log n (п)
3 = 1 + 1 + 1
3 = 3

Это кажется довольно круглым при использовании логарифмических тождеств, но, учитывая то, где я нахожусь в моем исследовании алгоритмов, это было странно утешительно.

0 голосов
/ 30 марта 2014

Застрял в том же упражнении и «решил» его так: a ^ b = mult (i = 1 до b) a

Подумав немного, я пришел к выводу, что это первичная факторизация (и 13, и 3 простые). Посмотрите на небольшую теорему Ферма.

(Я знаю, это старая ветка, но, может быть, это поможет кому-то, кто тоже ищет ответ на это упражнение.)

...