直接或间接地调用自身的算法称为递归算法。用函数自身给出定义的函数称为递归函数。 在计算机算法设计与分析中，使用递归技术往往使函数的定义和算法的描述简洁且易于理解。
对于大运算来说由于过程太多效率很低，且开销大，常用递推代替
编写一个递归函数，将10进制转化成radix进制（输出二进制形式）
#include using namespace std; void change(int t,int r){ if(t!=0){ change(t/r,r); cout<<t%r; } } int main(){ cout<<“10jinzhi”<<endl; int ten; int radix; cin>>ten>>radix; cout<<“out”<<radix<<" jinzhi"<<endl; change(ten,radix); cout<<endl; return 0; }
逆序，正序数位输出
#include using namespace std; void Reverse( int n); int main(){ Reverse(12345); } void Reverse( int n){ if(n/10==0) cout<<n; else{ cout<<n%10; Reverse(n/10); } }
//下面是另一种输出 /void Reverse( int n){ if(n/10==0) cout<<n<<" “; else{ Reverse(n/10); cout<<n%10<<” "; } }/
集合的全排列问题
设计一个递归算法生成n个元素{r1,r2,…,rn}的全排列（n!种）。 设R={r1,r2,…,rn}是要进行排列的n个元素， Ri=R-{ri}。 集合X中元素的全排列记为perm(X)。 (ri)perm(X)表示在全排列perm(X)的每一个排列前加上前缀得到的排列。
#include using namespace std;
void Perm(int list[], int k, int m){ if(k==m){ for(int i=0;i<=m;i++) cout<<list[i]<<" "; cout<<endl; } else for(int j=k;j<=m;j++) { swap(list[k],list[j]); Perm(list,k+1,m); swap(list[k],list[j]); } } int main(){ int list[] = {1,2,3,4,5,6}; Perm(list,0,3); return 0; }
整数划分问题
将正整数n表示成一系列正整数之和：n=n1+n2+…+nk， 其中n1≥n2≥…≥nk≥1，k≥1。 正整数n的这种表示称为正整数n的划分。求正整数n的不同划分个数。 例如正整数6有如下11种不同的划分： 6； 5+1； 4+2，4+1+1； 3+3，3+2+1，3+1+1+1； 2+2+2，2+2+1+1，2+1+1+1+1； 1+1+1+1+1+1。
#include using namespace std; int zshf(int n,int m){ if(n<1) return 0; else if(n1||m1) return 1; else if(n<m) return zshf(n,n); else if(n==m) return zshf(n,m-1)+1; return zshf(n,m-1)+zshf(n-m,m); } int main(){ int n; n=zshf(6,3); cout<<n<<endl; return 0; }
排队购票问题
一场球赛开始前，售票工作正在紧张进行中。 每张球票为50元， 有m+n个人排队等待购票， 其中有m 个人手持50元的钞票， 另外n个人手持100元的钞票。 求出这m+n个人排队购票，使售票处不至出现找不开钱的局面的不同排队种数 。（约定：开始售票时售票处没有零钱；拿同样面值钞票的人对换位置为同一种排队。）
#include
using namespace std;
int f(int n,int m){ int y; if(m==0) y=1; else if(n<m) y=0; else y=f(n-1,m)+f(n,m-1); return y; } int main() { int n,m; cout<<“请输入”<<endl; cin>>n>>m; cout<<f(n,m); }
分治思想
分治法的基本思想 分治法的基本思想是将一个规模为n的问题分解为k个规模较小的子问题，这些子问题互相独立且与原问题相同。 对这k个子问题分别求解。如果子问题的规模仍然不够小，则再划分为k个子问题，如此递归的进行下去，直到问题规模足够小，很容易求出其解为止。 将求出的小规模的问题的解合并为一个更大规模的问题的解，自底向上逐步求出原来问题的解。 分治法的设计思想是，将一个难以直接解决的大问题，分割成一些规模较小的相同问题，以便各个击破，分而治之。
大事化小，小事化了
可以应用分治法的情况
该问题的规模缩小到一定的程度就可以容易地解决；
该问题可以分解为若干个规模较小的相同问题 利用该问题分解出的子问题的解可以合并为该问题的解；
该问题所分解出的各个子问题是相互独立的，即子问题之间不包含公共的子问题。
这条特征涉及到分治法的效率，如果各子问题是不独立的，则分治法要做许多不必要的工作，重复地解公共的子问题，此时虽然也可用分治法，但一般用动态规划较好
二分搜索技术
#include
using namespace std;
int BinarySearch(int a[],int x,int n){ int left = 0; int right = n-1; while(left<=right){ int middle = (left+right)/2; if(x==a[middle]) return middle; else if(x>a[middle]) left = middle+1; else right=middle-1; } return -1; }
int main() { int a[]={9,5,4,6,2,3}; cout<<BinarySearch(a,5,6); }
众数和重数
问题描述：给定含有n个元素的多重集合S，每个元素在S中的次数称为该元素的重数。多重集S中重数最大的元素称为众数。 例如，S={1,2,2,2,3,5}。众数为2，其重数为3。 任务：对于给定的由n个自然数组成的多重数集S,编程计算S的众数及其重数。
#include using namespace std; struct mdata{ int data; int count; }; void msort(int a[], int s, int e, mdata &result){ int left,right,middle,count=1; left=s;right=e;middle=(s+e)/2; int temp=a[left]; while(left<right){ while(a[right]>=temp){ if(a[right]==temp) count++; right–; } if(left<right) a[left]=a[right]; while(a[left]<temp){ if(a[left]==temp) count++; left++; } if(left<right) a[left]=a[right]; } a[right]=temp; if(count>result.count){result.count=count; result.data=temp; } if(right-s>result.count) msort(a,s,right-1, result); if(e-right>result.count) msort(a,right+1,e,result); return ; } int main() { mdata result={0,0}; int a[10]={2,1,3,2,5,2,3,3,3,3}; msort(a,0,9,result); cout<<result.data<<" "<<result.count<<endl; return 0; }
循环赛日程表
循环赛日程表问题，设有n=2k个选手要进行循环赛，设计一个满足以下要求的比赛日程表：
每个选手必须与其他n-1个选手各赛一次；
每个选手一天只能赛一次；
循环赛一共进行n-1天。
#include using namespace std; #define MAX 100 int a[MAX][MAX]; void Copy(int tox, int toy, int fromx, int fromy, int r) { for (int i = 0; i < r; i++) for (int j = 0; j < r; j++) a[tox + i][toy + j] = a[fromx + i][fromy + j]; }
void Table(int k) { int i, r; int n = 1; for (i = 1; i <= k; i++) n = n * 2; for (i = 0; i < n; i++) a[0][i] = i + 1; //k´Î¿½±´,r¾ØÐÎÇøÓòµÄ¿í¶È for (r = 1; r < n; r = r * 2) for (i = 0; i < n; i += 2 * r) { Copy(r, r + i, 0, i, r); Copy(r, i, 0, r + i, r); / } }
int main() { Table(3); for (int i = 0; i <= 7; i++) { for (int j = 0; j <= 7; j++) cout << a[i][j] << " "; cout << endl; } return 0; }
棋盘覆盖问题
在一个2k×2k个方格组成的棋盘中，恰有一个方格与其他方格不同，称该方格为一特殊方格，且称该棋盘为一特殊棋盘。 在棋盘覆盖问题中，要用图示的4种不同形态的L型骨牌覆盖给定的特殊棋盘上除特殊方格以外的所有方格，且任何2个L型骨牌不得重叠覆盖。 覆盖任意一个2k×2k的特殊棋盘，用到的骨牌数恰好为(4K-1)/3。
//ÆåÅ̸²¸ÇÎÊÌâ #include using namespace std; int tile=1; int board[4][4]; void CB(int tr, int tc, int dr, int dc, int size) { if (size == 1) return; int t = tile++; int s = size / 2;
if (dr < tr + s && dc < tc + s) CB(tr, tc, dr, dc, s); else { // Óà t ºÅLÐ͹ÇÅƸ²¸ÇÓÒÏÂ½Ç board[tr + s - 1][tc + s - 1] = t; // ¸²¸ÇÆäÓà·½¸ñ CB(tr, tc, tr + s - 1, tc + s - 1, s); } if (dr < tr + s && dc >= tc + s) CB(tr, tc + s, dr, dc, s); else { board[tr + s - 1][tc + s] = t; CB(tr, tc + s, tr + s - 1, tc + s, s); } if (dr >= tr + s && dc < tc + s) CB(tr + s, tc, dr, dc, s); else { board[tr + s][tc + s - 1] = t; CB(tr + s, tc, tr + s, tc + s - 1, s); } if (dr >= tr + s && dc >= tc + s) CB(tr + s, tc + s, dr, dc, s); else { board[tr + s][tc + s] = t; CB(tr + s, tc + s, tr + s, tc + s, s); }} int main() { int s; int size=1; cin >> s; for (int i = 1; i <= s; i++) { size = size * 2; } int dr, dc; cin >> dr >> dc; CB(0, 0, dr, dc, size); for (int i = 0; i < 4; i++) { for (int j = 0; j < 4; j++) cout << board[i][j]; cout << endl; }
}
输油管道问题
某石油公司计划建造一条由东向西的主输油管道。该管道要穿过一个有n口油井的油田。从每口油井都要有一条输油管道沿最短路经（或南或北）与主管道相连。 如果给定n口油井的位置，即它们的x坐标（东西向）和y坐标（南北向），应如何确定主管道的最优位置，即使各油井到主管道之间的输油管道长度总和最小的位置？
给定n口油井的位置，编程计算各油井到主管道之间的输油管道最小长度总和。
#include #include using namespace std; int main() { int n; int x; int y; int a[12]; cin >> n; for (int k = 0; k < n; k++) { cin >> x >> a[k]; } sort(a, a + n);
int min = 0; for (int i = 0; i < n; i++) { min += (int)fabs(a[i] - a[n / 2]); } cout << min << endl;}
