C++算法设计中的组合问题

内容导读

互联网集市收集整理的这篇技术教程文章主要介绍了C++算法设计中的组合问题，小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含1741字，纯文字阅读大概需要3分钟。

内容图文

分治法解决最大子段和问题

int MaxSum(int a[ ], int left, int right)
   {
       int sum=0,midsum=0,leftsum=0,rightsum=0;
       int center,s1,s2,lefts,rights;
       if (left==right) {      //如果序列长度为1，直接求解
           sum=a[left];          
       }
      else {
          center=(left+right)/2;    //划分
          leftsum=MaxSum(a, left, center);  
                                                       //对应情况①，递归求解
          rightsum=MaxSum(a, center+1, right);         //对应情况②，递归求解                                                     
        s1=0; lefts=0;             //以下对应情况③，先求解s1
        for (int i=center; i>=left; i--)
        {
            lefts+=a[i];
            if (lefts>s1) s1=lefts;
        }
        s2=0; rights=0;             //再求解s2
        for (int j=center+1; j<=right; j++)
        { 
            rights+=a[j];
            if (rights>s2) s2=rights;
        }
        sum=s1+s2;              //计算情况③的最大子段和 
        if (sum<leftsum) sum=leftsum;  
                     //合并，在sum、leftsum和rightsum中取较大者
        if (sum<rightsum) sum=rightsum;
     }
     return sum;
}

减治法解决淘汰赛冠军问题

bool Comp(char A,char B){//A大就赢 
   if(A<B){
   	return false;
   }
   return true;
} 
char Game(char r[], int n) {
        int i=n,j;
        while (i>1) {
	    i=i/2;
        for (j=0; j<i; j++)
            if (Comp(r[j+i],r[j]))
                r[j]=r[j+i];               //胜者放在 r[j] 中, j=0,1,2,…,i/2 -1
        }
       return r[0];
}

减治法和递归解决假币问题
假设：假币比较轻

int a[]={2,2,2,2,2,1,2,2}; 
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=num2=n/3;
	else  num1=num2=n/3+1;
	num3=n-num1-num2;
	for(i=0;i<num1;i++)
	   add1+=a[low+i];
	for(i=num1;i<num1+num2;i++)
	   add2+=a[low+i];
	if(add1<add2)  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 a[]={-20,11,-4,13,-5,-2};
	cout<<MaxSum(a,0,5)<<endl;	
	
	char r[]={'A','M','Z','D'};
	cout<<Game(r,4)<<endl;

    cout<<Coin(0,8,8);
	return 0;
} 

内容总结

以上是互联网集市为您收集整理的C++算法设计中的组合问题全部内容，希望文章能够帮你解决C++算法设计中的组合问题所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。

内容备注

版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 gblab@vip.qq.com 举报，一经查实，本站将立刻删除。

内容手机端

---