前言就不说概念了,就写写讲过的题的思想,晚上写写老师讲的题的代码; 

第二章递归与分治:

汉诺塔问题(Hanoi):

  • 解决思想就是:将n-1个碟子借助b移动到c,在将最后一个移动到b,最后在将n-1个碟子借助a从c到b;
  • 终止条件:n=0;
  • 移动方法是从a->b->c->a,在移动圆盘的时候,若是奇数次移动,则将最小的圆盘移动到顺时针方向的下一个塔座上,若是偶数次移动,则在其他两个塔座之间,将较小的圆盘移动到另一个塔座上去;

排列问题:

  • 题目:问题描述:R={r1,r2,…,rn}是要进行排列的n个元素,求R的全排列Perm(R)
  • 递归关系:perm(R)由(r1)perm(R1),(r2)perm(R2)  ,…, (rn)perm(Rn)构成,其中Ri=R-{ri}。
  • 终止条件:n=1时,Perm(R)=r ,r是R中的唯一元素
  • 参数设置:待排序数组List,开始下标k,终止下标m
  • 思想:
  • 将整组数中的所有的数分别与第一个数交换,这样就总是在处理后n-1个数的全排列。
  • 代码:
    #include<iostream>
    using namespace std;
    void prem(int list[],int k,int m){
        if(k==m){//递归终止条件
            for(int i=0;i<m;i++){
                cout<<list[i]<<" ";
            }
            cout<<endl;
        }
        else{
            for(int i=k;i<m;i++){
                swap(list[k],list[i]);
                /*将每一个数都与要排列的第一个数
                交换这样就只用处理m-k个数的全排列了*/
                prem(list,k+1,m);//递归后面的数
                swap(list[k],list[i]);/*递归完成之后
                恢复原样要不会影响后续的排列的*/
            }
        }
    }
    int main(){
        int a[]={1,3,5,6};
        prem(a,0,4);
    }

分治思想:

  • Divide:整个问题划分为多个子问题。

  • Conquer:求解各子问题(递归调用设计的算法)

  • Combine:合并子问题的解,形成原问题的解。

大整数乘法:

  • 问题:

    输入n10进制整数XY (XY位数较大)

    输出:XY乘积

  • 需要进行4次n/2位乘的操作,3次不超过2n位的整数加法,2次移位   则

     至于O(n2)则是根据master定理;

  • 改进是通过数学手段减少了乘的次数;

Strassen矩阵乘法:

  • 问题:给定两个n*n的矩阵A,B,求C=A*B

  • 进行了8次n/2*n/2的矩阵乘法,还有4次矩阵加法,矩阵加法的时间复杂度为O(n2)则

     

  • 改进是通过数学手段,减少他的乘的次数;

棋盘覆盖问题:

  • 不做详解了,晚上出代码讲解,结合代码理解吧;

快速排序:

  • 想是:以a[p]为基准元素将a[p:r]分成三段 a[p:q-1], a[q],  a[q+1:r],

           a[p:q-1]<a[q]<a[q+1:r]   递归分解:对a[p:q-1]和a[q+1:r]进行排序   合并:不需任何运算;

  • 代码:

  • #include<iostream>
    using namespace std;
    int parition(int a[],int p,int r){
        int i=p,j=r+1,x=a[p];
        while(true){
            while(a[++i]<x&&i<r);
            while(a[--j]>x);
            if(i>=j){
                break;
            }
            swap(a[i],a[j]);
        }
        a[p]=a[j];
        a[j]=x;
        return j;
    }
    void QuickSort(int a[],int p,int r){
        if(p<r){
            int q=parition(a,p,r);
            QuickSort(a,p,q-1);
            QuickSort(a,q+1,r);
        }
    }
    int main(){
        int a[]={4,8,3,7,1};
        QuickSort(a,0,4);
        for(int i=0;i<=4;i++){
            cout<<a[i]<<" ";
        }
    }
    

     

循环赛日程表:

  • 我也有点懵,二维指针,申请空间int **a=new int *[n];//开辟行空间for(int i=0;i<n;i++)a[i]=new int [n];//开辟列空间;
  • 代码:
    #include <iostream>
    #include <cmath>
    using namespace std;
    void Table(int k, int **a) {
    	int n = pow(2, k);
    	for (int i = 1; i <= n; i++)
    		a[1][i] = i;
    	int m = 1;
    	for (int s = 1; s <= k; s++) {
    		n /= 2;
    		for (int t = 1; t <= n; t++) {
    			for (int i = m + 1; i <= 2 * m; i++) {
    				for (int j = m + 1; j <= 2 * m; j++) {
    					a[i][j + (t - 1) * m * 2] =
    							a[i - m][j + (t - 1) * m * 2 - m];
    					a[i][j + (t - 1) * m * 2 - m] =
    							a[i - m][j + (t - 1) * m * 2];
    				}
    			}
    		}
    		cout << endl;
    		m *= 2;
    	}
    	//输出日程安排
    	
    }
    
    
    int main() {
    	using namespace std;
    	int k;
    	cin >> k;
    	int n = pow(2, k);
    	n+= 1; //行列从标号1开始
    	//二级指针作为参数的创建和消除的方法
    	int **a=new int*[n];
        for(int i=0;i<n;i++){
            a[i]=new int[n];
        }
    	Table(k, a);
    	for (int i = 1; i <n; i++) {
    		for (int j = 1; j <n; j++)
    			cout << a[i][j] << " ";
    		cout << endl;
    	}
    }
    
    

    建议背住代码;不太好理解;