算法复习笔记（四）减治法

减治法部分的初步学习，从下面四个例子：

1.折半查找

2.二叉树查找

3.选择问题

4.组合问题中的减治:

减治法的核心：

与分治法不同，减治法只针对其部分子问题进行求解，同时也是采取划分后选择计算的思想

补充知识点：

中位数：

中位数是一个非常具有代表性的数字，我们在现实生活中，通常会选择中位数来代表

一部分数据的趋势，相比于平均数更加具有代表性。

1.折半查找：

            基本思想：

                    （1）若给定值与中间记录的关键码相等，查找成功

                    （2）若给定值少于中间记录的关键码，则在中间记录的左半区继续查找

                    （2）若给定值大于中间记录的关键码，则在中间记录的右半区继续查找

    2.1.1折半查找算法实现 ：递归

#include<iostream>
 using namespace std;
 int searchMin(int r[],int low,int heigh,int k)
 {
     int mid=(low+heigh)/2;
     if(low>heigh)
     return 0;
     if(r[mid]==k)
    return mid+1;
    else if(r[mid]>k)
        return searchMin(r,low,mid-1,k);
    else
        return searchMin(r,mid+1,heigh,k);
 }
 int main()
 {
     int a[10]={1,3,5,8,12};
     int k=0;
    cin>>k;
     cout<<searchMin(a,0,4,k);
     return 0;
  }            

折半查找算法实现 ：非递归

#include <iostream>
using namespace std;
int BinSerchMid(int r[],int n,int k)
{   int low=0,high=n-1,mid;
    while (low<=high)
    {   mid=(low+high)/2; 
        if ( k<r[mid]) high=mid-1;
        else if ( k>r[mid]) low=mid+1;
             else  return mid+1; 
    }
    return 0;
}
int main( )
{    int  a[100],b[100],n,k,i,ans;
     cin>>n>>k; 
     for (i=0; i<n; i++) cin>>a[i];
     ans=BinSerchMid(a,n,k);
     if (ans==0) cout<<"No !"<<endl;   else  cout<<ans<<endl;
}           

2.二叉查找树

//二叉查找树
#include<iostream>
using namespace std;
struct BiNode
{
    int data;
    BiNode *lchild;
    BiNode *rchild;
};

BiNode * SearachBST(BiNode *root,int k)
{
    if(root==NULL)
        return NULL;
    else if(root->data ==k )
    {
        cout<<"找到了 "<<root->data<<endl;
        return root;
    }
        else if(k<root->data)
            return SearachBST(root->lchild,k);
        else
            return SearachBST(root->rchild,k);
}

BiNode * InsertBST(BiNode * root,int data)
{
    if(root==NULL)
    {
        root=new BiNode;
        root->data=data;
        root->lchild=root->rchild=NULL;
        return root;
    }
    if(data<=root->data)
        root->lchild=InsertBST(root->lchild,data);
    else
        root->rchild=InsertBST(root->rchild,data);
    return root;
}

BiNode * createBST(int a[],int n)
{
    //为 T 申请一个新结点，该结点为叶子 
    BiNode *T=new BiNode;
    T->data=a[0];T->lchild=T->rchild=NULL; 
    for(int i=0;i<n;i++)
    {
        InsertBST(T,a[i]);
        /*if(T->data==0)
        cout<<"T==NULL";*/    
    }
    return T;

}


int main()
{
    BiNode * TR=new BiNode;
    int r[100]={10,45,67,83,42,58,55,90,70,63};
    TR=createBST(r,10);
    for(int i=0;i<10;i++)
        cout<<SearachBST(TR,r[i])<<" ";
    return 0;
}           

思想：

快速排序的patition下得出的位置是稳定的

我们通过这位位置和K进行比较 从而找出需要我们排序的那一部分

复杂性分析：深度至少是【log2n】至多是n，所以二叉排序树的查找性能在o(log2n)和o(n)之间

        2.3选择问题：

算法分析：    

（1）最好情况：每次划分的轴值恰好是序列的中值，这可以保证处理的区间比上次减半，由于在一次划分后，只需处理一个子序列，比较次数的递推式是：

        T(n)=T(n/2)+O(n)=O(n)

（2）最差情况：每次划分的轴值恰好是序列的最大值／最小值，这可以保证处理的区间比上次少一，比较次数的递推式是：

        T(n)=T(n-1)+O(n)=O(n的平方)

（3）平均情况：假设每次划分的轴值恰好是序列的中的一个随机位置，处理区间按照一种随机的方式减少，可以证明，算法的平均时间是O(n)

//查找第K小的数
#include<iostream>
using namespace std;

int patition(int r[],int low,int heigh)
{
    int i=low,j=heigh;
    while(i<j &&r[i]<r[j])
    j--;
    if(i<j&& r[i]>r[j])
    {
        int temp=r[i];
        r[i]=r[j];
        r[j]=temp;
        i++;
    }
    while(i<j &&r[i]<r[j])
    i++;
    if(i<j&& r[i]>r[j])
    {
        int temp=r[i];
        r[i]=r[j];
        r[j]=temp;
        j++;
    }
    return i;
    
}

int searchMinK(int r[],int low,int heigh,int k)
{
    int pv=0;
    pv=patition(r,low,heigh);
    if(pv==k)
    return r[k];
    else if(pv>k)
        return searchMinK(r,low,pv-1,k);
        else
        return searchMinK(r,pv+1,heigh,k);
}

int main()
{
    int a[10]={1,8,4,3,5};
    int k=0;
    cin>>k;
    cout<<searchMinK(a,0,4,k);    
    return 0;
 }
            

        4.1假币问题：

       问题描述：

        在n枚外观相同的硬币中，有一枚是假币，并且已知假币较轻。可以通过一架天平来任意比较两组硬币，从而得知两组硬币的重量是否相同，或者哪一组更轻一些，但不知道轻多少，假币问题是要求设计一个高效的算法来检测出这枚假币。

        算法思路：

        解决这个问题的最自然的想法就是一分为二，也就是把硬币分成两组。把n枚硬币分成两组，每组有枚硬币，如果n为奇数，就留下一枚硬币，然后把两组硬币分别放到天平的两端。

        如果两组硬币的重量相同，那么留下的硬币就是假币；否则，用同样的方法对较轻的那组硬币进行同样的处理，假币一定在较轻的那组里。

        算法分析：

           在假币问题中，每次用天平比较后，只需解决一个规模减半的同样的问题，所以，它属于一个减治算法。该算法在最坏情况下满足如下的递推式：

算法的复杂性为O(log2n)。

Important!!!

假币问题的改进算法：考虑不是把硬币分成两组，而是分成三组，前两组有n/3组硬币，其余的硬币作为第三组，将前两组硬币放到天平上。

       如果他们的重量相同，则假币一定在第三组中，用同样的方法对第三组进行处理；如果前两组的重量不同，则假币一定在较轻的那一组中，用同样的方法对较轻的那组硬币进行处理。

显然这个改进算法存在递推式：

const int N=8; //假设求解8枚硬币问题
int a[N]={2,2,1,2,2,2,2,2];//真币的重量是2，假币的重量是1
int Coin(int low,int high,int n)//在a[low]-a[high]中查找假币
{
    int i,num1,num1,num3;//num1,num2和num3存储3组硬币的个数
    int add1=0,add2=0;//add1和add2存储前两组硬币重量和
    if(n==1)
        return low+1;//返回序号，即下标+1
    if(n%3 =0) //三组硬币的个数相同
        num1=num2=n/3;
    else
        num1=num2=n/3+1;//前两组由[n/3]枚硬币
    num3=n-num1-num2;
    for(i=0;i<num1;i++) //计算第一组硬币的重量和
        add1=add1+a[low+1];
    for(i=num1;i<num1+num2;i++)
        add2=add2+a[low+1];
    if(add1<add2) //在第1组查找，下标范围是low-low+num1-1
        return Coin(low,low+num1-1,num1);
    else if (add1>add2)//在第2组查找，下标范围是low+num1到low+num1+num2-1 
        return Coin(low+num1,low+num1+num2-1,num2);
    else  //在第1组查找，  
        return Coin(low+num1+num2,high,num3)'
 }