欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  Java

一个简单的java小算法

程序员文章站 2022-04-23 10:54:19
...
一、问题

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(N2),但是能不能把它变成为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<x,y,z<100的话,k的取值范围只能是1,2,3,下面我们继续上代码。

	/*
	 * 优化方法
	 */
	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小算法的详细内容,更多请关注其它相关文章!

相关标签: java,小算法