蓝桥杯——递归二：典型递归模型（2017.2.20）

1. 递归法实现折半查找

源代码：

法一：

#include <stdio.h>#define maxn 1010int Find(int a[],int k,int low,int high){	int i,mid;	if(low>high)		i=-1;	else	{		mid=(low+high)/2;		if(a[mid]==k)			i=mid;		else if(a[mid]<k)			i=Find(a,k,mid+1,high);		else			i=Find(a,k,low,mid-1);	}	return i;}int main(){	int a[maxn];	int i,n,k;	int low,high,index;	while(scanf("%d",&n)!=EOF)	{		for(i=0;i<n;i++)			scanf("%d",&a[i]);		scanf("%d",&k);		low=0,high=n-1;		index=Find(a,k,low,high);		if(index>=0)			PRintf("%d/n",index+1);		else			printf("Not found!/n");	}	return 0;}法二：
#include <stdio.h>#define maxn 1010void Find(int a[],int k,int low,int high){	int i,mid;	if(low>high)		printf("Not found!/n");	else	{		mid=(low+high)/2;		if(a[mid]==k)			printf("%d/n",mid+1);		else if(a[mid]<k)			Find(a,k,mid+1,high);		else			Find(a,k,low,mid-1);	}}int main(){	int a[maxn];	int i,n,k;	int low,high,index;	while(scanf("%d",&n)!=EOF)	{		for(i=0;i<n;i++)			scanf("%d",&a[i]);		scanf("%d",&k);		low=0,high=n-1;		Find(a,k,low,high);	}	return 0;}程序截图：
2. 递归法求Fibonacci数列的第n项，其中1<=n<=40
源代码：
#include <stdio.h>#define maxn 1010int fib(int n){	if(n==1 || n==2)		return 1;	else		return fib(n-1)+fib(n-2);}int main(){	int i,n;	while(scanf("%d",&n)!=EOF)		printf("fib(%d)=%d/n",n,fib(n));	return 0;}程序截图：
3. 汉诺塔问题
源代码：
#include <stdio.h>int step=0;void print(char x,char y){	printf("%c->%c/n",x,y);	step++; }void move(int n,char s1,char s2,char s3)    //s1-起点 s2-经过的柱 s3-终点 {	int step=0;	if(n==1)		print(s1,s3);	else	{		move(n-1,s1,s3,s2);		print(s1,s3);		move(n-1,s2,s1,s3);	}}int main(){	int n;	while(scanf("%d",&n)!=EOF)	{		move(n,'A','B','C');                //将n个盘子从A柱移到C柱		printf("step=%d/n",step);		step=0;	}	return 0;}程序截图：
4. 几种排序算法的递归实现
（1）冒泡排序
源代码：
#include <stdio.h>#include <string.h>#define maxn 1010void bubblesort(int a[],int start,int end){	int i,t;	if(start<=end)	{		for(i=start;i<end;i++)		{			if(a[i]<a[i+1])			{				t=a[i];				a[i]=a[i+1];				a[i+1]=t;			}		}		printf("%d ",a[end]);		end--;		bubblesort(a,start,end);	}}int main(){	int i,n,a[maxn]={0};	int start,end;	while(scanf("%d",&n)!=EOF)	{		for(i=0;i<n;i++)			scanf("%d",&a[i]);		start=0,end=n-1;		bubblesort(a,start,end);		printf("/n");		memset(a,0,sizeof(n));	}	return 0;}程序截图：
（2）选择排序
源代码：
#include <stdio.h>#define maxn 1010void SelectSort(int a[],int start,int end){	int i,j,k;	int t,index;	if(start<end)	{		t=a[start];		index=start;		for(i=start+1;i<end+1;i++)		{			if(a[index]>a[i])				index=i;		}		if(start!=index)		{			t=a[start];			a[start]=a[index];			a[index]=t;		}		start++;		SelectSort(a,start,end);	}}int main(){	int n,a[maxn];	int i,start,end;	while(scanf("%d",&n)!=EOF)	{		for(i=0;i<n;i++)			scanf("%d",&a[i]);		start=0,end=n-1;		SelectSort(a,start,end);		for(i=0;i<n;i++)			printf("%d ",a[i]);		printf("/n");	}	return 0;}程序截图：
（3）快速排序
源代码：
#include <stdio.h>#define maxn 1010void Quicksort(int a[],int left,int right){	int i=left,j=right;	int tmp;	if(left<right)	{		tmp=a[left];		while(i!=j)		{			while(j>i && a[j]>=tmp)				j--;			a[i]=a[j];			while(i<j && a[i]<=tmp)				i++;			a[j]=a[i];		}		a[i]=tmp;		Quicksort(a,left,i-1);		Quicksort(a,i+1,right);	}}int main(){	int i,n,left,right;	int a[maxn];	while(scanf("%d",&n)!=EOF)	{		for(i=0;i<n;i++)			scanf("%d",&a[i]);		left=0,right=n-1;		Quicksort(a,left,right);		for(i=0;i<n;i++)			printf("%d ",a[i]);		printf("/n");	}	return 0;}程序截图：
5. 递归打印杨辉三角形
源代码：
#include <stdio.h>int fun(int x,int y){	if(y==0 || y==x)		return 1;	else		return (fun(x-1,y-1)+fun(x-1,y));}int main(){	int i,j,n;	while(scanf("%d",&n)!=EOF)	{		for(i=0;i<n;i++)		{			for(j=0;j<=i;j++)				printf("%4d",fun(i,j));			printf("/n");		}	}	return 0;}程序截图：
附各题思路分析及要点整理：