欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

对百钱买百鸡问题传统解法的一点改进

程序员文章站 2022-06-23 20:42:27
...
/**
 * "百钱买百鸡"是我国古代的著名数学题,题目这样描述:
 * 3文钱可以买1只公鸡,2文钱可以买1只母鸡,1文钱可以买3只小鸡。
 * 用100文钱买100只鸡,那么各有公鸡、母鸡、小鸡多少只? 
 */
public class HundredChickenHundredMoney {
	public static void main(String[] args) {
		traditionalSolution();
		System.out.println("华丽丽的分割线====================");
		improvedSolution();
		System.out.println("华丽丽的分割线又出现了~~~~~~~~~~~~~~");
		moreImprovedSolution();
		System.out.println("呵呵+++++++++++++++++++++++++++++");
		moremoreImprovedSolution();
	}
	
	/**
	 * 设100文钱买到的100只鸡中,
	 * 公鸡有x只,母鸡有y只,则小鸡有100-x-y只,
	 * x,y都为非负整数,且100>=100-x-y>=0,
	 * 则有不定方程:8x+5y=200,
	 * 我在网上浏览到的方法都是用两个循环来求得x和y的所有组合,
	 * 代码如下:
	 */
	public static void traditionalSolution(){
		for(int y = 0; y <= 40; y++){
			for(int x = 0; x <= 25; x++){
				if(8*x + 5*y == 200){
					System.out.printf("公鸡有%d只,母鸡有%d只,小鸡有%d只。\n", x, y, 100-x-y);
				}
			}
		}
	}
	
	/**
	 * 对不定方程:8x+5y=200, 经过分析可以发现:
	 * 8和5是互素的,也就是说:当我们把不定方程的形式稍加变化,
	 * 变成:8x=200-5y, 因为5显然能整除等式右边, 故必能整除等式左边,
	 * 因为5显然能整除200,所以5必能整除8x,
	 * 又5与8互素,所以5必能整除x,当等式成立的时候。
	 * 则可简化原来的两层循环只一层循环,代码如下:
	 */
	public static void improvedSolution(){
		for(int x = 0; x <= 25; x++){
			if(x%5 == 0){
				System.out.printf("公鸡有%d只,母鸡有%d只,小鸡有%d只。\n", x, Math.round(40-1.6*x), Math.round(60+0.6*x));
			}
		}
	}
	
	/**
	 * 因为最终结果的100文钱对应100只鸡,
	 * 钱与鸡(不管是什么鸡)必是一一对应的关系,
	 * 可以将公鸡和小鸡、母鸡和小鸡配对,
	 * 令gx为公鸡和小鸡的对数,mx为母鸡和小鸡的对数,
	 * 则有不定方程:4gx + 5mx = 100,
	 * 则有可进一步减少循环次数,代码如下:
	 */
	public static void moreImprovedSolution(){
		for(int mx = 0; mx <= 20; mx++){
			if(mx%4 == 0){
				System.out.printf("公鸡有%d只,母鸡有%d只,小鸡有%d只。\n", Math.round(25-1.25*mx), 2*mx, Math.round(75-0.75*mx));
			}
		}
	}
	
	/**
	 * 在网上看到的解法
	 */
	public static void moremoreImprovedSolution(){
		for(int t = 0; t <= 5; t++){
			System.out.printf("公鸡有%d只,母鸡有%d只,小鸡有%d只。\n", 25-5*t, 8*t,75-3*t);
		}
	}
}


参考博客:http://27769.eduol.cn/archives/2007/281469.html