题解 | #百钱买百鸡问题#
百钱买百鸡问题
http://www.nowcoder.com/practice/74c493f094304ea2bda37d0dc40dc85b
百钱买百鸡问题
描述
公元前五世纪，我国古代数学家张丘建在《算经》一书中提出了“百鸡问题”：鸡翁一值钱五，鸡母一值钱三，鸡雏三值钱一。百钱买百鸡，问鸡翁、鸡母、鸡雏各几何？现要求你打印出所有花一百元买一百只鸡的方式。
输入描述：
输入任何一个整数，即可运行程序。
输出描述：
输出有数行，每行三个整数，分别代表鸡翁，母鸡，鸡雏的数量
示例：
输入：1
输出：
0 25 75
4 18 78
8 11 81
12 4 84
0 25 75
4 18 78
8 11 81
12 4 84
方法一
思路分析
根据描述整理得到：共有100元，鸡翁，母鸡，鸡雏的数量之和为100
- 一只鸡翁5元，设置鸡翁数量为i，总数不能超过20只；
- 一只母鸡3元，设置母鸡数量为j，总数不能超过33只；
- 三只小鸡1元，设置小鸡数量为k，总数不能超过300只；
因此三层嵌套循环遍历，判定条件为：
- 三类鸡的总数是为100；
-
总钱数是否为100，变换条件如下：
- 鸡雏的数量是否为3的倍数
核心代码
#include<bits/stdc++.h>
using namespace std;
int main()
{
int n;
cin>>n;
if(n>0)
{
int i=0,j=0,k=0;
for(i=0;i<=20;i++)
{
for(j=0;j<=33;j++)
{
for(k=0;k<=300;k++)
{
if(k%3==0&&15*i+j*9+k==300&&i+j+k==100)//判断三类鸡的总数是为100，总钱数是否为100，还要判断鸡雏的数量是否为3的倍数
cout<<i<<" "<<j<<" "<<k<<endl;
}
}
}
}
}
复杂度分析
- 时间复杂度：三层嵌套循环，为$O(20*33*300)$，总的时间复杂度为$O(1)$
- 空间复杂度：空间复杂度为$O(1)$
方法二
思路分析
实际上遍历鸡翁，母鸡的数量之后，直接可以计算出符合条件的小鸡的数量，判定条件也减少
图解
核心代码
#include<bits/stdc++.h>
using namespace std;
int main()
{
int n;
cin>>n;
if(n>0)
{
int i=0,j=0,k=0;
for(i=0;i<=20;i++)
{
for(j=0;j<=33;j++)
{
k=100-i-j;//小鸡的数量
if(15*i+j*9+k==300)//判断花费是否为100
cout<<i<<" "<<j<<" "<<k<<endl;
}
}
}
}
复杂度分析
- 时间复杂度：两层嵌套循环，为$O(20*33)$，时间复杂度为$O(1)$
- 空间复杂度：空间复杂度为$O(1)$
方法三
思路分析+图解
根据前面的推导，我们希望继续减小循环嵌套，因此做如下推导：因此只需要遍历k即可。
核心代码
#include<bits/stdc++.h>
using namespace std;
int main()
{
int n;
cin>>n;
if(n>0)
{
int i=0,j=0,k=0;
for(int m=0;m<=5;m++)
{
i=4*m;//鸡翁
j=25-7*m;//母鸡
k=75+3*m;//小鸡
if(j>=0)
cout<<i<<" "<<j<<" "<<k<<endl;
}
}
}
复杂度分析
- 时间复杂度：只需要一次循环，时间复杂度为$O(1)$，相比于前两种方法，时间又减小了
- 空间复杂度：空间复杂度为$O(1)$
查看11道真题和解析