遞歸(Recursion)：指函數(shù)的定義中調(diào)用函數(shù)自身的方法硕糊。
遞歸調(diào)用過程：
Recursion
舉個很好玩的栗子：
用遞歸調(diào)用輸出圖片上的字:
#include <stdio.h>
void Recursion(int depth){
printf("抱著");
if (!depth) printf("我的小鯉魚");
else Recursion(--depth);
printf("的我");
}
int main(){
printf("嚇得我抱起了\n");
Recursion(2);
putchar('\n');
}
爬樓梯：
小明爬樓梯，他每次可以走一級或兩級臺階郎逃，輸入樓梯的級數(shù)，求不同的走法數(shù)。
分析：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個籃子里放法總數(shù)為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的整數(shù)勋眯，可以使用加減乘除四種運算以及括號把這四個數(shù)連接起來得到一個表達式∮の啵現(xiàn)在的問題是是否存在一種方式使得表達式的值等于24
- 分析：n個數(shù)算24，必須先有兩個數(shù)先算客蹋，剩下的問題就變成了n-1個數(shù)算24塞蹭，所以可以枚舉先算的兩個數(shù)以及運算方式
邊界條件：一個數(shù)算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)：將一個難以直接解決的大問題分割成一些規(guī)模較小的相同問題，以便各個擊破讶坯，分而治之番电。
適用條件：
- 規(guī)模縮小到一定程度可以解決
- 該問題可以分解為幾個規(guī)模較小的相同問題
- 子問題的解可以合并成大問題的解
- 子問題相互獨立
一般算法設計模式：
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)：
問題描述：給定一個單調(diào)遞增的整數(shù)序列辆琅，問某個整數(shù)是否在序列中漱办。
//在數(shù)組a中查找x，n代表數(shù)組長度
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)：
歸并：將兩個有序的數(shù)組歸并成一個更大的有序數(shù)組婉烟。
歸并排序：先(遞歸地)將一個數(shù)組分成兩半分別排序娩井，然后將結果歸并起來。
//原地歸并似袁，將a[low,mid]和a[mid+1,high]合并為一個有序數(shù)組洞辣。
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];//輔助數(shù)組
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數(shù)組中
else if(j>high)a[k]=aux[i++];//右半邊用完
else if(aux[i]<aux[j])a[k]=aux[i++];
else a[k]=aux[j++];
}
}
//將數(shù)組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):
步驟：
- 從數(shù)列中挑出一個元素扬霜，稱為"基準"(pivot)定鸟。
- 重新排序數(shù)列，所有比基準值小的元素擺放在基準前面著瓶，所有比基準值大的元素擺在基準后面（相同的數(shù)可以到任何一邊）联予。在這個分區(qū)結束之后，該基準就處于數(shù)列的中間位置蟹但。這個稱為分區(qū)（partition）操作躯泰。
- 對”基準”左邊和右邊的兩個子集，不斷重復第一步和第二步华糖，直到所有子集只剩下一個元素為止
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;
}
