我也来试着出一题：我很喜欢的一个案例---民主的海盗

代码:


:- ensure_loaded(library(lists)).

gen_list([], 0, _).
gen_list([H|T], N, H) :- NewN is N - 1, gen_list(T, NewN, H).

payoff(0, L0, L1, P, _, P) :- length(L0, N), gen_list(L1, N, 0).
payoff(NP, [H0|T0], [H1|T1], P, M, CP) :-
H0 =< M, !,
NewNP is NP - 1,
H1 is H0 + 1,
NewCP is CP + H1,
payoff(NewNP, T0, T1, P, M, NewCP).
payoff(NP, [_|T0], [0|T1], P, M, CP) :-
payoff(NP, T0, T1, P, M, CP).

payoff(0, L0, L1, 0) :- length(L0, N), gen_list(L1, N, 0).
payoff(NP, L0, L1, P) :-
msort(L0, L0S), nth1(NP, L0S, M), payoff(NP, L0, L1, P, M, 0).

ending(X, 1, [X]) :- !.
ending(X, N, L) :-
N0 is N - 1,
NP is N0 // 2,
ending(X, N0, L0),
payoff(NP, L0, L1, P),
(X >= P ->
R is X - P,
L = [R|L1]
;
L = [-1|L0]
).


wdx04 写道:

代码:


:- ensure_loaded(library(lists)).

gen_list([], 0, _).
gen_list([H|T], N, H) :- NewN is N - 1, gen_list(T, NewN, H).

payoff(0, L0, L1, P, _, P) :- length(L0, N), gen_list(L1, N, 0).
payoff(NP, [H0|T0], [H1|T1], P, M, CP) :-
H0 =< M, !,
NewNP is NP - 1,
H1 is H0 + 1,
NewCP is CP + H1,
payoff(NewNP, T0, T1, P, M, NewCP).
payoff(NP, [_|T0], [0|T1], P, M, CP) :-
payoff(NP, T0, T1, P, M, CP).

payoff(0, L0, L1, 0) :- length(L0, N), gen_list(L1, N, 0).
payoff(NP, L0, L1, P) :-
msort(L0, L0S), nth1(NP, L0S, M), payoff(NP, L0, L1, P, M, 0).

ending(X, 1, [X]) :- !.
ending(X, N, L) :-
N0 is N - 1,
NP is N0 // 2,
ending(X, N0, L0),
payoff(NP, L0, L1, P),
(X >= P ->
R is X - P,
L = [R|L1]
;
L = [-1|L0]
).


代码说明：
谓词 gen_list(-L, +N, +X)： 将L合一为由N个X组成的列表。
谓词 payoff(+N, +L0, -L1, -P)：需要收买的人数为N，当前海盗死后的金子分布为L0，以最小代价收买到N个海盗之后的分布为L1，收买所需金子数为P

　　10名海盜搶得了窖藏的100塊金子，並打算瓜分這些戰利品。這是一些講民主的海盜（當然是他們自己特有的民主），他們的習慣是按下面的方式進行分配：最厲害的一名海盜提出分配方案，然後所有的海盜（包括提出方案者本人）就此方案進行表決。如果50%或更多的海盜贊同此方案，此方案就獲得通過並據此分配戰利品。否則提出方案的海盜將被扔到海裡，然後下提名最厲害的海盜又重複上述過程。
　　所有的海盜都樂於看到他們的一位同夥被扔進海裏，不過，如果讓他們選擇的話，他們還是寧可得一筆現金。他們當然也不願意自己被扔到海裏。所有的海盜都是有理性的，而且知道其他的海盜也是有理性的。此外，沒有兩名海盜是同等厲害的——這些海盜完全按照厲害的等級排好了座次，並且每個人都清楚自己和其他所有人的等級。這些金塊不能再分，也不允許幾名海盜共有金塊，因為任何海盜都不相信他的同夥會遵守關於共用金塊的安排。這是一夥每人都只為自己打算的海盜。最凶的一名海盜應當提出什麼樣的分配方案才能使他獲得最多的金子呢？
　　為方便起見，我們按照這些海盜的怯懦程度來給他們編號。最怯懦的海盜為1號海盜，次怯懦的海盜為2號海盜，如此類推。這樣最厲害的海盜就應當得到最大的編號，而方案的提出就將倒過來從上至下地進行。
　　分析所有這類策略遊戲的奧妙就在於應當從結尾出發倒推回去。遊戲結束時，你容易知道何種決策有利而何種決策不利。確定了這一點後，你就可以把它用到倒數第2次決策上，如此類推。如果從遊戲的開頭出發進行分析，那是走不了多遠的。其原因在於，所有的戰略決策都是要確定：“如果我這樣做，那麼下一個人會怎樣做？”
　　因此在你以下海盜所做的決定對你來說是重要的，而在你之前的海盜所做的決定並不重要，因為你反正對這些決定也無能為力了。
　　記住了這一點，就可以知道我們的出發點應當是遊戲進行到只剩兩名海盜——即1號和2號——的時候。這時最厲害的海盜是2號，而他的最佳分配方案是一目了然的：100塊金子全歸他一人所有，1號海盜什麼也得不到。由於他自己肯定為這個方案投贊成票，這樣就占了總數的50%，因此方案獲得通過。
　　現在加上3號海盜。1號海盜知道，如果3號的方案被否決，那麼最後將只剩2個海盜，而1號將肯定一無所獲——此外，3號也明白1號瞭解這一形勢。因此，只要3號的分配方案給1號一點甜頭使他不至於空手而歸，那麼不論3號提出什麼樣的分配方案，1號都將投贊成票。因此3號需要分出盡可能少的一點金子來賄賂1號海盜，這樣就有了下面的分配方案： 3號海盜分得99塊金子，2號海盜一無所獲，1號海盜得1塊金子。
　　4號海盜的策略也差不多。他需要有50%的支援票，因此同3號一樣也需再找一人做同黨。他可以給同黨的最低賄賂是1塊金子，而他可以用這塊金子來收買2號海盜。因為如果4號被否決而3號得以通過，則2號將一文不名。因此，4號的分配方案應是：99塊金子歸自己，3號一塊也得不到，2號得1塊金子，1號也是一塊也得不到。
　　5號海盜的策略稍有不同。他需要收買另兩名海盜，因此至少得用2塊金子來賄賂，才能使自己的方案得到採納。他的分配方案應該是：98塊金子歸自己，1塊金子給3號，1塊金子給1號。
　　這一分析過程可以照著上述思路繼續進行下去。每個分配方案都是唯一確定的，它可以使提出該方案的海盜獲得盡可能多的金子，同時又保證該方案肯定能通過。照這一模式進行下去，10號海盜提出的方案將是96塊金子歸他所有，其他編號為偶數的海盜各得1塊金子，而編號為奇數的海盜則什麼也得不到。這就解決了10名海盜的分配難題。
　　Omohundro的貢獻是他把這一問題擴大到有500名海盜的情形，即500名海盜瓜分100塊金子。顯然，類似的規律依然成立——至少是在一定範圍內成立。事實上，前面所述的規律直到第200號海盜都成立。 200號海盜的方案將是：從1到199號的所有奇數號的海盜都將一無所獲，而從2到198號的所有偶數號海盜將各得1塊金子，剩下的1塊金子歸200號海盜自己所有。
　　乍看起來，這一論證方法到200號之後將不再適用了，因為201號拿不出更多的金子來收買其他海盜。但是即使分不到金子，201號至少還希望自己不會被扔進海裏，因此他可以這樣分配：給1到199號的所有奇數號海盜每人1塊金子，自己一塊也不要。
　　202號海盜同樣別無選擇，只能一塊金子都不要了——他必須把這100塊金子全部用來收買100名海盜，而且這100名海盜還必須是那些按照201號方案將一無所獲的人。由於這樣的海盜有101名，因此202號的方案將不再是唯一的——賄賂方案有101種。
　　203號海盜必須獲得102張贊成票，但他顯然沒有足夠的金子去收買101名同夥。因此，無論提出什麼樣的分配方案，他都註定會被扔到海裏去喂魚。不過，儘管203號命中註定死路一條，但並不是說他在遊戲進程中不起任何作用。相反，204號現在知道，203號為了能保住性命，就必須避免由他自己來提出分配方案這麼一種局面，所以無論204號海盜提出什麼樣的方案，203號都一定會投贊成票。這樣204號海盜總算僥倖揀到一條命：他可以得到他自己的1票、203號的1票、以及另外100名收買的海盜的贊成票，剛好達到保命所需的50%。獲得金子的海盜，必屬於根據202號方案肯定將一無所獲的那101名海盜之列。
　　205號海盜的命運又如何呢？他可沒有這樣走運了。他不能指望203號和204號支持他的方案，因為如果他們投票反對205號方案，就可以幸災樂禍地看到205號被扔到海裏去喂魚，而他們自己的性命卻仍然能夠保全。這樣，無論205號海盜提出什麼方案都必死無疑。206號海盜也是如此——他肯定可以得到205號的支持，但這不足以救他一命。類似地，207號海盜需要104張贊成票——除了他收買的100張贊成票以及他自己的1張贊成票之外，他還需3張贊成票才能免於一死。他可以獲得205號和206號的支援，但還差一張票卻是無論如何也弄不到了，因此207號海盜的命運也是下海喂魚。
　　208號又時來運轉了。他需要104張贊成票，而205、206、207號都會支援他，加上他自己一票及收買的100票，他得以過關保命。獲得他賄賂的必屬於那些根據204號方案肯定將一無所獲的人（候選人包括2到200號中所有偶數號的海盜、以及201、203、204號）。
　　現在可以看出一條新的、此後將一直有效的規律：那些方案能過關的海盜（他們的分配方案全都是把金子用來收買100名同夥而自己一點都得不到）相隔的距離越來越遠，而在他們之間的海盜則無論提什麼樣的方案都會被扔進海裏——因此為了保命，他們必會投票支持比他們厲害的海盜提出的任何分配方案。得以避免葬身魚腹的海盜包括201、202、204、208、216、232、264、328、456號，即其號碼等於200加2的某一方冪的海盜。
　　現在我們來看看哪些海盜是獲得賄賂的幸運兒。分配賄賂的方法是不唯一的，其中一種方法是讓201號海盜把賄賂分給1到199號的所有奇數編號的海盜，讓202號分給2到200號的所有偶數編號的海盜，然後是讓204號賄賂奇數編號的海盜，208號賄賂偶數編號的海盜，如此類推，也就是輪流賄賂奇數編號和偶數編號的海盜。
　　結論是：當500名海盜運用最優策略來瓜分金子時，頭44名海盜必死無疑，而456號海盜則給從1到199號中所有奇數編號的海盜每人分1塊金子，問題就解決了。由於這些海盜所實行的那種民主制度，他們的事情就搞成了最厲害的一批海盜多半都是下海喂魚，不過有時他們也會覺得自己很幸運——雖然分不到搶來的金子，但總可以免於一死。只有最怯懦的200名海盜有可能分得一份髒物，而他們之中又只有一半的人能真正得到一塊金子，的確是怯懦者繼承財富。

wdx04 写道:

代码:


:- ensure_loaded(library(lists)).

gen_list([], 0, _).
gen_list([H|T], N, H) :- NewN is N - 1, gen_list(T, NewN, H).

payoff(0, L0, L1, P, _, P) :- length(L0, N), gen_list(L1, N, 0).
payoff(NP, [H0|T0], [H1|T1], P, M, CP) :-
H0 =< M, !,
NewNP is NP - 1,
H1 is H0 + 1,
NewCP is CP + H1,
payoff(NewNP, T0, T1, P, M, NewCP).
payoff(NP, [_|T0], [0|T1], P, M, CP) :-
payoff(NP, T0, T1, P, M, CP).

payoff(0, L0, L1, 0) :- length(L0, N), gen_list(L1, N, 0).
payoff(NP, L0, L1, P) :-
msort(L0, L0S), nth1(NP, L0S, M), payoff(NP, L0, L1, P, M, 0).

ending(X, 1, [X]) :- !.
ending(X, N, L) :-
N0 is N - 1,
NP is N0 // 2,
ending(X, N0, L0),
payoff(NP, L0, L1, P),
(X >= P ->
R is X - P,
L = [R|L1]
;
L = [-1|L0]
).


代码说明：
谓词 gen_list(-L, +N, +X)： 将L合一为由N个X组成的列表。
谓词 payoff(+N, +L0, -L1, -P)：需要收买的人数为N，当前海盗死后的金子分布为L0，以最小代价收买到N个海盗之后的分布为L1，收买所需金子数为P

Mercury Liao 写道:
能大概讲一下编程的思路吗？
特别是，怎么算出决定给谁金子，不给谁金子？

wdx04 写道:

Mercury Liao 写道:
能大概讲一下编程的思路吗？
特别是，怎么算出决定给谁金子，不给谁金子？

首先确定需要收买多少人(NP=除自己以外的海盗数//2)，然后递归计算“假如我被扔进海里，下一个人如何分配金子”(下一方案)。如果希望某人支持你，就必须给他比下一方案更多的金子。同时你又希望花费尽可能少的金子，因此就把所有人在下一方案下获得的金子数量由低到高排序，只花钱收买排在前面的NP个人就行(排序之后位置信息丢失了，所以我这里采用的是一种简化算法，排序后取第NP个人的金子数M，然后把所有金子数<=M的人当作潜在的收买对象，正确性有待论证)，其他人什么也得不到。收买的花费为这NP个人(每人在下一方案下获得的金子数量+1)之和。当这个和小于或等于金子总数时，方案成立，你可以得到剩余的金子；如果这个和大于金子总数，也就是说钱不够收买足够多的海盗，那就只能被扔进海里了。

代码:

%算出除自己以外，还需要多少赞成票。Pirate是剩余海盗数。
need_support(Pirate, Need_Vote) :- N is Pirate - 1, Need_Vote is N // 2.

%将List中，最大的Delete个元素修改为0，并返还为List_Out。
delete_max(List, Delete, List_Out) :-
  Delete > 0 ->
  max_list(List, Max), nth1(N, List, Max), replace(List, N, 0, Newlist), D is Delete - 1, delete_max(Newlist, D, List_Out);
  List_Out = List.

list_plus([]) --> [], !.
list_plus(List) --> {List = [H|T], H1 is H + 1}, [H1], list_plus(T).

%当只剩2个海盗时，所有的金子都是海盗1的。
proposal(Gold, 2, [Gold, 0]).

proposal(Gold, Pirate, Proposal) :-
  Surplus is Pirate - 1, proposal(Gold, Surplus, NextProposal), list_plus(NextProposal, Pricelist, []),
  need_support(Pirate, Need), Delete is Surplus - Need,
  delete_max(Pricelist, Delete, Paylist), sumlist(Paylist, Pay),
  (Pay > Gold -> Proposal = [-1|Paylist] ; Get is Gold - Pay, Proposal = [Get|Paylist]).


ending(Gold, Pirate, Get) :-
  proposal(Gold, Pirate, Proposal), nth1(1, Proposal, G),
  (G \= -1 -> Get = Proposal ; P is Pirate - 1, ending(Gold, P, NextProposal), Get = [-1|NextProposal]).

ending(Gold, Pirate, Index, Get) :- ending(Gold, Pirate, Get_list), nth1(Index, Get_list, Get).

%将List中第Index个元素以With替换，并输出为ListOut。
replace(List, Index, With, ListOut) :-
  Idx is Index - 1, length(Before,Idx),
  append(Before, [_Discard|Rest], List),
  append(Before, [With|Rest], ListOut).

Mercury Liao 写道:
那我的思路跟你的是一样的，
但是…我的程序跑得慢得多，
不晓得我的代码哪里有多余计算，
500名海盗的情况下甚至是out of local stack。

还有一个更严重的问题，按我的代码，
执行ending(100, 202, Get1).得到的是Get1 = [0, 0, 1, 0, 1, 0, 1, 0, 1|...]，
而执行ending(100, 204, Get2)时，得到的是Get2 = [0, 0, 0, 0, 1, 0, 1, 0, 1|...]，
也就是说，当海盗数为204人时我的程序是错的，
因为程序如果正确的话，应该后面202名海盗在Get1与Get2获得的金子数要是不一样的，
也就是说，在Get1能得到金子的海盗，在Get2得不到金子，
（因为当只有203名海盗时，海盗1必死无疑，剩下的202名海盗可以按Get1分配；
而当总数有204名海盗时，如果海盗1提出的Get2方案让后面202名海盗拿的和Get1一样多，
那按照规则，后面202名全会投反对票，
因为得到的金子数一样的话，他们乐于见到比自己强悍的海盗被丢下海。）
不晓得你的程序是多了什么条件，使其能在这个问题上得到正确的解？

代码:


label_list([H|L1], [H-N|L2], N) :- NewN is N + 1, !, label_list(L1, L2, NewN).
label_list([], [], _).
label_list(L, La) :- label_list(L, La, 1).

first_n_labels(_, 0, Labels, LabelsAc) :- !, msort(LabelsAc, Labels).
first_n_labels([_-V|Las], N, Labels, LabelsAc) :- NewN is N - 1, first_n_labels(Las, NewN, Labels, [V|LabelsAc]).
first_n_labels(Las, N, Labels) :- first_n_labels(Las, N, Labels, []).

delete_labeled([_|L1], [N|Labels], [0|L2], N) :- NewN is N + 1, !, delete_labeled(L1, Labels, L2, NewN).
delete_labeled(L, [], L, _) :- !.
delete_labeled([H|L1], Labels, [H|L2], N) :- NewN is N + 1, !, delete_labeled(L1, Labels, L2, NewN).
delete_labeled(L1, Labels, L2) :- delete_labeled(L1, Labels, L2, 1).

delete_max(L, 0, L) :- !.
delete_max(L1, Delete, L2) :-
label_list(L1, La),
keysort(La, Las),
reverse(Las, Lasv),
first_n_labels(Lasv, Delete, Labels),
delete_labeled(L1, Labels, L2).


wdx04 写道:

Mercury Liao 写道:
能大概讲一下编程的思路吗？
特别是，怎么算出决定给谁金子，不给谁金子？

首先确定需要收买多少人(NP=除自己以外的海盗数//2)，然后递归计算“假如我被扔进海里，下一个人如何分配金子”(下一方案)。如果希望某人支持你，就必须给他比下一方案更多的金子。同时你又希望花费尽可能少的金子，因此就把所有人在下一方案下获得的金子数量由低到高排序，只花钱收买排在前面的NP个人就行(排序之后位置信息丢失了，所以我这里采用的是一种简化算法，排序后取第NP个人的金子数M，然后把所有金子数<=M的人当作潜在的收买对象，正确性有待论证)，其他人什么也得不到。收买的花费为这NP个人(每人在下一方案下获得的金子数量+1)之和。当这个和小于或等于金子总数时，方案成立，你可以得到剩余的金子；如果这个和大于金子总数，也就是说钱不够收买足够多的海盗，那就只能被扔进海里了。

wdx04 写道:

Mercury Liao 写道:
那我的思路跟你的是一样的，
但是…我的程序跑得慢得多，
不晓得我的代码哪里有多余计算，
500名海盗的情况下甚至是out of local stack。

还有一个更严重的问题，按我的代码，
执行ending(100, 202, Get1).得到的是Get1 = [0, 0, 1, 0, 1, 0, 1, 0, 1|...]，
而执行ending(100, 204, Get2)时，得到的是Get2 = [0, 0, 0, 0, 1, 0, 1, 0, 1|...]，
也就是说，当海盗数为204人时我的程序是错的，
因为程序如果正确的话，应该后面202名海盗在Get1与Get2获得的金子数要是不一样的，
也就是说，在Get1能得到金子的海盗，在Get2得不到金子，
（因为当只有203名海盗时，海盗1必死无疑，剩下的202名海盗可以按Get1分配；
而当总数有204名海盗时，如果海盗1提出的Get2方案让后面202名海盗拿的和Get1一样多，
那按照规则，后面202名全会投反对票，
因为得到的金子数一样的话，他们乐于见到比自己强悍的海盗被丢下海。）
不晓得你的程序是多了什么条件，使其能在这个问题上得到正确的解？

我估计第二个问题是delete_max的实现有问题,我自己写了一个delete_max和你的其它代码合起来运行结果是对的。
思路是先给列表的每个元素打上位置标记，然后排序，选取最大的Delete个元素的标记，按标记删除。

代码:


label_list([H|L1], [H-N|L2], N) :- NewN is N + 1, !, label_list(L1, L2, NewN).
label_list([], [], _).
label_list(L, La) :- label_list(L, La, 1).

first_n_labels(_, 0, Labels, LabelsAc) :- !, msort(LabelsAc, Labels).
first_n_labels([_-V|Las], N, Labels, LabelsAc) :- NewN is N - 1, first_n_labels(Las, NewN, Labels, [V|LabelsAc]).
first_n_labels(Las, N, Labels) :- first_n_labels(Las, N, Labels, []).

delete_labeled([_|L1], [N|Labels], [0|L2], N) :- NewN is N + 1, !, delete_labeled(L1, Labels, L2, NewN).
delete_labeled(L, [], L, _) :- !.
delete_labeled([H|L1], Labels, [H|L2], N) :- NewN is N + 1, !, delete_labeled(L1, Labels, L2, NewN).
delete_labeled(L1, Labels, L2) :- delete_labeled(L1, Labels, L2, 1).

delete_max(L, 0, L) :- !.
delete_max(L1, Delete, L2) :-
label_list(L1, La),
keysort(La, Las),
reverse(Las, Lasv),
first_n_labels(Lasv, Delete, Labels),
delete_labeled(L1, Labels, L2).


这个delete_max也可以解决500个海盗时out of local stack的问题，只不过速度还是比较慢。
引起栈溢出的主要原因就是递归深度太高，而减少递归深度的办法就是使用尾递归优化，像我的代码里面只在ending/3里面有一处递归调用不能尾递归优化，而你在proposal/3里面还有一处，对性能影响可能比较大。

Mercury Liao 写道:

wdx04 写道:

Mercury Liao 写道:
能大概讲一下编程的思路吗？
特别是，怎么算出决定给谁金子，不给谁金子？

首先确定需要收买多少人(NP=除自己以外的海盗数//2)，然后递归计算“假如我被扔进海里，下一个人如何分配金子”(下一方案)。如果希望某人支持你，就必须给他比下一方案更多的金子。同时你又希望花费尽可能少的金子，因此就把所有人在下一方案下获得的金子数量由低到高排序，只花钱收买排在前面的NP个人就行(排序之后位置信息丢失了，所以我这里采用的是一种简化算法，排序后取第NP个人的金子数M，然后把所有金子数<=M的人当作潜在的收买对象，正确性有待论证)，其他人什么也得不到。收买的花费为这NP个人(每人在下一方案下获得的金子数量+1)之和。当这个和小于或等于金子总数时，方案成立，你可以得到剩余的金子；如果这个和大于金子总数，也就是说钱不够收买足够多的海盗，那就只能被扔进海里了。

那我的思路跟你的是一样的，
但是…我的程序跑得慢得多，
不晓得我的代码哪里有多余计算，
500名海盗的情况下甚至是out of local stack。

还有一个更严重的问题，按我的代码，
执行ending(100, 202, Get1).得到的是Get1 = [0, 0, 1, 0, 1, 0, 1, 0, 1|...]，
而执行ending(100, 204, Get2)时，得到的是Get2 = [0, 0, 0, 0, 1, 0, 1, 0, 1|...]，
也就是说，当海盗数为204人时我的程序是错的，
因为程序如果正确的话，应该后面202名海盗在Get1与Get2获得的金子数要是不一样的，
也就是说，在Get1能得到金子的海盗，在Get2得不到金子，
（因为当只有203名海盗时，海盗1必死无疑，剩下的202名海盗可以按Get1分配；
而当总数有204名海盗时，如果海盗1提出的Get2方案让后面202名海盗拿的和Get1一样多，
那按照规则，后面202名全会投反对票，
因为得到的金子数一样的话，他们乐于见到比自己强悍的海盗被丢下海。）
不晓得你的程序是多了什么条件，使其能在这个问题上得到正确的解？

代码:

%算出除自己以外，还需要多少赞成票。Pirate是剩余海盗数。
need_support(Pirate, Need_Vote) :- N is Pirate - 1, Need_Vote is N // 2.

%将List中，最大的Delete个元素修改为0，并返还为List_Out。
delete_max(List, Delete, List_Out) :-
  Delete > 0 ->
  max_list(List, Max), nth1(N, List, Max), replace(List, N, 0, Newlist), D is Delete - 1, delete_max(Newlist, D, List_Out);
  List_Out = List.

list_plus([]) --> [], !.
list_plus(List) --> {List = [H|T], H1 is H + 1}, [H1], list_plus(T).

%当只剩2个海盗时，所有的金子都是海盗1的。
proposal(Gold, 2, [Gold, 0]).

proposal(Gold, Pirate, Proposal) :-
  Surplus is Pirate - 1, proposal(Gold, Surplus, NextProposal), list_plus(NextProposal, Pricelist, []),
  need_support(Pirate, Need), Delete is Surplus - Need,
  delete_max(Pricelist, Delete, Paylist), sumlist(Paylist, Pay),
  (Pay > Gold -> Proposal = [-1|Paylist] ; Get is Gold - Pay, Proposal = [Get|Paylist]).


ending(Gold, Pirate, Get) :-
  proposal(Gold, Pirate, Proposal), nth1(1, Proposal, G),
  (G \= -1 -> Get = Proposal ; P is Pirate - 1, ending(Gold, P, NextProposal), Get = [-1|NextProposal]).

ending(Gold, Pirate, Index, Get) :- ending(Gold, Pirate, Get_list), nth1(Index, Get_list, Get).

%将List中第Index个元素以With替换，并输出为ListOut。
replace(List, Index, With, ListOut) :-
  Idx is Index - 1, length(Before,Idx),
  append(Before, [_Discard|Rest], List),
  append(Before, [With|Rest], ListOut).

代码:

proposal(Gold, Pirate, Proposal) :-
  Surplus is Pirate - 1, ending(Gold, Surplus, NextProposal), list_plus(NextProposal, ......

代码:

:- use_module(library(chr)).
:- chr_constraint ending/3, del/2, p/1.


p(N), ending(Gold, Pirate, Get) ==> Pirate < N | Del is Pirate - Pirate // 2, list_plus(Get, GG, []), del(GG, Del).
del(Get, N) <=> N > 0 | N1 is N - 1, max_list(Get, Max), nth1(X, Get, Max), replace(Get, X, 0, G1), del(G1, N1).
ending(Gold, Pirate, Get), del(Proposal, 0) <=>
    sumlist(Proposal, Pay), (Pay =< Gold -> SG is Gold - Pay, NG = [SG|Proposal]; NG = [-1|Get]), NP is Pirate + 1, ending(Gold, NP, NG).


replace(List, Index, With, ListOut) :-
  Idx is Index - 1, length(Before,Idx),
  append(Before, [_Discard|Rest], List),
  append(Before, [With|Rest], ListOut).
 
list_plus([]) --> [], !.
list_plus(List) --> {List = [H|T], H1 is H + 1}, [H1], list_plus(T).

小马过河 写道:98, 0, 1, 0, 1 ？
呵呵，我没有看完全部的资料。但是这个结果。不太智能。。。。
如果这么分配，第一个人拿98个，那4个人都不会同意。第一个死的就是提出这个方案的人。

Mercury Liao 写道:

wdx04 写道:

Mercury Liao 写道:
能大概讲一下编程的思路吗？
特别是，怎么算出决定给谁金子，不给谁金子？

首先确定需要收买多少人(NP=除自己以外的海盗数//2)，然后递归计算“假如我被扔进海里，下一个人如何分配金子”(下一方案)。如果希望某人支持你，就必须给他比下一方案更多的金子。同时你又希望花费尽可能少的金子，因此就把所有人在下一方案下获得的金子数量由低到高排序，只花钱收买排在前面的NP个人就行(排序之后位置信息丢失了，所以我这里采用的是一种简化算法，排序后取第NP个人的金子数M，然后把所有金子数<=M的人当作潜在的收买对象，正确性有待论证)，其他人什么也得不到。收买的花费为这NP个人(每人在下一方案下获得的金子数量+1)之和。当这个和小于或等于金子总数时，方案成立，你可以得到剩余的金子；如果这个和大于金子总数，也就是说钱不够收买足够多的海盗，那就只能被扔进海里了。

感觉上，"排序后取第NP个人的金子数M，然后把所有金子数<=M的人当作潜在的收买对象"，
这句话好像有时会有问题，比如如果<=M-1的有NP-1个，
<=M的有NP+X个，那你收买所有<=M的应该会多收买到不必要的X个人。

代码:

payoff(NP, L0, L1, P) :-
msort(L0, L0S), nth1(NP, L0S, M), payoff(NP, L0, L1, P, M, 0).

代码:

payoff(NP, L0, L1, P) :- payoff(NP, L0, L1, P, 0, 0).