JAVA高级面试进阶训练营视频教程

admin

一：上代码

#比例法
def rate_method(p,n):
    lst =[] #保存各组席位数
    sum_ =sum(p)    #人数和
    k =0#临时变量
    for i in p:
        lst.append(i/sum_*n)
        k += int(i/sum_*n)

    while k!=n:
        max_ =0
        for i in lst:
            max_ =i if (i -int(i)) > max_- int(max_)else max_  #小鼠的比较
        lst[lst.index(max_)] =int(max_) +1
        k +=1
    for i in lst:
        lst[lst.index(i)] =int(i)  
    print(lst)
           
           
#Q值法：
def q_value(p,n):       #p:保存各组人数的列表，n:席位数
    lst =[] #保存各组席位数
    for i in p:
        lst.append(1) #初始席位数都为1
    lst_ =lst[:]     #临时列表，保存各组Q值
    for i in range(n-len(p)):
        for i in range(len(p)):
            lst_ =p*p/(lst+1)/lst
        max_index=lst_.index(max(lst_))
        lst[max_index] +=1
    print(lst)

#d'Hondt 方法
def d_Hondt(p,n):       #p必须以大到小顺序排序
    lst =[] #保存各组席位数
    a,b=0,0 #保存比值,下一项比值
    for i in p:
        lst.append(0) #初始席位数都为0
    for i in range(n):
        for j in range(len(p)):
            a =p[j]/(i+1)
            if b>a:
                break
            b =p[j]/(i+2)
            lst[j] += 1
        if sum(lst) ==n:    #放在第一个循环内，是考虑到不太可能只除了1就分配好了
            break
    print(lst)

if __name__ =='__main__':
    p =[432,333,235] #从大到小比较好，为了一次性使用所有方法
    n =10
    rate_method(p,n)
    q_value(p,n)
    d_Hondt(p,n)

 

二：席位分配常用的三种方法：

1.比例分配 ：公平而又简单

2.Q值法：（摘自：数学模型-姜启源-）

        设两方人数分别 p1 和 p2 ,占有席位分别是 n1 和 n2 ,则两方每个席位代表的人数分别为 p1/n1 和 p2/n2 .显然仅当 p1/n1 = p2/n2 时席位的分配才是公平的.但是因为人数和席 位都是整数,所以通常 p1/n1 ≠ p2/n2 ,这时席位分配不公平,并且 pi ni (i= 1, 2)数值较大的一方吃亏,或者说对这一方不公平.

         不妨假设 p1/n1 > p2/n2 ,不公平程度可用数值 p1/n1 - p2/n2 衡量.如设 p1 = 120, p2 = 100, n1 = n2 = 10,则 p1/n1 - p2/n2 = 12 - 10 = 2,它衡量的是不 公平的绝对程度,常常无法区分两种程度明显不同的不公平情况.例如上述双方 人数增加为 p1 = 1 020 和 p2 = 1 000,而席位 n1 , n2 不变时, p1/n1 - p2/n2 = 102 - 100 = 2,即绝对不公平程度不变.但是常识告诉我们,后面这种情况的不公 平程度比起前面来已经大为改善了.

        为了改进上述绝对标准,自然想到用相对标准.仍记 p1 , p2 为 A, B 两方的 固定人数, n1 , n2 为两方分配的席位(可变),若 p1/n1 > p2/n2 ,则定义

　　rA ( n1 , n2 ) =(p1 /n1 - p2 /n2)/( p2 /n2)　　　　  (1)           为对 A 的相对不公平度.

若 p2 n2 > p1 n1 ,则定义

　　rB ( n1 , n2 ) =(p2 /n2 - p1/ n1 )/(p1 n1)　　　　(2)　　　　为对 B 的相对不公平度

　　建立了衡量分配不公平程度的数量指标 rA ,rB 后,制定席位分配方案的原 则是使它们尽可能小. 确定分配方案 假设 A, B 两方已分别占有 n1 和 n2 席,利用相对不公平 度 rA 和 rB 讨论,当总席位增加 1 席时,应该分配给 A 还是 B. 不失一般性可设 p1 /n1 > p2 /n2 ,即对 A 不公平.当再分配 1 个席位时,关 于 pi ni (i= 1,2)的不等式可能有以下 3 种情况: 1 . p1/ ( n1 + 1) > p2 /n2 ,这说明即使 A 方增加 1 席,仍然对 A 不公平,所以 这一席显然应分给 A 方. 2 . p1 /(n1 + 1) < p2 /n2 ,说明当 A 方增加 1 席时将变为对 B 不公平,参照 (2)式可计算出对 B 的相对不公平度为　　rB ( n1 + 1, n2 ) =p2 /(n1 + 1) /(p1 /n2)- 1 　　　　(3)3 . p1 /n1 > p2/ ( n2 + 1),即当 B 方增加 1 席时将对 A 不公平,参照(1)式可 计算出对 A 的相对不公平度为

　　rA ( n1 , n2 + 1) =p1 (/ n2 + 1) (p2/ n1) - 1 　　　　(4)

　　(不可能出现 p1 /n1 < p2 /( n2 + 1)的情况.为什么 ?) 因为公平分配席位的原则是使得相对不公平度尽可能地小,所以如果 rB ( n1 + 1, n2 ) < rA ( n1 , n2 + 1) (5) 则这 1 席应分给 A 方;反之则分给 B 方.根据(3),(4)两式,(5)式等价于 (p2 ^2) /(n2 (n2 + 1) )< (p1^2 )/ n1 ( n1 + 1) (6) 还不难证明,上述第 1 种情况的 p1 /( n1 + 1) > p2 /n2 也会导致(6)式.于是我们 的结论是:当(6)式成立时增加的 1 席应分给 A 方,反之则分给 B 方.或者,若记 Qi =( p i^2)/ (ni( ni + 1)),i= 1,2,则增加的 1 席应分给 Q 值较大的一方. 上述方法可以推广到有 m 方分配席位的情况.设第 i 方人数为 pi,已占有 ni 个席位,i= 1,2,⋯, m.当总席位增加 1 席时,计算
Qi =(pi^2)/(ni( ni + 1)), i= 1,2,⋯, m 　　　　(7)
应将这一席分给 Q 值最大的一方.这种席位分配方法称 Q 值法.

3.d’ Hondt 方法:

将各组人数用正整数 n = 1, 2, 3,⋯相除,将所得商数从大到小取前 n个(n 为席位数)