海盗分金 python 源码

# _*_ coding utf-8 _*_ # Author: houshi01 # Data: 5/25/2020 11:46 # Name: PiratePuzzle # Tools: PyCharm #import random #经济学上有个“海盗分金”模型：是说5个海盗抢得100枚金币，他们按抽签的顺序依次提方案：首先由1号提出分配方案，然后5人表决，投票要超过半数同意方案才被通过，否则他将被扔入大海喂鲨鱼，依此类推。 #假定“每个海盗都是绝顶聪明且很理智”，那么“第一个海盗提出怎样的分配方案才能够使自己的收益最大化？” #result 为分配的最终结果 #payoff 为每个海盗可能得到最大收益 class pirate(object): index = 0 coin = 0 def __init__(self,index,coin): self.index = index self.coin = coin def update_payoff(pirate_number,pirate_total,result,payoff): pirate_index = pirate_total - pirate_number for ix in range(pirate_index+1,pirate_total): if result[ix].coin > payoff[ix].coin: payoff[ix].coin = result[ix].coin def bubble_sort(array): n = len(array) for i in range(n): # Last i elements are already in place for j in range(0, n - i - 1): if array[j].coin > array[j + 1].coin: array[j], array[j + 1] = array[j + 1], array[j] #def myprint(array): # n = len(array) # for ix in range(n): # print("%4d: %4d %4d" % (ix, array[ix].index, array[ix].coin)) # print("\n") def solution(pirate_total, coin_total,result,payoff): #initial 3 pirates pirate_index = pirate_total - 3 result[pirate_index+0].coin = coin_total result[pirate_index+1].coin = 0 result[pirate_index+2].coin = 0 # for pirate_number in range(4,pirate_total+1): vote_number = int(pirate_number / 2) pirate_index = pirate_total - pirate_number # got vote from current location to the last one votes = payoff[pirate_index+2:] bubble_sort(votes) #clean result assigned_coins = 0 for i in range(pirate_total): result[i].coin = 0 #myprint(votes) for i in range(vote_number): result[votes[i].index].coin = votes[i].coin + 1 assigned_coins = assigned_coins + result[votes[i].index].coin #print("[%d]: (%d %d), %d assigned_coins = %d" %(i, votes[i].index, votes[i].coin, result[votes[i].index].coin, assigned_coins )) result[pirate_index+1].coin = 0 result[pirate_index+0].coin = coin_total - assigned_coins if(result[pirate_index].coin < 0): print("There are no more coins for assignment! (%d)" % result[pirate_index].coin) break #myprint(result) update_payoff(pirate_number,pirate_total,result,payoff) #myprint(payoff) print("[%2d, %2d]" % (pirate_number, vote_number + 1), end=':') #for ix in range(0, pirate_total): for ix in range(pirate_index, pirate_total): print(" %2d" % result[ix].coin, end=',') print("\n") def init_array(array, number): for ix in range (0, number): item = pirate(ix,0) array.append(item) if __name__ == "__main__": PIRATE_CNT = 50 COIN_CNT = 100 result = [] payoff = [] init_array(result, PIRATE_CNT) init_array(payoff, PIRATE_CNT) solution(PIRATE_CNT,COIN_CNT,result,payoff)