经典算法问题的java实现<二>
1.数值转换(System Conversion)
1.1 r进制数
数N的r进制可以表示为：
1.2 十进制转换为r进制
十进制数N和其他r进制数的转换是计算机实现计算的基本问题，基解决方案很多，其中一个简单算法基于下列原理：
N = (N div d) * r + N mod r (其中： div为整除运算，mod为求余运算)
问题：如何将非负十进制(Decimal)整数转化为八进制数(Octonary Number)？
将十进制转化为r进制：
十进制非负整数转换为八进制：
斐波那契数列是从第0项和第1项开始，之后的项等于其前面相邻两项之和。
0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597, 2584, 4181, 6765, 10946,......
2.2 兔子生育问题：
第一个月初有一对刚诞生的兔子 第二个月之后(第三个月初)它们可以生育 每月每对可生育的兔子会诞生下一对新兔子兔子永不死去2.3 兔子问题的分析：
斐波那契数列的java非递归实现：
参照资料：http://zh.wikipedia.org/wiki/%E6%96%90%E6%B3%A2%E9%82%A3%E5%A5%91%E6%95%B0%E5%88%97#.E6.87.89.E7.94.A8
3.秦九韶算法求一元n次多项式的值(Compute Polynomial's value)
3.1 秦九韶算法介绍：
秦九韶算法是中国南宋时期的数学家秦九韶提出的一种多项式简化算法。在西方被称作霍纳算法。
秦九韶算法：
一般地，一元n次多项式的求值需要经过[n(n+2)]/2次乘法和n次加法，而从上面的演算可以看出秦九韶算法只需要n次乘法和n次加法。极大地降低了算法复杂度。
参照:http://zh.wikipedia.org/wiki/%E9%9C%8D%E7%B4%8D%E6%BC%94%E7%AE%97%E6%B3%95
3.2 秦九韶算法实现：
以上全排列的算法采用了交换，回溯，递归的方法。
参照地址：http://www.haogongju.net/art/37504
上图为八皇后问题的一个例子。
八皇后问题的java实现如下。该算法支持n皇后。当n>=16以后计算时间会很长。import java.util.Calendar;public class EightQueens {//统计解的个数int count ;//皇后数static int N = 8;//记录皇后的位置,x[i]表示皇后i放在棋盘的第i行的第x[i]列int [] X = new int[N];/** * 测试皇后k在第k行第x[k]列时是否与前面已放置好的皇后相攻击. * (X[j] == X[k]时，两皇后在同一列上， * k-j == Math.abs(X[j] - X[k])时，两皇后在同一斜线上。 * @param k * @return */boolean check(int k) {for (int row = 0; row < k; row ++) {if ((X[row] == X[k] || k-row == Math.abs(X[row] - X[k]))) {return false ;}}return true;}/** * 回溯求皇后的放置方案。 * 对于八皇后t的最大值为8. * @param row row -> [0,1,2,3,4,5,6,7,8] */void backtrack(int row) {//row == N 时，算法搜索至叶结点，得到一个新的N皇后互不攻击的放置方案if(row == N) {count++;printQueen();} else {for (int col = 0; col < N; col++) {X[row] = col;//第row行的皇后放在col列上if(check(row)) {//放置成功再放row+1行的backtrack(row+1);}}}}/** * 打印皇后 */void printQueen() {System.out.println("==================第"+count+"种皇后图==================");for (int row = 0; row < N; row++) {for (int col = 0; col < N; col++) {if (col == X[row]) {System.out.print("@ ");} else {System.out.print("* ");}}System.out.println();}}/** * @param args */public static void main(String[] args) {EightQueens queen = new EightQueens();long t1 = Calendar.getInstance().getTimeInMillis();//从0开始回溯queen.backtrack(0);long t2 = Calendar.getInstance().getTimeInMillis();//打印花费的时间。System.out.println("花费："+(t2-t1)+"ms");//打印方案总数System.out.println(queen.count);}}
有兴趣的读者可以参照以下连接，去研究八皇后算法。
http://www.animatedrecursion.com/advanced/the_eight_queens_problem.htmlhttp://www.durangobill.com/N_Queens.htmlhttp://jsomers.com/nqueen_demo/nqueens.htmlhttp://www.math.utah.edu/~alfeld/queens/queens.htmlhttp://bridges.canterbury.ac.nz/features/eight.htmlhttp://c2.com/cgi/wiki?EightQueensInManyProgrammingLanguageshttp://baike.baidu.com/view/698719.htm
