Я изучаю Prolog с помощью SWI Prolog, и у меня есть сомнения относительно следующих двух решений программы расчета чисел Фибоначчи:
Первый такой:
fib(1,1).
fib(2,1).
fib(N,F) :- N > 2,
N1 is N-1,
fib(N1,F1),
N2 is N-2,
fib(N2,F2),
F is F1+F2.
Для меня довольно ясно, как это работает, это очень просто.
Затем у меня есть эта вторая версия, которая, читая код, кажется, работает как предыдущая, но после этого она вычисляет число Фибоначчи N, сохраняет его в базе данных Prolog с помощью предиката asserta/2 для повторного использования. это после.
Так, например, если я вычисляю число Фибоначчи для 10 и 11, когда я иду вычислять число Фибоначчи для 12, я буду использовать результат двух предыдущих вычислений.
Итак, мой код:
:-dynamic fibDyn/2.
fibDyn(1,1).
fibDyn(2,1).
fibDyn(N,F) :- N > 2,
N1 is N-1,
fibDyn(N1,F1),
N2 is N-2,
fibDyn(N2,F2),
F is F1+F2,
asserta(fibDyn(N,F)).
Мне кажется, что логика та же, что и в предыдущем:
F — число Фибоначчи для N, если N>2, и используйте рекурсию для вычисления числа Фибоначчи для N (как в предыдущем примере).
Я ожидаю, что программа будет работать быстрее, если я попрошу вычислить номер числа Фибоначчи для числа, которое я уже вычислил и занес в базу данных чисел Фибоначчи своих предшественников (или некоторых из них), но мне кажется, что она работает в странный способ: он слишком быстр и способен напрямую вычислять числа Фибоначчи для очень больших целых чисел (другая версия не работает с такими большими числами)
Другая странная вещь заключается в том, что если я делаю трассировку запроса, я получаю что-то вроде этого:
[trace] ?- fibDyn(200,Fib).
Call: (6) fibDyn(200, _G1158) ? creep
Exit: (6) fibDyn(200, 280571172992510140037611932413038677189525) ? creep
Fib = 280571172992510140037611932413038677189525 .
Как видите, получается не выполнять код предиката Фибоначчи, а напрямую получать результат (откуда?!?!)
Вместо этого, если я выполняю этот запрос (используя первую версию), я получаю, что программа его вычислит:
[trace] ?- fib(3,Fib).
Call: (6) fib(3, _G1158) ? creep
^ Call: (7) 3>2 ? creep
^ Exit: (7) 3>2 ? creep
^ Call: (7) _G1233 is 3+ -1 ? creep
^ Exit: (7) 2 is 3+ -1 ? creep
Call: (7) fib(2, _G1231) ? creep
Exit: (7) fib(2, 1) ? creep
^ Call: (7) _G1236 is 3+ -2 ? creep
^ Exit: (7) 1 is 3+ -2 ? creep
Call: (7) fib(1, _G1234) ? creep
Exit: (7) fib(1, 1) ? creep
^ Call: (7) _G1158 is 1+1 ? creep
^ Exit: (7) 2 is 1+1 ? creep
Exit: (6) fib(3, 2) ? creep
Fib = 2 .
Почему? Я ожидаю, что вторая версия (та, которая использует предикат asserta) будет вычислять число Фибоначчи для двух чисел и использовать это значение для генерации решения следующего.
Например, у меня может быть следующая ситуация: я еще никогда не вычислял числа Фибоначчи и прошу вычислить число Фибоначчи N=4, чтобы оно вычислило его (как во второй опубликованной трассировке стека).
Поэтому я прошу рассчитать число Фибоначчи для N=5, а он использует число Фибоначчи для N=4, чтобы оно было сохранено. Затем я прошу его рассчитать число Фибоначчи N = 6, и, наконец, он сможет использовать сохраненные числа Фибоначчи 4 и 5.
Что мне не хватает? Можете ли вы помочь мне понять?
