Java基础算法题

在网上搜索Java的基础算法题，差不多都是那50道，也有很多人贴了代码。参考着一份代码，我自己也大概写了一遍，还有一些小分析，有些重复性的或者太简单的题目就没有写了。有的题有自己的代码和网上的代码的对比。自己的很多编程习惯都不规范，由于时间问题，排版也有些乱，现放到blog上，打击凑合看吧，希望不吝给予指正。

我参考的：http://www.cnblogs.com/tonylp/archive/2013/03/20/2971272.html

http://blog.sina.com.cn/s/blog_60fafdda0100wb21.html

 【程序1】 TestRabbit.java

题目：古典问题：有一对兔子，从出生后第3个月起每个月都生一对兔子，小兔子长到第三个月后每个月又生一对兔子，假如兔子都不死，问每个月的兔子总数为多少？ 
分析：

题目中说的从出生后的第3个月开始每个月都生一对兔子，意思就是新出生的每对兔子，长满2个月之后就开始生小兔子了。

也就是：小兔子出生→满1个月→满2个月，生一对小兔子。这个我总容易理解有偏差。

所以可知，所分析的当前第i个月，这个月的兔子总数，大致可以分为2部分，1部分是非新生的，另一部分是当月新生的。非新生的应该是第i-1个月的兔子总数，新生的取决于第i-2个月的兔子总数。即兔子[i]=兔子[i-1]+兔子[i-2]。

前两个月兔子都是1对，从第3个月开始，每个月的兔子就是前两个月的兔子数之和。

所以： 兔子的规律为数列1,1,2,3,5,8,13,21....

我的代码：

递归的方法：

【程序2】 FindPrimeNumber.java
题目：判断101-200之间有多少个素数，并输出所有素数。 
分析：判断素数的方法：用一个数分别去除以2到这个数本身，如果有能被整除的情况，则表明此数不是素数，反之是素数。

我的代码：

 

【程序3】FindDaffodilNumber.java
题目：打印出所有的"水仙花数"，所谓"水仙花数"是指一个三位数，其各位数字立方和等于该数本身。例如： 
153是一个"水仙花数"，因为153=1的三次方＋5的三次方＋3的三次方。 
分析：利用for循环控制100-999个数，每个数分解出个位，十位，百位。

这个过程中遇到一个问题，关于String的substring(int beginIndex,int endIndex)，之前一直理解错了。截取的子字符串的起始下标是beginIndex，终止坐标是endIndex-1，而不是endIndex。所以当beginIndex==endIndex时，子字符串是空的。

想要输出一个字符串某一位上的字符，可以直接使用str.charAt(n);

我的代码：

【程序4】FenJie.java
题目：将一个正整数分解质因数。例如：输入90,打印出90=2*3*3*5。 
程序分析：对n进行分解质因数，应先找到一个最小的质数k(k=2)，然后按下述步骤完成： 
(1)如果这个质数恰等于n，则说明分解质因数的过程已经结束，打印出即可。 
(2)如果n>k，但n能被k整除，则应打印出k的值，并用n除以k的商,作为新的正整数你n,重复执行第一步。 
(3)如果n不能被k整除，则用k+1作为k的值,重复执行第一步。

我的代码：

网上的代码：

【程序6】Test1.java GcdTest.java后者是辗转相除法
题目：输入两个正整数m和n，求其最大公约数和最小公倍数。 
1.程序分析：利用辗除法。

我的代码：（未使用辗除法）

以上代码可以直接简化为如下：

辗除法：

辗除法（zhǎnchú fǎ ）——辗转相除法， 又名欧几里德算法（Euclidean algorithm）乃求两个正整数之最大公因子的算法。它是已知最古老的算法， 其可追溯至3000年前。它首次出现于欧几里德的《几何原本》（第VII卷，命题i和ii）中，而在中国则可以追溯至东汉出现的《九章算术》。它并不需要把二数作质因子分解。

设两数为a、b(b<a)，求它们最大公约数(a、b)的步骤如下：用b除a，得a=bq......r 1(0≤r)。若r1=0，则(a，b)=b；若r1≠0，则再用r1除b，得b=r1q......r2 (0≤r2).若r2=0，则(a，b)=r1，若r2≠0，则继续用r2除r1,……如此下去，直到能整除为止。其最后一个非零余数即为(a，b)。

两个数之积=这两个数的最大公约数*最小公倍数

【程序11】 TestTN.java
题目：有1、2、3、4个数字，能组成多少个互不相同且无重复数字的三位数？都是多少？ 
分析：可填在百位、十位、个位的数字都是1、2、3、4。组成所有的排列后再去 掉不满足条件的排列。

代码：

这种嵌套循环的思想没有想到

【程序20】TestAdd2.java
题目：有一分数序列：2/1，3/2，5/3，8/5，13/8，21/13...求出这个数列的前20项之和。 
分析：请抓住分子与分母的变化规律。

我的代码：

网上的代码：

把分子和分母分别放到两个数组中。

【程序21】TestJieCheng.java
题目：求1+2!+3!+...+20!的和 
分析：此程序只是把累加变成了累乘。

我的代码：使用递归

网上的代码：

【程序26】Ex26.java
题目：请输入星期几的第一个字母来判断一下是星期几，如果第一个字母一样，则继续 判断第二个字母。 
1.程序分析：用情况语句比较好，如果第一个字母一样，则判断用情况语句或if语句判断第二个字母。 

我的代码：

【程序33】YangHui.java
题目：打印出杨辉三角形（要求打印出10行如下图） 

分析： 
     1
    1 1
   1 2 1
  1 3 3 1
 1  4 6 4 1
1 5 10 10 5 1

我的代码：

循环有点儿多。。。效率应该很低吧。。发现我特别喜欢用好多层循环。。。囧

 

网上的代码：

     1
    1 1
   1 2 1
  1 3 3 1
 1  4 6 4 1
1 5 10 10 5 1

思想：

观察每一行的数组可知，从第三行开始，每一行的数组，首尾都是1，第2个数到倒数第2个数，都是上边一行的这个位置上的数与前一个数的和。所以可以定义一个数组，一行一行的重新赋值，打印。

【程序37】 Test3Quit.java
题目：有n个人围成一圈，顺序排号。从第一个人开始报数（从1到3报数），凡报到3的人退出圈子，问最后留下的是原来第几号的那位。 

代码：

【程序44】 TestEven.java
题目：一个偶数总能表示为两个素数之和。 

代码：

 

转载请注明来自：http://java-future.iteye.com