0

N次元ベクトルのセットに対して最小の支配ベクトルを構築するプログラムを作成する必要があります。ベクトルのセットSの支配的なベクトルは、i番目の成分がS内のすべてのベクトルのi番目の成分以上であり、iがベクトルのすべての次元に及ぶベクトルとして定義されます。寸法Nは、ユーザーからの入力として受け取る必要があります。

4

2 に答える 2

0

Prologにはベクトルがありません。リスト、またはアリティNの構造体を使用できます。2番目のケースでは、もちろんNは許可されている最大アリティよりも小さくする必要があります（SWI-Prologの長さは無制限です...）

リストを使用する場合は、このコードで十分です。Nはリストの長さから暗黙的であると思います。

'minimal dominating vector'([V|Vs], Min) :-
  'minimal dominating vector'(Vs, V, Min).

'minimal dominating vector'([], M, M).
'minimal dominating vector'([V|Vs], MinSoFar, Min) :-
   maplist(min, V, MinSoFar, Updated),
   'minimal dominating vector'(Vs, Updated, Min).

min(X, Y, M) :- X < Y -> M = X ; M = Y.

テスト：

?- 'minimal dominating vector'(["abc","aab","uaa"],M),format('~s',[M]).
aaa
M = [97, 97, 97].

Prologにmaplist/4がない場合（P＃のこの詳細を思い出せません）、に置き換えmaplist(min, V, MinSoFar, Updated),てminvect(V, MinSoFar, Updated),、この定義を追加します

minvect([], [], []).
minvect([N|Ns], [M|Ms], [R|Rs]) :- min(N,M,R), !, minvect(Ns,Ms,Rs).

注意してください、私が数年前にP＃を試したとき、私はそれが非常に遅く、記憶が空いていることに気づきました。大きなアレイがある場合は、LINQを使用することをお勧めします

于 2012-11-20T15:35:05.367 に答える
0

シリアル実装：

fnt(M,N) :-
    fnt2(M,N,0,[]).

fnt2(_,N,N,Ds) :-
    reverse(Ds,R),
    write(R).
fnt2(M,N,K,Ds) :-
    column(M,K,Col),
    max_list(Col,H),
    K2 is K+1,
    fnt2(M,N,K2,[H|Ds]).


row(M, N, Row) :-
    nth(N, M, Row).

column(M, N, Col) :-
    transpose(M, MT),
    row(MT, N, Col).

symmetrical(M) :-
    transpose(M, M).

transpose([[]|_], []) :- !.
transpose([[I|Is]|Rs], [Col|MT]) :-
    first_column([[I|Is]|Rs], Col, [Is|NRs]),
    transpose([Is|NRs], MT).

first_column([], [], []).
first_column([[]|_], [], []).
first_column([[I|Is]|Rs], [I|Col], [Is|Rest]) :-
    first_column(Rs, Col, Rest).

nth(0,[X|_],X).
            nth(N,[_|T],R):- M is N-1,nth(M,T,R).

max_list([H], H).
max_list([H|T], M2) :- 
  max_list(T, M),
  M2 is max(H, M).

並列実装（マイナーな調整）

fnt(M,N) :-
    fnt2(M,N,0,[]).

fnt2(_,N,N,Ds) :-
    reverse(Ds,R),
    write(R).
fnt2(M,N,K,Ds) :-
    column(M,K,Col),
    max_list(Col,H),
    K2 is K+1,
    fork(fnt2(M,N,K2,[H|Ds])).


row(M, N, Row) :-
    nth(N, M, Row).

column(M, N, Col) :-
    transpose(M, MT),
    row(MT, N, Col).

symmetrical(M) :-
    transpose(M, M).

transpose([[]|_], []) :- !.
transpose([[I|Is]|Rs], [Col|MT]) :-
    first_column([[I|Is]|Rs], Col, [Is|NRs]),
    transpose([Is|NRs], MT).

first_column([], [], []).
first_column([[]|_], [], []).
first_column([[I|Is]|Rs], [I|Col], [Is|Rest]) :-
    first_column(Rs, Col, Rest).

nth(0,[X|_],X).
            nth(N,[_|T],R):- M is N-1,nth(M,T,R).

max_list([H], H).
max_list([H|T], M2) :- 
  max_list(T, M),
  M2 is max(H, M).

reverse(A,R) :- reverse(A,[],R).
reverse([X|Y],Z,W) :- reverse(Y,[X|Z],W).
reverse([],X,X).

テスト：

time(fnt([[1,2,3,56],[14,5,6,43],[7,8,9,22]],4)).
于 2012-11-21T09:49:58.433 に答える