从空瓶换酒到博弈论

一天晚上，微信群里有人扔了一道智力题出来：

123.jpg

接下来出现了各种答案。我自忖不是个聪明人，所以老老实实在纸上画图模拟，然后得出答案。我的答案是最后能喝到15瓶酒，剩3个盖子，1个空瓶。
　　但是有人说，可以喝到20瓶。20瓶的你怎么算的啊？某甲：酒+瓶+盖=2元，2瓶=2元，4盖=2元 ，解方程得 酒=0.5元 10÷0.5=20瓶。……听上去好有道理啊，我竟无言以对？
　　某乙：喝到15瓶时，盖和瓶不够换了，这个时候，找卖酒的借一瓶，喝完，够换了，换一瓶酒再还回去，所以又可以愉快滴喝下去了。……居然还有这种操作？
　　策略不同，得到的结果不同，这让人想到博弈论。博弈论又被称为对策论（Game Theory），既是现代数学的一个新分支，也是运筹学的一个重要学科。博弈论主要研究公式化了的激励结构间的相互作用，是研究具有斗争或竞争性质现象的数学理论和方法。 博弈论考虑游戏中的个体的预测行为和实际行为，并研究它们的优化策略。……听上去太高深了，我们来看一个典型的博弈论例子——枪手博弈。

彼此痛恨的甲、乙、丙三个枪手准备决斗。甲枪法最好，十发八中；乙枪法次之，十发六中；丙枪法最差，十发四中。如果三人同时开枪，并且每人只发一枪；第一轮枪战后，谁活下来的机会大一些？

一般人认为甲的枪法好，活下来的可能性大一些。但合乎推理的结论是，枪法最糟糕的丙活下来的几率最大。因为甲为了自己的存活率，首先会考虑干掉枪法仅次于自己的乙，而乙则会先考虑干掉枪法最好的甲——毕竟把甲干掉，再和丙PK，胜算也更大。结果，居然一轮下来，最有可能活下来的是枪法最烂的丙。
　　如果丙先开枪，如何才能确保自己的存活率呢？先打谁？打甲还是乙？一般人会说，当然先打甲。错了，如果按照博弈论的原理，他的最优策略是谁也不打，放个空枪——确保甲和乙首先对决就确保了自己的安全。……居然还有这种操作！
　　是的，在编程的过程中，我们谁也没有考虑到可以先借再还这种操作，因此，我们只能喝到15瓶。（当然，在现实生活中，除非啤酒老板脑子有包才会做让你借了又还这种事。）但是这个例子给我们打开了一条新的思路。在固有思维算法的基础上，仍有优化策略的可能性。

附几种不赊账算法的C++程序 谁写出来允许赊账的算法，记得分享一下。
方法一： 作者：陈瀚智（10岁）这小孩课上20分钟就做出来了，作为老师也感到了来自智商方面的碾压……

#include<iostream>
using namespace std;
int main()
{
    int a,t=0,g=0,p=0,n; //t是总共能喝几瓶酒，g是盖子数，p是空瓶数 
    cout<<"请输入钱数:";
    cin>>n;             
    for(a=1;a<=n/2;a++)    //n元钱第一轮可以喝n/2瓶 
    {
        t++;             //每喝完一瓶酒总数加一    
        g++;            //每喝完一瓶酒盖子数加一
        p++;            //每喝完一瓶酒空瓶加一
    }
    while(g>3||p>1)     //如果还能续一杯 
    {
        if(g>3)         //如果盖子多于3个 
        {
            t++;        //多喝一瓶酒 
            g-=4;       //花掉4个盖子 
            g++;        //又加一个盖 
            p++;        //也加一个空瓶 
        }
        if(p>1)         //如果空瓶多于1个 
        {
            t++;        //多喝一瓶酒  
            p-=2;      //花掉2个空瓶 
            p++;        //又加一个盖
            g++;        //也加一个空瓶
        }
    }
    cout<<"能喝"<<t<<"瓶";//输出总瓶数 
    return 0;
}

方法二：作者：徐文佳（11岁） 递归算法， 赞一个

//空瓶换酒 
#include<iostream>
using namespace std;
int change(int bottle,int cap,int beer) //换酒函数 
{
    if (bottle<2&&cap<4) return beer;   //当瓶不够2、盖不够4，不能换酒时，直接返回酒的值 
    else
    {
        if(bottle>=2) {bottle=bottle-2;bottle++;cap++;beer++;change(bottle,cap,beer);
        }//当空瓶大于2，换酒，这时， 空瓶数减2，空瓶增加1，盖加1，酒加1；递归调用换酒函数change继续换 
        if(cap>=4) {cap=cap-4;cap++;bottle++;beer++;change(bottle,cap,beer);
        }//当盖子大于4，换酒，这时， 盖子数减4，空瓶增加1，盖加1，酒加1；递归调用换酒函数change继续换 
    }
}   
int main()
{
    int n,bottle,cap,beer=0;
    cout<<"请输入钱数:"; 
    cin>>n;      //输入初始钱数 
    beer=n/2;    //赋初值， 酒的数量 
    bottle=n/2;   //瓶的初值 
    cap=n/2;      //盖的初值 
    cout<<"最多能喝:"<<change(bottle,cap,beer)<<"瓶酒"<<endl;      //调用换酒函数 change，传递 瓶、盖、酒 三个变量 
    return 0;
}

方法三： 作者：不愿透露姓名的某人（成人）
为了模拟出每一次换酒的过程，多添了一些废话

#include<cstdio>
using namespace std;
int main()
{
    int beer = 0;
    int money = 10;
    int bottle = 0;
    int cap = 0;
    printf("请输入钱数：");
    scanf("%d",&money);
    printf("钱: %d, 酒: %d, 瓶: %d, 盖: %d\n", money, beer, bottle, cap);
    printf("-------------------\n");
    while (money >= 2) {
        money -= 2;
        beer++;
        bottle++;
        cap++;
        printf("用2元钱买1酒喝掉,得到1瓶和1盖\n");
        printf("钱: %d, 酒: %d, 瓶: %d, 盖: %d\n", money, beer, bottle, cap);
        printf("-------------------\n");
        while (bottle >= 2) {
            bottle -= 2;
            beer++;
            bottle++;
            cap++;
            printf("用2瓶换1酒喝掉,得到1瓶和1盖\n");
            printf("钱: %d, 酒: %d, 瓶: %d, 盖: %d\n", money, beer, bottle, cap);
            printf("-------------------\n");
            while (cap >= 4) {
                cap -= 4;
                beer++;
                bottle++;
                cap++;
                printf("用4盖换1酒喝掉,得到1瓶和1盖\n");
                printf("钱: %d, 酒: %d, 瓶: %d, 盖: %d\n", money, beer, bottle, cap);
                printf("-------------------\n");
            }
        }
    }



    return 0;
}