Prolog:将数字拆分为一系列递增的整数 [英] Prolog: Splitting a number into a sequence of increasing integers

问题描述

在 uni 中做了一些 Prolog 并做了一些练习后，我决定更进一步，尽管我不得不承认我不太了解递归，我明白了概念和想法，但如何编码它仍然是一个问题为我.所以这就是为什么我很好奇是否有人知道如何帮助解决这个问题.

这个想法被赋予一个数字，例如45、检查是否可以做一个从1开始到n+1的列表，并且列表的总和是否与给定的数字相同.

所以对于 45，[1,2,3,4,5,6,7,8,9] 是正确的.

到目前为止，我尝试查看在 Prolog 中实现的 [sum_list/2][1] ，但它只检查列表是否与它后面的数字相同.

所以给定一个谓词lijstSom(L,S)(荷兰语为listSum)，给定

?- lijstSom(L, 45)L = [1,2,3,4,5,6,7,8,9];错误的

我的想法是例如如果 S = 45，执行数字的步骤(增加 1)并减去 S，如果 0 是余数，则返回列表，否则返回 false.

但为此你需要计数器，我发现在递归中很难理解这一点.

递归步骤.

Base case 空列表，0(计数器 nr，即减去 S)，45(S，余数)

[1], 1, 44[1,2], 2, 42[1,2,3], 3, 39

解决方案

我不知道如何阅读示例

?- lijstSom(L, 45)L = [1,2,3,4,5,6,7,8,9],错误的

...但将谓词 lijstSom(List, Sum) 视为将某些整数列表与其总和相关联，而不是计算整数列表的总和.为什么是某些列表"?因为我们有一个约束，即整数列表中的整数必须以 1 为增量单调递增，从 1 开始.

因此，您可以询问 Prolog 处理器以下内容:

"说说 lijstSom/2 的第一个参数和第二个参数 lijstSom/2 之间的关系(假设第一个是单调递增的整数列表，第二个是整数):

lijstSom([1,2,3], Sum)

...应该返回真(因为是的，至少有一个解决方案)并给 Sum = 6(因为它构造解决方案也是......我们是建构主义的某个角落.>

lijstSom(L, 6)

...应该返回真(因为是的，至少有一个解决方案)并给出解决方案 [1,2,3].

lijstSom([1,2,3], 6)

...应该返回真(因为是的，[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 与 [1,2,3]lijstSom> 作为 7 =/= 1+2+3.

人们甚至可能想让 Prolog Processor 说一些有趣的事情:

lijstSom([1,2,X], 6)

X = 3

甚至

lijstSom([1,2,X], S)

X = 3S = 6

事实上，lijstSom/2 在物理上尽可能接近数学魔法，也就是说:

• 可以不受限制地访问浮在柏拉图数学空间某处的列表<->求和关系的完整表格.
• 能够在非常少的步骤中找到正确的条目.
• 然后输出.

当然，出于非常实际的原因，我们仅限于低指数和有限数量的可识别符号的多项式算法.糟透了！

因此，首先使用归纳定义定义 lijstSom(L,S):

• lijstSom([a list with final value N],S) ... 为真如果 ... lijstSom([a list],SN and立>
• lijstSom([],0) 因为空列表的总和为 0.

这很好，因为它提供了将任意长度的列表最终减少到大小为 0 的列表的方法，同时保持其总和的全部知识！

Prolog 不擅长处理列表的尾部，但擅长处理列表的头部，所以我们作弊 &更改我们对 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 的数学要求，并允许 Prolog 处理器执行其计算:在第二个子句中，它可以从列表的值计算大小为 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).

更好！

(我们还添加了 '!' 来告诉 Prolog 处理器在这一点之后不要寻找替代解决方案，因为我们对算法的了解比以往任何时候都多.此外，第三行有效，但只是因为我在运行下面的测试并让它们通过后就搞定了.)

如果检查失败，Prolog Processor 会说false" - 您的输入没有解决方案.这正是我们想要的.

但这有用吗?我们能在这台卓越物理机器的数学性"上走多远?

加载 library(clpfd) 以获取约束并使用 library(plunit) 用于单元测试:

把它放到一个文件 x.pl 中，你可以用 [x] 别名 consult('x') 加载或重新加载make 在 Prolog 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("调用 K=~w, V=~w, Rest=~w, N=~w\n", [K,V,Rest,N]),K#=V+1，T+K #= N,#>0，V#＞0, % 需要避免无限下降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).测试(6 验证"):- lijstSom([3,2,1],6).test("0 构造") :- lijstSom(L,0) , L = [].test("1 构造") :- lijstSom(L,1) , L = [1].test("3 构造") :- lijstSom(L,3) , L = [2,1].test("6 构造") :- 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("1extreme partial") :- lijstSom([X],S) , X = 1, S = 1.测试(3 极端部分") :- lijstSom([X,1],S) , X = 2, S = 3.test("6extreme partial") :- lijstSom([X,2,1],S), X = 3, S = 6.test("6 部分列表") :- lijstSom([X|L],6) , X = 3, L = [2,1].% 测试 NOPES 的重要性test("bad list", fail) :- lijstSom([3,1],_).测试(坏总和"，失败):- lijstSom([3,2,1],5).测试(反向列表"，失败):- lijstSom([1,2,3],6).测试(从 2 无限下降"，失败):- lijstSom(_,2).测试(从 9 无限下降"，失败):- lijstSom(_,9).:- end_tests(listsom).

然后

?- run_tests(listsom).% PL-Unit: listom ...................... 完成% 所有 22 项测试均通过

Dijkstra 会怎么说?是的，他可能会抱怨一些事情.

After doing some Prolog in uni and doing some exercises I decided to go along somewhat further although I got to admit I don't understand recursion that well, I get the concept and idea but how to code it, is still a question for me. So that's why I was curious if anyone knows how to help tackle this problem.

The idea is given a number e.g. 45, check whether it is possible to make a list starting with 1 going n+1 into the list and if the sum of the list is the same as the given number.

So for 45, [1,2,3,4,5,6,7,8,9] would be correct.

So far I tried looking at the [sum_list/2][1] implemented in Prolog itself but that only checks whether a list is the same as the number it follows.

So given a predicate lijstSom(L,S) (dutch for listSum), given

?- lijstSom(L, 45)
L = [1,2,3,4,5,6,7,8,9];
False

My Idea was something along the line of for example if S = 45, doing steps of the numbers (increasing by 1) and subtracting it of S, if 0 is the remainder, return the list, else return false.

But for that you need counters and I find it rather hard to grasp that in recursion.

EDIT:

Steps in recursion.

Base case empty list, 0 (counter nr, that is minus S), 45 (S, the remainder)

[1], 1, 44

[1,2], 2, 42

[1,2,3], 3, 39

解决方案

I'm not sure how to read the example

?- lijstSom(L, 45)

L = [1,2,3,4,5,6,7,8,9],

False

...but think of the predicate lijstSom(List, Sum) as relating certain lists of integers to their sum, as opposed to computing the sum of lists of integers. Why "certain lists"? Because we have the constraint that the integers in the list of integers must be monotonically increasing in increments of 1, starting from 1.

You can thus ask the Prolog Processor the following:

"Say something about the relationship between the first argument of lijstSom/2 and the second argument lijstSom/2 (assuming the first is a list of monotonically increasing integers, and the second an integer):

lijstSom([1,2,3], Sum)

... should return true (because yes, there is at least one solution) and give Sum = 6 (because it constructs the solution, too ... we are some corner of Construtivism here.

lijstSom(L, 6)

... should return true (because yes, there is at least one solution) and give the solution [1,2,3].

lijstSom([1,2,3], 6)

... should return true (because yes, [1,2,3] has a sum 6); no further information is needed.

lijstSom(L, S)

... should an infinite series of true and pairs of solution ("generate the solutions").

L = [1], S = 1;
L = [1,2], S = 3;
L = [1,2,3], S = 6;
...

lijstSom([1,2,3], 7)

...should return false ("fail") because 7 is not in a relation lijstSom with [1,2,3] as 7 =/= 1+2+3.

One might even want things to have Prolog Processor say something interesting about:

lijstSom([1,2,X], 6)

X = 3

or even

lijstSom([1,2,X], S)

X = 3
S = 6

In fact, lijstSom/2 as near to mathematically magical as physically possible, which is to say:

• Have unrestricted access to the full table of list<->sum relationships floating somewhere in Platonic Math Space.
• Be able to find the correct entry in seriously less than infinite number of steps.
• And output it.

Of course we are restricted to polynomial algorithms of low exponent and finite number of dstinguishable symbols for eminently practical reasons. Sucks!

So, first define lijstSom(L,S) using an inductive definition:

• lijstSom([a list with final value N],S) ... is true if ... lijstSom([a list],S-N and
• lijstSom([],0) because the empty list has sum 0.

This is nice because it gives the recipe to reduce a list of arbitrary length down to a list of size 0 eventually while keeping full knowledge its sum!

Prolog is not good at working with the tail of lists, but good with working with the head, so we cheat & change our definition of lijstSom/2 to state that the list is given in reverse order:

lijstSom([3,2,1], 6)

Now some code.

#= is the "constain to be equal" operator from library(clpfd). To employ it, we need to issue use_module(library(clpfd)). command first.

lijstSom([],0).
lijstSom([K|Rest],N) :- lijstSom([Rest],T), T+K #= N.

The above follows the mathematical desiderate of lijstSom and allows the Prolog Processor to perform its computation: in the second clause, it can compute the values for a list of size A from the values of a list of size A-1, "falling down" the staircase of always decreasing list length until it reaches the terminating case of lijstSom([],0)..

But we haven't said anything about the monotonically decreasing-by-1 list. Let's be more precise:

lijstSom([],0) :- !.
lijstSom([1],1) :- ! .
lijstSom([K,V|Rest],N) :- K #= V+1, T+K #= N, lijstSom([V|Rest],T).

Better!

(We have also added '!' to tell the Prolog Processor to not look for alternate solutions past this point, because we know more about the algorithm than it will ever do. Additionally, the 3rd line works, but only because I got it right after running the tests below and having them pass.)

If the checks fail, the Prolog Processor will says "false" - no solution for your input. This is exactly what we want.

But does it work? How far can we go in the "mathematic-ness" of this eminently physical machine?

Load library(clpfd) for constraints and use library(plunit) for unit tests:

Put this into a file x.pl that you can load with [x] alias consult('x') or reload with make on the Prolog 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).

Then

?- run_tests(listsom).
% PL-Unit: listsom ...................... done
% All 22 tests passed

What would Dijkstra say? Yeah, he would probably bitch about something.

这篇关于Prolog:将数字拆分为一系列递增的整数的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！