一、问题
5文钱买一只公鸡，3文钱买一只母鸡，一文钱买三只雏鸡。现在用100文钱买一百只鸡，那么公鸡、母鸡、雏鸡各有多少只？
二、思路
首先列出一个数学公式，设公鸡、母鸡、雏鸡各有i，j，k只，那么有等式：
5i+3j+k/3=100
立即学习“Java免费学习笔记（深入）”；
i+j+k=100; i,j,k>=0
很明显，这个问题有多个解。可以使用枚举法，公鸡最多不超过20只，因为要买100只，如果全买公鸡，那么总数达不到要求，最少0只；同理，母鸡最多不超过30只，最少0只；雏鸡，情况比较特殊，虽然可以买到300只左右，但是只要100只鸡。而且要花完100文钱，所以不可能只卖雏鸡。
三、步骤
1、建立三重for循环
2、进行条件判断
3、输出
四、代码
package datastructure;
/**
* @author wangpeng
*
*/
public class Cock_number {
/**
* @param args
*/
public static void main(String[] args) {
for (int i = 0; i < 100 / 5; i++) {
for (int j = 0; j < 100 / 3; j++) {
for (int k = 0; k < 100 * 3; k++) {
if (i + j + k ==100 && i * 5 + j * 3 + j/ 3 == 100) {
System.out.println("公鸡:" + i + "\t母鸡:"+ j + "\t小鸡:" + k);
}
}
}
}
}
}五、输出
公鸡:0母鸡:25小鸡:75
公鸡:3母鸡:20小鸡:77
公鸡:4母鸡:18小鸡:78
公鸡:7母鸡:13小鸡:80
公鸡:8母鸡:11小鸡:81
公鸡:11母鸡:6小鸡:83
公鸡:12母鸡:4小鸡:84
六、优化
这次我们要求公鸡、母鸡、小鸡都必须有，那么就需要从1开始：
/*
* 所有鸡都有
*/
public static void method_2() {
for (int i = 1; i < 20; i++) {
for (int j = 1; j < 33; j++) {
int z = 100 - i - j;
if (z % 3 == 0 && i * 5 + j * 3 + z / 3 == 100) {
System.out.println("公鸡:" + i + "\t母鸡:" + j + "\t小鸡:" + j);
}
}
}
}输出：
公鸡:4母鸡:18小鸡:78
公鸡:8母鸡:11小鸡:81
公鸡:12母鸡:4小鸡:84
结果出来了，确实这道题非常简单，我们知道目前的时间复杂度是O(N2),但是能不能把它变成为O(N)呢。所以我们可以继续优化一下，从结果中我们可以发现这样的一个规律：公鸡是4的倍数,母鸡是7的递减率，小鸡是3的递增率，规律哪里来，肯定需要我们推算一下这个不定方程。
x+y+z=100 ①
5x+3y+z/3=100 ②
令②x3-① 可得
7x+4y=100
=>y=25-(7/4)x ③
又因为0<y<100的自然数，则可令
x=4k ④
将④代入③可得
=> y=25-7k ⑤
将④⑤代入①可知
=> z=75+3k ⑥要保证0
/*
* 优化方法
*/
public static void method_3() {
int i,j,z;
for(int k=1;k<=3;k++){
i = 4 * k;
j = 25 - 7 * k;
z = 75 + 3 * k;
System.out.println("公鸡:" + i + "\t母鸡:" + j + "\t小鸡:" + z);
}
} 
