一個簡單的java小演算法

一、問題

    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

###小雞: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(N²),但是能不能把它变成为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中文網其他相關文章！