A simple java algorithm

1. Question

## It costs 5 cents to buy a rooster, 3 cents to buy a hen, and 1 cent to buy three chicks. Now if you buy 100 chickens for 100 Wen, how many roosters, hens, and chicks are there?

2. Ideas

First list a mathematical formula, assuming that roosters, hens, and chicks each have i, j, k only, then there is an equation:

## 5i+3j+k/3=100

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

# Obviously, this problem has multiple solutions. You can use the enumeration method. The maximum number of roosters is 20, because you need to buy 100. If you buy all roosters, the total number will not meet the requirements, and the minimum is 0. Similarly, the maximum number of hens is 30, and the minimum is 0;

Chicks, the situation is quite special. Although you can buy about 300 chickens, you only need 100 chickens. And it would cost 100 Wen, so it was impossible to just sell chicks.

##3. Steps

1. Create a triple for loop

## 2 , perform conditional judgment

## 3. Output

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. OutputCock: 0

Hen: 25 Chicks:75

Rooster:3

Hen:20Chicks:77Rooster:4
Hen :18Chick:78Cock:7
Hen:13Chick:80Cock:8
Hen:11Chicks:81Rooster:11
Hen:6Chicks:83Rooster:12
Hen:4Chicks: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);
	}
	}

The above is the detailed content of A simple java algorithm. For more information, please follow other related articles on the PHP Chinese website!