流离之人追逐幻影

用户名：pwj666

访问量：60204

签　名：

不想总是要失去后才懂得珍惜

等　　级
排　　名	37
经　　验	13954
参赛次数	11
文章发表	110
年　　龄	23
在职情况	在职
学　　校
专　　业

　　自我简介：

TA的其他文章

【原理、题解、代码】最大公约数与最小公倍数
浏览：186

你可能喜欢

百(N)钱百(N)鸡问题【四层解法递进】-题解(C++代码)

　　作者: 流离之人追逐幻影　　　　发表时间：2019-06-18 02:55:11 浏览：3059　|　评论：3　

原题链接：C语言训练-百钱百鸡问题

首先先来认识一下，何谓**暴力破解法**？是指从可能的解集合（空间）中一一列举各情况，用题目给定的检验条件判定哪些是无用的，哪些是有用的。能使命题成立者，即为问题的解。

**基本思路:**
（1）建立问题的数学模型，确定问题的可能解的集合（可能解的空间）。
        
（2）逐一列出可能解集合中的元素，验证是否是问题的解。

优化方向：**通过加强约束条件，缩小可能解的集合的规模。**
按照暴力破解法的思想，我们首先会想到的就是直接所有循环破解，管你牛鬼蛇神。

解法一：
1.抽象出数学模型，这里指的就是方程组

设公鸡为x，母鸡为y,小鸡为z，

鸡：  x+y+z=100

钱：  5x+3y+1/3z=100

2.代码

```
#include<iostream>
using namespace std;
 
int main(){
	int x,y,z;
	for(x=0;x<=20;x++)//公鸡不会超过20只
		for(y=0;y<=34;y++)//母鸡不会超过34只
			for(z=0;z<=100;z++)//小鸡不会超过100只
				if((x+y+z)==100 && (5*x+3*y+z/3)==100&&z%3==0)//同时要满足z是3的整数
cout<<"cock="<<x<<","<<"hen="<<y<<","<<"chicken="<<z<<endl;
	return 0;
}
```
![](/image_editor_upload/20190618024516_68914.png)

```
算法分析：显然，该算法嵌套三重循环，算法复杂度为O(n^3), 循环次数为20*34*100，数量级为10^4，这种算法根本不能满足我们的需求。所以聪明一点的人可能会想到要减少一个循环的嵌套，以此降低算法复杂度。
```
解法二：
1.减少一个循环的嵌套，模型不变，进一步优化算法

2.代码
```
#include<iostream>
using namespace std;
int main(){
	int x,y,z;
	for(x=0;x<=20;x++)//公鸡不会超过20只
		for(y=0;y<=34;y++)//母鸡不会超过34只
		{
			z=100-x-y;//根据x,y可求出z
			if(z==(300-15*x-9*y)&&z%3==0)
cout<<"cock="<<x<<","<<"hen="<<y<<","<<"chicken="<<z<<endl;
		}						
	return 0;
}

```
```
算法分析：显然，该算法嵌套二重循环，算法复杂度为O(n^2), 循环次数为20*34，数量级为10^2，这种算法比上一算法足足降低了2个数量级，可见循环嵌套越多，算法就越差。所以还需要继续优化，用我们的初中数学知识就OK.
```

解法三：1.每使用一个for(x)循环，就相当于将一个未知数(x)变成已知数（x）, 两个方程两个未知数，方程就具有可解性了， 这样就可以， 继续减少一个循环的嵌套

鸡：  x+y+z=100

钱：  15x+9y+z=300

=>>7x+4y=100   ->y    ->z

2.代码：
```
#include<iostream>
using namespace std;
int main(){
	int x,y,z;
	for(x=0;x<=20;x++)//公鸡不会超过20只
	{
		y=25-1.75*x;//先求y
		z=100-x-y;//再求z
		if(z==(300-15*x-9*y)&&z%3==0&&y>0&&&z>0)
cout<<"cock="<<x<<","<<"hen="<<y<<","<<"chicken="<<z<<endl;
	}
	return 0;
}
```
```
算法分析：显然，该算法只有一重循环，算法复杂度为O(n), 循环次数为20，数量级为10，这种算法比上一算法降低了1个数量级，说明该算法还是不错的，可以满足我们竞赛的需求。不过数学思维比较好的人，可以通过结果反过来继续优化。
```
![](/image_editor_upload/20190618024941_55548.png)
通过上图的结果，我们发现  x以4递增，y以7递减,   z以3递增，所以可以直接打印
```
#include<iostream>
using namespace std;
int main(){
	int x,y,z;
	for(int k=0;k<=3;k++)
	{
        x = 4 * k;
        y = 25 - 7 * k;
        z = 75 + 3 * k; 
cout<<"cock="<<x<<","<<"hen="<<y<<","<<"chicken="<<z<<endl;
	}
	return 0;
}

```
```
算法分析：这种算法可以说是接近最优了，不过在AC的时候，强烈建议使用解法三，因为你不可能一开始就知道结果是什么和有多少种解法，以上是我对该算法的理解，如果你觉得还有优化的细节，欢迎留言，一同进步。
```
赠人玫瑰，手有余香。点个赞吧。^-^
蟹蟹，有问题请留言。

0.0分

67 人评分

看不懂代码解释一下代码? 或者生成一段代码？试试AI编程助手吧

　　评论区

N11koo

这个写的题解确实牛 小学生都看得懂

2022-11-19 01:58:39

bilibili用户

牛逼啊理解了比其他人瞎写厉害多了

2020-07-16 22:11:45

验题君

嗯，这种循序渐见的思路对我们学习帮助很大！

2019-10-17 10:14:54

流离之人追逐幻影

TA的其他文章

你可能喜欢

C语言程序设计教程（第三版）课后习题9.1 （C语言代码）

蛇行矩阵（C++代码）

C语言程序设计教程（第三版）课后习题8.6 （C语言代码）

C语言程序设计教程（第三版）课后习题5.6 （C语言代码）

【数组的距离】（C语言代码）

百(N)钱百(N)鸡问题【四层解法递进】-题解(C++代码)

评论区

精彩推荐

C语言程序设计教程（第三版）课后习题11.11 （C语言代码）

矩阵转置（C语言代码）

C语言程序设计教程（第三版）课后习题7.2 （Java代码）

C语言程序设计教程（第三版）课后习题5.8 （C语言代码）

【亲和数】（C语言代码）

C语言程序设计教程（第三版）课后习题7.3 （C语言代码）

C语言程序设计教程（第三版）课后习题4.9 （C语言代码）

C语言程序设计教程（第三版）课后习题6.2 （C语言代码）

字符串的输入输出处理（C语言代码）

C语言程序设计教程（第三版）课后习题6.1 （C语言代码）

流离之人追逐幻影

TA的其他文章

你可能喜欢

C语言程序设计教程（第三版）课后习题9.1 （C语言代码）

蛇行矩阵 （C++代码）

C语言程序设计教程（第三版）课后习题8.6 （C语言代码）

C语言程序设计教程（第三版）课后习题5.6 （C语言代码）

【数组的距离】 （C语言代码）

百(N)钱百(N)鸡问题【四层解法递进】-题解(C++代码)

评论区

精彩推荐

C语言程序设计教程（第三版）课后习题11.11 （C语言代码）

矩阵转置 （C语言代码）

C语言程序设计教程（第三版）课后习题7.2 （Java代码）

C语言程序设计教程（第三版）课后习题5.8 （C语言代码）

【亲和数】 （C语言代码）

C语言程序设计教程（第三版）课后习题7.3 （C语言代码）

C语言程序设计教程（第三版）课后习题4.9 （C语言代码）

C语言程序设计教程（第三版）课后习题6.2 （C语言代码）

字符串的输入输出处理 （C语言代码）

C语言程序设计教程（第三版）课后习题6.1 （C语言代码）

蛇行矩阵（C++代码）

【数组的距离】（C语言代码）

　　评论区

矩阵转置（C语言代码）

【亲和数】（C语言代码）

字符串的输入输出处理（C语言代码）