分治法求集合最大元

2018-06-17 23:43:43来源:未知 阅读 ()

新老客户大回馈,云服务器低至5折

题目:输入n  然后输入n个整数,用分治法求这n个数中的最大元;

思路:把这列数分成两半,递归下去,到只剩一个数时停止,返回这个数,如果不是一个数则返回分成的两段数最大值的较大者;

实验提示:在规模为n的数据元素集合中找出最大元。当n=2时,一次比较就可以找出两个数据元素的最大元和最小元。当n>2时,可以把n个数据元素分为大致相等的两半,一半有n/2个数据元素,而另一半有n/2个数据元素。 先分别找出各自组中的最大元,然后将两个最大元进行比较,就可得n个元素的最大元

 

代码如下:

#include <iostream>
#include <algorithm>
#include <stdio.h>
#include <string.h>
#include <math.h>
#include <stdlib.h>
#include <set>
#include <queue>
#include <vector>
using namespace std;

int calc(int a[],int l,int r)
{
    if(l==r) return a[l];
    return max(calc(a,l,(l+r)/2),calc(a,(l+r)/2+1,r));
}

int main()
{
    int a[1005];
    int n;
    cout<<"数列长度: "<<endl;
    scanf("%d",&n);
    if(n==0) {puts("数列长度不能为0!"); return 0;}
    cout<<"请输入数列: "<<endl;
    for(int i=0;i<n;i++) scanf("%d",&a[i]);

    printf("这个数列的最大元为: %d\n",calc(a,0,n-1));
    return 0;
}

 

标签:

版权申明:本站文章部分自网络,如有侵权,请联系:west999com@outlook.com
特别注意:本站所有转载文章言论不代表本站观点,本站所提供的摄影照片,插画,设计作品,如需使用,请与原作者联系,版权归原作者所有

上一篇:线性筛法(欧拉筛法)求素数

下一篇:hdu-2444-二分图判定+最大分配