[2023.03二级]2.百鸡问题

题目描述

“百鸡问题”是出自我国古代《张丘建算经》的著名数学问题。大意为：“每只公鸡5元，每只母鸡3元，每3只小鸡1元；现在有100元，买了100只鸡，共有多少种方案？”
小明很喜欢这个故事，他决定对这个问题进行扩展，并使用编程解决：如果每只公鸡x 元，每只母鸡y元，每z只小鸡1元；现在有n元，买了m只鸡，共有多少种方案？

输入格式

输入一行，包含五个整数，分别为问题描述中的x、y、z、n、m。

输出格式

输出一行，包含一个整数C，表示有C种方案。

数据范围

对于全部数据，保证有1 ≤ x, y, z ≤ 10，1 ≤ n, m ≤ 1000。

样例

输入样例1
5 3 3 100 100

输出样例1
4

样例解释1
这就是问题描述中的“百鸡问题”。4种方案分别为：
公鸡0只、母鸡25只、小鸡75只；
公鸡4只、母鸡18只、小鸡78只；
公鸡8只、母鸡11只、小鸡81只；
公鸡12只、母鸡 4只、小鸡84只。

输入样例2
1 1 1 100 100

输出样例2
5151

解法一：超时只能得到一部分分数

结构：三重循环嵌套结构

· 外层循环i控制公鸡数量
· 中间层循j环控制母鸡数量
· 内层循环k控制小鸡数量

问题：如何构成一组方案数

公鸡x元,母鸡y元,小鸡z只1元,n元钱买m只鸡
公鸡数量i只,母鸡数量j只,小鸡数量k只

1. 满足恒等式：购买鸡的总数量 = 三种鸡的数量之和
   · m == i + j + k
2. 满足恒等式：购买鸡的总钱数 = 三种鸡的钱数之和
   · n == i * x + j * y + k / z;
3. 隐藏条件：购买小鸡的数量应该是z的整数倍
   · k % z == 0

参考程序

#include<iostream>
using namespace std;
int main() 
{
    int x,y,z,n,m,res=0; // res表示购买小鸡的方案数
    cin>>x>>y>>z>>n>>m;
    for(int i=0;i<=m;i++) // 公鸡数量
        for(int j=0;j<=m;j++) // 母鸡数量
            for(int k=0;k<=m;k++) // 小鸡数量
                if(k%z==0 && i*x+j*y+k/z==n && i+j+k==m)
                    res++; // 方案数加一
    cout<<res; // 输出总方案数
    return 0;
}

解法二

结构：双重循环嵌套结构

· 外层循环i控制公鸡数量
· 内层循环j控制母鸡数量

问题：如何构成一组方案数

公鸡x元,母鸡y元,小鸡z只1元,n元钱买m只鸡
公鸡数量i只,母鸡数量j只

1. 计算小鸡数量 = 购买鸡的总数量 - 公鸡数量 - 母鸡数量
   · k = m - i - j
2. 满足恒等式：购买鸡的总钱数 = 三种鸡的钱数之和
   · n == i * x + j * y + k / z;
3. 隐藏条件：购买小鸡的数量应该是z的整数倍
   · k % z == 0
4. !!! 重点 !!!：根据第一条,k可能是负数,不能购买负数只鸡
   · 增加条件：k >= 0

参考程序

#include<iostream>
using namespace std;
int main() 
{
    int x,y,z,n,m,res=0; // res表示购买小鸡的方案数
    cin>>x>>y>>z>>n>>m;
    for(int i=0;i<=m;i++) // 公鸡数量
    {
        for(int j=0;j<=m;j++) // 母鸡数量
        {
            int k = m - i - j; // 小鸡数量
            if(k>=0 && k%z==0 && i*x+j*y+k/z==n) 
            {
                res++; // 方案数加一
            }
        }
    }
    cout<<res; // 输出总方案数
    return 0;
}

扩展：优化代码

公鸡x元,母鸡y元,小鸡z只1元,n元钱买m只鸡
公鸡数量i只,母鸡数量j只

优化方法

1. 公鸡购买最多数量 = 购买总钱数 ÷ 公鸡单价
   · 即公鸡最多数量 = n / x
2. 母鸡购买最多数量 = (购买总钱数 - 购买公鸡钱数) ÷ 母鸡单价
   · 即母鸡最多数量 = (n - x * i) / y

参考程序

#include<iostream>
using namespace std;
int main() 
{
    int x,y,z,n,m,res=0; // res表示购买小鸡的方案数
    cin>>x>>y>>z>>n>>m;
    for(int i=0;i<=n/x;i++) // 公鸡数量
    {
        for(int j=0;j<=(n-i*x)/y;j++) // 母鸡数量
        {
            int k = m - i - j; // 小鸡数量
            if(k>=0 && k%z==0 && i*x+j*y+k/z==n) 
            {
                res++; // 方案数加一
            }
        }
    }
    cout<<res; // 输出总方案数
    return 0;
}