减治法（引例中位数、查找问题：折半&二叉&选择、排序问题：堆排序、组合问题：淘汰赛冠军问题&假币问题）

查找问题 

 折半查找

        折半查找与待查值每比较依次，根据比较结果是的查找的区间减半

        *前提：序列有序，若序列无序，需要先进行排序

#include
using namespace std;
 
int BinSearch(int r[],int n,int k){
	int low=0,high=n-1;
	int mid;
	while(low<=high){
		mid=(low+high)/2;
		if(k
			high=mid-1;
		}
		else if(k>r[mid]){
			high=mid+1;
		}
		else{
			return mid;
		}
	}
	return -1; //查找失败，返回-1 
}
 
int main(){
	int n;
	cout<<"请输入序列长度:"<
	cin>>n; 
	int a[n];
	cout<<"请输入序列："<
	for(int i=0;i
		cin>>a[i];
	}
	int k;
	cout<<"请输入待查找的值："<
	cin>>k;
	int res;
	res=BinSearch(a,n,k);
	cout<<"您所查找的值在"<"下标位置"<
	return 0;
}

二叉查找树（有bug）

        若左子树不为空，左子树上所有结点小于根结点；右子树不为空，右子树上所有结点大于根节点；左右子树都是二叉排序树。

        #在一个无序序列中执行查找操作，可以将无序序列建立一个二叉查找树，然后再二叉查找树中查找值为k的记录。若成功，返回记录k的存储地址；失败，返回空。

#include
using namespace std;
//用二叉链表存储二叉查找树，设root为指向二叉链表的跟指针
struct BiNode{
	int data;
	BiNode *lchild,*rchild;
}; 
 
//二叉树存在以后，二叉树的查找算法 
BiNode *searchBST(BiNode *root,int k){
	if(root==NULL) //如果二查找树为空，查找失败
	{
		return NULL; 
	} 
	if(root->data==k){ //如果相等 查找成功
		return root; 
	}
	else if(root->data//向左边递归查找 查找左子树 
		return searchBST(root->lchild,k); 
	}
	else if(root->data>k){ //向右递归查找 查找右子树
		return searchBST(root->rchild,k); 
	}
}
 
//在执行查找操作之前首先需要建立无序二叉查找树
BiNode *InsertBST(BiNode *root,int data){
	if(root==NULL){
		//首先 为data申请一个新的结点 
		root=new BiNode;
		root->data=data;
		//其次，让该结点成为叶子结点
		root->lchild=root->rchild=NULL;
		return root; 
	}
	if(data<=root->data){//插入在左子树 
		root->lchild=InsertBST(root->lchild,data);
	}
	else if(data>root->data){//插入在右子树 
		root->rchild=InsertBST(root->rchild,data);
	}
	return root;
}
 
//将无序序列建立一个二叉查找树
BiNode *CreateBST(int a[],int n){
	BiNode *T=NULL;
	for(int i=0;i
		T=InsertBST(T,a[i]); //在二叉查找树中插入元素a[i] 
	}
	return T;
} 
 
int main(){
	int n;
	cout<<"请输入待排序的结点个数："<
	cin>>n;
	int a[n];
	BiNode *T=new BiNode();
	cout<<"请输入每个结点："<
	for(int i=0;i
		cin>>a[i];
		T=CreateBST(a,n);
	}
	int k;
	cout<<"请输入待查找的值"<
	cin>>k;
	cout<<"查找值就在"; 
	cout<<searchBST(T,k)<<"位置";
}

 选择问题：寻找T的第k小元素的问题

#include
using namespace std;
 
int Partition(int r[],int low,int high){
	//对数据进行划分 
	//无序数组 左边 右边 左小右大
	int i=low,j=high;
	while(i
		//扫描右侧 
		while(i
		if(i
			//如果左边比右边的大 就交换 （左小右大）
			int temp=r[i];
			r[i]=r[j];
			r[j]=temp;
			i++; //移动左边的指针 
		}
		//扫描左侧 
		while(i
		if(i
			//如果右边比左边的小 就交换 保证左边是小的 右边是大的
			int temp=r[i];
			r[i]=r[j];
			r[j]=temp; 
			j--; //右边的指针向左移动 
		}
	}
	//循环结束i=j时候
	//返回i的坐标就是中间值 
	return i;
}
 
int SelectMink(int r[],int k,int low,int high)
{
	//选择问题的实现 k是待查找的数 
	int s;//s是要找的轴值 （位置坐标） 
	s= Partition(r,low,high);
	//如果在中间，就直接返回找到了 ！查找成功 
	if(s==k){
		return r[s];
	}
	//如果k
	else if(k
		return SelectMink(r,k,low,s-1);
	}
	//如果k>r[i] 在右边递归查找 
	else{
		return SelectMink(r,k,s+1,high);
	}
}
 
int main(){
	cout<<"请输入数据总数："<
	int n;
	cin>>n;
	int r[n];
	cout<<"请输入数据:"<
	for(int i=0;i
		cin>>r[i];
	}
	int k; //传入的是数据的位置坐标 
	cout<<"请输入想查找的第k个元素："<
	cin>>k;
	k=k-1; 
	int low=0,high=n-1;
	int res=SelectMink(r,k,low,high); //要找的是排行老四位置的数是多少 
	cout<
}

排序问题

插入排序：用插入排序的方法对一个记录序列进行升序排列。

*依次将待排序序列中的每一个记录插入到一个已经排好序的序列中，直到所有记录都排好序

#include
using namespace std;
/*
void InsertSort(int r[],int n){
	int i,j=0; //待排序记录序列存储在r[1]~r[n]中 
	for(i=2;i<=n;i++){ //从第二个记录开始执行插入操作
		if(r[i]
			r[0]=r[i]; //暂存待插记录，设置哨兵
			for(j=i-1;r[j]>r[0];j--){ //寻找插入位置
				r[j+1]=r[j]; //记录后移 
			}
		} 
		r[j+1]=r[0]; 
	}
}*/
 
void InsertSort(int* arr, int n)
{
	for (int i = 0; i < n - 1; ++i)
	{
		//记录有序序列最后一个元素的下标
		int end = i;
		//待插入的元素
		int tem = arr[end + 1];
		//单趟排
		while (end >= 0)
		{
			//比插入的数大就向后移
			if (tem < arr[end])
			{
				arr[end + 1] = arr[end];
				end--;
			}
			//比插入的数小，跳出循环
			else
			{
				break;
			}
		}
		//tem放到比插入的数小的数的后面
		arr[end  + 1] = tem;
		//代码执行到此位置有两种情况:
		//1.待插入元素找到应插入位置（break跳出循环到此）
		//2.待插入元素比当前有序序列中的所有元素都小（while循环结束后到此）
	}
}
int main(){
	int n;
	cout<<"请输入个数："<
	cin>>n;
	int r[n];
	cout<<"请输入数组："<
	for(int i=0;i
		cin>>r[i];
	}
	InsertSort(r,n);
	cout<<"排序后的结果是："<
	for(int i=0;i
		cout<" ";
	}
	return 0;
}

堆排序 

*1）筛选法：整成大（小）顶堆

2）将堆顶元素和堆的最后一个元素进行交换，重复步骤1

#include
using namespace std;
 
//首先将无序序列调整成堆，由于叶子结点均可以看作是堆，因此，可以从编号最大的分支节点直至根节点反复调用筛选法 
void SiftHeap(int r[],int k,int n){
	//筛选法 输入的数组 数组规模 
	int i,j,temp;//i:要筛选的结点 j:i的左孩子
	i=k;
	j=2*i+1;
	while(j
		if(j-1&&r[j]1]) j++; //比较i的左右孩子 j
		if(r[i]>r[j]) break; //结束比较 根节点已经大于左右孩子中的较大者 
		else{
			temp=r[i]; //交换 
			r[i]=r[j];
			r[j]=temp;
			i=j; //被筛选结点位于原来结点j的位置 
			j=2*i+1; //j得继续找做孩子 
		}		 
	} 
}
 
void HeapSort(int r[],int n){
	//堆排序 变成从小到大的输出顺序了 
	int i,temp;
	for(i=(n-1)/2;i>=0;i--){ //从最后一个非叶结点开始 
		SiftHeap(r,i,n); //调整成堆 
	}
	for(i=1;i<=n-1;i++){
		//重复执行移走对顶及重建堆的操作
		temp=r[0];
		r[0]=r[n-i];
		r[n-i]=temp;
		SiftHeap(r,0,n-i);//只需要调整根节点 
	}
}
 
//堆排序 
int main(){
	int n;
	cout<<"请输入数据总数:";
	cin>>n;
	int a[n];
	cout<<"请输入数组:";
	for(int i=0;i
		cin>>a[i];
	} 
	HeapSort(a,n);
	for(int i=0;i
		cout<
	}
	return 0;
}

组合问题

淘汰赛冠军问题

char Game(int n,char r[]){
	int i=n;
	while(i>1){ //比赛直到剩余1人即为冠军
		i=i/2;
		for(int j=0;j
			if(Comp(r[j+1],r[j])) //模拟两位选手比赛 若mem1获胜返回1 
				//若mem2获胜返回0 
				r[j]=r[j+1]; //将胜者存入r[j]中 
		} 
	}
	return r[0]; //返回冠军 
}

 实例：洛谷

#include 
using namespace std;
struct node
{
	int num,grade;//编号，能力值
} a[130];//最多为2^7，即128，故设数组130
int main()
{
	int n,m = 1;
	cin>>n;
	for(int i = 1;i <= n;i++) m *= 2;//共有z^n支队伍
	for(int i = 1;i <= m;i++)
	{
		a[i].num = i;//记录编号 
		cin>>a[i].grade;
	}
	while(m > 2)//循环条件 
	{
		int q = 0;//初始化 
		for(int i = 1;i <= m;i += 2)//每次+2，两两比较的缘故 
		{
			if(a[i].grade > a[i + 1].grade) a[++q] = a[i]; //q为计数用
			else a[++q] = a[i + 1];
		} 
		m /= 2;//每次减少一半，a数组的前一半便是晋级的队伍
	}
	//最后只剩下两支队伍，比较后输出亚军的编号，即能力值较小的队伍 
	if(a[1].grade > a[2].grade) cout<2].num<
	else cout<1].num<
	return 0; 
} 

 假币问题

add1存储第一组硬币的重量和

add2存储第二组硬币的重量和

add3存储第三组硬币的重量和

add1

add2

add1=add2 在第三组中

#include 
using namespace std;
const int N=8;
 
int a[N]={2,2,1,2,2,2,2,2}; //假币的重量是1 
 
int Coin(int low,int high,int n){
	int i,num1,num2,num3; //分别存储三个硬币的个数
	int add1=0,add2=0;//存储前两组硬币的重量和
	if(n==1){
		return low+1; //递归结束条件 
	}
	if(n%3==0){//如果恰好可以被整除
		num1=n/3; 
		num2=n/3;
	}
	else{
		num1=n/3+1; //前两组向上取整 
		num2=n/3+1;
	}
	num3=n-num1-num2; //不管是那种情况，第三种的个数都是这也
	//计算重量
	for(i=0;i
		add1=add1+a[low+i];
	} 
	for(i=num1;i
		add2=add2+a[low+i];
	}
	//两组比较大小
	if(add1//在第一组中 
		return Coin(low,low+num1-1,num1); 
	} 
	else if(add1>add2){//在第二组中
		return Coin(low+num1,low+num1+num2-1,num2); 
	} 
	else{//在第三组中
		return Coin(low+num1+num2,high,num3); 
	} 
} 
 
int main()
{
	int n;
	n=Coin(0,7,8);
	cout<
}