算法系统学习-取数先取如何必定获胜?(相对或近似贪心)

发布时间: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<<"拿右边"
    
    }
}
复制代码

因此,在算法设计之前数学模型的选择是非常重要的。


 

ItVuer - 免责声明 - 关于我们 - 联系我们

本网站信息来源于互联网,如有侵权请联系:561261067@qq.com

桂ICP备16001015号