算法(Java)

技术2022-06-23 56

//汉诺塔问题(递归)package org;

import java.util.Scanner;

public class Tower { public static void main(String[] args) { System.out.println("输入盘子的个数："); Scanner sc=new Scanner(System.in); int n=sc.nextInt(); tower(n,'A','B','C'); } public static void tower(int n,char a, char b, char c){ if(n!=0){ tower(n-1,a,c,b); System.out.println("move disk "+n+"/t"+"from"+a+"/t"+"to "+c); c=a; tower(n-1,b,a,c); } }}//---------------------------------------------------------------------------------------------------//斐波那契级数(递归,当n比较大时，效率比较低)package org;

import java.util.Scanner;

public class Fib { public static long fib(int n){ if(n==1 || n==2) return 1; else return fib(n-1)+fib(n-2); } /* 测试 */ public static void main(String[] args) { System.out.println("输入一个整数："); Scanner sc=new Scanner(System.in); int n=sc.nextInt(); System.out.println("结果为："+fib(n)); }}//---------------------------------------------------------------------------------------------------//最大公约数(递归)package org;

import java.util.Scanner;

public class MaxGcd { /* 递归实现 */ public static int gcd(int m, int n){ if(n==0) return m; else if(m<=n) return gcd(n,m); else return gcd(n,m%n); } /* 非递归实现 */ public static int gcd2(int m, int n){ if(m>=n){ while(n!=0){ int rem=m % n; m=n; n=rem; } } else gcd2(n,m); return m; } /* 测试 */ public static void main(String[] args) { System.out.println("请输入两个整数m和n"); Scanner sc=new Scanner(System.in); int m=sc.nextInt(); int n=sc.nextInt(); System.out.println(m+"和"+n+"的最大公约数为："+gcd(m,n)); }}//---------------------------------------------------------------------------------------------------//简单的0/1背包问题(递归)：设一背包可容物品的最大质量为m，现有n件物品，质量为m1，m2，...，mn，mi均为正整数，要从n件物品中挑选若干件，//使背包的质量之和正好为mpackage org;

public class Bag01 { public static boolean knap(int weight, int[] a, int n){ if(n<=0) return false; if(weight==a[n-1]) return true; else{ if(weight>=a[n-1]){ //能放 if(knap(weight-a[n-1],a,n-1)) return true; else return knap(weight,a,n-1); //不放 }else //不能放 return knap(weight,a,n-1); //不放 } } /* 测试 */ public static void main(String[] args) { int weight=68; int a[]={16,21,6,31,2,5,7,8,10,15}; boolean flag=knap(weight,a,10); System.out.println(flag); }}//---------------------------------------------------------------------------------------------------//求n!package org;

import java.util.Scanner;

public class Factorial { /* 递归实现 */ public static long fac(int n){ if(n==0 || n==1) return 1; else{ return (n * fac(n-1)); } } /* 非递归实现 */ public static long fac2(int n){ int sum=1; if(n==0 || n==1) return 1; for(int i=2;i<=n;i++){ sum*=i; } return sum; } /* 测试 */ public static void main(String[] args) { System.out.println("输入一个整数："); Scanner sc=new Scanner(System.in); int n=sc.nextInt(); System.out.println(n+"！="+fac(n)); }}//---------------------------------------------------------------------------------------------------//求n个数的排列(递归)package org;

/* permutation: 排列 */public class Permutation { public static void perm(int[] data, int start, int end){ if(start==end-1){ for(int i=0;i<end;i++) System.out.print(data[i]); System.out.println(); }else{ for(int i=start;i<end;i++){ int temp; temp=data[i]; data[i]=data[start]; data[start]=temp; perm(data,start+1,end); } } } /* 测试 */ public static void main(String[] args) { int[] data={1,2,3,4}; int end=4; perm(data,0,end); }}//---------------------------------------------------------------------------------------------------//求最大元素最小元素(分治算法)package org;

public class MaxMinElement { public static int findMax(int[] srcData, int left, int right){ if(left==right) return srcData[left]; int mid=(left+right)/2; int leftMax=findMax(srcData, left,mid); int rightMax=findMax(srcData, mid+1,right); return leftMax>rightMax ? leftMax : rightMax; } public static int findMin(int[] srcData, int left, int right){ if(left==right) return srcData[left]; int mid=(left+right)/2; int leftMin=findMin(srcData, left, mid); int rightMin=findMin(srcData,mid+1,right); return leftMin<rightMin ? leftMin : rightMin; } /* 测试 */ public static void main(String[] args) { int[] srcData={22,13,-9,-5,15,60,17,47,31}; int right=9; int max=findMax(srcData, 0, right-1); int min=findMin(srcData, 0, right-1); System.out.println("max="+max+"/t"+"min="+min); }}//---------------------------------------------------------------------------------------------------//二分检索package org;

public class BinarySearch { public static int search(int[] a, int left, int right, int key) { if (left > right || left < 0 || right > a.length) return -1; int low = left; int high = right - 1; while (low <= high) { int mid = (low + high)>>>1; //与 int mid=(low+high)/2 等价，但执行效率高 int midVal = a[mid]; if (midVal < key) low = mid + 1; else if (midVal > key) high = mid - 1; else return mid; // key found } return -(low + 1); // key not found. } /* 测试 */ public static void main(String[] args) { int[] a={-9,-1,1,2,3,4,5,6,7}; System.out.println(search(a, 0, 8,-1)); }}//---------------------------------------------------------------------------------------------------//快速排序package org;

public class QuickSort { public static int[] sortASC(int[] array){ if(array==null) return null; int[] srcData=(int[])array.clone(); return quickSort(srcData, 0, srcData.length-1); } /* srcData:待排序的数组 first:起始下标 last:终止下标*/ private static int[] quickSort(int[] srcData, int first, int last){ if(first<last){ int pos=partition(srcData,first,last); quickSort(srcData, first, pos-1); quickSort(srcData, pos+1, last); } return srcData; } /* 根据数组的第一个数分治，把比数组第一个数大的往后排，把比数组第一个数小的往前排 */ private static int partition(int[] srcData, int first, int last){ int temp=srcData[first]; int pos=first; for(int i=first+1;i<=last;i++){ if(srcData[i]<temp){ pos++; swap(srcData,pos,i); } } swap(srcData,first,pos); return pos; } /* 交换数组中下标为src和dest的值 */ private static void swap(int[] data,int src,int dest){ int temp=data[src]; data[src]=data[dest]; data[dest]=temp; } /* 测试 */ public static void main(String[] args) { int[] array={22,13,-5,-8,15,60,17,31,47}; System.out.println("排序前："); for(int i=0;i<array.length;i++){ System.out.print(array[i]+" "); } System.out.println(); System.out.println("排序后："); int[] afterSortArray=sortASC(array); for(int i=0;i<afterSortArray.length;i++){ System.out.print(afterSortArray[i]+" "); } }}//---------------------------------------------------------------------------------------------------//归并排序package org;

public class MergeSort { private static void mergeSort(int[] a, int[] temp, int left, int right) { if (left < right) { int center = (left + right) / 2; mergeSort(a, temp, left, center); mergeSort(a, temp, center + 1, right); merge(a, temp, left, center + 1, right); } }

public static void mergeSort(int[] a) { int[] temp = new int[a.length]; mergeSort(a, temp, 0, a.length - 1); }

private static void merge(int[] a, int[] temp, int leftPos, int rightPos, int rightEnd) { int leftEnd = rightPos - 1; int tmpPos = leftPos; int numElements = rightEnd - leftPos + 1; while (leftPos <= leftEnd && rightPos <= rightEnd) if (a[leftPos] <= a[rightPos]) temp[tmpPos++] = a[leftPos++]; else temp[tmpPos++] = a[rightPos++]; while (leftPos <= leftEnd) temp[tmpPos++] = a[leftPos++]; while (rightPos <= rightEnd) temp[tmpPos++] = a[rightPos++]; for (int i = 0; i < numElements; i++, rightEnd--) a[rightEnd] = temp[rightEnd];

} /* 测试 */ public static void main(String[] args) { int[] a = { 1, 13, 24, 26, 2, 15, 27, 38 }; System.out.println("排序前："); for (int i = 0; i < a.length; i++) System.out.print(a[i] + " "); System.out.println(); mergeSort(a); System.out.println("排序后："); for (int i = 0; i < a.length; i++) System.out.print(a[i] + " "); }}//---------------------------------------------------------------------------------------------------//LCS问题：(给出两个字符串，求出两个字符串的最长公共子序列)package org;

public class LCS { public static void main(String[] args) { char[] left = "abcbdab".toCharArray(); //21232523311324 char[] right = "bdcaba".toCharArray(); //312123223445 char [] result = delLGS(left, right); String strResult=""; for(int index = 0;index<result.length;index++){ strResult = strResult+ result[index]+""; } System.out.println(strResult); } public static char[] delLGS(char[] left, char[] right) { int lenLeft = left.length; int lenRight = right.length; int c[][] = new int[lenLeft][lenRight]; char[] p; int start, end, len, i, j = 0; end = len = 0; for (i = 0; i < lenLeft; i++) { for (j = lenRight - 1; j >= 0; j--) { if (left[i] == right[j]){ // 元素相等时 if (i == 0 || j == 0) c[i][j] = 1; else { c[i][j] = c[i - 1][j - 1] + 1; } } else c[i][j] = 0; if (c[i][j] > len) { len = c[i][j]; end = j; } } } start = end - len + 1; p = new char[len]; for (i = start; i <= end; i++){ p[i - start] = right[i]; } return p; } } /* LCS问题就是求两个字符串最长公共子串的问题。 * 解法就是用一个矩阵来记录两个字符串中所有位置的两个字符之间的匹配情况， * 若是匹配则为1，否则为0。然后求出对角线最长的1序列， * 其对应的位置就是最长匹配子串的位置 *///---------------------------------------------------------------------------------------------------//矩阵链乘积问题：(给定n个矩阵{A1,A2,...,An},其中Ai与Ai+1是可乘的，i=1,2,...,n-1.//如何确定计算矩阵链乘积的计算次序，使得依此次序计算矩阵连乘积需要的次数最少)package org;

import java.util.ArrayList;import java.util.Date;import java.util.List;import java.util.Random;

public class MatrixChainOrder { private double m[][]; private int s[][]; public MatrixChainOrder(MatrixArray p) { int n, i, j, k, l; double q; n = p.getMatrixArrayLength(); m = new double[n][n]; s = new int[n][n]; for (i = 0; i < n; i++) { for (j = 0; j < n; j++) { s[i][j] = 0; } } for (i = 0; i < n; i++) { m[i][i] = 0; } for (l = 2; l < n; l++) { for (i = 1; i < (n - l + 1); i++) { j = i + l - 1; m[i][j] = 99999999999999999999.0; for (k = i; k < j; k++) { q = m[i][k] + m[k + 1][j] + p.getMatrixArray(i - 1)* p.getMatrixArray(k) * p.getMatrixArray(j); if (q < m[i][j]) { m[i][j] = q; s[i][j] = k; } } } } }// end of MatrixChainOrder

public double getM(int i, int j) { return m[i][j]; } public int getS(int i, int j) { return s[i][j]; }

public static void main(String args[]) { Date date1, date2, date3; long d1, d2, d3; MatrixArray p; int i, j; double sum = 1.0, k = 0.0; p = new MatrixArray(100); p.ranMakeMatrixArray(100); p.makeMatrixChain(); MatrixChainOrder newOrder; newOrder = new MatrixChainOrder(p); Matrix A, B; date1 = new Date(); d1 = date1.getTime(); System.out.println(d1); A = p.matrixMultiply(p); date2 = new Date(); d2 = date2.getTime(); System.out.println(d2); B = p.matrixChainMultiply(newOrder); date3 = new Date(); d3 = date3.getTime(); System.out.println(d3); d1 = d2 - d1; d2 = d3 - d2; System.out.println("普通相乘用时" + d1 + "毫秒"); System.out.println("优化相乘用时" + d2 + "毫秒"); }}

class Matrix { private int i, j; private double matrix[][]; // 初始化矩阵 public void makeMatrix(int i, int j) { this.i = i; this.j = j; matrix = new double[i][j]; } // 随机生成矩阵元素 public void ranFillMatrix(int random) { int s, t; Random ran = new Random(); for (s = 0; s < i; s++) { for (t = 0; t < j; t++) { matrix[s][t] = ran.nextDouble() * random; } } } // 获取矩阵元素 public double getMatrix(int i, int j) { return matrix[i][j]; } // 取得矩阵的列数 public int getMatrixI() { return i; } // 取得矩阵的行数 public int getMatrixJ() { return j; } // 设定矩阵中某个元素的值 public void setMatrix(int i, int j, double value) { matrix[i][j] = value; } // 矩阵相乘 public Matrix multiplyMatrix(Matrix matrix) { int s, t;// 记录传入矩阵的维数 int start, middle, end;// 矩阵运算游标 double sum; s = matrix.getMatrixI(); t = matrix.getMatrixJ(); Matrix matrixResult = new Matrix(); matrixResult.makeMatrix(i, t); for (start = 0; start < i; start++) { for (end = 0; end < t; end++) { sum = 0; for (middle = 0; middle < j; middle++) { sum = sum + this.matrix[start][middle]* matrix.getMatrix(middle, end); } matrixResult.setMatrix(start, end, sum); } } return matrixResult; }}

class MatrixArray { private int matrixnum; private int array[]; private List matrixobjectarray; // 获取矩阵 public Matrix getMatrix(int i) { return (Matrix) matrixobjectarray.get(i); } public MatrixArray(int i) { int j; matrixnum = i; array = new int[matrixnum]; } // 随机生成链乘矩阵 public void ranMakeMatrixArray(int random) { int j; Random ran = new Random(); for (j = 0; j < matrixnum; j++) { array[j] = ran.nextInt(random) + 1; } } // 获取链乘阵的维数 public int getMatrixArray(int i) { return array[i]; } public int getMatrixArrayLength() { return matrixnum; } // 产生具体的矩阵 public void makeMatrixChain() { int i, j; matrixobjectarray = new ArrayList(); Matrix x; for (i = 0; i < matrixnum - 1; i++) { x = new Matrix(); x.makeMatrix(array[i], array[i + 1]); x.ranFillMatrix(100); matrixobjectarray.add(i, x); } } // 矩阵基础乘 public Matrix matrixMultiply(MatrixArray p) { Matrix A; int i; A = p.getMatrix(0); for (i = 1; i < p.getMatrixArrayLength() - 1; i++) { A = A.multiplyMatrix(p.getMatrix(i)); } return A; }

// 优化解 public Matrix matrixChainMultiply(MatrixChainOrder S) { return mCM(matrixobjectarray, S, 0, matrixnum - 2); }

private Matrix mCM(List A, MatrixChainOrder S, int i, int j) { Matrix x, y; if (j > i) { x = mCM(A, S, i, S.getS(i, j)); y = mCM(A, S, S.getS(i, j) + 1, j); return x.multiplyMatrix(y); } return (Matrix) A.get(i); }}//---------------------------------------------------------------------------------------------------//N皇后问题package org;

public class QueenN { private final int size; // 棋盘的大小，也表示皇后的数目 private int[] location; // 皇后在棋盘的每行上的列的位置 private int[] colsOccupied; // 皇后在棋盘上占据的列 private int[] cross1Occupied; // 皇后在棋盘上占据的正对角线 private int[] cross2Occupied; // 皇后在棋盘上占据的反对角线 private static int count; // 解决方案的个数 private static final int STATUS_OCCUPIED = 1; // 占领状态 private static final int STATUS_OCCUPY_CANCELED = 0; // 未占领状态

public QueenN(int size) { this.size = size; location = new int[size]; colsOccupied = new int[size]; cross1Occupied = new int[2 * size]; cross2Occupied = new int[2 * size]; }

public void printLocation() { System.out.println("以下是皇后在棋盘上的第" + count + "种摆放位置"); for (int i = 0; i < size; i++) System.out.println("行：" + i + "列：" + location[i]); }

// 判断位置(i,j)是否被占领 private boolean isOccupied(int i, int j) { return (colsOccupied[j] == STATUS_OCCUPIED) || (cross1Occupied[i - j + size - 1] == STATUS_OCCUPIED) || (cross2Occupied[i + j] == STATUS_OCCUPIED); }

// 如果参数flag为1，表示占领位置(i,j); // 如果参数flag为0，表示取消占领位置(i,j); private void setStatus(int i, int j, int flag) { colsOccupied[j] = flag; // 宣布占领或取消占领第j列； cross1Occupied[i - j + size - 1] = flag; // 宣布占领或取消占领正对角线 cross2Occupied[i + j] = flag; // 宣布占领或取消占领反对角线 }

// 从第i行开始摆放皇后 public void place(int i) { for (int j = 0; j < size; j++) // 在第i行分别尝试把皇后放在每一列上 if (!isOccupied(i, j)) // 判断该位置是否被占领 { location[i] = j; // 摆放皇后，在第i行把皇后放在你j列 setStatus(i, j, STATUS_OCCUPIED); // 宣布占领(i,j)位置 if (i < size - 1) place(i + 1); // 如果所有皇后没有摆完，递归摆放下一行皇后 else { count++; // 统计解决方案的个数 printLocation(); // 完成任务，打印所有皇后的位置 } // 回溯，取消占领位置(i,j) setStatus(i, j, STATUS_OCCUPY_CANCELED); } }

public void start() { place(0); // 从第0行开始放置皇后 }

public static void main(String[] args) { new QueenN(8).start(); // 开始执行8皇后 }}//---------------------------------------------------------------------------------------------------//0/1背包问题(给定n种物品和一个容量为C的背包，物品i的重量是wi，其价值为vi，背包问题是如何选择装入背包的物品，//使得装入背包中物品的总价值最大?)package org;

import java.util.*;

public class KnapSack1 { public static void main(String[] args) { Scanner in = new Scanner(System.in); System.out.println("请输入物品的数量:"); int n = in.nextInt(); int[] w = new int[n]; int[] v = new int[n]; System.out.println("现在请输入这些物品的重量:"); for (int i = 0; i < n; i++) { w[i] = in.nextInt(); } System.out.println("现在请输入这些物品的价值:"); for (int i = 0; i < n; i++) { v[i] = in.nextInt(); } System.out.println("现在请输入背包的容量:"); int c = in.nextInt(); /** *按单位重量价值r[i]=v[i]/w[i]降序排列 */ double startTime = System.currentTimeMillis(); double[] r = new double[n]; int[] index = new int[n]; for (int i = 0; i < n; i++) { r[i] = (double) v[i] / (double) w[i]; index[i] = i; } double temp = 0; for (int i = 0; i < n - 1; i++) { for (int j = i + 1; j < n; j++) { if (r[i] < r[j]) { temp = r[i]; r[i] = r[j]; r[j] = temp; int x = index[i]; index[i] = index[j]; index[j] = x; } } } /** *排序后的重量和价值分别存到w1[]和v1[]中 */ int[] w1 = new int[n]; int[] v1 = new int[n]; for (int i = 0; i < n; i++) { w1[i] = w[index[i]]; v1[i] = v[index[i]]; } System.out.println(Arrays.toString(w1)); System.out.println(Arrays.toString(v1)); /** *初始化解向量x[n] */ int[] x = new int[n]; for (int i = 0; i < n; i++) { x[i] = 0; } /** *求解并打印解向量 */ for (int i = 0; i < n; i++) { if (w1[i] < c) { x[i] = 1; c = c - w1[i]; } } System.out.println("解向量是:" + Arrays.toString(x)); /** *根据解向量求出背包中存放物品的最大价值并打印 */ int maxValue = 0; for (int i = 0; i < n; i++) { if (x[i] == 1) maxValue += v1[i]; } System.out.println("背包中物品的最大价值为:"+ maxValue); }}/* * 贪心算法描述： 1.改变数组w和v的排列顺序，使其按单位重量价值v[i]/w[i]降序排列； 2.将数组x[n]初始化为0； //初始化向量 * 3.i=1; 4.循环直到（w[i]>C); 4.1 x[i]=1; 4.2 C=C-w[i]; 4.3 i++; 5. x[i]=C/w[i]; */package org;

import java.util.*;

public class KnapSack2 { public static void main(String[] args) { Scanner in = new Scanner(System.in); System.out.println("请输入物品的数量:"); int n = in.nextInt(); int[] w = new int[n]; int[] v = new int[n]; System.out.println("现在请输入这些物品的重量:"); for (int i = 0; i < n; i++) { w[i] = in.nextInt(); } System.out.println("现在请输入这些物品的价值:"); for (int i = 0; i < n; i++) { v[i] = in.nextInt(); } System.out.println("现在请输入背包的容量:"); int c = in.nextInt(); /** *按单位重量价值r[i]=v[i]/w[i]降序排列 */ double[] r = new double[n]; int[] index = new int[n]; for (int i = 0; i < n; i++) { r[i] = (double) v[i] / (double) w[i]; index[i] = i; } double temp = 0; for (int i = 0; i < n - 1; i++) { for (int j = i + 1; j < n; j++) { if (r[i] < r[j]) { temp = r[i]; r[i] = r[j]; r[j] = temp; int x = index[i]; index[i] = index[j]; index[j] = x; } } } /** *排序后的重量和价值分别存到w1[]和v1[]中 */ int[] w1 = new int[n]; int[] v1 = new int[n]; for (int i = 0; i < n; i++) { w1[i] = w[index[i]]; v1[i] = v[index[i]]; } System.out.println(Arrays.toString(w1)); System.out.println(Arrays.toString(v1)); /** *调用函数KnapSackBackTrack()，输出打印装完物品以后的最大价值 */ KnapSackBackTrack(w1, v1, w1.length, c); } /** *用回溯法求0、1背包最大价值的函数定义 */ public static void KnapSackBackTrack(int[] w, int[] v, int n, int c) { int CurrentWeight = 0; int CurrentValue = 0; int maxValue = 0; int i = 0; while (i >= 0) { if (CurrentWeight + w[i] <= c) { CurrentWeight += w[i]; CurrentValue += v[i]; i++; } else break; } if (i < n) { maxValue = CurrentValue; System.out.println("背包中物品的最大价值为:"+ maxValue); return; } System.out.println("背包中物品的最大价值为:"+ maxValue); return; }}/* 回溯算法描述： 1.将各物品按单位重量价值从大到小排序； 2.bestP=0; 3.BackTrack(1); 4.输出背包的最大值bestP; BackTrack(int i) 1. if(i>n){ if(bestP<cp) bestP=cp; return; } 2.若（cw+w[i]<=C,则 //进入左子树 2.1 cw=cw+w[i]; 2.2 cp=cp+p[i]; 2.3 BackTrack(i+1); 2.4 cw=cw-w[i]; cp=cp-p[i]; */---------------------------------------------------------------------------------------------------

专利

最新回复(0)