4

私は Prolog を初めて使用し、部分配列の最大問題のインスタンスを解決しようとしています。

次の非常にエレガントな C++ コードを取得しました。

int maxSubArray(vector<int> List)
{
    int maxsofar = 0;
    int maxendinghere = 0;
    for (int i = 0; i < List.size(); i++)
    {
        maxendinghere = max(maxendinghere+List[i], 0);
        maxsofar = max(maxsofar, maxendinghere);
    }
    return maxsofar;
}

そして、ここに私のプロローグコードがあります:

max(X,X,X).
max(X,Y,X) :- X>Y.
max(X,Y,Y) :- X<Y. %define max function

prev(L,T,H) :-
   reverse(L,[H|T1]),
   reverse(T,T1).  %split L to H(last element) and T(the remaining list)

f([],0,0).
f(L,M,N) :-
   f(L1,M1,N1),
   prev(L,L1,E),
   max(M1,N,M),
   max(K,0,N), 
   K is N1+E.

から最大合計を取得しようとしますf(L,M,N)。LはリストでMあり、結果です (最大合計は、C++ コードの変数「maxsofar」と同様です)。取得したいのNは、C++ コードの「maxendinghere」としての中間変数です。L以前のリストからの答えを得たいのですL1が、変数の関係は C++ コードとまったく同じです。

ただし、次のクエリは機能しません。

?- f([1,2,3],X,Y).
is/2: Arguments are not sufficiently instantiated

どこに問題があるのか​​わからない。

4

1 に答える 1

3

この回答は、 clpfd に基づくの Prolog ポートを示しています。

:- use_module (ライブラリ( clpfd ))。

zs_maxmum/2次のように定義します。

zs_maxmum(Zs, MSF) :-
   zs_maxmum_(Zs, 0,_, 0,MSF).

zs_maxmum_([], _,_, MSF,MSF).
zs_maxmum_([Z|Zs], MEH0,MEH, MSF0,MSF) :-
   max(0,MEH0+Z)  #= MEH1,
   max(MSF0,MEH1) #= MSF1,
   zs_maxmum_(Zs, MEH1,MEH, MSF1,MSF).

サンプルクエリ:

?- zs_maxmum([-2,1,-3,4,-1,2,1,-5,4], Max).
Max = 6.

?- zs_maxmum([-2,3,4,-5,8,-12,100,-101,7], Max).
Max = 100.

いくつかの注意事項:

  • 実際には配列ではなく、リストを操作します。
  • を含む任意のサブリストを認め[]ます。目標はzs_maxmum([-2,-3,-4], 0)成功します。
于 2015-08-20T07:14:13.273 に答える