Խրված է Prolog ծրագրի հետ

Թվում է, թե խնդրի էությունը մի ֆունկցիա է, որը վերցնում է 10 թվից երկու վեկտոր և վերադարձնում է համընկնման ընդհանուր միավորը:

Առաջինն այն է, որ Prolog-ը գործառույթներ չունի. այն ունի պրեդիկատներ։ Բայց դուք կարող եք հեշտությամբ թարգմանել ֆունկցիայի հայեցակարգը պրեդիկատ հասկացության՝ տրամադրելով փոփոխականներ, որոնք կարող են կապված լինել «ֆունկցիայի» ելքերի հետ.

% Match V1 and V2, and unify M with the match score.
match(V1, V2, M) :- ...

Պարզ չէ, թե ինչպես են վեկտորները համընկնում (բայց ես կարծում եմ, որ դա նույնական գրառումների քանակն է, թե՞ յուրաքանչյուր զույգ մուտքերի միջև բացարձակ տարբերությունների գումարը): Բայց այս պրեդիկատը, հավանաբար, կսահմանվի բազային գործով (0 երկարությամբ ցուցակների համար) և ընդհանուր դեպքով, որը հաշվարկում է այն յուրաքանչյուր ցուցակի գլուխների և ցուցակների վերջում գտնվող ռեկուրսների համար:

match([], [], 0).  % I'm assuming the match score for empty lists is 0.
match([H1|T1], [H2|T2], M) :-
    match_single_entry(H1, H2, M1),  % Somehow compute the score for two single entries.
    match(T1, T2, M2),  % Recurse on the tails.
    M is M1+M2.  % Combine the two scores and bind to the output variable M.

Ես թողել եմ match_single_entry անորոշ: Այն սահմանելուց հետո դուք պետք է փորձեք առաջադրել match-ը տարբեր թեկնածուների վեկտորներով՝ ընդդեմ ընտրողի վեկտորի.

% Let's try getting the match score for adams:
?- match([1,1,1,1,1,1,1,1,1,1], [0,0,0,1,1,1,-1,-1,-1,1], AdamsScore).

AdamsScore = 3 ;

No

Հաջորդ մարտահրավերը մեկ այլ պրեդիկատ գրելն է՝ best_candidates, որը վերցնում է ընտրողի վեկտորը գումարած թեկնածուի վեկտորների բազմությունը, յուրաքանչյուրը գնահատում և վերադարձնում է, այսինքն՝ կապում է BestMatchesին համապատասխանող ելքային փոփոխականին՝ նրանց, ովքեր լավագույնն են գնահատում: Կրկին, այս պրեդիկատը կարող է կրկնվել թեկնածու վեկտորների բազմության վրա՝ սահմանելով բազային դեպք (առանց թեկնածուների, հետևաբար՝ լավագույնների) և ռեկուրսիվ դեպքի, որը միաժամանակ մշակում է մեկ թեկնածու:

Յուրաքանչյուր թեկնածուի վեկտորի գնահատում

Ինչպես նշում եք, թեկնածու վեկտորն ունի անուն, որին հաջորդում են արժեքները: Սա նշանակում է, որ վեկտորը հեշտությամբ կարելի է բաժանել [Name|Values] = V-ով, իսկ Values-ը կարող է փոխանցվել matchին՝ ընտրողների վեկտորի հետ համեմատելու համար:

Մյուս բանը անունները BestMatches ցուցակում պահելն է: best_candidates պրեդիկատը պետք է գնահատի յուրաքանչյուր թեկնածուի վեկտոր՝ ինչ-որ տեղ պահելով այդ միավորները, այնուհետև պետք է գտնի լավագույն միավորը, այնուհետև պետք է անցնի սկզբնական թեկնածուների անունները և ավելացնի դրանք, որոնք նույնքան լավն են, որքան լավագույն միավորը:

Առաջարկվում է ավելացնել նախադրյալ՝ առաջին մասը կատարելու համար.

% Score all vectors, returning a list of scores.
% score_vectors(VoterVector, AllVectors, AllScores)
score_vectors(V, [], []).
score_vectors(V, [H|T], [SH, ST]) :-
    ... score V against H, matching the result against SH.
    ... recurse on T and ST.

(Լրացրե՛ք երկու տողերը ...-ով) Այնուհետև օգտագործեք պարզ նախադրյալ՝ AllScores-ից առավելագույն միավորը գտնելու համար (կամ կարող է ներկառուցված պրեդիկատ դա անելու համար):

Այնուհետև կազմեք մեկ այլ պրեդիկատ, որը կրկնում է բոլոր վեկտորները և միավորները և ընտրում նրանց, որոնք համապատասխանում են լավագույն գնահատականին.

% Pick best candidates.
% pick_best(AllVectors, AllScores, BestScore, BestNames).
pick_best([], [], BS, []).
pick_best([H|T], [SH|ST], BS, [Name|NT]) :-
    H = [Name|Values],
    SH >= BS.
pick_best([H|T], [SH|ST], BS, NT) :-
    H = [Name|Values],
    SH < BS.

Այնուհետև կառուցեք best_candidates այս երեք քայլերից.

best_candidates(VoterVector, CandidateVectors, BestNames) :-
    score_vectors(VoterVector, CandidateVectors, Scores),
    maximum(Scores, BestScore),
    pick_best(CandidateVectors, Scores, BestScore, BestNames).

Ես ցույց կտամ լուծում, որն իրականացվել է SWI-Prolog գրադարանի օգնությամբ (ագրեգատ):

:- [library(aggregate)].

best_candidates(Votes, Candidates, Best) :-
    maplist(count_matched(Votes), Candidates, NamesCounted),
    keysort(NamesCounted, BestDown),
    reverse(BestDown, Best).

count_matched(Votes, [Name|ThisVotes], MatchCount-Name) :-
    aggregate_all(sum(V * T),
        ( nth1(I, Votes, V),
          nth1(I, ThisVotes, T)
        ), MatchCount).

test(BestMatches) :-
    best_candidates(
         [           0,   0,   0,   1,   1,   1,  -1,  -1,  -1,   1],
        [[adams   ,  1,   1,   1,   1,   1,   1,   1,   1,   1,   1],
         [grant   , -1,  -1,  -1,  -1,  -1,  -1,  -1,  -1,  -1,  -1],
         [polk    ,  1,  -1,   1,  -1,   1,  -1,   1,  -1,   1,  -1],
         [jackson ,  1,   0,   1,   0,   1,   0,   1,   0,   1,   0],
         [taft    ,  0,  -1,   0,  -1,   0,  -1,   0,  -1,   0,  -1],
         [ford    ,  1,   1,   1,   1,   0,   0,   0,   0,   0,   0],
         [madison ,  0,   0,   0,   1,  -1,   0,   0,  -1,   1,   1]],
        BestMatches),
    BestMatches = [_-A, _-B, _-C|_],
    writeln([A, B, C]).

փորձարկման արդյունք:

?- test(L).
[madison,ford,adams]
L = [1-madison, 1-ford, 1-adams, -1-jackson, -1-grant, -2-taft, -3-polk].