序言列表构建的更多麻烦 [英] More trouble with prolog list building

问题描述

我很抱歉在此发布另一个问题，但我似乎只是在这里兜圈子！

I'm sorry to post another question on this, but I just seem to be going in circles here!

对于我的程序，我需要制作一个列表列表，每个子列表包含 2 个数字，X 和 Y 以及这两个数字的总和和乘积.到目前为止，我有以下内容:

For my program I need to make a list of lists, with each sublist containing 2 numbers, X and Y along with the sum and product of these 2 numbers. So far I have the following:

genList(100,N, X,[]).

genList(S,N, X,[[X,Y,Sum,Product]|Xs]):-

    Y is N+1,
    Sum is X+Y,
    NewS is Sum,
    Sum<101,
    Product is X*Y,
    N1 is N+1,
    genList(NewS,N1, X,Xs).

genList(S,N,X,Q):-
    N+X < 101,
    NextX is X + 1,
    genList(0,NextX,NextX,Q).

我们的目标是找到总和<= 100的每一对数字.所以通过上面的一个起始值，X会找到每一对1<=100.X＜Y，其中 sum<=100，并用所有数字 2-N 遍历它会给出可能对的完整列表.

The goal is to find every pair of numbers where sum<= 100. So running through the above for one starting value, X would find every pair 1 < X < Y, where sum<=100, and running through it with all numbers 2-N would give a complete list of possible pairs.

对于那些感兴趣的人，我正在解决的问题是总和/乘积问题，描述为 这里(页面第二个)

For those interested, the problem I'm working through is the sum/product problem, described here (Second on the page)

如果有人能帮忙解决这个问题，我们将不胜感激！

If anyone could help with this it would be greatly appreciated!

此外，无法使用内置的 prolog 谓词，因此这样做的方法很复杂，而不是使用 findall.

Also, no built in prolog predicates are able to be used, hence the complicated way of doing this rather than with a findall.

这个谓词产生的输出的一小段摘录如下:

A small extract of the output produced by this predicate is as follows:

[[5,6,11,30],[5,7,12,35],[5,8,13,40],[5,9,14,45],[5,10,15,50],[5,11,16,55],[5,12,17,60],[5,13,​​18,65],[5,14,19,70],[5,15,20,75],[5,16,21,80],[5,17,22,85],[5,18,23,90],[5,19,24,95],[5,20,25,100],[5,21,26,105],[5,22,27,110], ...

[[5,6,11,30],[5,7,12,35],[5,8,13,40],[5,9,14,45],[5,10,15,50],[5,11,16,55],[5,12,17,60],[5,13,18,65],[5,14,19,70],[5,15,20,75],[5,16,21,80],[5,17,22,85],[5,18,23,90],[5,19,24,95],[5,20,25,100],[5,21,26,105],[5,22,27,110], ...

我认为已经很接近了，但仍有一些不太对劲的地方.

I think it's very close, but there's still something not quite right.

它循环数字对，但需要使用;"查看所有答案，这不是我想要的.此外，在所有答案都用尽后，它返回 false.我就是想不通.

It cycles through number pairs, but requires the use of ";" to view all the answers, which isn't what I want. Additionally, it returns false after all the answers are exhausted. I just can't figure it out.

此外，它给出了起始值的完整答案，但每次都会删除一个子列表，直到我只剩下最后一组对.

Also, it gives a complete answer for the starting value, but then removes a sublist each time until I'm left with only the last set of pairs.

例如genList(0,48,48,Q).给我:

E.g. genList(0,48,48,Q). gives me:

[[48,49,97,2352],[48,50,98,2400],[48,51,99,2448],[48,52,100,2496]]
[[48,49,97,2352],[48,50,98,2400],[48,51,99,2448],[48,52,100,2496],[49,50,99,2450],[49,51,100,2499]]
[[48,49,97,2352],[48,50,98,2400],[48,51,99,2448],[49,50,99,2450],[49,51,100,2499]]
[[48,49,97,2352],[48,50,98,2400],[49,50,99,2450],[49,51,100,2499]]
[[48,49,97,2352],[49,50,99,2450],[49,51,100,2499]]
[[49,50,99,2450],[49,51,100,2499]]
false.

如您所见，每次都会删除一个子列表，我就是不明白为什么！

As you can see, a sublist gets removed each time, I just can't see why!

推荐答案

好了，您就快到了.由于您已经在这个问题上花费了相当多的时间，我将向您展示一些有效的代码并对其进行评论:

Well, you're almost there. Since you spent quite some time on this problem already I'll just show you some valid code and comment it:

首先我们调用一个工作谓词，它将携带X和Y作为参数并将它们初始化为0:

First we call a worker predicate that'll carry X and Y as arguments and initialize them to 0:

validPair(Result) :-
    validPair(0, 0, Result).

然后我们处理我们的基本情况.由于我们从 0 开始，因此基本情况是上限.我们本可以反过来，这真的只是一个选择.请注意，这里的删减意味着我们不必担心在以下子句中 Y 优于 100，因为在这种情况下它们不会被执行.

Then we handle our base case. Since we started from 0, the base case is the upper bound. We could have went the other way around, it's just a choice really. Note that the cut here means that we won't have to worry about Y being superior to 100 in our following clauses since they won't be executed in that case.

validPair(_X, 101, []) :- !.

现在的情况是 X 符合 100 的总和的正确限制.我们首先检查一切是否正常，然后我们使用 !/0 谓词再次阻止执行到达我们的最后一个子句，因为那没有意义.完成后，我们只需 avec 计算有趣的值并将它们添加到列表中.

Here is now the case where X fits the correct limits for the sum to be under 100. We first check that everything is ok and then we use the !/0 predicate to once more prevent the execution to reach our last clause since that wouldn't make sense. After it's done we just avec to calculate the interesting values and add them to the list.

validPair(X, Y, [[X, Y, Sum, Product]|R]) :-
    Limit is min(100 - Y, Y),
    X =< Limit,
    !,
    Sum is X + Y,
    Product is X * Y,
    NextX is X + 1,
    validPair(NextX, Y, R).

剩下要处理的唯一情况是 X 超过我们固定的限制，以便总和低于 100.当这种情况发生时，我们重新开始下一个 Y 并将 X 重置为 0.

The only case left to handle is when X goes above the limit we fixed so that the sum is under 100. When that happens we start again with the next Y and reset X to 0.

validPair(_X, Y, R) :-
    NextY is Y + 1,
    validPair(0, NextY, R).

如果有任何问题，请在评论中要求澄清.

If anything troubles you please ask for clarification in comments.

注意:这里使用的切割是红色切割——即谓词的正确性完全取决于子句的顺序.这是不好的做法.尝试用适当的保护来补充它们(例如 X =<100)，这将是一个很好的补充:)

Note: the cuts used here are red cuts - ie the correctness of the predicate totally depends on the order of the clauses. It's bad practise. Try to supplement them with proper guards (like X =< 100 for example), it'd be a good addition :)

现在让我们审核您的代码 :D我将首先评论风格:在这个子句中(因为它没有正文，所以称为事实)，您只使用 N 和 X 一次，即您不关心存储它们的值.在这种情况下，我们用 _ 前缀他们的名字，或者只使用匿名变量 _:

Now let's audit your code :D I'll start by commenting on the style: In this clause (called fact since it has no body), you use N and X only once ie you do not care about storing their value. In this case, we prefix their name with a _ or just use the anonymous variable _:

genList(100,N, X,[]).

变成

genList(100, _N, _X, []).

或

genList(100, _, _, []).

这里与 S 相同.本条不使用.它仅用于第一个.如果您也想在这里记录它在其他子句中的使用，您可以用 _ 或 _Sum 替换它(好的做法).然后，您使用两个变量来保存完全相同的值.它对这里没有兴趣.只需使用 Sum 作为第一个参数调用你的下一个 genList/4 而不是为此声明一个新变量.Y 和 N1 也一样.该子句的正确版本如下:

Same thing here with S. It's not used in this clause. It's only used in the first one. You can replace it by _ or _Sum if you want to document its use in the other clause here too (good practise). Then, you use two variables to hold the exact same value. It has no interest here. Just call your next genList/4 with Sum as first argument instead of declaring a new variable just for that. Same thing with Y and N1. A proper version of this clause turns:

genList(S,N, X,[[X,Y,Sum,Product]|Xs]):-
    Y is N+1,
    Sum is X+Y,
    NewS is Sum,
    Sum<101,
    Product is X*Y,
    N1 is N+1,
    genList(NewS,N1, X,Xs).

进入

genList(_PreviousSum, N, X,[[X, Y, Sum, Product]|Xs]):-
    Y is N+1,
    Sum is X + Y,
    Sum<101,
    Product is X * Y,
    genList(Sum, Y, X, Xs).

你的最后一个子句有一个算术问题:N + X 只是术语 +(N, X).它不是 N + X 的值.您必须像在其他子句中一样使用 is/2 谓词.与 S 的第二个子句相同的问题.那些小的编辑变成:

Your last clause has an issue with arithmetic: N + X is just the term +(N, X). It's not the value N + X. You have to use the is/2 predicate just as in your other clauses. Same issue as the second clause for S. Those little edits turn:

genList(S,N,X,Q):-
    N+X < 101,
    NextX is X + 1,
    genList(0,NextX,NextX,Q).

进入

genList(_PreviousSum, N, X, Q) :-
    Sum is N + X,
    Sum < 101,
    NextX is X + 1,
    genList(0, NextX, NextX, Q).

所以，目前你修正的程序看起来像:

So, at the moment your corrected program looks like:

genList(100, _N, _X, []).
genList(_PreviousSum, N, X,[[X, Y, Sum, Product]|Xs]):-
    Y is N+1,
    Sum is X + Y,
    Sum<101,
    Product is X * Y,
    genList(Sum, Y, X, Xs).
genList(_PreviousSum, N, X, Q) :-
    Sum is N + X,
    Sum < 101,
    NextX is X + 1,
    genList(0, NextX, NextX, Q).

由于它只是样式编辑，因此不会改变其行为.

Since it was just style edits, it doesn't change its behavior.

现在让我们看看它有什么问题，不是在风格上，而是在逻辑上.首先，基本情况.这里一切都很好.你检查总和是否是你的上限，如果它是返回 [].完美！

Now let's look at what was wrong about it, not in the style, but in the logic. First, the base case. Here everything is fine. You check for the sum being your upper bound and if it is return []. Perfect!

genList(100, _N, _X, []).

现在，您的内部递归".几乎没问题.让我们看看让我烦恼的细节:你有一个值保存你之前的总和，但计算一个新的值并根据上限 + 1 重新测试它.更好的主意是测试 PreviousSum 对<代码><100 并删除 Sum <;101 测试.最好证明您为此有争论的事实是合理的！另外，更容易理解的是，它是用来防止在该限制情况下执行该子句的.所以，

Now, your "inner recursion". It's almost fine. Let's look at the detail that bugs me: you have a value that holds your previous sum, but compute a new one and retest it against the upper bound + 1. a better idea would be to test PreviousSum against < 100 and to remove the Sum < 101 test. It'd better justify the fact that you have an argument just for that! Plus it's more understandable that it's guard being used to prevent execution of the clause in that limit case. So,

genList(_PreviousSum, N, X,[[X, Y, Sum, Product]|Xs]):-
    Y is N+1,
    Sum is X + Y,
    Sum<101,
    Product is X * Y,
    genList(Sum, Y, X, Xs).

会变成

genList(PreviousSum, N, X,[[X, Y, Sum, Product]|Xs]):-
    PreviousSum < 100,
    Y is N+1,
    Sum is X + Y,
    Product is X * Y,
    genList(Sum, Y, X, Xs).

请注意，此修改有点风格化，它不会修改程序行为.尽管如此，它仍然使它更具可读性！

Note that this modification is kinda stylistic, it doesn't modify the program behavior. It's still makes it way more readable though!

现在，大灰狼:genList(_PreviousSum, N, X, Q) :-总和为 N + X，总和101,NextX 是 X + 1，genList(0, NextX, NextX, Q).这里有很多话要说.首先，您不需要计算 Sum，因为 PreviousSum 已经拥有该值.然后，应该测试 <100 而不是 <101.然后，应该测试 X >= N，因为只有在这种情况下，您才不想通过第二个子句而是在这个子句中.最后但并非最不重要的一点是，与其用 genList(0, NextX, NextX, Q) 开始新的迭代，不如从 genList(NextX, 0, NextX, Q) 开始.在这里，您没有正确重置值.结果子句是:

Now, the big bad wolf: genList(_PreviousSum, N, X, Q) :- Sum is N + X, Sum < 101, NextX is X + 1, genList(0, NextX, NextX, Q). Many things to say here. First and once again, you do not need to compute Sum since PreviousSum already holds the value. Then, it should be tested for < 100 instead of < 101. Then, it should be tested that X >= N, because that's only in that case that you do not want to go through your second clause but in this one instead. And last but not least, instead of starting a new iteration with genList(0, NextX, NextX, Q) you should start it with genList(NextX, 0, NextX, Q). Here you didn't reset properly the values. The resulting clause is:

genList(PreviousSum, N, X, Q) :-
    PreviousSum < 100,
    N >= X,
    NextX is X + 1,
    genList(NextX, 0, NextX, Q).

如您所见，我们知道如果 N >= X，我们不能通过我们的第二个子句.我们应该添加适当的测试以确保它是正确的:

As you saw, we know formalized that we can't go through our second clause if N >= X. We should add to it the proper test to be assured that it's correct:

genList(PreviousSum, N, X,[[X, Y, Sum, Product]|Xs]):-
    PreviousSum < 100,
    N < X,
    Y is N+1,
    Sum is X + Y,
    Product is X * Y,
    genList(Sum, Y, X, Xs).

大功告成，你的程序是正确的！

Here you're done, your program is correct!

最终版本是:

genList(100, _N, _X, []).
genList(PreviousSum, N, X,[[X, Y, Sum, Product]|Xs]):-
    PreviousSum < 100,
    N < X,
    Y is N+1,
    Sum is X + Y,
    Product is X * Y,
    genList(Sum, Y, X, Xs).
genList(PreviousSum, N, X, Q) :-
    PreviousSum < 100,
    N >= X,
    NextX is X + 1,
    genList(NextX, 0, NextX, Q).

变量命名还是很差的.更清晰的版本是:

The variable naming is still poor. A clearer version would be:

genList(100, _X, _Y, []).
genList(PreviousSum, X, Y,[[X, Y, Sum, Product]|Xs]):-
    PreviousSum < 100,
    X < Y,
    NewX is X + 1,
    Sum is X + Y,
    Product is X * Y,
    genList(Sum, NewX, Y, Xs).
genList(PreviousSum, X, Y, Q) :-
    PreviousSum < 100,
    X >= Y,
    NextY is Y + 1,
    genList(NextY, 0, NextY, Q).

这里你仍然有一个问题(是的，它永远不会结束:D):在计算总和等之前增加变量的事实意味着你跳过了一些值.尝试增加之后.让它作为练习:)

Here you still have a problem (yeah it nevers ends :D): the fact that you increment your variables BEFORE calculating the sum product etc means that you skip some values. Try to increment after. It's let as an exercise :)

这篇关于序言列表构建的更多麻烦的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！