欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识！
您现在的位置是： 首页

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

程序员文章站 2022-05-13 17:06:55
...

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

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;
}



3.选择问题

思想：
快速排序的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.组合问题中的减治:

        4.1假币问题：

       问题描述：

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

        算法思路：

        解决这个问题的最自然的想法就是一分为二，也就是把硬币分成两组。把n枚硬币分成两组，每组有枚硬币，如果n为奇数，就留下一枚硬币，然后把两组硬币分别放到天平的两端。
        如果两组硬币的重量相同，那么留下的硬币就是假币；否则，用同样的方法对较轻的那组硬币进行同样的处理，假币一定在较轻的那组里。

        算法分析：

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

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

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

Important!!!

假币问题的改进算法：考虑不是把硬币分成两组，而是分成三组，前两组有n/3组硬币，其余的硬币作为第三组，将前两组硬币放到天平上。
       如果他们的重量相同，则假币一定在第三组中，用同样的方法对第三组进行处理；如果前两组的重量不同，则假币一定在较轻的那一组中，用同样的方法对较轻的那组硬币进行处理。

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

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

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

示例代码：

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)'
 }

相关标签： 算法设计 减治法 假币问题 选择问题

上一篇： MyMVC框查找Action的过程详解

下一篇： php ftp_connect()返回bool(true)

推荐阅读