Я не уверен, как читать пример
?- lijstSom(L, 45)
L = [1,2,3,4,5,6,7,8,9],
False
... но думаю, что предикат lijstSom(List, Sum) связывает определенные списки целых чисел с их суммой, а не вычисляет сумму списки целых чисел. Почему "определенные списки"? Поскольку у нас есть ограничение, что целые числа в списке целых чисел должны монотонно увеличиваться с шагом 1, начиная с 1.
Таким образом, вы можете задать процессору Prolog следующее:
"Скажите кое-что о связи между первым аргументом lijstSom/2 и вторым аргументом lijstSom/2 (при условии, что первый представляет собой список монотонно увеличивающихся целых чисел, а второй - целое):
lijstSom([1,2,3], Sum)
... следует вернуть true (потому что да, есть хотя бы одно решение) и дать Sum = 6 (потому что оно тоже создает решение ... мы здесь какой-то угол Конструктивизма .
lijstSom(L, 6)
... должен вернуть true (потому что да, есть хотя бы один решение) и дают решение [1,2,3].
lijstSom([1,2,3], 6)
... должны вернуть true (потому что да, [1,2,3] имеет сумму 6), дополнительная информация не требуется.
lijstSom(L, S)
... если бесконечные серии true и пары решений («генерировать решения»).
L = [1], S = 1;
L = [1,2], S = 3;
L = [1,2,3], S = 6;
...
lijstSom([1,2,3], 7)
... следует вернуть false («ошибка»), потому что 7 не находится в отношении lijstSom с [1,2,3] как 7 = / = 1 + 2 + 3.
Можно даже захотеть, чтобы процессор Prolog сказал что-то интересное о:
lijstSom([1,2,X], 6)
X = 3
или даже
lijstSom([1,2,X], S)
X = 3
S = 6
На самом деле, lijstSom/2 как математически близко магически настолько физически, насколько это возможно, то есть:
- Иметь неограниченный доступ к полной таблице списка <-> сумм отношений, плавающих где-то в Платони c Математическое пространство.
- Be возможность найти правильную запись за серьезно меньшее, чем бесконечное число шагов.
- и вывести ее.
Конечно, мы ограничены полиномиальными алгоритмами с низким показателем степени и конечным числом dstinguishable символы по исключительно практическим причинам. Отстой!
Итак, сначала определим lijstSom(L,S), используя индуктивное определение:
lijstSom([a list with final value N],S) ... верно, если ... lijstSom([a list],S-N и lijstSom([],0) потому что пустой список имеет сумму 0.
Это хорошо, потому что он дает рецепт, чтобы сократить список произвольной длины до списка размера 0 в конечном итоге, сохраняя при этом полное знание своей суммы !
Пролог не подходит для работы с хвостом списков, но хорош для работы с головой, поэтому мы изменяем и изменяем наше определение lijstSom/2, чтобы утверждать, что список задан в обратном порядке:
lijstSom([3,2,1], 6)
Теперь немного кода.
#= - это оператор «приравнивать к равенству» из библиотеки (clpfd) . Чтобы использовать его, нам нужно сначала ввести команду use_module(library(clpfd))..
lijstSom([],0).
lijstSom([K|Rest],N) :- lijstSom([Rest],T), T+K #= N.
Вышеизложенное следует математическому желанию lijstSom и позволяет процессору Пролог выполнять свои вычисления: во втором предложении он может вычислить значения для списка размера A из значений списка размера A-1, «падая» вниз по лестнице с постоянно уменьшающейся длиной списка, пока не достигнет конечного случая lijstSom([],0)..
Но мы ничего не сказали о монотонно уменьшающемся на 1 списке. Давайте будем более точными:
lijstSom([],0) :- !.
lijstSom([1],1) :- ! .
lijstSom([K,V|Rest],N) :- K #= V+1, T+K #= N, lijstSom([V|Rest],T).
Лучше!
(Мы также добавили '!', Чтобы сказать процессору Пролога не искать альтернативные решения после этой точки, потому что мы знаем больше о алгоритм, чем он когда-либо будет. Кроме того, 3-я строка работает, но только потому, что я понял его сразу после запуска тестов, приведенных ниже, и их прохождения.)
Если проверки не пройдены, процессор Prolog скажет: ложь "- нет решения для вашего ввода. Это именно то, что мы хотим.
Но работает ли это? Как далеко мы можем go в «математике» 1150 * -тиности этой чрезвычайно физической машины?
Загрузите library(clpfd) для ограничений и используйте library(plunit) для модульных тестов:
Поместите это в файл x.pl, который вы можете загрузить с помощью [x] псевдоним consult('x') или перезагрузите с помощью make в Прологе. REPL:
:- use_module(library(clpfd)).
lijstSom([],0) :-
format("Hit case ([],0)\n"),!.
lijstSom([1],1) :-
format("Hit case ([1],1)\n"),!.
lijstSom([K,V|Rest],N) :-
format("Called with K=~w, V=~w, Rest=~w, N=~w\n", [K,V,Rest,N]),
K #= V+1,
T+K #= N,
T #> 0, V #> 0, % needed to avoid infinite descent
lijstSom([V|Rest],T).
:- begin_tests(listsom).
test("0 verify") :- lijstSom([],0).
test("1 verify") :- lijstSom([1],1).
test("3 verify") :- lijstSom([2,1],3).
test("6 verify") :- lijstSom([3,2,1],6).
test("0 construct") :- lijstSom(L,0) , L = [].
test("1 construct") :- lijstSom(L,1) , L = [1].
test("3 construct") :- lijstSom(L,3) , L = [2,1].
test("6 construct") :- lijstSom(L,6) , L = [3,2,1].
test("0 sum") :- lijstSom([],S) , S = 0.
test("1 sum") :- lijstSom([1],S) , S = 1.
test("3 sum") :- lijstSom([2,1],S) , S = 3.
test("6 sum") :- lijstSom([3,2,1],S) , S = 6.
test("1 partial") :- lijstSom([X],1) , X = 1.
test("3 partial") :- lijstSom([X,1],3) , X = 2.
test("6 partial") :- lijstSom([X,2,1],6) , X = 3.
test("1 extreme partial") :- lijstSom([X],S) , X = 1, S = 1.
test("3 extreme partial") :- lijstSom([X,1],S) , X = 2, S = 3.
test("6 extreme partial") :- lijstSom([X,2,1],S) , X = 3, S = 6.
test("6 partial list") :- lijstSom([X|L],6) , X = 3, L = [2,1].
% Important to test the NOPES
test("bad list", fail) :- lijstSom([3,1],_).
test("bad sum", fail) :- lijstSom([3,2,1],5).
test("reversed list", fail) :- lijstSom([1,2,3],6).
test("infinite descent from 2", fail) :- lijstSom(_,2).
test("infinite descent from 9", fail) :- lijstSom(_,9).
:- end_tests(listsom).
Тогда
?- run_tests(listsom).
% PL-Unit: listsom ...................... done
% All 22 tests passed
Что скажет Дейкстра ? Да, он, вероятно, ссорится о чем-то.