Un algorithme Java simple

1. Question

5 centimes achètent un coq, 3 centimes achètent une poule, et 1 centime achètent trois poussins. Maintenant, si vous achetez 100 poulets pour 100 Wen, combien y a-t-il de coqs, de poules et de poussins ?

2. Idées

Commencez par énumérer une formule mathématique, en supposant que les coqs, les poules et les poussins ont chacun i, j, k. seulement, alors il y a une équation :

5i+3j+k/3=100

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

Évidemment, ce problème a plusieurs solutions. Vous pouvez utiliser la méthode d'énumération. Le nombre maximum de coqs ne dépasse pas 20, car vous devez en acheter 100. Si vous achetez tous les coqs, le nombre total ne répondra pas aux exigences, et le minimum est de même 0 ; le nombre maximum de poules est de 30 et le minimum est de 0 ; Les poussins sont dans une situation particulière. Bien que vous puissiez acheter environ 300 poulets, vous n'en avez besoin que de 100. Et cela coûterait 100 centimes, donc il était impossible de simplement vendre des poussins.

3. Étapes

1. Créez un triple pour la boucle

2, effectuer un jugement conditionnel

3. Sortie

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. Sortie

Coq : 0Poule :25Poussins : 75
Coq : 3Poule : 20Poussins : 77
Coq : 4 Poule : 18 Poussins : 78
Coq : 7Poule : 13Poussins : 80
Coq : 8Poule : 11Poussins : 81
Coq : 11Poule : 6Poussins : 83
Coq : 12Poules : 4Poussins : 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);
	}
	}

Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!