том, чтобы определить 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).
Рис. 8. 4. Отношения в последовательности Фибоначчи. 'Конфигурация' изображается
здесь в виде большого круга и определяется тремя параметрами: индексом М и двумя
последовательными числами f( M-1) и f( М).
Упражнения
8. 1. Все показанные ниже процедуры подсп1, подсп2 и подсп3 реализуют отношение взятия подсписка. Отношение подсп1 имеет в значительной мере процедурное определение, тогда как подсп2 и подсп3 написаны в декларативном стиле. Изучите поведение этих процедур на примерах нескольких списков, обращая внимание на эффективность работы. Две из них ведут себя одинаково и имеют одинаковую эффективность. Какие? Почему оставшаяся процедура менее эффективна?
подсп1( Спис, Подспис) :-
начало( Спис, Подспис).
подсп1( [ _ | Хвост], Подспис) :-
% Подспис - подсписок хвоста
подсп1( Хвост, Подспис).
начало( _, [ ]).
начало( [X | Спис1], [X | Спис2] ) :-
начало( Спис1, Спис2).
подсп2( Спис, Подспис) :-
конк( Спис1, Спис2, Спис),
конк( Спис3, Подспис, Cпис1).
подсп3( Спис, Подспис) :-
