文章目录
- 二、分治与递归
-
- 1、递归
-
- 1.1、递归的思想
- 1.2、选择排序
- 1.3、生成排列
- 1.4、如何求解递归方程（图解）
- 2、分治
-
- 2.1、分治的思想
- 2.2、什么时候可以使用分治（一般符合4个条件）
- 2.3、简单样例
-
- 2.3.1、二分搜索
- 2.3.2、快速排序
- 2.3.3、归并排序
- 2.4、进阶样例
-
- 2.4.1、覆盖残缺棋盘
- 2.4.2、大整数乘法（n位）
- 2.4.3、Strassen矩阵乘法实现
二、分治与递归
1、递归
1.1、递归的思想
递归：一个函数自己调用自己的过程我们称为递归。
递归是计算机、数学、运筹等领域经常使用给的最强大的解决问题办法的方法之一，它用一种简单的方式来解决那些用其他方法解决可能挺复杂的问题。而且有些问题利用递归来解决可能简单易于理解。
**基本思想：**把一个问题划分为一个或者多个规模更小子问题，用相同的办法来解决更小规模的子问题。
递归算法设计的基本步骤：
- 问题的初始条件（
递归结束的出口条件
- 设计一个策略，将一个问题划分为一个或者
多个一步步接近递归出口的相似的规模更小的子问题。
- 将所解决的各个小问题的解组合得到原问题的解。
如果无法保证递归有出口，则递归无法结束导致内存耗尽。
经典问题——汉诺塔问题
我们如果按照正常思维想，当问题规模变大，那将是无法想象的难。
按照递归的思想：
- 问题是：
将n个盘中从A移动到C
- 子问题：
将n-1个盘从B移动到C
- 当要移动的盘子剩下1个直接移动即可。
void hanoi(int n,char A,char B,char C){//第一个位置表示n个盘的位置，第二个位置是辅助柱，第三个盘是目的盘
//问题：n个盘从A移动到C
if(n==1){//出口条件
printf("%c ---> %c\n",A,C);
return;
}
else//子问题
hanoi(n-1,A,C,B) ;//n个盘从A移动到C--先将n-1个盘借助C移动到B
printf("%c ---> %c\n",A,C);//再将剩下的一个盘中从A移动到C
hanoi(n-1,B,A,C);//最后将n-1个盘从B移动到C
}
1.2、选择排序
选择排序：每次寻找数列中的最小元素（或者最大元素）排在
已经排好序的数字（开始时为空）后面
，最后完成排序。
很明显：n个元素先找到最小的元素，排序。然后再在剩下的n-1个元素里面先找到最小的元素，排序。依此类推。当剩下的元素只剩下1个，则直接排序。
1.3、生成排列
给定一个数字n（正整数）,如何生成从0到n的全排列序列？（
n!
）如n=3
- 1 2 3
- 1 3 2
- 2 1 3
- 2 3 1
- 3 1 2
-
3 2 1
6种全排列 ，（3！）=6
算法学习（二）分治递归二、分治与递归
#include<stdio.h>
void swap(int a[],int i,int j){
int temp;
temp = a[i];
a[i]=a[j];
a[j]=temp;
}
void display(int a[],int n){
for(int i=0;i<n;i++){
printf("%d ",a[i]);
}
printf("\n");
}
void getN(int a[],int start,int n){//对n个数全排列,序列升序
if(start>=n){//出口条件
display(a,n);//打印数组
return;
}
for(int i=start;i<n;i++)//这个下标是谁先排在前面
{
swap(a,i,start);//保证每次选到的数都排在前面
getN(a,start+1,n);//剩下的n-1个数进行全排列
//交换回来
swap(a,i,start);//保证下一次我们不改变序列
}
}
int main(){
int n=5;
int a[n];
for(int i=0;i<n;i++){
a[i]=i+1;
printf("%d ",a[i]);
}
printf("开始：\n");
getN(a,0,n);
}
1.4、如何求解递归方程（图解）
应用：
2、分治
2.1、分治的思想
2.2、什么时候可以使用分治（一般符合4个条件）
注意如果子问题不是独立的，就会包括大量的重复计算，我们就会用到动态规划里边所说的
带备忘录的自顶向下
计算。动态规划和分治法非常类似，都有最优子结构特征，都要能划分为子问题。动态规划要求子问题一般是重叠的。
2.3、简单样例
2.3.1、二分搜索
2.3.2、快速排序
快排我们很熟悉了，利用了一个基准值，然后两个下标（理解为哨兵放哨）。图中的A[q]就是我们说的基准值了。一般基准值是随机选择基准策略防止因数据的特征导致的快排效率不够好。因为快排的效率取决于划分的对称性。
2.3.3、归并排序
拓展：
2.4、进阶样例
2.4.1、覆盖残缺棋盘
问题描述：
在一个有2N ×2N个方格组成的棋盘中，有一个方格残缺（残缺方格位置随机），要求用如下①~④的三格板完全覆盖棋盘中为残缺的方格。
三格板的编号：4个格子缺少第i格，则为i号
输入：输入N、残缺格子的位置（二维数组里边的位置，用值0表示）
输出填充的情况
例如：下面是一个4×4的棋盘，其中黑色的方格代表残缺的方格。
使用三格板覆盖后如下图
分析问题：
- 问题规模是N，棋盘大小是2N × 2N
下面我们以一组分析如下：
边界情况：当N=0，不需要三格板；当N=1，需要一个三格板；
很好的符合了分治的4个特点：
- 问题规模变小时比较容易解决
- 问题可以划分为若干个子问题
- 子问题的解合并为问题的解
- 子问题之间独立
算法设计
package dataStruct;
import java.util.Scanner;
/**
* 分治法实现残缺棋盘的覆盖
*/
public class ChessBoard {
public int tile =1;
public int[][] board=new int[100][100];//棋盘
/**
*
* @param tr 开始填充的位置 行下标
* @param tc 开始填充的位置 列下标
* @param dr 残缺格子的位置 行下标
* @param dc 残缺格子的位置 列下标
* @param size 棋盘的规模数，2^size
*/
public void chessBoard(int tr,int tc,int dr,int dc,int size){
if(size == 1)//问题规模如果是1，不需要填充
return;
int t = tile++;//三格板的编号
int s = size / 2;//分割棋盘，如8*8——4*4——2*2
//覆盖左上角棋盘
if(dr < tr + s && dc < tc + s)
{//残缺方格在左上角
chessBoard(tr, tc, dr, dc, s);
}
else
{//此部分无残缺方格，将右下角方格当成残缺方格
board[tr + s - 1][tc + s - 1] = t;
chessBoard(tr, tc, tr + s - 1, tc + s - 1, s);
}
//覆盖右上角棋盘
if (dr < tr + s && dc >= tc + s)
{//残缺方格在右上角
chessBoard(tr, tc + s, dr, dc, s);
}
else
{//此部分无残缺方格，将左下角方格当成残缺方格
board[tr + s -1][tc + s] = t;
chessBoard(tr, tc + s, tr + s - 1, tc + s, s);
}
//覆盖左下角棋盘
if (dr >= tr + s && dc < tc + s)
{//残缺方格在左下角
chessBoard(tr + s, tc, dr, dc, s);
}
else
{//此部分无残缺方格，将右上角方格当成残缺方格
board[tr + s][tc + s - 1] = t;
chessBoard(tr + s, tc, tr + s, tc + s -1, s);
}
//覆盖右下角棋盘
if (dr >= tr + s && dc >= tc + s)
{//残缺方格在右下角
chessBoard(tr + s, tc + s, dr, dc, s);
}
else
{//此部分无残缺方格，将左上角方格当成残缺方格
board[tr + s][tc + s] = t;
chessBoard(tr + s, tc + s, tr +s, tc + s, s);
}
}
public void displayBoard(int size){
for(int i=0;i<size;i++){
for(int j=0;j<size;j++){
System.out.printf("%-4d",board[i][j]);//类似于C语言的printf函数。
}
System.out.println();
}
}
public static void main(String[]args){
Scanner sc = new Scanner(System.in);
int size = sc.nextInt();
int tr = sc.nextInt();
int tc = sc.nextInt();
int dr = sc.nextInt();
int dc = sc.nextInt();
ChessBoard chessBoard = new ChessBoard();
chessBoard.chessBoard(tr,tc,dr,dc,size);
chessBoard.displayBoard(size);
}
}
因为数组初始化时默认为0，我这里没有将残缺格子赋值为0 了。
2.4.2、大整数乘法（n位）
我们都知道当整数的位数很大，使用乘法计算，可能导致的数溢出，或者计算效率低下。n位数字一一相乘，位数大变得慢。那么我们有没有可能将其优化呢？
答案是肯定的！我们可以利用分治法。分而治之，再合并结果。
情况有如下的三种：
我们只需要每次分治的时候，判断当前的位数N是否为奇数，奇数我们将N+1，理解为补0.
当N<4,我们不需要分治了，直接计算返回结果。
也就是我们只需要知道处理情况2就行了。如图所示：
#include<stdio.h>
#include<math.h>
#include<iostream>
using namespace std;
int SIGN(long A)
{
return A > 0 ? 1 : -1;
}
//X、Y为输入的数 ，n为对齐后的位数
long caculatorBigNumber(long X,long Y, int n){
int sign = SIGN(X) * SIGN(Y);
if (X == 0 || Y == 0)//位数不同的时候，补充的0使得分割得到的数为0
return 0;
if(n<4)
return X*Y; //当划分的位数小于4，我们不需要再递归分治了，直接计算。
if(n%2==1)//保证每次划分后我们判断划分的位数是不是偶数，不是我们就必须补充0，让它变为偶数
n=n+1;
X = labs(X);
Y = labs(Y);
//我们的位数是对齐修改为了偶数
long A = (long)(X / pow(10, n / 2));
long B = (X % (long)pow(10, n / 2));
long C = (long)(Y / pow(10, n / 2));
long D = (Y % (long)pow(10, n / 2));
long AC = caculatorBigNumber(A, C, n / 2);
long BD = caculatorBigNumber(B, D, n / 2);
long ABCD = caculatorBigNumber((A - B), (D - C), n / 2) + AC + BD;
//cout<<"A="<<A<<" B="<<B<<" C="<<C<<" D="<<D<<endl;
//cout<<"AC="<<AC<<" BD="<<BD<<" ABCD="<<ABCD<<endl;
return (long long)(sign * (AC * pow(10, n) + ABCD * pow(10, n / 2) + BD));
}
int main(){
int i=0;
while(i<10){
long a ,b;
int n;
printf("请输入要计算的数:\n");
scanf("%ld%ld",&a,&b);
printf("请输入两个数中最大的位数：\n");
scanf("%d",&n);
printf("%ld",caculatorBigNumber(a,b,n));
i++;
}
return 0;
}
注意，这里的数据不能输入过大，否则溢出。
2.4.3、Strassen矩阵乘法实现
1、传统的矩阵乘法公式：
也就是蛮力法
代码实现：
int[][] maxtixCaculator(int [][]maxtix1,int [][]maxtix2,int n){
int [][]result = new int[n][n];
for(int i=0;i<n;i++){
for(int j=0;j<n;j++){
result[i][j]=0;
for(int k=0;k<n;k++){
result+=maxtix1[i][k]*maxtix2[k][j];
}
}
}
return result;
}
2、简单的分治法实现：
算法导论中的伪码：
你好要设计好如何分块，同时还额外增加了递归栈，因此简单的分治法并没有比暴力法好。
那我们应该如何做才能优化呢？我们应该如同优化大整数乘法那个样子，将计算的子问题减少。简单的分治法进行了8个子问题的递归计算，如果我们可以将8变小则可以降低复杂度了 。
Strassen矩阵乘法：
由于代码比较长，就不想琢磨写了。参考这位仁兄的：
矩阵乘法三种方法（蛮力法、分治法、strassen）
package algorithms;
public class strassen {
//创建一个随机数构成的nxn矩阵
public static int[][] initializationMatrix(int n){
int[][] result = new int[n][n];//创建一个nxn矩阵
for(int i = 0;i < n;i++){
for(int j = 0;j < n;j++){
result[i][j] = (int)(Math.random()*10); //随机生成1~10之间的数
}
}
return result;
}
//蛮力法求矩阵相乘
public static int[][] BruteForce(int[][] p,int[][] q,int n){
int[][] result = new int[n][n];
for(int i=0;i<n;i++){
for(int j=0;j<n;j++){
result[i][j] = 0;
for(int k=0;k<n;k++){
result[i][j] += p[i][k]*q[k][j];
}
}
}
return result;
}
//分治法求矩阵相乘
public static int[][] DivideAndConquer(int[][] p,int[][] q,int n){
int[][] result = new int[n][n];//创建一个nxn矩阵
//当n为2时，用蛮力法求矩阵相乘，返回结果结果
if(n == 2){
result = BruteForce(p,q,n);
return result;
}
//当n大于3时，采用分治法，递归求最终结果
if(n > 2){
int m = n/2;
//将矩阵p分成四块
int[][] p1 = QuarterMatrix(p,n,1);
int[][] p2 = QuarterMatrix(p,n,2);
int[][] p3 = QuarterMatrix(p,n,3);
int[][] p4 = QuarterMatrix(p,n,4);
//将矩阵q分成四块
int[][] q1 = QuarterMatrix(q,n,1);
int[][] q2 = QuarterMatrix(q,n,2);
int[][] q3 = QuarterMatrix(q,n,3);
int[][] q4 = QuarterMatrix(q,n,4);
//将结果矩阵分成同等大小的四块
int[][] result1 = QuarterMatrix(result,n,1);
int[][] result2 = QuarterMatrix(result,n,2);
int[][] result3 = QuarterMatrix(result,n,3);
int[][] result4 = QuarterMatrix(result,n,4);
//最关键的步骤，递归调用DivideAndConquer()函数，并用公式相加
result1 = AddMatrix(DivideAndConquer(p1,q1,m),DivideAndConquer(p2,q3,m),m);//y=ae+bg
result2 = AddMatrix(DivideAndConquer(p1,q2,m),DivideAndConquer(p2,q4,m),m);//s=af+bh
result3 = AddMatrix(DivideAndConquer(p3,q1,m),DivideAndConquer(p4,q3,m),m);//t=ce+dg
result4 = AddMatrix(DivideAndConquer(p3,q2,m),DivideAndConquer(p4,q4,m),m);//u=cf+dh
//合并，将四块小矩阵合成整体
result = TogetherMatrix(result1,result2,result3,result4,m);//把分成的四个小矩阵合并成一个大矩阵
}
return result;
}
//strassen法
public static int[][] StrassenMethod(int[][] p,int[][] q,int n){
int[][] result = new int[n][n];//创建一个nxn矩阵
int m = n/2;
//将矩阵p分成四块
int[][] p1 = QuarterMatrix(p,n,1);
int[][] p2 = QuarterMatrix(p,n,2);
int[][] p3 = QuarterMatrix(p,n,3);
int[][] p4 = QuarterMatrix(p,n,4);
//将矩阵q分成四块
int[][] q1 = QuarterMatrix(q,n,1);
int[][] q2 = QuarterMatrix(q,n,2);
int[][] q3 = QuarterMatrix(q,n,3);
int[][] q4 = QuarterMatrix(q,n,4);
int[][] m1 = DivideAndConquer(AddMatrix(p1,p4,m),AddMatrix(q1,q4,m),m);
int[][] m2 = DivideAndConquer(AddMatrix(p3,p4,m),q1,m);
int[][] m3 = DivideAndConquer(p1,ReduceMatrix(q2,q4,m),m);
int[][] m4 = DivideAndConquer(p4,ReduceMatrix(q3,q1,m),m);
int[][] m5 = DivideAndConquer(AddMatrix(p1,p2,m),q4,m);
int[][] m6 = DivideAndConquer(ReduceMatrix(p3,p1,m),AddMatrix(q1,q2,m),m);
int[][] m7 = DivideAndConquer(ReduceMatrix(p2,p4,m),AddMatrix(q3,q4,m),m);
//将结果矩阵分成同等大小的四块
int[][] result1 = QuarterMatrix(result,n,1);
int[][] result2 = QuarterMatrix(result,n,2);
int[][] result3 = QuarterMatrix(result,n,3);
int[][] result4 = QuarterMatrix(result,n,4);
result1 = AddMatrix(ReduceMatrix(AddMatrix(m1,m4,m),m5,m),m7,m);
result2 = AddMatrix(m3,m5,m);
result3 = AddMatrix(m2,m4,m);
result4 = AddMatrix(AddMatrix(ReduceMatrix(m1,m2,m),m3,m),m6,m);
result = TogetherMatrix(result1,result2,result3,result4,m);//把分成的四个小矩阵合并成一个大矩阵
return result;
}
//获取矩阵的四分之一，number用来确定返回哪一个四分之一
public static int[][] QuarterMatrix(int[][] p,int n,int number){
int rows = n/2; //行数减半
int cols = n/2; //列数减半
int[][] result = new int[rows][cols];
switch(number){
//左上
case 1 :
{
for(int i=0;i<rows;i++)
for(int j=0;j<cols;j++)
result[i][j] = p[i][j];
break;
}
//右上
case 2 :
{
for(int i=0;i<rows;i++)
for(int j=0;j<n-cols;j++)
result[i][j] = p[i][j+cols];
break;
}
//左下
case 3 :
{
for(int i=0;i<n-rows;i++)
for(int j=0;j<cols;j++)
result[i][j] = p[i+rows][j];
break;
}
//右下
case 4 :
{
for(int i=0;i<n-rows;i++)
for(int j=0;j<n-cols;j++)
result[i][j] = p[i+rows][j+cols];
break;
}
default:
break;
}
return result;
}
//把均分为四分之一的矩阵，合成一个矩阵
public static int[][] TogetherMatrix(int[][] a,int[][] b,int[][] c,int[][] d,int n){
int[][] result = new int[2*n][2*n];
for(int i=0;i<2*n;i++){
for(int j=0;j<2*n;j++){
if(i<n){
if(j<n)
result[i][j] = a[i][j];
else
result[i][j] = b[i][j-n];
}else{
if(j<n)
result[i][j] = c[i-n][j];
else
result[i][j] = d[i-n][j-n];
}
}
}
return result;
}
//求两个矩阵相加结果
public static int[][] AddMatrix(int[][] p,int[][] q,int n){
int[][] result = new int[n][n];
for(int i=0;i<n;i++){
for(int j=0;j<n;j++){
result[i][j] = p[i][j]+q[i][j];
}
}
return result;
}
//求两个矩阵相减结果
public static int[][] ReduceMatrix(int[][] p,int[][] q,int n){
int[][] result = new int[n][n];
for(int i=0;i<n;i++){
for(int j=0;j<n;j++){
result[i][j] = p[i][j]-q[i][j];
}
}
return result;
}
//输出矩阵的函数
public static void PrintfMatrix(int[][] matrix,int n){
for(int i=0;i<n;i++){
for(int j=0;j<n;j++)
System.out.printf("% 4d",matrix[i][j]);
System.out.println();
}
}
public static void main(String args[]){
int[][] p = initializationMatrix(8);
int[][] q = initializationMatrix(8);
//输出生成的两个矩阵
System.out.println("p：");
PrintfMatrix(p,8);
System.out.println();
System.out.println("q：");
PrintfMatrix(q,8);
//输出分治法矩阵相乘后的结果
int[][] bru_result = BruteForce(p,q,8);//新建一个矩阵存放矩阵相乘结果
System.out.println();
System.out.println("\np*q(蛮力法)：");
PrintfMatrix(bru_result,8);
//输出分治法矩阵相乘后的结果
int[][] dac_result = DivideAndConquer(p,q,8);//新建一个矩阵存放矩阵相乘结果
System.out.println();
System.out.println("p*q(分治法)：");
PrintfMatrix(dac_result,8);
//输出strassen法矩阵相乘后的结果
int[][] stra_result = StrassenMethod(p,q,8);//新建一个矩阵存放矩阵相乘结果
System.out.println("\np*q(strassen法)：");
PrintfMatrix(stra_result,8);
}
}
一个有趣的思考：