Online Judge | Problem Set | Authors | Online Contests | User | ||||||
---|---|---|---|---|---|---|---|---|---|---|
Web Board Home Page F.A.Qs Statistical Charts | Current Contest Past Contests Scheduled Contests Award Contest |
根据排序不等式证明假设质量分别是a1,a2,a3...an(n>=2),不妨设最佳合并的顺序就是a1,a2,a3...an(n>=2)。合并之后的质量为m,则有: m=2sqrt(2sqrt(2sqrt(......)sqrt(an-2))sqrt(an-1))sqrt(an)..............(1) 将(1)式两边取2^(n-1),有: m^(2^(n-1))=2^(常数)*a1*a2*a3^2*a4^4*a5^8*...*an^(2^(n-2))..............(2) 将(2)式两边同时取对数ln,有: (2^(n-1))*ln(m)=常数*ln(2)+ln(a1)+ln(a2)+2ln(a3)+4ln(a4)+...+2^(n-2)ln(an) 对上式右边使用函数y=2^x,y=ln(x)的单调递增性和排序不等式(反序和<=乱序和),可知,当上式左端取最小值时即右端取最小值即an<an-1<an-2<...<a1 因此最佳合并顺序为从大到小合并。 Followed by: Post your reply here: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator