Золотой треугольник

Руслан Богатырев
11.09.2001
Мир ПК, #07/2001
Постоянный адрес статьи: http://www.osp.ru/pcworld/2001/07/130.htm

Занимательное программирование

Реализация треугольника Паскаля

Простейшая (и наименее эффективная) реализация треугольника Паскаля выполняется в виде рекурсивной процедуры PascalTriangle0. В ней нужно предусмотреть возврат 1 при условии (i = 0) OR (j = i), а также возврат i при (i = 1) OR (j = i-1). Эти условия определяют бедра треугольника и первые внутренние диагонали. В остальных случаях должно вычисляться выражение

x:= PascalTriangle0(i-1,j-1) + PascalTriangle0(i-1,j)

Другим вариантом реализации алгоритма может служить использование факториала для значений, не превышающих 12 (как мы уже отмечали выше, это связано с ограничением разрядной сетки). Эту реализацию разместим в процедуре с именем PascalTriangle1. Здесь при реализации факториала (но уже не в виде рекурсивной процедуры, а через импровизированный стек) мы добьемся куда лучших результатов:

stack[0] := x; stack[1] := k; x := stack[0] * stack[1]; INC(k).

Наконец мы вплотную подошли к реализации основного решения, за которое будет отвечать процедура PascalTriangle2. Обратим внимание (рис.1) на ту особенность треугольника Паскаля, что он симметричный, следовательно, вычисления необходимо делать только для левой его половины.

i = s+3; 
j = t+2.

Реализуем их через процедуру LoadPas (для преобразования индексов она использует процедуру Segment). Теперь осталось включить вызов процедуры LoadPas в инициализацию модуля (процедура On) и для вычисления элементов треугольника Паскаля написать простейшую процедуру PascalTriangle2, обеспечивающую обращение к элементам готового массива. Нам еще необходимо доделать каркас, и задача будет решена (листинг 6).

Реализация архитектуры

Теперь, когда у нас каркас с базовыми алгоритмами решения нашей задачи почти готов, можно дополнить модуль Pascaline полезными командами вычисления чисел Фибоначчи (листинг 7) и простых чисел (листинг 8). Поскольку особенность алгоритма нахождения простых чисел связана с тем, что он вычисляет сразу целый набор чисел в заданном диапазоне, то для доступа к результатам мы можем вопользоваться таким полезным приемом, как реализация механизма итератора с помощью классов. Основная его идея (впервые, пожалуй, реализованная в языке CLU) состоит в том, чтобы объединить список и процедуры доступа к нему в специальный объект. В нашем случае класс итератора обладает тремя методами: Init, First и Next. Подобная реализация (листинг 9) удобна на уровне контроллера и внесена в модуль TriangleTF.

Для проверки эффективности наших альтернативных реализаций создадим модуль TriangleTst, процедуры которого будут запускаться после обработки командной строки процедурой TriangleTF.ExecCommand. В модуле TriangleTst сформируем неоднородный список процедур (листинг 10) с альтернативными реализациями PascalTriangle и Fibonacci и, последовательно его обрабатывая, будем запускать процедуры с параметрами, полученными с помощью генератора случайных чисел. Попутно мы реализовали процедуры вычисления чисел Фибоначчи.

А теперь вернемся к нашей первой задаче об игре в камешки. Она носит название «фибоначчиев ним» и была предложена Р.Гаскелом и М.Виниганом (подробное доказательство см.[1], с.552). В одном ее названии уже таится ключ к разгадке. Да, это числа Фибоначчи.

Упростим условия задачи. Будем считать, что число камешков в кучке не 1000, а всего 20. Как мы помним, любое натуральное число можно представить в виде суммы несоседних чисел Фибоначчи единственным способом: 20 = 13 + 5 + 2 = F₇ + F₅ + F₃. Последнее слагаемое в таком разложении и показывает, сколько камешков для победы должен взять игрок, делающий первый ход. Если второй игрок, скажем, возьмет в ответ максимально возможное на этом ходу число камешков — 4, то первому играющему останется вновь разложить оставшиеся 14 камешков в сумму ряда Фибоначчи (14 = F₇ + F₂ = 13 + 1) и взять один камешек. Такая стратегия всегда будет приводить его к успеху. А вот если число камешков в кучке изначально совпадало бы с одним из чисел Фибоначчи, то победу одержал бы второй игрок (проверьте это сами). Теперь нам осталось выяснить, сколько же надо взять камешков первому игроку, когда общее их число составляет 1000. Разложим его в сумму ряда Фибоначчи: 1000 = F16 + F7 = 987 + 13. Итак, первому игроку для победы нужно взять 13 камешков. Попробуйте сами расширить модуль Pascaline, включив в него процедуру разложения любого натурального числа в ряд Фибоначчи.

Красота — критерий правильности

Подведем итоги. Построение каркаса отняло у нас значительное время, однако позволило создать такую архитектуру, которая может легко наращиваться и при этом оставаться достаточно простой и прозрачной для понимания и поиска возможных ошибок. Реализация альтернативных вариантов алгоритмов сняла многие вопросы за счет проверки на практике их эффективности. К тому же они служили дополнительным контролем для более сложных в реализации, но зато и более эффективных алгоритмов. Не менее важно и то, что мы на конкретном проекте познакомились с механизмами языков Оберон и Оберон-2, поддерживающих как концепцию ООП, так и концепцию модульного (компонентного) программирования. Модули стали главными строительными блоками, а классы ввиду их гибкости и расширяемости больше всего подошли для уровня контроллера (специального преобразователя), где требуется соединять разные виды представления данных и обеспечивать исполнение команд модельного слоя.

Профессор Роберт Флойд, автор одного из первых компиляторов языка Алгол-60, раскрывая секреты своей творческой лаборатории, заметил: «После того как поставленная задача решена, я повторно решаю ее с самого начала, прослеживая и повторяя только суть предыдущего решения. Я проделываю эту процедуру до тех пор, пока решение не становится настолько четким и ясным, насколько это для меня возможно. Затем я ищу общее правило решения аналогичных задач, которое заставило бы меня подходить к решению поставленной задачи наиболее эффективным способом с первого раза».

Вы, наверное, уже обратили внимание, что ряд Фибоначчи и треугольник Паскаля могут реализовываться через рекурсивные процедуры. Иными словами, их элементы подобны общему. В этом смысле они вполне подпадают под определение фрактала, предложенное Бенуа Мандельбротом (1987), который называл этим именем структуру, состоящую из частей, которые в каком-то смысле подобны целому. Кстати, относительно недавно в контуре канонического фрактала Мандельброта обнаружили «лепестки», в точности подчиняющиеся числам Фибоначчи.

Формируя каркас проекта и решая поставленные задачи, мы познакомились с одним из возможных стилей программирования. Разумеется, выбор автора был субъективен, и на практике вам придется самостоятельно выбирать стиль. Главное, чтобы он помогал строить понятные и эстетичные программы. Красота не только в математике служит критерием правильности. Если реализация алгоритмов на языке программирования выглядит понятно, органично и не вызывает отторжения, значит, у нее есть все шансы быть правильной.

Оберон/Оберон-2 и Object Pascal. Десять важных отличий

1. Имена идентификаторов. Ключевые и зарезервированные идентификаторы записываются заглавными буквами (при просмотре текста это сразу бросается в глаза и как бы задает каркас программы). Идентификаторы чувствительны к регистру. Поэтому очень удобно переменную записывать со строчной буквы, а тип с заглавной, например, map: Map.

2. Составные операторы. Отсутствие лишних скобок begin-end. Для составных операторов требуется только завершающая скобка END: начало определяется самим оператором. Связка BEGIN-END используется лишь для задания границ процедур и модулей (в теле инициализации). При этом после END обязательно указывается имя процедуры/модуля. В операторе IF применяется ступенчатая схема IF-ELSIF-ELSE, сокращающая избыточную вложенность.

3. Операторы безусловного перехода. Отсутствие оператора goto и его меток. В случае необходимости оператор goto можно легко моделировать с помощью универсального цикла LOOP (с выходом из него по оператору EXIT). Кроме того, имеется оператор HALT, принудительно останавливающий выполнение программы.

4. Типы данных. Числовые типы задают иерархию, учитываемую при совместимости типов: LONGREAL і REAL і LONGINT і INTEGER і SHORTINT. Больший тип поглощает меньший. Для работы со строками используются массивы литер: ARRAY OF CHAR. Признаком завершения строки является литера с кодом 0X (до X указывается шестнадцатизначное значение кода). Все операции над строками, кроме стандартной процедуры COPY, вынесены в библиотечные модули.

5. Конструкторы типов. Вся индексация массивов ведется с 0: при его описании задается размер, а не диапазон индексов. В качестве типа для формальных параметров процедур и базового типа для указателей могут использоваться открытые массивы. Отсутствие типа «перечисление». Отсутствие вариантных записей. Тип «множество» (SET) задает только набор целых чисел 0..MAX(SET), зависящий от платформы.

6. Экспорт-импорт идентификаторов. Области видимости идентификаторов определяются не блоками, а границами модулей и процедур. Вместо конструкций unit, interface, uses, отвечающих в Object Pascal за экспорт-импорт идентификаторов в Обероне/Обероне-2 используется единая конструкция модуля (MODULE с оператором IMPORT, регламентирующим список импортируемых модулей). Экспорт в Обероне-2 избирательный: если после идентификатора ставится признак «*», то экспорт полный (поддерживается чтение и запись), если признак «-», то экспорт частичный (только чтение). Интерфейс модуля (DEFINITION) генерируется автоматически по заданным признакам экспорта и обеспечивает раздельную компиляцию. Имеется механизм локальной синонимизации имен модулей.

7. Обработка исключений. Отсутствие операторов обработки исключений. Используются только контрольные вставки ASSERT с указанием булевого выражения. Если оно ложно, то выполнение программы в данной точке будет остановлено.

8. Системное программирование. Средства низкоуровневого программирования (работа с байтами и битами, регистрами, адресами, обощенными указателями) заключены в псевдомодуле SYSTEM (в исполняющей системе языка) и его импорт сигнализирует о возможном появлении проблем переносимости при последующем использовании импортирующего модуля на других платформах.

9. Наследование. В Обероне/Обероне-2 используется понятие расширения типа. Расширению подвергается только тип «запись» (как универсальная конструкция). Это означает, что новый тип может создаваться с расширением полей своего предшественника (механизм наследования): новый тип «проецируется» на предшествующий.

10. Классы и объекты. Для объектно-ориентированного программирования в дополнение к расширению типа добавляются связанные процедуры (type-bound procedures), играющие роль методов классов/объектов. С их помощью и благодаря операторам IS и WITH (в Обероне/Обероне-2 это аналог оператора CASE для разных классов) обеспечивается полиморфизм. Классы в Обероне/Обероне-2 присутствуют не в явном виде, а через расширение типов и специальные процедуры—методы. Динамическое порождение объектов (с помощью NEW, с размещением в куче и последующей сборкой мусора) и понятие изменяемого динамического типа (а не вариантного типа, как в Object Pascal) обеспечиваются указателями в комбинации с расширением типа. Инкапсуляция реализуется механизмом экспорта-импорта модулей.

Числа Фибоначчи и «золотое сечение»

0, 1, 1, 2, 3, 5, 8, 13, 21 ... — это знаменитая последовательность чисел Фибоначчи (F_n+2 = F_n + F_n+1). Она хорошо известна в связи с так называемой задачей о кроликах, которую в 1202 г. в работе «Liber Abaci» («Книга абака») представил великий европейский математик средневековья, итальянский купец Леонардо Фибоначчи (Пизанский). В соответствии с ее условиями каждая пара кроликов ежемесячно дает одну пару приплода, при этом она становится способной к размножению спустя месяц после появления на свет. Числа Фибоначчи дают ответ на вопрос, сколько пар кроликов будет всего через 1, 2, 3 и т.д. месяцев.

Леонардо Фибоначчи (1170—1250), будучи купцом, неоднократно путешествовал по странам Востока и в своей книге использовал труды арабских математиков (аль-Хорезми, Абу Камила и др.). Числа Фибоначчи были известны еще индийским ученым, которые анализировали ритмику стихосложения. Имя итальянца было увековечено в названии последовательности этих чисел с легкой руки французского математика Эдуарда Люка, доказавшего благодаря их удивительным свойствам, что число 2¹²⁷–1 является простым.

Если посмотреть на отношение соседних чисел Фибоначчи, то можно заметить, что оно стремится к числу 6=(1+5^1/2)/ 2 = 1,61803398874989484820... Наиболее замечательное свойствo ряда Фибоначчи состоит в том, что отношение двух последовательных членов ряда попеременно то больше, то меньше «золотого сечения». Соответственно, 6 ^n-2Fn <= 6 ^n-1. Евклид называл число 6 отношением крайнего и среднего (пропорции при делении отрезка). И по сей день многие архитекторы, скульпторы, художники, писатели, поэты считают «золотое сечение» наиболее эстетичным.

«Золотое сечение» было известно архитекторам эпохи Возрождения, но они применяли его сравнительно редко. Лука Пачоли называл «золотое сечение» божественной пропорцией. Термин «золотое сечение» возник в Германии в первой половине XIX в. В XX в. известный архитектор Ле Корбюзье изобрел модулер — систему двух шкал, обеспечивающую соблюдение архитектурных пропорций и повторение однотипных форм. Деления голубой шкалы вдвое крупнее делений красной шкалы, которая основана на числах Фибоначчи (т. е. на «золотом сечении»).

Одно из интересных свойств чисел Фибоначчи было открыто в начале XVII в. Й.Кеплером: F_n+1x F_n-1 – F²_n = (–1)ⁿ. Числа Фибоначчи могут вычисляться не только рекурсивно. В начале XVIII в. Бине вывел следующую формулу: Fn = ((1+5^1/2) ⁿ⁺¹ – (1–5^1/2)ⁿ+1) / (2ⁿ⁺¹x5^1/2). Как мы уже отмечали, числа Фибоначчи имеют прямую связь с треугольником Паскаля: Fn = Σ ⁿ_k=0 C_k^n-k. Хорошо известна теорема Люка, в соответствии с которой некоторое целое число делит Fm и Fn тогда и только тогда, когда оно является делителем Fd, где d = gcd(m,n), т. е. d — наибольший общий делитель m и n. В частности, gcd(Fm,Fn) = F_gcd(m,n) .

Другие интересные свойства чисел Фибоначчи:

1. Если n не является простым числом, то и Fn не является простым.
2. Σⁿ_k=0 F_k = F_n+2 – 1.
3. F² _n + F²_n+1 = F²_2n+1.
4. F2_n — F2_n-1 = F_n-2 x F_n+1.
5. Последние цифры чисел Фибоначчи образуют периодическую последовательность с периодом 60. Две последние цифры образуют периодическую последовательность с периодом, равным 300. Для трех последних цифр период равен 1500, для четырех — 15 000, для пяти — 150 000.
6. Делители чисел Фибоначчи сами образуют ряд Фибоначчи (каждое третье число делится на 2, каждое четвертое на 3, каждое пятое на 5, каждое шестое на 8 и т.д.).
7. Каждое число Фибоначчи, которое является простым (кроме F₄ = 3), имеет простой индекс. Обратное утверждение неверно.

Интересен и тот факт, что с помощью суммы чисел Фибоначчи можно представлять любое натуральное число. Так что подобно двоичной системе счисления может использоваться и система счисления Фибоначчи. Она также записывается в виде последовательности 0 и 1 (стоящих на местах соответствующих чисел Фибоначчи). Таких представлений может быть несколько, но если мы примем правило, согласно которому рядом не могут находиться две единицы (их можно обнулить и перенести в старший разряд), то представление будет единственным.

Ряд Фибоначчи привлекал внимание математиков своей загадочной особенностью возникать в самых неожиданных местах. Числа Фибоначчи эффективно применяются при распределении памяти, при сортировке и обработке информации, генерировании случайных чисел, в методах оптимизации, позволяющих находить приближенные значения максимумов и минимумов сложных функций.

Врезки:

Листинг 10. Модуль TriangleTst. Динамические типы, классы, неоднородные списки

TYPE
  Proc = POINTER TO ProcDesc; (* класс процедур *)
  ProcDesc = RECORD
    id : INTEGER; (* номер реализации *)
    next: Proc; (* ссылка на следующий *)
  END;
  Pas = POINTER TO PasDesc;
  (* класс процедур для треугольника Паскаля *)
  Fib = POINTER TO FibDesc;
  (* класс процедур для чисел Фибоначчи *)
  PasDesc = RECORD (ProcDesc)
    proc: Pascaline.ProcType1
  END;
  FibDesc = RECORD (ProcDesc)
    proc: Pascaline.ProcType2
  END;
  List = RECORD (* неоднородный список *)
    first: Proc; (* первый элемент *)
    this : Proc; (* текущий элемент *)
  END;

PROCEDURE ExecThisProc* (VAR isPas: BOOLEAN;
VAR id: INTEGER; VAR p1,p2,f1: SHORTINT;
VAR result: LONGINT);
BEGIN
  IF (list.this # NIL) THEN
    IF (list.this IS Pas)
      (* проверяем динамический тип *) THEN
      isPas := TRUE; id := list.this^.id;
      result := list.this(Pas)^.proc(pas1,pas2)
      (* приводим к типу *)
    ELSIF (list.this IS Fib)
      (* проверяем динамический тип *) THEN
      isPas := FALSE; id := list.this^.id;
      result := list.this(Fib)^.proc(fib1)
      (* приводим к типу *)
    END;
    p1 := pas1; p2 := pas2; f1 := fib1;
  END;
END ExecThisProc;

Листинг 9. Уровень контроллера (Controller). Модуль TriangleTF. Реализация итератора

TYPE PrimeIterator = RECORD
(* вырожденная запись, с ней связываем методы *)
END;
PROCEDURE (VAR t: PrimeIterator) Init (high: LONGINT);
BEGIN
  Pascaline.r.int := high; Pascaline.InitPrime;
END Init;

PROCEDURE (VAR t: PrimeIterator) First
(VAR elem: LONGINT): BOOLEAN;
BEGIN
  Pascaline.FirstPrime; elem := 0;
  IF Pascaline.sPrimeIsEmpty THEN RETURN FALSE
  ELSE elem := Pascaline.r.result; RETURN TRUE
  END;
END First;

PROCEDURE (VAR t: PrimeIterator) Next
(VAR elem: LONGINT): BOOLEAN;
BEGIN
  Pascaline.NextPrime; elem := 0;
  IF Pascaline.sPrimeIsEmpty THEN RETURN FALSE
  ELSE elem := Pascaline.r.result; RETURN TRUE
  END;
END Next;

PROCEDURE P (high: LONGINT);
VAR num: Number.Integer; iter: PrimeIterator;
  ok: BOOLEAN;
  s: ARRAY 256 OF CHAR;
BEGIN
  iter.Init(high); num.picture := "@N_12";
  ok := iter.First(num.body);
  WHILE ok DO
    num.Format(s); Print(s); ok := iter.Next(num.body);
  END;
END P;

Листинг 8. Модуль Pascaline. Реализация простых чисел через "решето Эратосфена"

PROCEDURE InitPrime*;
VAR k,j,p,q: LONGINT; step: SHORTINT; init: BOOLEAN; set: LONGINT;
BEGIN (* PRE: r.int - верхняя граница диапазона чисел *)
  ASSERT (r.int > 3);
  primeDesc.this := 1; primeDesc.count := 0;
  primeDesc.max := (r.int DIV 2) - 1;
  (* только среди нечетных *)
  set := (primeDesc.max DIV MAX(SET)) + 1;
  (* кол-во наборов *)
  NEW(isPrime,set);
  (* формируем динамический массив множеств *)
  FOR k := 1 TO primeDesc.max DO
    (* выставляем бит; isPrime<0> не используется *)
    INCL(isPrime[k DIV MAX(SET)], k MOD MAX(SET));
  END;
  k := 1; j := 1; p := 3; q := 4;
  (* p = 2*j + 1; q = 2*j + 2*j^2 *)
  step := 1; (* шаг алгоритма *)
  LOOP (* цикл фиктивный: это переключатель шагов *)
    CASE step OF
    1: IF ~((j MOD MAX(SET)) IN isPrime[j DIV MAX(SET)]) THEN
         step := 3;
       ELSE k := q; step := 2;
       END;
  | 2: IF (k <= primeDesc.max) THEN
         EXCL(isPrime[k DIV MAX(SET)], k MOD MAX(SET));
         INC(k,p); (* еще раз *)
       ELSE step := 3;
       END;
  | 3: INC(j); INC(p,2); q := q + 2*p - 2;
       IF (j <= primeDesc.max) THEN step := 1;
       ELSE EXIT (* выходим из цикла LOOP *)
       END;
    ELSE (* других вариантов нет *)
    END;
  END;
  init := FALSE; sPrimeIsEmpty := TRUE;
  FOR k := 1 TO primeDesc.max DO
    IF ((k MOD MAX(SET)) IN isPrime[k DIV MAX(SET)]) THEN
      IF ~init THEN
        primeDesc.this := k; r.result := 2*k + 1;
        init := TRUE;
        sPrimeIsEmpty := FALSE;
      END;
      INC(primeDesc.count);
    END;
  END; (* POST: r.result содержит первое простое число *)
END InitPrime;

Листинг 7. Модуль Pascaline. Реализация чисел Фибоначчи через стек

PROCEDURE Fibonacci3* (i: SHORTINT): LONGINT;
VAR x: LONGINT; k: SHORTINT; stack: ARRAY 2 OF LONGINT;
BEGIN (* PRE: i >= 0; i <= MaxFibINDEX *)
  IF (i = 0) OR (i = 1) THEN RETURN 1
  ELSE (* i > 1 *) stack[0] := 1; stack[1] := 1;
  k := 2;
  REPEAT
    x := stack[0] + stack[1]; stack[0] := stack[1];
    stack[1] := x;
    INC(k);
  UNTIL (k > i);
  RETURN x
  END; (* POST: sBadIndex = FALSE *)

END Fibonacci3;

Листинг 6. Модуль Pascaline. Реализация треугольника Паскаля через динамические сегменты

PROCEDURE Segment (s,t: SHORTINT): LONGINT;
VAR k: INTEGER;
BEGIN (* обращение к одномерному массиву через динамические сегменты *)
  k := (((s+3) DIV 2)-1) * ((s+2) DIV 2) + t;
  (* вычисление индекса *)
  ASSERT(pas[k] > 0);
  (* проверка на инициализацию элемента *)
  RETURN pas[k]
END Segment;

PROCEDURE LoadPas;
VAR s,t,size: SHORTINT; k: INTEGER;
BEGIN (* заполнение массива готовыми значениями *)
  FOR k := 0 TO MaxPasINDEX-1 DO
    pas[k] := -1;
  (* для контроля за заполнением *)
  END;
  pas[0] := 6;
  (* первый элемент знаем *)
  k := 1; (* индекс массива pas *) s := 1;
  (* номер сегмента *)
  REPEAT (* цикл по сегментам *)
    size := ((s+4) DIV 2) - 1;
    (* кол-во элементов в сегменте *)
    t := 0;
    (* индекс внутри сегмента *)
    WHILE (k < PasCOUNT) & (t < size) DO
    (* цикл внутри сегмента *)
      IF (t = 0) THEN pas[k] := Segment(s-1,0) + (s+3);
      (* ODD - признак нечетности; смотрим посл. эл-ты
         четных сегментов *)
      ELSIF ~ODD(s) & (t = size-1) THEN
        pas[k] := 2*Segment(s-1,size-2);
      ELSE pas[k] := Segment(s-1,t-1) + Segment(s-1,t);
      END;
      INC(t); INC(k)
    END;
    INC(s);
  UNTIL (s > MaxPasINDEX+4);
END LoadPas;

PROCEDURE PascalTriangle2* (i,j: SHORTINT): LONGINT;
VAR k: LONGINT;
BEGIN (* PRE: i >= 0; j >= 0; j <= i; i <= MaxPasINDEX *)
  IF (j = 0) OR (j = i) THEN RETURN 1
  (* стороны треугольника *)
  ELSIF (j = 1) OR (j = i-1) THEN RETURN i
  (* диагонали под сторонами *)
  ELSE (* j <= i; i > 3; j > 1 *)
    IF (j-2 >= ((i DIV 2)-1)) THEN j := i-j END;
    (* за счет симметрии *)
    k := (((i-1) DIV 2)-1) * ((i-2) DIV 2) + (j-2);
    (* нужен индекс *)
    RETURN pas[k]
  END; (* POST: sBadIndex = FALSE *)
END PascalTriangle2;