一、問題
5文錢買一隻公雞,3文錢買一隻母雞,一文錢買三隻雛雞。現在用100文錢買一百隻雞,那麼公雞、母雞、雛雞各有多少隻?
二、想法
## 先列出數學公式,設公雞、母雞、雛雞各有i,j, k隻,那麼有等式:
5i+3j+k/3=100
# 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
六、优化
这次我们要求公鸡、母鸡、小鸡都必须有,那么就需要从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); } }
以上是一個簡單的java小演算法的詳細內容。更多資訊請關注PHP中文網其他相關文章!