递归与分治

递归(Recursion)：指函数的定义中调用函数自身的方法。

递归调用过程：

Recursion

举个很好玩的栗子：

用递归调用输出图片上的字:

#include <stdio.h>
void Recursion(int depth){
    printf("抱着");
    if (!depth) printf("我的小鲤鱼");
    else Recursion(--depth);
    printf("的我");
}
int main(){
    printf("吓得我抱起了\n");
    Recursion(2);
    putchar('\n');
}

---

爬楼梯：

小明爬楼梯，他每次可以走一级或两级台阶，输入楼梯的级数，求不同的走法数。
分析：n级台阶走法=先走一级后（n-1）级台阶走法+先走两级后(n-2)级台阶走法,即f(n)=f(n-1)+f(n-2)，边界条件n=1 ,1 n=2, 2

int stairs(int n)
{
    if(n==1)return 1;
    else if(n==2)return 2;
    else return stairs(n-1)+stairs(n-2);
} 

---

放苹果：

把M个相同的苹果放在N个相同的篮子里，允许有的篮子空着不放，问共有多少种不同放法？5，1，1和1，5，1是同一种放法

• 分析：设i个苹果放在k个篮子里放法总数为f(i,k)则：
  k>i时，f(i,k)=f(i,i)，其他k-1个篮子为空
  k<=i时，总放法=有盘子为空的放法+没有盘子为空的放法
  f(i,k)=f(i,k-1)+f(i-k,k)
  f(i,k-1)可以理解为拿出来一个篮子空着不放，这样就变成了有盘子为空
  f(i-k,k)可以理解为拿出来k个苹果放在每个篮子里，保证篮子不空，然后放剩下的i-k个苹果。

int f(int m,int n)
{
  if(m==0)return 1;
  if(n<=0)return 0;
  if(n>m)return f(m,m);
  return f(m,n-1)+f(m-n,n);

---

算24:

给出4个小于10的整数，可以使用加减乘除四种运算以及括号把这四个数连接起来得到一个表达式。现在的问题是是否存在一种方式使得表达式的值等于24

• 分析：n个数算24，必须先有两个数先算，剩下的问题就变成了n-1个数算24，所以可以枚举先算的两个数以及运算方式
  边界条件：一个数算24

#include <iostream>
#include <cmath>
using namespace std;
double a[5];
#define EPS 1e-6
/* run this program using the console pauser or add your own getch, system("pause") or input loop */
bool count24(double a[],int n);

int main(int argc, char** argv) {
    for(int i=0;i<5;++i)cin>>a[i];
    while(a[0]!=0)
    {
        if(count24(a,4))cout<<"Yes"<<endl;
        else cout<<"No"<<endl;
        for(int i=0;i<5;++i)cin>>a[i];
    }
    return 0;
}
bool isZero(double x)
{
    return (fabs(x-24)<=EPS);
}
bool count24(double a[],int n)
{
    if(n==1)return isZero(a[0]-24);
    double b[5];
    for(int i=0;i<n-1;++i)
    {
        for(int j=i+1;j<n;++j)
        {
            int m=0;
            for(int k=0;k<n;++k)
            {
                if(k!=i&&k!=j)
                {
                    b[m++]=a[k];
                }
            }
            b[m]=a[i]+a[j];
            if(count24(b,m+1))return true;
            b[m]=a[i]-a[j];
            if(count24(b,m+1))return true;
            b[m]=a[i]*a[j];
            if(count24(b,m+1))return true;
            if(!isZero(a[j]))
            {
                b[m]=a[i]/a[j];
                if(count24(b,m+1))return true;
            }
            if(!isZero(a[i]))
            {
                b[m]=a[j]/a[i];
                if(count24(b,m+1))return true;
            }
            
        }
    }
    return false;
}

---

分治(divide-and-conquer)：将一个难以直接解决的大问题分割成一些规模较小的相同问题，以便各个击破，分而治之。

适用条件：

• 规模缩小到一定程度可以解决
• 该问题可以分解为几个规模较小的相同问题
• 子问题的解可以合并成大问题的解
• 子问题相互独立

一般算法设计模式：

divide-and-conquer(P)
{
    if(|P|<=n0)adhoc(p);    //base-case
    divide P into smaller subinstances P1,P2,P3...Pk;
    for(int i=1;i<=k;k++)
    {
        yi=divide-and-conquer(Pi);
    }
    return merge(y1,y2...yk);
}

---

二分查找(binary Search)：

问题描述：给定一个单调递增的整数序列，问某个整数是否在序列中。

//在数组a中查找x，n代表数组长度
int binarySearch(int *a,int n,int x)
{
    int low=0,high=n-1;
    int mid;
    while(low<=high)
    {
        mid=(low+high)/2;
        if(a[mid]==x){
            return mid;
        }
        else if(a[mid]<x)
        {
            low=mid+1;
        }
        else if(a[mid]>x)
        {
            high=mid-1;
        }
    }
    return -1;
}

---

归并排序(Merge Sort)：

归并：将两个有序的数组归并成一个更大的有序数组。
归并排序：先(递归地)将一个数组分成两半分别排序，然后将结果归并起来。

//原地归并，将a[low,mid]和a[mid+1,high]合并为一个有序数组。
void merge(int *a,int low,int high)
{
    int mid = (low + high)/2;
    int i = low;
    int j = mid + 1;
    int aux[high-low+1];//辅助数组
    for(int k = 0;k<=high;++k)
    {
        aux[k] = a[k];
    }
    for(int k=0;k<=high;++k)
    {
        if(i>mid)a[k]=aux[j++];//左半边用完，将右半边剩余元素复制到a数组中
        else if(j>high)a[k]=aux[i++];//右半边用完
        else if(aux[i]<aux[j])a[k]=aux[i++];
        else a[k]=aux[j++];
    }
}
//将数组a[low,high]排序。
void mergeSort(int* a,int low,int high)
{
    if(high>low){
        int mid=(high+low)/2;
        mergeSort(a,low,mid);
        mergeSort(a,mid+1,high);
        merge(a,low,mid,high);
    }
}

mergeSort

---

快速排序(quick Sort):

步骤：

1. 从数列中挑出一个元素，称为"基准"(pivot)。
2. 重新排序数列，所有比基准值小的元素摆放在基准前面，所有比基准值大的元素摆在基准后面（相同的数可以到任何一边）。在这个分区结束之后，该基准就处于数列的中间位置。这个称为分区（partition）操作。
3. 对”基准”左边和右边的两个子集，不断重复第一步和第二步，直到所有子集只剩下一个元素为止

void quickSort(int* a,int low,int high)
{
    if(high<=low)return;
    int j=partition(a,low,high);
    quickSort(a,low,j-1);
    quickSort(a,j+1,high);
}

int partition(int* a,int low,int high)
{
    int i=low;
    int j=high+1;
    int v=a[low];
    while(true)
    {
        while(a[++i]<v)if(i==high)break;
        while(v<a[--j])if(j==low)break;
        if(i>=j)break;
        swap(a[i],a[j]);
    }
    swap(a[low],a[j]);
    return j;
}

---