发布时间:2022-08-18 18:57
有AB 两个人轮流取2n个数中的n个数,取数之和大者为胜,若相同则先取者胜。请用算法让先取数的人胜(取数时只能看到2n个数的两边的数,即每次都只能看到该头和尾)
假设这组数为:6,16,27,6,12,9,2,11,6,5。用贪心策略每次两人都取两边的数中较大的一个数
用贪心算法的情况来看:
假设A,B两人取数,每次都只能取两边,那么6,16,27,6,12,9,2,11,6,5,先取者胜,以A先取,取数结果为:
第几次取数 | 1 | 2 | 3 | 4 | 5 | 总和 |
---|---|---|---|---|---|---|
A | 6 | 27 | 12 | 5 | 11 | 61 |
B | 16 | 6 | 9 | 6 | 2 | 29 |
所以A胜出
但是如果数据的不同也将会影响结果
假设这组数据为:
16,27,7,12,9,2,11,6 如果仍然用贪心算法,先取数时A败
第几次取数 | 1 | 2 | 3 | 4 | 总和 |
---|---|---|---|---|---|
A | 16 | 7 | 9 | 11 | 43 |
B | 27 | 12 | 6 | 2 | 47 |
所以B胜出
其实,我们只能看到两边的数据,无论是先取还是后取都无法保证100%胜出,因此我们这时一般的策略是用近似贪婪算法。
假设A和B玩这游戏,N个数排成一行,从左到右编号,依次是1,2,3........N因为N为偶数,又因为A先取数,B后取,,所以A可以一开始选择先取奇数(即最左边的数),又可以选择偶数(即最右边的数)
假设A第一次取奇数编号(编号为1)的数,则接着B只能取到偶数编号(编号为2或者N)的数。
假设B第一次取到偶数编号(编号为N)的数,则接着B只能取到奇数编号(编号为1或N-1)的数。
因此无论A第一次怎么取数,而B只能取到另一边的数(偶编号或者奇编号)的数
以上是对第一个回合的分析,显然对后续也是一样的适用的。也就是说,A能够让B自始至终只取一种编号的数。这样,我们只要比较奇编号之和与偶编号之和,谁大,以决定最开始A是取奇数还是偶数即可。
有了以上的数学模型,那么我们只需要计算一组数的奇数位和偶数位的数据之和,然后就可以确定先取数者必胜的取数方式。
main(){
int i,s1,s2,data;
cin>>n;
s1=0;
s2=0;
for(i=1;i<=n;i++){
cin>>data;
if(i mod 2=0){
s2=s2+data;
}else{
s1=s1+data;
}
}if(s1>s2){
cout<<"拿左边"
}else{
cout<<"拿右边"
}
}
复制代码
因此,在算法设计之前数学模型的选择是非常重要的。