百钱买百鸡问题

描述

公元前五世纪，我国古代数学家张丘建在《算经》一书中提出了“百鸡问题”：鸡翁一值钱五，鸡母一值钱三，鸡雏三值钱一。百钱买百鸡，问鸡翁、鸡母、鸡雏各几何？
现要求你打印出所有花一百元买一百只鸡的方式。
输入描述：
输入任何一个整数，即可运行程序。
输出描述：
 输出有数行，每行三个整数，分别代表鸡翁，母鸡，鸡雏的数量
示例：
输入：1
输出：
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，变换条件如下：5*i+3*j+k/3==100\Leftrightarrow15*i+9*j+k==300
  • 鸡雏的数量是否为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)$