2 
bc(0,N,R,R):- N>0,R is 1,!.
bc(M,0,R,R):- M>0,R is 1,!.
bc(N,N,R,R):- R is 1,!.
bc(M,N,R,R1):- 
    M1 is M - 1, 
    N1 is N - 1, 
    bc(M1,N1,R,R2),
    bc(M1,N,R,R3),
    R1 is R2+R3.

为什么它返回假？

任务是：使用以下公式编写递归程序C(M,N) (0 ≤ m ≤ n )以找出二项式系数：

C(m,0)=C(0,n)=C(n,n)=1
C(m,n)=C(m−1,n−1)+C(m−1,n)

PS：我使用在线编译器 SWISH。

4

1 回答 1

4

首先，让我们正确说明二项式系数的公式。的传统定义c(M, N)将有M >= N >= 0，而不是N >= M >= 0如所述。这很重要，因为给出的公式：

C(m,0)=C(0,n)=C(n,n)=1 C(m,n)=C(m−1,n−1)+C(m−1,n)

假设0 ≤ n ≤ m，而不是所陈述的 ( 0 ≤ m ≤ n)。所以它是不正确的（要么是错误的，要么是你写错了）。此外，C(0, n)不是有效系数，除非n = 0。所以这种情况没有意义，可以省略。它已经被C(m, 0).

问题的错误表述可能是您在结果中得到“错误”的主要原因。

C(n, 0) = C(n, n) = 1将涵盖以下基本（非递归）案例：

bc(N, 0, 1) :- N #>= 0.
bc(N, N, 1) :- N #> 0.    % The N = 0 case is already covered in the first base case

然后根据给定的公式递归处理更一般的情况：

bc(M, N, R) :-
    N #> 0,        % The N = 0 case is already covered in the first base case
    M #> N,        % The M = N case is already covered in the second base case
    R #>= M,       % This constraint prevents unbounded search in non-solution space
    M1 #= M - 1,   % The rest of this is just the given formula
    N1 #= N - 1,
    bc(M1, N1, R1),
    bc(M1, N, R2),
    R #= R1 + R2.

编写 Prolog 谓词时的一些原则：

  • 确保准确、正确地陈述您的问题。这听起来很明显，但在这种情况下是一个问题。

  • 使用 CLP(FD) 进行整数推理。Prolog 的意义在于更具有相关性。使用is/2更为迫切。例如，X is Y * 2如果未绑定，将生成实例化错误Y。但X #= Y * 2会产生潜在的解决方案。如果is/2由于任意要求而必须使用，您可以将其替换回去。

  • 在谓词子句中应用约束，使它们互斥。也就是说，除非它是您想要的，否则对于给定的解决方案，不要让您的谓词以不止一种方式成功。特别是，使您的不同子句不重叠。例如，如果您有一个谓词，其中第一个参数是自然数（非负整数），并且您的基本情况为foo(0, 1).，那么在递归情况下，foo(N, R) :-您需要一个约束N > 0或N #> 0，假设没有另一边在递归情况下可能需要和/或不同的效果或其他参数。

  • 您可以在所需的解决方案空间内约束或绑定变量越多，您的代码就越不会在尝试不是有效解决方案的选项时徘徊，并且在最坏的情况下，由于对此类非解决方案选项缺乏限制而不会终止. 例如，在这个问题中，我们添加了当和R #>= M时为真的约束。如果没有这个限制，Prolog 将探索无限的情况，并在某些情况下导致不终止。N > 0N < MR < M

运行查询：

| ?- bc(3,2,R).

R = 3 ? ;

no
| ?- bc(4,2,R).

R = 6 ? ;

no
| ?-

ETC...

通过使用 CLP(FD) 运算符，您还可以运行如下查询：

| ?- bc(4,X,6).

X = 2 ? ;

no
| ?-

和...

| ?- bc(N, K, 6).

N = 6
K = 1 ? ;

N = 4
K = 2 ? ;

N = 6
K = 5 ? ;

no
| ?- ;
于 2017-11-10T17:45:14.127 回答