精华内容
下载资源
问答
  • 分治法求最大最小值

    2019-12-20 21:53:40
    package Main; import java.util.*; public class Main { static int []a= {5,6,2,1,4,9,2,13,656,223}; public static void main(String []args) { Scanner input=new Scanner(System.in);...
    package Main;
    
    import java.util.*;
    public class Main {
    	static int []a= {5,6,2,1,4,9,2,13,656,223};
    	
    	public static void main(String []args) {
    		Scanner input=new Scanner(System.in);
    		System.out.println(bi(a,0,a.length-1)[0]+" "+bi(a,0,a.length-1)[1]);
    	
    	}
    	public static int[] bi(int []a,int i,int j) {
    		int []b=new int[2];
    		if(i==j)
    			b[0]=b[1]=a[i];
    		else if(j-i==1)
    		{
    			b[0]=a[i]<a[j]?a[i]:a[j];
    			b[1]=a[i]>=a[j]?a[i]:a[j];
    		}
    		else {
    			b[0]=bi(a,i,(i+j)/2)[0]<bi(a,(i+j)/2+1,j)[0]?bi(a,i,(i+j)/2)[0]:bi(a,(i+j)/2+1,j)[0];
    			b[1]=bi(a,i,(i+j)/2)[1]>=bi(a,(i+j)/2+1,j)[1]?bi(a,i,(i+j)/2)[1]:bi(a,(i+j)/2+1,j)[1];
    			}
    		return b;
    	}
    
    }
    
    在这里插入代码片
    
    展开全文
  • 分治法求最大最小值

    千次阅读 2014-09-25 09:38:33
    // 用分治法求最大最小值 public static int getMax(int[] array, int i, int j) { int Max1 = 0; int Max2 = 0; if (i == j) { return Max1 = Max2 = array[j
    http://www.nowamagic.net/librarys/veda/detail/257
    
    	// 用分治法求最大最小值
    	public static int getMax(int[] array, int i, int j) {
    		int Max1 = 0;
    		int Max2 = 0;
    		if (i == j) {
    			return Max1 = Max2 = array[j];
    		} else if (i == (j - 1)) {
    			Max1 = array[i];
    			Max2 = array[j];
    			return Max1 > Max2 ? Max1 : Max2;
    		} else {
    			int mid = (i + j) / 2;
    			Max1 = getMax(array, i, mid);
    			Max2 = getMax(array, mid, j);
    			return Max1 > Max2 ? Max1 : Max2;
    		}
    	}
    }
    假设数组的大小为8,用直接的算法,最大值最小值总需要比较14次,而用分治算法可以一次性求出最大和最小,只需要10次比较。

    展开全文
  • 分治法 可以用分治法解决的问题一定包含了诸多的子问题,这些子问题的解题方式及问题形式都与大问题一样,并且都是可解的。所以我们利用分治法解决问题一定要先找他的最小的子问题,然后解决它,由于分治法的本质...

    分治法

    可以用分治法解决的问题一定包含了诸多的子问题,这些子问题的解题方式及问题形式都与大问题一样,并且都是可解的。所以我们利用分治法解决问题一定要先找他的最小的子问题,然后解决它,由于分治法的本质其实就是递归问题,所以我们最终可以解决原有问题。下面给出一个数组,求出其中的最大值和最小值。

    代码

    #include <iostream>
    using namespace std;
    void divide_and_conquer(int a[],int begin,int end,int *max_value,int *min_value)
    {
        if(end - begin <= 1)
        {
            if(a[begin] > a[end])
            {
                *max_value = a[begin];
                *min_value = a[end];
                return;
            }
            else
            {
                *max_value = a[end];
                *min_value = a[begin];
                return;
            }
        }
            int mid = (begin + end) / 2;
        int min1,min2,max1,max2;
        //左侧的最大最小值
        divide_and_conquer(a,begin,mid,&max1,&min1);
        //右测的最大最小值
        divide_and_conquer(a,mid+1,end,&max2,&min2);
        *max_value = max1 > max2 ? max1 : max2;
        *min_value = min1 < min2 ? min1 :min2;
    }
    int main()
    {
        int a[] = {1,2,5,6,100,4,2,9};
        int m_x = 0;
        int m_i = 0;
        divide_and_conquer(a,0,9,&m_x,&m_i);
        cout<<"最大值为:"<<m_x<<endl;
        cout<<"最小值为:"<<m_i<<endl;
        return 0;
    }
    展开全文
  • 本文为大家分享了C语言实现分治法实例代码,供大家参考,具体内容如下使用分治法求最大值这个函数将数组a[l]...a[r]分成a[l],...,a[m]和a[m+1],...a[r]两部分,分别求出每一部分的最大元素(递归地),并返回较大的那一...

    本文为大家分享了C语言实现分治法实例代码,供大家参考,具体内容如下

    使用分治法求最大值

    这个函数将数组a[l]...a[r]分成a[l],...,a[m]和a[m+1],...a[r]两部分,分别求出每一部分的最大元素(递归地),并返回较大的那一个作为整个数组的最大元素.如果数组大小是偶数,则两部分大小相等;如果是奇数,第一部分比第二部分的大小大1.

    #include

    #include

    #include

    #include

    using namespace std;

    #define OK 1

    #define ERROR -1

    #define TRUE 1

    #define FALSE 0

    typedef int Status;

    int Max(int a[], int l, int r)

    {

    int u, v, m = (l + r) / 2;

    //当区间中只有一个元素,递归终止,并将该元素返回

    if(l == r)

    return a[l];

    //递归原区域的左边

    u = Max(a, l, m);

    //递归原区域的右边

    v = Max(a, m+1, r);

    //返回最大值

    return (u>v)?u:v;

    }

    int main()

    {

    //举例验证

    int a[7] = {6, 5, 3, 4, 7, 2, 1};

    int maxx = Max(a, 0, 6);

    printf("%d\n", maxx);

    return 0;

    }

    汉诺塔的解

    我们把盘子(递归地)移动到c上的方案是,将除了最下面的盘子之外的所有盘子移到b上,然后将做下面的盘子移到c上,然后(递归地)再将其他盘子移回到最下面的盘子上面.

    #include

    #include

    #include

    #include

    using namespace std;

    #define OK 1

    #define ERROR -1

    #define TRUE 1

    #define FALSE 0

    typedef int Status;

    //输出盘子的移动

    void shift(int n, char x, char y)

    {

    printf("Move %d disk: %c ---------> %c\n", n, x, y);

    }

    void hanoi(int n, char a, char b, char c)

    {

    //递归终止的条件

    if(n == 1)

    {

    //将a上最下面的盘子移到c上

    shift(n, a, c);

    return;

    }

    //以c为中间轴,将a上的盘子移动到b上

    hanoi(n-1, a, c, b);

    shift(n, a, c);

    //以a为中间轴,将b上的盘子移动到c上

    hanoi(n-1, b, a, c);

    }

    int main()

    {

    //举例验证

    hanoi(4, 'a', 'b', 'c');

    return 0;

    }

    使用分治法在尺子上画刻度

    要在尺子上画刻度线,我们首先在左半边画刻度线,然后在中间画一条最长的刻度线,最后在右半边画刻度线.

    #include

    #include

    #include

    #include

    using namespace std;

    #define OK 1

    #define ERROR -1

    #define TRUE 1

    #define FALSE 0

    typedef int Status;

    //画线

    void mark(int m, int h)

    {

    //由于无法实际表示刻度线之间的高度差,故用实际数字来体现

    printf("%d ", h);

    }

    //划分该区域内的刻度

    void rule(int l, int r, int h)

    {

    //找到该区域的中间

    int m = (l + r) / 2;

    //当高度大于0

    if(h)

    {

    //划分小区域

    rule(l, m, h-1);

    //画线

    mark(m, h);

    //划分小区域

    rule(m+1, r, h-1);

    }

    }

    int main()

    {

    //举例验证

    rule(0, 14, 4);

    return 0;

    }

    以上就是本文的全部内容,希望对大家的学习有所帮助,也希望大家多多支持脚本之家。

    展开全文
  • 使用分治法的思想:首先把数组分成两部分,在把这两部分中的每一部分分成两部分,一直递归分解直到每一部分小于等于2个数为止,然后比较这两个数,判断最大最小值,然后回弹比较直到递归的最外层,就可以判断最大...
  • 分治法就是讲大规模问题化成小的同类型问题,分开求解再合并各个解...用分治法求最大最小值:  public static int getMax(int[] array, int i, int j) {  int Max1 = 0;  int Max2 = 0;  if (i =
  • 分治法求数组最大最小值

    千次阅读 2016-04-08 09:09:26
    常规的做法是遍历一次,分别最大值和最小值,但我这里要说的是分治法(Divide and couquer),将数组分成左右两部分,先出左半部份的最大值和最小值,再出右半部份的最大值和最小值,然后综合起来总体的最大...
  • 分治法求最大值和最小值 实验报告 
  • 分治法求最大最小值的问题,这是关于算法设计与分析的一个实验代码,本人菜鸟,请大家勿笑。
  • 分治法求最大最小值

    千次阅读 2013-11-04 12:00:13
    分治法查找数组元素的最大值和最小值。 2. 方法概述  (1)将数据集 S 均分为 S1 和 S2;  (2)求解 S1 和 S2 中的最大最小值;  (3)最终的最大最小值可以计算得到:min( S1, S2 ), max( S1, S2 );  ...
  • 这个问题其实就是输入n个数,找出最大和最小数的问题。 解决问题的策略 蛮力策略:对金块逐个进行比较查找。(扫描数组一轮,寻找最大和最小的数。)该策略需要进行(n-1)次的比较才能得到Ma...
  • 【转】分治法求最大最小值 分治算法通俗的讲就是把一个规模比较大的问题分成n个规模较小的问题来解决,再将每个小规模的问题进行合并,最后得到结果。通常问题规模比较大难以用普通的编程方法实现,...
  • 分治法求数组的最大最小值

    千次阅读 2015-01-18 15:05:37
    分治法的思想就是每次将数组一分为二,分别求两部分的最大值与最小值,然后比较哪部分的更大和更小,最后得出整个数组的最大最小值。... 函数功能:分治法求double型数组的最大最小值 参数:double array[] 待求数组
  • DC分治法求数组最大最小值

    千次阅读 2012-03-21 09:05:59
    #include void dcMaxMin( int [], int, int, int *, int * ); void dcMaxMin( int arr[], int low, int high, int *tmpMax, int *tmpMin ) { if ( high - low )// 最多俩元素 { if
  • 求最大最小值分治法

    千次阅读 2018-03-18 20:55:44
    分治法求找出一个数组A[0], A[1], …, A[N-1]中的最大元素和最小元素。输入:共两行,第一行输入一个整数n,表示数组元素的个数,第二行共输入n个元素。输出:输出两个元素,分别为n个整数中的最大值和最小值。...
  • 分治法求数组的最小值最大

    千次阅读 2012-09-21 11:18:40
    * 分治法求数组的最小值最大值 */ import java.util.Arrays; public class MinAndMaxArray { public static void main(String[] args) { int arr[] = { -2, -9, 0, 5, 2 }; int result[] = new int[2]; ...
  • 查找的 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... //比较前后两段的最大最小值 } }
  • 分治法求最值

    2016-01-10 12:46:14
    简答易懂的分治法求最大最小值
  • 给定n个数,在最坏情况下用 3n/2-2 次比较找出这n个数中元素的最大值和最小值。 要求只编写函数  void maxmin(int a[],int low,int high,int *max,int *min). 系统会自动在程序的最后加上如下代码: int...
  • 分治法:将一个复杂的一分为二,然后对这两部分递归调用该函数,直到找到函数出口,求解出最简单的情况 需要注意的是分治时开始和结束位置参数的选择,一开始写的是s到mid-1,另一个是mid到e,然后就会数组为奇数个...

空空如也

空空如也

1 2 3 4 5 ... 7
收藏数 134
精华内容 53
关键字:

分治法求最大最小值