c++程序【百钱买百鸡】的解法
题型介绍:
百鸡问题是一个数学问题,
出自中国古代约5—6世纪成书的《张邱建算经》,
是原书卷下第38题,
也是全书的最后一题,
该问题导致三元不定方程组,
其重要之处在于开创“一问多答”的先例。
问题及解答:
今有鸡翁一,值钱伍;
鸡母一,值钱三;
鸡鶵三,值钱一。
凡百钱买鸡百只,
问鸡翁、母、鶵各几何?
第一种答案:
答曰:鸡翁四,值钱二十;
鸡母十八,值钱五十四;
鸡鶵七十八,值钱二十六。
第二种答案:
又答:鸡翁八,值钱四十;
鸡 母十一,值钱三十三,
鸡鶵八十一,值钱二十七。
第三种答案:
又答:鸡翁十二,值钱六十;
鸡母四、值钱十二;
鸡鶵八十 四,值钱二十八。”
第四种答案(后人补充的):
又答:鸡翁零,值钱零;
鸡母二十五、值钱七十五;
鸡鶵七十五,值钱二十五。”
现扩展为如果用n元钱买m只鸡,问公鸡 母鸡 小鸡各可买几只?注意:必须把n元钱用完,且每只鸡的个数不得少于0。
聪明的你能通过编写程序解决这个问题吗?
样例输入
100 100
样例输出
0 25 75
4 18 78
8 11 81
12 4 84
分析:直接暴力枚举肯定不行,时间复杂度是n^3,如果用二重循环,很多情况下还是会时间超限,我们可以发现,小鸡的数量肯定是3的倍数,因此只要用一个数组储存0~m里三的倍数就行了,然后求出母鸡和公鸡的只数就行了(虽然本质上来说和二重循环没有区别)
程序如下(2022/6/22 15:41修改)
#include<bits/stdc++.h>
using namespace std;
int a[1005];
int main()
{
int n,m,q=0;
cin>>n>>m;
for(int i=0;i<=m;i+=3){
a[++q]=i;
}
for(int i=1;i<=q;i++){
int t=m-a[i],p=n-(a[i]/3);
for(int j=0;j<=t;j++){
int k=t-j;
if(j*5+k*3+a[i]==n&&a[i]+j+k==m) cout<<j<<' '<<k<<' '<<a[i]<<"\n";
}
}
}
本文内容由网友自发贡献,版权归原作者所有,本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容,请联系:hwhale#tublm.com(使用前将#替换为@)