JAVA算法趣味题目求解-白红宇

JAVA算法趣味题目求解

阅读量：4040 次

发布时间：2019-05-24

本文共 4101 字，大约阅读时间需要 13 分钟。

JAVA算法趣味题目求解

题目一

写一个算法，求下面序列之和： $1,1,-1,1,...(-1)^n$

当看到这个题目时，你会怎么想？

这个题目看起来非常简单，使用for循环，或者while循环等，累加求和呀！

于是就有了第一个算法（JAVA语言实现）：

public static int sumSolution_1(int N) {		int result = 0;		for (int i = 1; i <= N; i++) {			result = result + (int) Math.pow(-1, i);		}		return result;}

但是如果我们找到数字求和之间的规律，将奇数位和偶数位的数先进行累加求和，这会是什么情况呢？

奇数位+偶数位 = 0

-1	1	-1	1
奇数位	偶数位	奇数位	偶数位

这时就可以采用下面的算法：

public static int sumSolution_2(int N) {		int result = 0;				if (N % 2 == 0) {			result = 0;		} else {			result = -1;		}		return result;}

当给N赋予不同的值，N=4，N=5，…N=10时，可以验证，以上两个算法都可以得到正确并且相同的结果。

但是当 N=10000000，即一千万时；N为1亿时，消耗的计算时间有差别吗？

下面的测试代码运行结果说明了问题：

package com.bean.algorithm.beginner;public class BeginerSum {	public static int sumSolution_1(int N) {		int result = 0;		for (int i = 1; i <= N; i++) {			result = result + (int) Math.pow(-1, i);		}		return result;	}	public static int sumSolution_2(int N) {		int result = 0;				if (N % 2 == 0) {			result = 0;		} else {			result = -1;		}		return result;	}	public static void main(String[] args) {		// TODO Auto-generated method stub		int sum = 0;		//n的取值为一千万		int n = 10000000;		long starttime = System.currentTimeMillis();		sum = sumSolution_1(n);		long endtime = System.currentTimeMillis();		System.out.println("SUM is: " + sum);		System.out.println("Elapsed time is: " + (endtime - starttime) + " ms");				long starttime2 = System.currentTimeMillis();		sum = sumSolution_2(n);		long endtime2 = System.currentTimeMillis();		System.out.println("SUM is: " + sum);		System.out.println("Elapsed time is: " + (endtime2 - starttime2) + " ms");	}}

程序运行结果：

SUM is: 0
Elapsed time is: 1044 ms
SUM is: 0
Elapsed time is: 0 ms

我们看到程序运行所耗费的时间截然不同。其实不光是运行时间不同，而且耗费的计算内存也是不同的。

所以，好的算法不仅仅要求计算结果正确，而且需要满足下面的特点：

正确性

易读性

健壮性

高效性

低存储性

好的算法评判的标准是通过：时间复杂度 和 空间复杂度 来判断。

题目二：棋盘上放麦子

有一个古老的传说，在棋盘上放麦子：8行8列的棋盘上有64个格子。第1个格子放1粒麦子，第2个格子上放2粒麦子，第3个格子上放4粒麦子，第4个格子上放8粒麦子，依次类推，每一个格子里放置的麦子数量是前一个格子的两倍。求把这64个格子都放满麦子的话，一共需要多少粒麦子？

假设把这64个格子都放满，需要S粒麦子：

其实这个问题转化为数学计算公式就是求：

$S = 2^0+2^1+2^2+2^{63}$

我们知道这将是一个很大的数字。

如果这样来思考：

把上面的等式左右两边同时乘以2，等式仍然成立，即

$2S = 2^1+2^2+2^3+2^{64}$

用第二个式子减去第一个式子，可以得到：

$S = 2^{64}-1$

这就是计算结果！

这时多么大的一个数字呀！

题目三：神奇的兔子数列

假设第1个月有1对刚诞生的兔子，第2个月进入成熟期，第3个月开始生育兔子，而1对成熟的兔子每月会生1对兔子，兔子永远不会死去…，那么，由1对初生兔子开始，12个月后会有多少对兔子呢？

兔子数列即斐波那契数列。有兴趣的读者可以查阅相关资料。

求斐波那契数列

$1, 1, 2, 3, 5, 8, 13, 21, 34 ， . . .$

常见的算法设计

public static int fib(int n){				if(n<1) {			return -1;		}				if(n==1||n==2) {			return 1;		}				return fib(n-1)+fib(n-2);		}

优化后的算法设计：

public static int fib2(int n) {				if(n<1) {			return -1;		}				int[] array=new int[n+1];		array[1]=1;		array[2]=1;		for(int i=3;i<=n;i++) {			array[i]=array[i-1]+array[i-2];		}				return array[n];		}

这两个算法有什么区别呢？

我们来看当 n=45 时，算法耗时的差别。

package com.bean.algorithm.beginner;public class FibDemo {		public static int fib(int n){				if(n<1) {			return -1;		}				if(n==1||n==2) {			return 1;		}				return fib(n-1)+fib(n-2);			}		public static int fib2(int n) {				if(n<1) {			return -1;		}				int[] array=new int[n+1];		array[1]=1;		array[2]=1;		for(int i=3;i<=n;i++) {			array[i]=array[i-1]+array[i-2];		}				return array[n];			}	public static void main(String[] args) {		// TODO Auto-generated method stub		int ANSWER;		//n的取值为45		int n = 45;		long starttime = System.currentTimeMillis();		ANSWER = fib(n);		long endtime = System.currentTimeMillis();		System.out.println("ANSWER is: " + ANSWER);		System.out.println("Elapsed time is: " + (endtime - starttime) + " ms");				long starttime2 = System.currentTimeMillis();		ANSWER = fib2(n);		long endtime2 = System.currentTimeMillis();		System.out.println("ANSWER is: " + ANSWER);		System.out.println("Elapsed time is: " + (endtime2 - starttime2) + " ms");	}}

程序运行结果：