分治法

分治法：分解，对小问题进行求解，合并小问题结果

合并排序

#define MAX 100
int MergeSort(int A[], int n){
	if(n<=1){
		return 1;
	}else{
		MergeSort(A,n/2);//对前半部分排序 
		MergeSort(A+n/2,n-n/2);//后半部分排序 
		Merge(A,n);//合并 
		return 1;
	}
}

int B[MAX];
int Merge(int A[],int n){
	int mid,s1,s2,i,b;
	mid=n/2;
	s1=0;
	s2=mid;
	b=0;
	while(s1<mid&&s2<n){
		if(A[s1]<=A[s2]){//判断前半部分和后半部分的第一个值谁小，就复制到B数组中，然后转到下一个位置， 
			B[b++]=A[s1++];//继续判断这个值和另一个数组的当前第一个值谁小 
		}else{
			B[b++]=A[s2++]; 
		}
	}
	if(s1<mid){//将剩余元素转移到B中（已排好序，且比前面的值都大） 
		for(i=s1;i<mid;i++){
			B[b++]=A[i];
		}
	}else{
			for(i=s2;i<n;i++){
			B[b++]=A[i];
		}
	}
	for(i=0;i<n;i++){//将B数组复制给A 
		A[i]=B[i]; 
	}
	return 1;
} 

快速排序

#include<iostream>
using namespace std;

int QuickSort(int A[],int n){
	int p;
	if(n<=1){
		return 1;
	}else{
		  p=Partition(A);//划分 
		  QuickSort(A,p);//第一部分排序 
		  QuickSort(A+P+1,n-p-1);//第二部分排序 
		  return 1;
	}
}

int Partition(int A[],int n){
	int low,high,x,p,i;
	p=A[0];//记录主元 
	x=0;//空指针 
	low=0;
	high=n-1;
	while(low<high){//指针从两头相对扫描直到相遇 
		while(low<high&&A[high]>p){//从后向前寻找比主元p小的元素 
			high--;
		}
		if(low<high){//A[high]<=p 
			A[x]=A[high];
			x=high;
		}
		while(low<high&&A[low]<=p){//从前向后寻找比主元p大的元素 
			low++;
		}
		if(low<high){//A[low]>p 
			A[x]=A[low];
			x=low;
		}
	}
	A[x]=p;
	return x;
}

二分搜索

int BinarySearch(int A[],int n,int x){
	//返回数组下标，查询失败返回-1 
	int mid,t;
	if(n<=0){
		return -1;
	}else{
		mid=n/2;
		if(A[mid]==x){
			return mid;
		}else if(x<A[mid]){
			return BinarySearch(A,mid,x);
		}else{
			t=BinarySearch(&A[n+mid+1],n-mid-1,x);
			return (t==-1)?-1:mid+1+t;
		}
	}
}

棋盘覆盖问题

#include<iostream>
using namespace std;

void chessBoard(int tr,int tc,int dr,int dc,int size);

const int maxNum=100;
int number;
int board[100][100];

int main(){
	int size_,x,y;
 	printf("请输入棋盘尺寸和特殊方块的方位：");
 	cin>>size_>>x>>y;
 	board[x][y]=number=1;
 	chessBoard(0,0,x,y,size_);
 	for(int i=0;i<size_;i++){
	 	for(int j=0;j<size_;j++){
	 		cout<<board[i][j]<<" ";
		 }
		 cout<<endl;
	 }
	 return 0;
}

void chessBoard(int tr,int tc,int dr,int dc,int size){
	//tr,tc是子棋盘左上角坐标，dr,dc是特殊 
	if(size==1){
		return;
	} 
	int t=++number;
	int s=size/2;//分割棋盘
	//	覆盖左上角子棋盘 
	if(dr<tr+s&&dc<tc+s){//特殊方格在此棋盘中 
		chessBoard(tr,tc,dr,dc,s);
	}else{//此棋盘中无特殊方格，则用t号L型骨牌覆盖该子棋盘 
		board[tr+s-1][tc+s-1]=t;
		chessBoard(tr,tc,tr+s-1,tc+s-1,s);
	}
	
	
		//覆盖右上角棋盘 
	if(dr<tr+s&&dc>=tc+s){//特殊方格在此棋盘中 
			chessBoard(tr,tc+s,dr,dc,s);
		}else{//此棋盘中无特殊方格，则用t号L型骨牌覆盖该子棋盘
			board[tr+s-1][tc+s]=t;
			chessBoard(tr,tc+s,tr+s-1,tc+s,s);
		}	
		
		//	覆盖左下角子棋盘 
	
		if(dr>=tr+s&&dc<tc+s){//特殊方格在此棋盘中 
		chessBoard(tr+s,tc,dr,dc,s);
	}else{//此棋盘中无特殊方格，则用t号L型骨牌覆盖该子棋盘 
		board[tr+s][tc+s-1]=t;
		chessBoard(tr+s,tc,tr+s,tc+s-1,s);}
		
		//覆盖右下角棋盘 
		if(dr>=tr+s&&dc>=tc+s){//特殊方格在此棋盘中 
			chessBoard(tr+s,tc+s,dr,dc,s);
		}else{//此棋盘中无特殊方格，则用t号L型骨牌覆盖该子棋盘
			board[tr+s][tc+s]=t;
			chessBoard(tr+s,tc+s,tr+s,tc+s,s);
		}
	}