Программирование на языке Пролог для искусственного интеллекта



         

Повышение эффективности зa счет добавления вычисленных фактов к базе данных - часть 4


Идея состоит на этот раз не в том, чтобы определить N-e число Фибоначчи просто как сумму своих предшественников по последовательности, оставляя рекурсивным вызовам организовать вычисления "сверху вниз" вплоть до самых первых двух чисел. Вместо этого можно работать "снизу вверх": начать с первых двух чисел и продвигаться вперед, вычисляя члены последовательности один за другим. Остановиться нужно в тот момент, когда будет достигнуто N-e число. Большая часть работы в такой программе выполняется процедурой

        фибвперед( М, N, F1, F2, F)

Здесь F1 и F2 - (М - 1)-е и М-е числа, а F - N-e число Фибоначчи. Рис. 8.4 помогает понять отношение фибвперед. В соответствии с этим рисунком фибвперед

находит последовательность преобразований для достижения конечной конфигурации (в которой М = N) из некоторой заданной начальной конфигурации. При запуске фибвперед все его аргументы, кроме F, должны быть конкретизированы, а М должно быть меньше или равно N. Вот эта программа:

        фиб3( N, F) :-

                фибвперед( 2, N, 1, 1, F).

                                    % Первые два числа Фиб. равны 1

        фибвперед( М, N, F1, F2, F2) :-

                М >= N.     % N-e число достигнуто

        фибвперед( M, N, F1, F2, F) :-

                M < N,       % N-e число еще не достигнуто

                СледМ is М + 1,

                СледF2 is F1 + F2,

                фибвперед( СледМ, N, F2, СледF2, F).

fig8_4.gif (2898 bytes)

Рис. 8. 4.  Отношения в последовательности Фибоначчи. "Конфигурация" изображается

здесь в виде большого круга и определяется тремя параметрами: индексом М и двумя

последовательными числами f( M-1) и f( М).




Содержание  Назад  Вперед