ГНОМОН. От фараонов до фракталов - Газале М.
ISBN 5-93972-171-0
Скачать (прямая ссылка):
(n2 + п + I)3 = п6 + 3 пъ + 6п4 + 7 п3 + 6n2 + Зп + 1,
и гамильтонов путь на нем. Для нахождения коэффициентов при nJ в разложении триадического числа (п2 + п + 1)х треугольник Паскаля уже не годится; соответствующий триадическому случаю треугольник показан на рис. 1.5с. Отметим, что сумма чисел, расположенных на любой линии j, равна 3J, т. е. количеству вершин соответствующего триадического гиперкуба, а любое целое число в верхней последовательности равно сумме трех предыдущих чисел. Следуя вершинам гамильтонова пути, можно составить код, подобный коду Грея, как показано на рис. 1.9. Если gi — знак ранга г в числе кода Грея, a U — соответствующий троичный знак, то gi задается выражением = (ti — ti+i mod 3). И наоборот, ti равен сумме gi и всех расположенных слева от него цифр по модулю 3. На рис. 1.9 показана также конструкция кодирующего диска с разрешением 40°. Сочетания белых, серых и черных областей отражают любые перестановки цифр 0, 1 и 2.
42
Глава I
Десятичный Серый Троичный
0 ООО 0 0 0
1 0 0 1 0 0 1
2 002 002
3 0 1 2 0 1 0
4 0 1 0 0 1 1
5 0 1 1 0 1 2
6 0 2 1 0 2 0
7 0 2 2 0 2 1
8 0 2 0 0 2 2
9 1 2 0 1 0 0
10 1 2 1 1 0 1
11 1 2 2 1 0 2
12 1 0 2 1 1 0
13 1 0 0 1 1 1
14 1 0 1 1 1 2
15 1 1 1 1 2 0
16 1 1 2 1 2 1
17 1 1 0 1 2 2
18 2 1 0 2 0 0
19 2 1 1 2 0 1
20 2 1 2 2 0 2
21 2 2 2 2 1 0
22 2 2 0 2 1 1
23 2 2 1 2 1 2
24 2 0 1 2 2 0
25 2 0 2 2 2 1
26 2 0 0 2 2 2
Рис. 1.9. Троичный (триадический) код Грея и кодирующий диск.
Глава II
Непрерывные дроби
Непрерывные дроби принадлежат сегодня к области «ненужной математики», т. е. математики, которая считается слишком сложной для средней школы, но чересчур элементарной для колледжа.
(Петр Бекман)1
Настоящая глава является ключевой для понимания последующих глав, посвященных итерационным процессам (таким как построение лестничных, или ступенчатых, схем), последовательностям Фибоначчи, витым фигурам и спиралям. Мы обсудим здесь особый род дробей, широко применяемый для вычисления алгебраических иррациональных чисел (таких как иррациональные квадратные корни), а также некоторых трансцендентных иррациональных чисел (например, е и 7г). Считается, что непрерывные (или цепные) дроби были впервые введены Уильямом Брункером (1620-1684), первым президентом Британского Королевского Общества, обнаружившим изящное выражение для вычисления трансцендентного числа 7г, которое мы вскоре рассмотрим. Итерационная природа непрерывных дробей видна невооруженным глазом. Позиционное представление квадратичных иррациональных чисел относительно периодического основания (десятичного или иного) само по себе периодическим не является, однако соответствующая непрерывная дробь периодична и может, как следствие, быть определена через конечное число элементов. Аналогичным образом, непрерывные дроби, представляющие числа е и 7г, следуют простым, пусть и не периодическим, схемам. Эти схемы исчерпывающе представлены в эйлеровых непрерывных дробях для е. Витые фигуры являются предшественниками спиралей и великолепными геометрическими метафорами для непрерывных дробей, что и объясняет центральную роль последних в последующих главах. В качестве вступления к разговору о непрерывных дробях рассмотрим один знаменитый алгоритм, доставшийся нам в наследство от древних греков.
ХА History of 7г (New York: St. Martin’s Press, 1971), p. 129.
44
Глава II
Алгоритм Евклида
Этот алгоритм приведен в седьмой книге «Начал» Евклида и предназначен для вычисления наибольшего общего делителя любых двух целых чисел. Хотя некоторые историки приписывают его авторство великому Евдоксу, алгоритм этот принято называть евклидовым.
Рассмотрим целые числа а и Ь, где b > 0. Несложно установить, что существует одна и только одна пара целых чисел q, г, удовлетворяющая следующим условиям:
Пусть d — целое число, на которое без остатка делится и число а, и число Ъ. Запишем
В вышеприведенных выражениях а и j3q — целые числа. Следовательно, r/d также должно быть целым числом, т. е. если d является делителем для а и Ь, то оно является делителем и для г, остатка от деления а на Ь. И наоборот, очевидно, что любой общий делитель чисел b иг является также делителем и для числа а. Множество общих делителей чисел а и Ь, таким образом, тождественно множеству общих делителей чисел b и г. Самое большое число этого множества называется наибольшим общим делителем (НОД) чисел а и Ь, оно же является НОД и для чисел b и г. Это записывается как
