-
CUMT算法导论课程
-
课本：计算机算法设计与分析（王晓东）
-
本blog代码为Java实现
第二章 分治与递归
递归
直接或间接调用算法自身。
全排列问题
求出n个元素的全排列，可以使用递归。即若要求出\(Perm(X_i)\),可以先求出\(Perm(X_{i-1})\),然后再依次加上前缀。
设\(R=\){\(r_1,r_2,r_3,···,r_n\)}是要进行排列的n个元素，\(R_i=R-\){\(r_i\)}。\((r_i)\)\(Perm(X)\)代表X的全排列加上前缀ri
R的全排列定义为：
当n = 1时,Perm(R) = r。
当n>1时,Perm(R)为 \((r_1)Perm(R_1),(r_2)Perm(R_2),···(r_n)Perm(R_n)\)。
代码实现：
/**
* @author CrisKey
* @date 2022/11/17 18:38
* 全排列问题
*/
public class Arrangement {
public int fullPermutation(List<String> list,int k,int m,int count){ //打印list[k:m]
//递归到递归基
if (k==m){
System.out.println(list);
count++;
}
for (int i=k;i<m;i++){
Collections.swap(list,i,k);
count = fullPermutation(list,k+1,m,count);
Collections.swap(list,i,k);
}
return count;
}
public static void main(String[] args) {
List<String> list = new ArrayList<>();
list = Arrays.asList("1","3","5","7","9");
Arrangement arrangement = new Arrangement();
int count = 0;
count = arrangement.fullPermutation(list,0,list.size(),count);
System.out.println("总共有"+count+"种排列方式");
}
}
整数划分问题
将正整数n表示为一系列正整数之和，
\(n=n_1+n_2+···+n_k\) (其中，\(n_1\ge n_2\ge n3 \ge ···\ge n_k \ge 1,k\ge 1\))
同样，本题可以用递归求解。
分析后可知，本题分为四种情况。
/**
* @author CrisKey
* @date 2022/11/17 19:39
* 整数划分问题
*/
public class Divide {
public static int partition(int n,int m){
if (n==1||m==1){
return 1;
}else if (m==n){
//整形本身
return partition(n,m-1)+1;
}else if (m>n){
return partition(n,n);
}else if (n<1||m<1) {
return 0;
}else {
return partition(n,m-1)+partition(n-m,m);
}
}
public static void main(String[] args) {
int x = 6;
int count = partition(x,x);
System.out.println("正整数x共有:"+String.valueOf(count)+"种划分");
}
}
Hanoi塔问题
汉诺塔是典型的递归问题。
/**
* @author CrisKey
* @date 2022/11/17 20:48
* 汉诺塔问题
*/
public class HanoiProblem {
public static void hanoi(int n,String A,String B,String C){
if (n>0){
hanoi(n-1,A,C,B);
System.out.println("将"+String.valueOf(n)+"从"+A+"移到"+C+"借助"+B);
hanoi(n-1,C,B,A);
}
}
public static void main(String[] args) {
hanoi(3,"A","B","C");
}
}
分治
二分搜索
二分搜索给定已排序好的n个元素，在这n个元素中找到特定元素x。
可以利用分治与递归，将问题划分为在数组的左边查找或者在数组的右边查找，可以降低时间复杂度。
使用二分搜索最坏情况下复杂度为\(O(logn)\)
/**
* @author CrisKey
* @date 2022/11/17 21:15
*/
public class BinarySearchProblem {
public static void BinarySearch(int[] arr,int left,int right,int flag){
if (right<left){
System.out.println("错误");
}else if (right==left){
if (flag==arr[right]){
System.out.println(right);
}
}
else{
int mid = (right-left)/2;
if (arr[mid]==flag){
System.out.println(mid);
}else if (arr[mid]<flag){
BinarySearch(arr,mid+1,right,flag);
}else {
BinarySearch(arr,left,mid-1,flag);
}
}
}
public static void main(String[] args) {
int []arr = new int[]{0,1,2,3,4,5,6,7,8,9,10};
BinarySearch(arr,0,10,5);
}
}
大整数乘法
\(设X与Y都是n位二进制数，现在要计算他们的乘积XY\)。
可以将\(X Y\)分段，将其分别分为两段，每段长\(n/2\)位。
