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.

但是为此你需要计数器，我发现在递归中很难掌握它.

递归步骤.

基本情况空列表，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)

... 应该 return true (因为是的，至少有一个解决方案)并且 给出 Sum = 6 (因为它构造解决方案也是……我们是 Construtivism 的某个角落.p>

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 与 [1,2,3]lijstSom> 作为 7 =/= 1+2+3.

人们甚至可能希望让 Prolog 处理器说出一些有趣的事情:

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 和 为真李>
• 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 处理器不要寻找超过这一点的替代解决方案，因为我们对算法的了解比以往任何时候都多.此外，第 3 行有效，但这只是因为我在运行下面的测试并让它们通过之后就得到了它.)

如果检查失败，Prolog 处理器将显示假" - 您的输入没有解决方案.这正是我们想要的.

但它有效吗?我们可以在这台卓越的物理机器的数学"方面走多远?

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

将其放入文件 x.pl 中，您可以使用 [x] 别名 consult('x') 加载该文件或使用重新加载Prolog REPL 上的 make:

:- use_module(library(clpfd)).lijstSom([],0) :-format("命中大小写 ([],0)
"),!.lijstSom([1],1) :-format("命中大小写 ([1],1)
"),!.lijstSom([K,V|Rest],N) :-format("调用时 K=~w, V=~w, Rest=~w, N=~w
", [K,V,Rest,N]),K#= V+1,T+K #= N,T#>0，V#＞0, % 需要避免无限下降lijstSom([V|Rest],T).:- begin_tests(listsom).测试(0验证"):- lijstSom([]，0).测试(1 验证"):- lijstSom([1]，1).测试(3 验证"):- lijstSom([2,1],3).测试(6 验证"):- lijstSom([3,2,1],6).测试(0构造"):- lijstSom(L，0)，L = [].测试(1 构造"):- lijstSom(L,1) ，L = [1].测试(3 构造"):- lijstSom(L,3) ，L = [2,1].测试(6 构造"):- lijstSom(L,6)，L = [3,2,1].测试(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.测试(6 部分"):- lijstSom([X,2,1],6)，X = 3.测试(1 极端部分"):- lijstSom([X]，S)，X = 1，S = 1.测试(3 极端部分"):- lijstSom([X,1],S) ，X = 2，S = 3.测试(6 极端部分"):- lijstSom([X,2,1],S) ，X = 3，S = 6.test("6 部分列表") :- lijstSom([X|L],6) , X = 3, L = [2,1].% 对测试 NOPES 很重要测试(坏列表"，失败):- 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: listsom ............ 完成% 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)
"),!.
lijstSom([1],1) :-
   format("Hit case ([1],1)
"),!.
lijstSom([K,V|Rest],N) :- 
   format("Called with K=~w, V=~w, Rest=~w, N=~w
", [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屋！