3.22 穷尽法_百鸡百钱.c

#include <stdlib.h>
#include <stdio.h>

/**
* 百鸡百钱问题：
* 100元去买100只鸡，公鸡5元一只，母鸡3元一只，小鸡3毛一只。
* 100元分别能买公鸡母鸡小鸡各多少只？
* 解：假设公鸡是X 母鸡是Y 小鸡是Z
* X + Y + Z = 100
* 5X + 3Y + Z/3.0 = 100
* 100/5= 20 100/3= 33 100/0.3~= 300
*
* 优化：
*   100 - X - Y = Z
*   100 - 5X - 3Y = Z*3
*
* 优化前运行：72114次
* 优化后运行：693次
*   
* 穷举法：(程序开发最常用到的)
*/

void main25()
{
    for (int X = 0; X <= 20; X++)
    {
        for (int Y = 0; Y <= 33; Y++)
        {
            for (int Z = 0; Z <= 100; Z++)  // 到不了300最多可以买100只 所以我们采用100
            {
                if ((5*X+3*Y+Z/3.0 == 100) && (X+Y+Z == 100))
                {
                    printf("公鸡为：%d母鸡为：%d小鸡为：%d\n",X,Y,Z);   // 第一个限制只有100元 第二个限制它们的总和只能是100
                }
            }
        }
    }

    printf("---------------- 优化后 ----------------\n");

    for (int X = 0; X <= 20; X++)
    {
        for (int Y =0; Y <= 33; Y++)
        {
            int Z = 100 - X -Y; // 小鸡 = 钱 - 购买公鸡 + 母鸡所花的钱 剩余的全买小鸡
            if (5*X+3*Y+Z/3.0 == 100)
            {
                printf("公鸡为：%d母鸡为：%d小鸡为：%d\n",X,Y,Z);
            }
        }
    }
    
    system("pause");
}