Ein einfacher Java-Algorithmus

1. Frage

5 Cent kaufen einen Hahn, 3 Cent kaufen eine Henne und 1 Cent kaufen drei Küken. Wenn Sie nun 100 Hühner für 100 Wen kaufen, wie viele Hähne, Hühner und Küken gibt es dann?

2. Ideen

Listen Sie zunächst eine mathematische Formel auf, vorausgesetzt Hähne, Hühner und Küken haben jeweils i, j, k nur dann gibt es eine Gleichung:

5i+3j+k/3=100

i+j+k=100; i,j,k>=0

Offensichtlich gibt es für dieses Problem mehrere Lösungen. Sie können die Aufzählungsmethode verwenden. Die maximale Anzahl an Hähnen beträgt nicht mehr als 20, da Sie 100 kaufen müssen Die maximale Anzahl an Hühnern beträgt 30 und die minimale Anzahl 0; Küken sind in einer besonderen Situation. Obwohl Sie etwa 300 Hühner kaufen können, benötigen Sie nur 100 Hühner. Und es würde 100 Cent kosten, also war es unmöglich, einfach Küken zu verkaufen.

3. Schritte

1. Erstellen Sie eine Triple-for-Schleife

2, bedingte Beurteilung durchführen

3. Ausgabe

4. Code

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);
					}
				}
			}
		}
	}
}

5. Ausgabe

Hahn: 0Henne :25Küken: 75Männchen: 3
Henne: 20Küken: 77Männchen: 4
Henne: 18 Küken: 78Männchen: 7
Henne: 13Küken: 80Männchen: 8
Henne: 11Küken: 81Hahn: 11
Henne: 6Küken: 83Hahn: 12
Hennen: 4Küken: 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);
	}
	}

Das obige ist der detaillierte Inhalt vonEin einfacher Java-Algorithmus. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!