精华内容
下载资源
问答
  • 算法实验-分治法查找最大最小值

    千次阅读 2020-02-02 15:54:55
    利用分治法查找数组元素的最大值与最小值。并计算出程序运行所需要的时间。 实验步骤 ①将问题分解,如果数组中只有一个元素,那么只需要比较该元素与当前的最大最小值并进行更新即可 ②将问题扩大,数组中有多个...

    实验原理

    利用分治法查找数组元素的最大值与最小值。并计算出程序运行所需要的时间。

    实验步骤

    ①将问题分解,如果数组中只有一个元素,那么只需要比较该元素与当前的最大值最小值并进行更新即可
    ②将问题扩大,数组中有多个元素,则可以通过套用二分法进行拆分,递归将整个数组拆分为多个只有一个元素的小数组,即分解为多个1问题
    ③最后将每一个小数组得到的结果进行比较,选取其中的最大值和最小值对存储最大值最小值的变量进行更新

    关键代码

    template<class type>//为了对任何类型进行比较,实际上只需要为int
    int BS(type a[],int left,int right,int & max,int & min){//第一个元素为数组,每次对数组的left和right进行更新,直到二者相等,即当前数组中只有一个元素;max和min为存储最大值和最小值的变量,必须为指针或者引用
    	int middle,max1,max2,min1,min2;
    	if(left==right){		
    		max=a[left];
    		min=a[left];	
    	}else{
    		middle=(left+right)/2;	
    		BS(a,middle+1,right,max1,min1);
    		BS(a,left,middle,max2,min2);
    		if(min1>min2) min=min2;
    		else min=min1;
    		if(max2>max1) max=max2;
    		else max=max1;
    	}
    }
    通过代码可以看出时间复杂度近似为nlogn
    

    完整代码

    #include <iostream>
    #include <fstream>
    #include <windows.h> 
    using namespace std;
    template<class type>
    int BS(type a[],int left,int right,int & max,int & min);
    int main()
    {
    	ofstream out;
    	out.open("output.txt");
    	ifstream in;
    	in.open("input.txt");
    	int n;
    	in>>n;
    	int a[n];
    	for(int i=0;i<n;i++){
    		in>>a[i];
    	} 
    	int max=a[0];
    	int min=max;
    	LARGE_INTEGER time,time0,time1,time2;
    	QueryPerformanceFrequency(&time);
    	QueryPerformanceCounter(&time0);
    	BS(a,0,n-1,max,min);
    	QueryPerformanceCounter(&time1);
    	out<<"最大值为:"<<max<<" 最小值为:"<<min<<"时间为:"<<1000.0*(time1.QuadPart-time0.QuadPart)/time.QuadPart<<"ms"<<endl;
    	return 0;
    }
    template<class type>
    int BS(type a[],int left,int right,int & max,int & min){
    	int middle,max1,max2,min1,min2;
    	if(left==right){		
    		max=a[left];
    		min=a[left];	
    	}else{
    		middle=(left+right)/2;	
    		BS(a,middle+1,right,max1,min1);
    		BS(a,left,middle,max2,min2);
    		if(min1>min2)
    			min=min2;
    		else
    			min=min1;
    		if(max2>max1)
    			max=max2;
    		else
    			max=max1;
    	}
    }
    //	}
    //	if(right==left+1){
    //		if(a[right]>a[left]){
    //			min=a[left];
    //			max=a[right];
    //		}else{
    //			min=a[right];
    //			max=a[left];
    //		}
    
    展开全文
  • 分治法查找最大最小值实验

    千次阅读 2020-04-09 21:19:49
    1.问题描述:输入一组数据,找出其中的最大最小值 2.分治思想: 找数组a范围l~R的最值=> ①范围一分为2 mid=(l+r)/2 ②最大值=max(l~mid最大值,mid+1~r最大值); ③最小值=min(l~mid最小值...

    1.问题描述:输入一组数据,找出其中的最大值最小值

    2.分治思想:

    找数组a范围l~R的最值:

    ①范围一分为2 mid=(l+r)/2

    ②最大值=max(l~mid最大值,mid+1~r最大值);

    ③最小值=min(l~mid最小值,mid+1~r最小值);

    边界:

    只有一个元素,最大值=最小值=a[l]

     

    3.代码实现:

     

    #include <iostream>
    #include <fstream>
    #include <windows.h>
    using namespace std;
    void search(int *a, int l,int r, int &maxi,int &mini){
    	if(l==r){
    		maxi=mini=a[l];return;
    	}
    	int mid=(l+r)/2;
    	int max1,max2,min1,min2;
    	search(a,l,mid,max1,min1);
    	search(a,mid+1,r,max2,min2);
    	maxi=max(max1,max2);
    	mini=min(min1,min2);
    } 
    int main(){
    	int n,i,maxi,mini;
    	LARGE_INTEGER nFreq,nBegin,nEnd;
    	double time; 
    	
    	ifstream in("input.txt");
    	ofstream out("output.txt");
    	in>>n;
    	int a[n];
    	for(i=0;i<n;i++)
    		in>>a[i];
    	
    	QueryPerformanceFrequency(&nFreq);	
    	QueryPerformanceCounter(&nBegin);
    	search(a,0,n-1,maxi,mini);
    	QueryPerformanceCounter(&nEnd);
    	time=(double)(nEnd.QuadPart-nBegin.QuadPart)/(double)nFreq.QuadPart; 
    	
    	
    	out<<"maxi:"<<maxi<<" mini:"<<mini<<"\n search time:"<<time<<"s\n";
    	in.close();
    	out.close();
    	return 0;
    }

    ②功能函数:生成规模为n的随机数

    #include <time.h>
    #include <stdlib.h>
    #include <fstream>
    #include <iostream>
    using namespace std;
    int main(){
    	int n;
    	cin>>n;
    	ofstream out("input.txt");
    	out<<n<<'\n';
    	srand((unsigned)time(NULL));
    	for(int i=0;i<n;i++){
    		out<<rand()<<' ';
    		if((i+1)%10==0) out<<'\n';
    	}
    	out.close();
    	return 0;
    } 

    4.复杂度分析:

    ①主函数:

    时间复杂度分析:

    search函数:

    递推关系:

    ①利用主定理:T(n)=kT(n/m)+f(n^{d})

    m^{d}= 1 < k=2

    T(n)=O(n^{log_{m}k})=O(n^{log_22})=O(n) 发现和遍历一样是O(n)的

    ②迭代

      C(n)=2C(n/2) +2 = 2(2C(n/4)+2)+2 = 2^{k}C(2)+2^{k}+2^{k-1}+***+2^{1}

       k=log_2(n/2), C(2)=1 

      C(n)=2^{k+1}+2^{k}=n+n/2-2=3/2n-2

    ③与遍历比较:

      C(n)=2n-2

    5.测试数据及结果分析:

     

    运行时间与规模
    规模n     10      100       1000 10000   100 000  500 000
    耗时/s 1.48e-005 1.7e-005  6.01e-005 6.542e-4  6.7138e-3 4.0174e-2

     

    展开全文
  • 使用分治法的思想:首先把数组分成两部分,在把这两部分中的每一部分分成两部分,一直递归分解直到每一部分小于等于2个数为止,然后比较这两个数,判断最大最小值,然后回弹比较直到递归的最外层,就可以判断最大...

    1、方法思想

    使用分治法的思想:首先把数组分成两部分,在把这两部分中的每一部分分成两部分,一直递归分解直到每一部分小于等于2个数为止,然后比较这两个数,判断最大最小值,然后回弹比较直到递归的最外层,就可以判断最大最小值;

    2、问题描述

    从一个无序的数列中查找最大值和最小值

    3、算法描述

    (1)采用分治的思想来描叙问题;

    (2)伪代码:

    FindMaxAndMin(a[],begin,end,pmax,pmin)

    If end-begin<=1

          Then pmax=a[begin]

                pmin=a[end]

          else pmax=a[end]

                pmin=a[begin]

        else mid=(begin+end)/2

          FindMaxAndMin(a[],begin,mid,pmax,pmin);

          FindMaxAndMin(a[],mid+1,end,pmax,pmin);

          Pmax=max{gmax,hmax}

          Pmin=min{gmin,hmin}  

    4、程序清单

     1 #include <iostream>
     2 using namespace std;
     3 
     4 void FindMaxAndMin(int a[], int begin, int end, int* pmax, int* pmin)
     5 {
     6     if(end-begin <=1)
     7     {
     8         if(a[begin] <= a[end])
     9         {
    10             *pmax = a[end];
    11             *pmin = a[begin];
    12             return;
    13         }
    14         else
    15         {
    16             *pmin = a[end];
    17             *pmax = a[begin];
    18             return;
    19         }
    20     }
    21 
    22     int min1, min2, max1, max2;
    23     int mid = (begin+end)/2;
    24     FindMaxAndMin(a, begin, mid, &max1, &min1);
    25     FindMaxAndMin(a, mid+1, end, &max2, &min2);
    26     *pmin = min1 < min2 ? min1 : min2;
    27     *pmax = max1 < max2 ? max2 : max1;
    28 }
    29 
    30 int main()
    31 {
    32     int a[] = {1,2,3,4,5,9,41,8,12,20,98};
    33     int max, min;
    34     FindMaxAndMin(a, 0, 10, &max, &min);
    35     cout<<"the max num is:"<<max<<",  the min num is:"<<min<<endl;
    36     return 0;
    37 }

     

    5、实验结果

    (可用文字描述和贴图等方式表现实验结果)   

    输入为:a[] = {1,2,3,4,5,9,41,8,12,20,98};

    输出为:

    (大二的时候写的,可能还有些问题,请见谅、、、)

    转载于:https://www.cnblogs.com/three-zone/archive/2011/10/24/acm1.html

    展开全文
  • 分治法查找数组最大最小值

    千次阅读 2010-12-16 22:14:00
    一直以来,在编程的道路上,只注重需求问题的解决方法,很少注重效率算法之类的东西,自然算法是比较薄弱的地方,刚看到有人在论坛问分治法的东西,到google搜索了下,把百度百科的分治法看了遍(话说google真比baidu厚道,很...

      一直以来,在编程的道路上,只注重寻求问题的解决方法,很少注重效率算法之类的东西,自然算法是比较薄弱的地方,刚看到有人在论坛问分治法的东西,到google搜索了下,把百度百科的分治法看了遍(话说google真比baidu厚道,很多时候搜东西,百度百科都是第一条显示),自己把那个小例子写了遍,打算以后尽量多学习学习算法之类的知识.

    大致说明下程序流程,调用Find函数后,将判断是否为最小子结构,如果不是则将它2分继续判断,如果是最小子结构,则把最小子结构的元素与全局最大最小值做比较.

    这里假设数据元素个数为8时,该程序走的流程应该是

    0-7分解为0-3->

    0-3分解为0-1满足最小子结构做完比较后return->

    继续0-3分解的2-3满足最小子结构做完比较后return->

    继续0-7分解的4-7->

    4-7分解为4-5满足最小子结构做完比较后return->

    继续4-7分解的6-7满足满足最小子结构做完比较后return,此时后面没有操作可做将一直return出第一次调用Find的位置,分治到处结束.

    展开全文
  • 分治法最大最小值

    千次阅读 2013-11-04 12:00:13
    分治法查找数组元素的最大值和最小值。 2. 方法概述  (1)将数据集 S 均分为 S1 和 S2;  (2)求解 S1 和 S2 中的最大最小值;  (3)最终的最大最小值可以计算得到:min( S1, S2 ), max( S1, S2 );  ...
  • 分治法查找数组元素的最大值和最小值(python实现) 实验内容 给定任意几组数据,利用分治法的思想,找出数组中的最大值和最小值并输出 实验原理 利用分治法,将一个数组元素大于 2 的数组分成两个子数组,然后对每...
  • 分治法实现寻找数组最大最小值 大致思路 我们拿到一个长度为K的一维数组,想要在短时间内进行最大最小值查找,第一种想法就是现将数组进行排序,这样首末的元素分别是最小和最大的元素。排序算法中,快速排序、...
  • 例题:金块问题 老板有一袋金块(共n块,n是2的幂(n>=2) ),最优秀的员工得到其中最...蛮力策略:对金块逐个进行比较查找。(扫描数组一轮,寻找最大和最小的数。)该策略需要进行(n-1)次的比较才能得到Ma...
  • 分治法查找数组元素的最大值和最小值   分治法简介:  分治法从字面上的解释是“分而治之”,就是把一个复杂的问题分成两个或者更多相同或者相似的子问题,再把子问题分成更小的子问题,直到最后子问题可以简单...
  • 分治法查找数组元素的最大值和最小值。 输入:随机输入10个整数输出: max=最大的那个数 min=最小的那个数 public class MaxAndMin{ public static void main(String[] args) { Scanner sc = new ...
  • 算法分析: 代码实现: #include "stdio.h" #include "stdlib.h" #include "time.h" #define ARRAY_SIZE 50 void FindMinMax (int *Array, int left, int right, int *min, int *max) {  if ((right - left)==1
  • 代码链接:pan.baidu.com/s/15inIth8Vl89R1CgQ_wYc2g 提取码:gf13 算法分析与设计第 1 次实验 ... 用分治法查找数组元素的最大值和最小值 实验目的 ...
  • 查找的 void func(int A[],int low,int high,int& minp,int& maxp) { int x, y; if (low == high)maxp = minp = A[low]; else if (low == high - 1) { minp = min(A[low], A[high]); maxp = max(A...
  • 给定数组a1,a2,a3,...an,找出数组中最大值和最小值。(数组中两两各不相同) 分析: 算法思想类似于上图,将数组两两分为一组,如果数组元素奇数个,就把最后一个元素单独分为一组,然后分别对每一组中相邻两...
  • /*分治法求最大元最小元*/ /* 思路:运用分治的思想,将要排序的整个数组从中间劈开,分别求其左右两边的最大最小值,然后将求出的最大最小值合起来进行比较。 当左右两边的数组小到一定程度时:(这个是先分再治,...
  • python实现查找数组中最大值和最小值 谷歌笔试题 题目描述: 给定数组 al,泣, a3,···an,要求找出数组中的最大值和最小值。假设数组中的值两两各不相同。 分治法 分治法就是将一个规模为 n的、难以直接解决的大...
  • 分治法实例

    2020-04-27 15:22:13
    分治法查找最大值和次大值 //求解最大和次大元素算法 #include <stdio.h> // 宏, 求两个数的最大值, 可用函数代替 #define max(x,y) ((x)>(y)?(x):(y)) // 宏, 求两个数的最小值, 可用函数代替 #define ...
  • 分治法学习

    2013-06-09 15:57:14
    1.二叉查找算法 2.查找最大最小值 3.归并排序 4.快速排序 5.选择第k小元素 //分治法求第K小的数 #include #include using namespace std; int FindSmall(int *a ,
  • 1.计算最大值和最小值分治法分治法计算最大值和最小值,是一个经典的算法程序。 原始数据使用随机函数生成。 采用结构化程序设计,可以很容易改为从标准输入或文件读入数据,只需要修改函数getData即可。 ...
  • //分治法最大最小值 import java.util.Scanner; public class num2_1_1 {  public static void max_min(int []a,int left,int right,int []maxnum,int []minnum)  {  if (left==right) //当只有一个...
  • 方法一:分治法,一分为二,分别查找子数组中最大值和最小值,合并时取两个子数组的较大者和较小者。f(n) = 2f(n-1)+2;f(n)=1.5n-2; 方法二:将数组中元素每两个一组,先比较每组中两个元素,让较大者与最大值...
  • /*分治法*/ #include #include #include #include using namespace std; int a[16]={1,3,5,7,9,11,14,2,4,6,8,10,12,14,16,18}; int b[9]={3,1,5,9,4,2,7,6,10}; int t[2]; vector splitEx(const string& src, ...
  • 分析,分治法,类似二分查找,可以先求解出左半部分的最大值和最小值,再求解出又半部分的最大值和最小值然后合并求解,就可以求解出整个数组中的最大值和最小值。 那么递归的出口条件是什么呢?当划分以后只有一个...
  • 二分查找算法

    2016-10-12 16:17:53
    刚才看到五大常用算法之一的分治法分治法有分而治之的思想,把规模不断的缩小,这样就...二分查找(折半查找)算法原理:将已排好序的数组,取出最小值的下标(即第一个值)和最大值的下标(即数组中的最后一个值)。
  • 三分查找

    2019-03-19 15:10:38
    类似于二分查找,三分搜索也是比较常用的基于分治思想的高效查找方法...但是为什么三分可以用于凸函数或者凹函数呐,这其实是因为这种函数总是有一个最大值或者最小值,这样就可以借此判断出三分中两个中点相...

空空如也

空空如也

1 2 3
收藏数 47
精华内容 18
关键字:

分治法查找最大最小值