Prolog - 从两个已排序的列表创建第三个排序的列表

发布于 2024-11-09 09:09:44 字数 581 浏览 0 评论 0原文

我正在尝试从 Prolog 中的两个已排序列表中获取第三个排序列表。算法如下： 1.比较两个列表的头部 1.1 如果第一个小于或等于第二个，则将其插入到第三个列表中，然后将其从第一个列表中删除。 1.2 否则，将第二个列表的头部插入到第三个列表中，并将其从第二个列表中删除。 2. 重复这些步骤，直到一个列表为空。

理论上这应该可行，但我缺少一些东西。

这是我的代码：

insSort([],[],[]).
insSort([],L,L).
insSort(L,[],L).
insSort([H1 | T1],[H2 | T2],L) :- H1 =< H2,
                                    append([H1],[],L1),
                                    insSort(T1,[H2 | T2],L1),L=L1,!.

insSort([H1 | T1],[H2 | T2],L) :- append([H2],[],L1),
                                    insSort(T2,[H1 | T1],L1),L=L1.

原文

I'm trying to obtain a third sorted list from two already sorted lists in Prolog.
The algorithm is the following:
1. Compare the heads of the two lists
1.1 if the first is less or equal to the second, insert it into the third list and then remove it from the first list.
1.2 else, insert the head of the second list into the third and remove it from the second.
2. repeat these steps until one list is empty.

In theory this should work, but there's something I'm missing.

Here's my code:

insSort([],[],[]).
insSort([],L,L).
insSort(L,[],L).
insSort([H1 | T1],[H2 | T2],L) :- H1 =< H2,
                                    append([H1],[],L1),
                                    insSort(T1,[H2 | T2],L1),L=L1,!.

insSort([H1 | T1],[H2 | T2],L) :- append([H2],[],L1),
                                    insSort(T2,[H1 | T1],L1),L=L1.

分享到QQ

分享到微博

如果你对这篇内容有疑问，欢迎到本站社区发帖提问参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。

发布评论

需要登录才能够评论，你可以免费注册一个本站的账号。

别低头，皇冠会掉 2024-11-16 09:09:44

我认为您误解了 Prolog 变量的行为方式。为变量分配值后（术语是“统一”），您将无法更改它。因此，当您将 [H1] 的值分配给 L1（使用 append 以相当复杂的方式）时，另一个 insSort 不能用它来返回结果。修复代码的方法如下：

insSort([],[],[]).
insSort([],L,L).
insSort(L,[],L).
insSort([H1 | T1],[H2 | T2],L) :- H1 =< H2,
                                  append([H1],L1,L),
                                  insSort(T1,[H2 | T2],L1),!.

insSort([H1 | T1],[H2 | T2],L) :- append([H2],L1,L),
                                  insSort(T2,[H1 | T1],L1).

这样，L 将变为 [H1|L1]，其中我们知道 H1< 的值/code> 我们稍后将通过再次调用 insSort 来计算 L1 的值。

另外，这里不需要使用 append ，类似 L = [H1|L1] 就足够了。

I think you misunderstand how Prolog variables behave. After you assign a value to a variable (the term is “unify”), you can't ever change it. So when you assign the value of [H1] to L1 (in a quite complicated way using append), another insSort can't use it to return the result. A way to fix your code would be like this:

insSort([],[],[]).
insSort([],L,L).
insSort(L,[],L).
insSort([H1 | T1],[H2 | T2],L) :- H1 =< H2,
                                  append([H1],L1,L),
                                  insSort(T1,[H2 | T2],L1),!.

insSort([H1 | T1],[H2 | T2],L) :- append([H2],L1,L),
                                  insSort(T2,[H1 | T1],L1).

This way, L is going to be [H1|L1], where we know the value of H1 and we're going to compute the value of L1 in a while by calling insSort again.

Also, there is no need to use append here, something like L = [H1|L1] would suffice.

回复收藏 0 原文

~没有更多了~