python/GESP/穷举法.md

### 穷举法
穷举法的基本思想是根据题目的部分条件确定答案的大致范围，并在此范围内对所有可能的情况逐一验证，直到全部情况验证完毕。若某个情况验证符合题目的全部条件，则为本问题的一个解；若全部情况验证后都不符合题目的全部条件，则本题无解。穷举法也称为枚举法。

用穷举法解题时，就是按照某种方式列举问题答案的过程。针对问题的数据类型而言，常用的列举方法一有如下三种：

（1）顺序列举 是指答案范围内的各种情况很容易与自然数对应甚至就是自然数，可以按自然数的变化顺序去列举。

（2）排列列举 有时答案的数据形式是一组数的排列，列举出所有答案所在范围内的排列，为排列列举。

（3）组合列举 当答案的数据形式为一些元素的组合时，往往需要用组合列举。组合是无序的。

例子如下：在公元五世纪我国数学家张丘建在其《算经》一书中提出了“百鸡问题 ”：
“鸡翁一值钱5，鸡母一值钱3，鸡雏三值钱1。百钱买百鸡，问鸡翁、母、雏各几何？”这个数学问题的数学方程可列出如下：
```cpp {.line-numbers}
Cock+Hen+Chick=100
Cock*5+Hen*3+Chick/3=100
```
显然这是个不定方程，适用于穷举法求解。依次取Cock值域中的一个值，然后求其他两个数，满足条件就是解。
该问题的C语言程序算法如下：
```cpp {.line-numbers}
int Cock,Hen,Chick; /*定义公鸡，母鸡，鸡雏三个变量*/
Cock=0;
while (Cock<=19) /*公鸡最多不可能大于19*/
{ 
    Hen=0;
    while (Hen<=33) /*母鸡最多不可能大于33*/
    {
        Chick=100-Cock-Hen;
    	if (Cock*15+Hen*9+Chick==300)/*为了方便，将数量放大三倍比较*/
    	printf("\n公鸡=%d\n母鸡=%d\n雏鸡=%d",Cock,Hen,Chick);
    	Hen=Hen+1;
	}
    Cock=Cock+1;
}
```