问题 A: 百钱买百鸡问题

题目描述

“百钱买百鸡”是我国著名的古代数学问题，中国古代数学家张丘建在他的《算经》中提出了这样一个问题：鸡翁一，值钱五，鸡母一，值钱三，鸡雏三，值钱一，百钱买百鸡，问翁、母、雏各几何？ 你的任务是求解下面这个问题。问题是这样描述的：a文钱可买一只公鸡，b文钱可买一只母鸡，c文钱可买d只小鸡。用m文钱买n只鸡，那么有公鸡x只、母鸡y只、小鸡z只。求解出符合题意的x,y,z。 输入

输入为一张表。第一行是一个固定不变的表头，格式见sample。后面有多行，每行为一组测试数据。每组测试数据由6个整数组成，分别为“a,b,c/d,m,n”。满足0<a,b,c,d<=50，50<=m,n<=108+1，并且母鸡和小鸡的单价不会相同。 输出

每组测试数据的运行结果输出为一张表，表头固定为“COCKS,HENS,CHICKS”。每组测试数据的一个可行解数出为一行，为三个整数：“x,y,z”。多组解按照公鸡数从少到多的顺序输出。若测试数据无解则输出“Cannot buy!”。两组测试数据之间用一个空行分隔开。 样例输入

COCK,HEN,CHICK,MONEY,CHICKS 3,2,1/3,100,100 5,3,1/3,100,100 8,5,1/7,100,100 8,5,1/7,300,300

样例输出

COCKS,HENS,CHICKS 0,40,60 5,32,63 10,24,66 15,16,69 20,8,72 25,0,75 COCKS,HENS,CHICKS 0,25,75 4,18,78 8,11,81 12,4,84 Cannot buy! COCKS,HENS,CHICKS 8,40,252

代码如下（枚举）：

#include <stdio.h> int main() { scanf("COCK,HEN,CHICK,MONEY,CHICKS"); int a,b,c,d,m,n,x,y,z,u; while (scanf("%d,%d,%d/%d,%d,%d",&a,&b,&c,&d,&m,&n)!=EOF) { u=0; for(x=0;x<=m/a;x++) { z=(m-a*x-b*n+b*x)*d/(c-b*d); y=n-x-z; if((x*a*d + y*b*d + z*c == m*d)&&(z>=0&&y>=0)) { if(u==0) { puts ("COCKS,HENS,CHICKS"); } printf("%d,%d,%d\n",x,y,z); u++; } } if(u==0) { printf("Cannot buy!\n"); printf("\n"); } else printf("\n"); } return 0; }

矩阵计算：

#include<stdio.h> int gcd(int a, int b) { int m; if(b==0) { m = a; } else if(a==0) { m = b; } else { int result = a % b; int x = a; int y = b; while(result!=0) { x = y; y = result; result = x % y; } m = y; } return m; } int main() { int a,b,c,d,m,n; int x,y,z; scanf("COCK,HEN,CHICK,MONEY,CHICKS"); while(scanf("%d,%d,%d/%d,%d,%d",&a,&b,&c,&d,&m,&n)!=EOF) { int dd = d; int mm = m; int aa = a; int bb = b; int cc = c; b = b - a; c = c - d * a; d = d; m = m - n * a; a = a - a; c = c; d = d * b; m /= b; b /= b; int g = gcd(c,d); c /= g; d /= g; int count = 1; int count_ = 0; int flag = 1; for(z=dd;z<n;z+=dd) { count_++; x = (n - m) - (d - c) * z / d; y = m - (c * z) / d; if(x>=0&&y>=0&&x*aa+y*bb+z*cc/dd==mm) { flag = 0; if(count==1) { printf("COCKS,HENS,CHICKS\n"); printf("%d,%d,%d\n",x,y,z); } else { printf("%d,%d,%d\n",x,y,z); } count++; } else { if(count_==n/dd&&flag) { printf("Cannot buy!\n"); } } } printf("\n"); } return 0; }