算法-04 动态规划法 回溯法

本文主要是介绍算法-04 动态规划法 回溯法，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

1 回溯法之 八皇后

要求：在八横八纵的网格中，找到任意八个点，且这八个点不能在同一行 也不再同一列。并且也不在任意一条对角线上。
思路：遍历每一列，判断这一列前面的列已经放好了的位置。则此行不能再放。
再判断这一列所有和这个位置构成对角线的点。这个点也不能在放。

	// 每一行 每一列的个数private int MAXQUEEN = 8;// 记录每一列皇后的下标private int col[] = new int[MAXQUEEN];// 记录方案数private int num = 0;

public static void main(String[] args) {Queen queen = new Queen();queen.getCount(0);}

	// 获取第n列皇后的 下标private void getCount(int n) {boolean[] row = new boolean[MAXQUEEN];for (int m = 0; m < n; m++) {// 其他列在此行中 已有皇后row[col[m]] = true;int d = n - m;// 判断正斜方向上是否可以放皇后if (col[m] - d >= 0) {row[col[m] - d] = true;}// 判断反斜方向是否可以放皇后if (col[m] + d <= MAXQUEEN - 1) {row[col[m] + d] = true;}}// 已经知道哪些点不可以放for (int i = 0; i < MAXQUEEN; i++) {if (row[i]) {continue;}col[n] = i;if (n < MAXQUEEN - 1) {getCount(n + 1);} else {num++;printQueen();}}}// 打印皇后的位置private void printQueen() {// 遍历行System.out.println("第" + num + "种方案");for (int i = 0; i < MAXQUEEN; i++) {// 遍历列for (int j = 0; j < MAXQUEEN; j++) {if (col[j] == i) {System.out.print("0 ");} else {System.out.print("+ ");}}System.out.println();}}

2 大数相乘

如果用int值直接相乘。那么有些不在int范围内的值无法计算。
大数相乘用输出字符串的形式来计算出两个较大值的乘积。

public static void main(String[] args) {BigCountMultyply bigCountMultyply = new BigCountMultyply();bigCountMultyply.setCharArray("4", "5");}//把字符串转成倒过来的char[]private void setCharArray(String strNum1,String strNum2){char[] charArray1 = exchangeCharArray(strNum1.toCharArray());char[] charArray2 = exchangeCharArray(strNum2.toCharArray());multyply(charArray1,charArray2);}//把char[] 倒过来private char[] exchangeCharArray(char[] charArray){int len = charArray.length;for(int i=0;i<len/2;i++){charArray[i]+=charArray[len-i-1];charArray[len-i-1] = (char) (charArray[i]-charArray[len-i-1]);charArray[i] = (char) (charArray[i] - charArray[len-i-1]);}return charArray;}

private void multyply(char[] a,char[] b){int len = a.length+b.length;int[] value = new int[len];//相乘for(int i=0;i<a.length;i++){for(int j=0;j<b.length;j++){value[i+j]+=Integer.parseInt(String.valueOf(a[i]))*Integer.parseInt(String.valueOf(b[j]));}}//进位for(int i=0;i<len;i++){int carry = value[i]/10;value[i] = value[i]%10;if(carry>0){value[i+1]+=carry;}}//找到最大位数int m = len-1;for(;m>=0;m--){if(value[m]>0){break;}}//输出乘积for(int i =m;i>=0;i--){System.out.print(value[i]);}}

3 约瑟夫杀人法

每数五个人就枪毙第五个人。

	private int TOTALSIZE = 20;private int LOOPSIZE = 5;public static void main(String[] args) {Josephus josephus = new Josephus();josephus.killNode();}

	private void killNode(){Node header = new Node(1);Node currentNode  = header;//构造链表for(int i=2;i<=TOTALSIZE;i++){currentNode = currentNode.next = new Node(i);}//收尾相连currentNode.next = header;//说明剩下的不止一个while(currentNode!=currentNode.next){for(int i=1;i<LOOPSIZE;i++){// 1,2,3,4,5,6currentNode = currentNode.next;}System.out.println("被枪毙的结点为："+currentNode.next.index);currentNode.next = currentNode.next.next;}System.out.println("仅剩下"+currentNode.index);}

class Node{int index;Node next;public Node(int index){this.index= index;}}

4 求两个字符串的最长子字符串

public static void main(String[] args) {LCSTest lcsTest = new LCSTest();lcsTest.getLongestChildrenSize("android", "random");}

private void getLongestChildrenSize(String strA, String strB) {char[] a = strA.toCharArray();char[] b = strB.toCharArray();int n = a.length;int m = b.length;// 矩阵为n行 m列int[][] matrix = new int[n][m];// 矩阵第一列for (int i = 0; i < n; i++) {if (a[i] == b[0]) {matrix[i][0] = 1;for (int j = i + 1; j < n; j++) {matrix[j][0] = 1;}break;}}// 矩阵第一行for (int i = 0; i < m; i++) {if (a[0] == b[i]) {matrix[0][i] = 1;for(int j=i+1;j<m;j++){matrix[0][j] = 1;}break;}}for(int i=1;i<n;i++){for(int j=1;j<m;j++){if(a[i] == b[j]){matrix[i][j] = matrix[i-1][j-1]+1; }else{matrix[i][j] = Math.max(matrix[i][j-1], matrix[i-1][j]);}}}for(int i =0;i<n;i++){for(int j=0;j<m;j++){System.out.print(matrix[i][j]+" ");}System.out.println();}}

这篇关于算法-04 动态规划法 回溯法的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---