간단한 자바 알고리즘

1. 질문

5센트로 수탉 한 마리, 3센트로 암탉 한 마리, 1센트로 병아리 세 마리를 살 수 있습니다. 이제 닭 100마리를 100원에 사면 수탉, 암탉, 병아리는 몇 마리 있습니까?

2. 아이디어

먼저 수학 공식을 나열하세요. 수탉, 암탉, 병아리가 각각 i, j, k를 갖는다고 가정하세요. 그런 다음 방정식이

5i+입니다. 3j+ k/3=100

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

분명히 이 문제에는 여러 가지 해결책이 있습니다. 열거 방법을 사용할 수 있습니다. 수탉은 100마리를 구매해야 하므로 최대 수탉 수는 20마리입니다. 수탉을 모두 구매하면 총 수는 요구 사항을 충족하지 않으며 최소 수탉 수는 0입니다. 마찬가지로 최대 수탉 수는 20마리입니다. 는 30이고 최소값은 0입니다. 병아리는 300마리 정도 살 수 있지만 닭은 100마리만 있으면 됩니다. 그리고 100원이 들기 때문에 병아리만 파는 것은 불가능합니다.

3단계

1. 트리플 for 루프 만들기

2. 조건부 판단

3. 출력

4. 코드

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. 출력

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

위 내용은 간단한 자바 알고리즘의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!