🌟 前言
Wassup guys,我是Edison😎
今天是C语言每日一练,第117天!
Let’s get it!
1. 问题描述
中国古代数学家张丘健在他的 《算经》 中提出了一个著名的 “百钱百鸡问题” 👇
一只公鸡值五钱,一只母鸡值三钱,三只小鸡值一钱,现在要用百钱买百鸡,请问公鸡、母鸡、小鸡各多少只?
2. 问题分析
如果用百钱只买公鸡,最多可以买20只,但题目要求买一百只,所以公鸡数量在 0~20 之间。
同理,母鸡数量在 0~33 之间。
在此把公鸡、母鸡和小鸡的数量分别设为cock、hen、chicken,则 c o c k + h e n + c h i c k e n = 100 cock+hen+chicken=100 cock+hen+chicken=100
因此百钱买百鸡问题就转换成解不定方程组的问题了:
3. 算法思路
对于不定方程组,我们可以利用穷举循环的方法来解决。
公鸡范围是 0~20,可用语句for(cock=0; cock<=20; cock++)
实现。
钱的数量是固定的,要买的鸡的数量也是固定的,母鸡数量是受到公鸡数量限制的。
同理,小鸡数量受到公鸡和母鸡数量的限制,因此可以利用三层循环的嵌套来解决:第一层循环控制公鸡数量,第二层控制母鸡数量,最里层控制小鸡数量。
4. 代码实现
📝
#include <stdio.h>
int main()
{
int cock = 0;
int hen = 0;
int chicken = 0;
for (cock = 0; cock <= 20; cock++) //外层循环控制公鸡数量取值范围0~20
{
for (hen = 0; hen <= 33; hen++) //中层循环控制母鸡数量取值范围0~30
{
for (chicken = 0; chicken <= 100; chicken++) //内层循环控制小鸡数量取值范围0~100
{
//在内外层循环条件控制下小鸡数量的取值限制用难一组解的合理性
if ((5*cock + 3*hen + chicken/3.0 == 100) && (cock + hen + chicken == 100))
{
printf("cock=%2d, hen=%2d, chicken=%2d\n", cock, hen, chicken);
}
}
}
}
return 0;
}
运行结果👇
文章来源:https://www.toymoban.com/news/detail-410824.html
5. 算法优化
以上算法需要穷举尝试 21 ∗ 34 ∗ 101 = 72114 21 *34*101=72114 21∗34∗101=72114 次,算法的效率明显太低了。
对于本题来说,公鸡的数量确定后,小鸡的数量就是固定为 100 − c o c k − h e n 100-cock-hen 100−cock−hen,无须进行穷举了。
此时约束条件就只有一个: 5 ∗ c o c k + 3 ∗ h e n + c h i c k e n / 3 = 100 5*cock+3*hen+chicken/3=100 5∗cock+3∗hen+chicken/3=100。
这样我们利用两重循环即可实现。
此算法只需尝试 21 ∗ 34 = 714 21 * 34 = 714 21∗34=714 次,实现时约束条件中限定了chicken必须能被3整除。
只有chicken能被3整除时才会继续进行约束条件 5 ∗ c o c k + 3 ∗ h e n + c h i c k e n / 3 = 100 5*cock+3*hen+chicken/3=100 5∗cock+3∗hen+chicken/3=100 的判断。
这样省去了chicken不能被3整除时需要进行的算术计算和条件判断,进一步提高了算法的效率。文章来源地址https://www.toymoban.com/news/detail-410824.html
到了这里,关于C语言每日一练——第118天:百钱百鸡问题的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!