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

/**
 * "百钱买百鸡"是我国古代的著名数学题，题目这样描述：
 * 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

评论

2 楼 中华好儿孙 2015-08-19  

kyzaqlx 写道

设：公鸡有x只，母鸡有y只，小鸡有z只
则：x + y + z = 100 且 3 * x + 2 * y + z / 3 = 100 且 z % 3 = 0 且 x >= 0 且 y >= 0
不妨设：z = 3 * t
则：x + y = 100 - 3 * t
    3 * x + 2 * y = 100 - t
=> x = (100 - t) - 2 * (100 - 3 * t) = 5 * t - 100
   y = 3 * (100 - 3 * t) - (100 - t) = 200 - 8 * t
=> x = 5 * t - 100 >= 0
   y = 200 - 8 * t >= 0
=> 20 <= t <= 25 且 x % 5 = 0 且 y % 8 = 0

对， 是这么个解法！

1 楼 kyzaqlx 2015-08-11  

设：公鸡有x只，母鸡有y只，小鸡有z只
则：x + y + z = 100 且 3 * x + 2 * y + z / 3 = 100 且 z % 3 = 0 且 x >= 0 且 y >= 0
不妨设：z = 3 * t
则：x + y = 100 - 3 * t
    3 * x + 2 * y = 100 - t
=> x = (100 - t) - 2 * (100 - 3 * t) = 5 * t - 100
   y = 3 * (100 - 3 * t) - (100 - t) = 200 - 8 * t
=> x = 5 * t - 100 >= 0
   y = 200 - 8 * t >= 0
=> 20 <= t <= 25 且 x % 5 = 0 且 y % 8 = 0