趣味算法二例（3）

------------------------------------------------------------------------------
百钱买百鸡
中国古代数学家著有一本古典数学问题的《算经》，其中记载的问题在当时都是
一些有趣的难题。其中最闻名的“百钱百鸡”问题叙述如下：
    “鸡翁一，值钱五；鸡母一，值钱三；鸡雏三，值钱一；百钱买百鸡，问翁、母、
雏各几何？”
    这个问题翻译成白话文就是：“一只公鸡值五文钱；一只母鸡值三文钱；三只小
鸡值一文钱；请问用一百文钱买一百只鸡，公鸡、母鸡和小鸡各有多少只？”
    我们假设公鸡、母鸡和小鸡的个数分别为x,y,z,那么买公鸡的钱数为5x，买母鸡
的钱数为3y，买小鸡的钱数为z/3；再由题意，x,y和z的和为100，因此我们可以得到
该问题的数学模型如下：
5x+3y+z/3=100
x+y+z=100
因为鸡的个数只能是整数，所以问题可以归结为求这个不定方程的整数解。
不定方程的求解途径一般是打出各变量的数值汇聚围，再用穷举法找到所有可能的解，
在本题中，假如100文钱全部买公鸡，最多买20只，因此x的取值在0~20之间；同理y的
取值在0~33之间。得到了变量x和y的取值汇聚围后，昝用C语言的二重for循环,让x和y 
分别作为外层和内层循环的循环变量，我们可以让计算机穷举所有可能的情况，从而
找到正确的解。

代码如下：

#include<stdio.h>
main()
{   int x,y,z,j=0;
    printf("Possible solutions to buy 100 fowls whith 100 yuan\n");
    for(x=0;x<=20;x++)     /*公鸡的数目作为外层循环的循环变量*/
        for(y=0;y<=33;y++) /*母鸡的数目作为内层循环的循环变量*/
        {   z=100-x-y;     /*用总鸡数方程计算小鸡的数目*/
            if(z%3==0&&5*x+3*y+z/3==100)  /*假如满足总钱数，找到合理的解*/
                printf("2d:cock=%-2d hen=%-2d chicken=%-2d\n",++j,x,y,z);
        }
}

运行结果：
1：cock=0   hen=25  chicken=75
2：cock=4   hen=18  chicken=78
3：cock=8   hen=11  chicken=81
4：cock=12  hen=4   chicken=84
--------------------------------------------------------------------------------

分油趣题
从大容器往外倒一定体积的液体也是中外古代数学家喜爱研究的一类问题，如下面这
道厨师分油的趣题：“有一位厨师要从盛12斤油的桶中倒出6斤油来，可是手边只有盛5
斤油和盛8斤油的两个桶，问如何操作才能将6斤取出来呢?”
我们首先用字母a,b,c代表12斤桶，8斤桶和5斤捅。规定倒油的顺序为：
    a->b->c->a
    并且必须符合如下规则：
    1.b(8斤桶)倒空后才能从a(12斤桶)中取油。
    2．c(5斤桶)盛满后才能向a(12斤捅)中倒油。
    我们设从a中往b倒油x次，从c往a倒油y次，那么最后a中剩下的油应该为12-
8x+6y斤，按照题意，我们得到如下方程，
    12-8x+6y=6：
    我们为了得到这个方程的解，应按照上述的倒油规则不断的倒下去，直到a中或b中
油的重量为6斤为止，另外也可以改变倒油的规则，看能否找到最好的倒油步聚。

代码：

#include<stdio.h>
int i;
main()
{   int a,y,z;
    printf("Input Full a ,Empty b,c,Get i:");  /*读入3个容器的容量和最后需要的数量*/
    scanf("%d%d%d",&a,&y,&z,&i);
    getti(a,y,z);
}
getti(int a,int y,int z)
{   int b=0,c=0;   /*b,c为二个容器的实际重量*/
    printf("a%d b%d c%d\n%4d%4d%4d\n",a,y,z,a,b,c);
    while(a!=i||b!=i)      /*假如满足要求退出循环*/
    {   if(!b)           /*假如b为空，从a往b倒油*/
        {   a-=y;b=y;
        }
        else if(c==z)
        {   a+=z;c=0     /*假如c已满，从c往a倒油*/
        }
        else if(b>z-c)
        {   b-=(z-c);c=z;  /*假如b的重量大于c的剩余重量，倒满c*/
        }
        else
        {   c+=b;b=0;   /*否则将b中的油全部倒入c*/
        }
        printf("%4d%4d%4d\n",a,b,c);  
    }
}

运行结果：
Input Full a, Empty b,c,  Get i: 12,8,5,6
a    b    c
12   8    5
12   0    0
4    8    0
4    3    5
9    3    0
9    0    3
1    8    3
1    6    5
6    6    0