精华内容
下载资源
问答
  • 贪心算法-数列极差问题-JAVA

    千次阅读 2015-02-08 12:35:32
    贪心算法-数列极差问题 【题目描述】   在黑板上写了N个正整数做成的一个数列,进行如下操作:每一次擦去其中的两个数a和b,然后在数列中加入一个数a×b+1,如此下去直至黑板上剩下一个数,在所有按这种操作...

    贪心算法-数列极差问题

    【题描述】 

     在黑板上写了N个正整数做成的一个数列,进行如下操作:每一次擦去其中的两个数a和b,然后在数列中加入一个数a×b+1,如此下去直至黑板上剩下一个数,在所有按这种操作方式最后得到的数中,最大的max,最小的为min,则该数列的极差定义为M=max-min。

    编程任务:对于给定的数列,编程计算出极差M。

    输入输出样例:

    输入:                    

    4

    2 1 4 3

     

    输出:

    13

    【算法分析】

    当看到此题时,我们会发现求max与求min是两个相似的过程。若我们把求解max与min的过程分开,着重探讨求max的问题。

    下面我们以求max为例来讨论此题用贪心策略求解的合理性。

    讨论:假设经(N-3)次变换后得到3个数:a ,b , max'(max'≥a≥b),其中max'是(N-2)个数经(N-3)次f变换后所得的最大值,此时有两种求值方式,设其所求值分别为 z1,z2,则有:z1=(a×b+1)×max'+1,z2=(a×max'+1)×b+1所以z1-z2=max'-b≥0若经(N-2)次变换后所得的3个数为:m,a,b(m≥a≥b)且m不为(N-2)次变换后的最大值,即m<max'则此时所求得的最大值为:

    z3=(a×b+1)×m+1此时z1-z3=(1+ab)(max'-m)>0 所以此时不为最优解。

    所以若使第k(1≤k≤N-1)次变换后所得值最大,必使(k-1)次变换后所得值最大(符合贪心策略的特点2),在进行第k次变换时,只需取在进行(k-1)次变换后所得数列中的两最小数p,q施加f操作:p←p×q+1,q←∞即可(符合贪心策略特点1),因此此题可用贪心策略求解。在求min时,我们只需在每次变换的数列中找到两个最大数p,q施加作用 f:p←p×q+1,q←-∞即可.原理同上。

    这是一道两次运用贪心策略解决的一道问题,它要求选手有较高的数学推理能力。


    import java.util.Scanner;
    
    
    public class Main {
    	public static void main(String[] args) {
    		Scanner sc = new Scanner(System.in);
    		int N = sc.nextInt();
    		int [] n = new int[N];
    		int max,min;
    		for (int i = 0; i < N; i++) {
    			n[i] = sc.nextInt();
    		}
    		int[] nclone = n.clone();//拷贝一次数组,因为有两次操作,分别求max和min。
    		//求出MAX:
    		int m = 0;
    		while(m != N-1){
    			for (int i = m; i < m+2; i++) {//循环为m到m+2,因为每次只要求出两个最小的值。
    				for (int j = i+1; j < n.length; j++) {
    					if(n[j]<n[i]){
    						int temp = n[j];
    						n[j] = n[i];
    						n[i] = temp;
    					}
    				}
    				if(i==m+1){
    					n[i] = n[i-1]*n[i]+1;
    				}
    			}
    			m++;
    		}
    		max = n[N-1];
    		
    		//求出MIN:
    		m = 0;//重新初始化m。
    		while(m != N-1){
    			for (int i = m; i < m+2; i++) {
    				for (int j = i+1; j < nclone.length; j++) {
    					if(nclone[j]>nclone[i]){//事实上只是将小于号改为大于号即可。
    						int temp = nclone[j];
    						nclone[j] = nclone[i];
    						nclone[i] = temp;
    					}
    				}
    				if(i==m+1){
    					nclone[i] = nclone[i-1]*nclone[i]+1;
    				}
    			}
    			m++;
    		}
    		min = nclone[N-1];
    		
    		//MAX - MIN :
    		System.out.println(max - min);
    	}
    }

    编程的思路:

    每次排序仅排除最小(或最大)的两个数,然后将二者运算的结果放在第二个数的位置,然后从第二个数的位置开始往后排序,重复上述过程。最后得到数组最末尾的那个数就是运算的MAX(或MIN)的结果。MAX-MIN即可得解。

    展开全文
  • 常用统计算法JAVA实现 - 极差(04)

    千次阅读 2019-01-15 15:58:36
    * * @描述:集中趋势量数:极差(不包含) &lt;br/&gt; * * @方法名: range &lt;br/&gt; * * @param in &lt;br/&gt; * * @return &lt;br/&gt; * * @返回类型 double &...
    /**
    	 * 
    	 *  * @描述:集中趋势量数:极差(不包含) <br/>
    	 *  * @方法名: range <br/>
    	 *  * @param in <br/>
    	 *  * @return <br/>
    	 *  * @返回类型 double <br/>
    	 *  * @创建人 micheal <br/>
    	 *  * @创建时间 2019年1月2日下午10:26:20 <br/>
    	 *  * @修改人 micheal <br/>
    	 *  * @修改时间 2019年1月2日下午10:26:20 <br/>
    	 *  * @修改备注 <br/>
    	 *  * @since <br/ >  * @throws <br/>
    	 *  
    	 */
    	public static double range(double[] in) {
    		if (in == null) {
    			throw new java.lang.NumberFormatException();
    		}
    		double max = Double.MIN_VALUE;
    		double min = Double.MAX_VALUE;
    		for (int i = 0; i < in.length; i++) {
    			max = Math.max(max, in[i]);
    			min = Math.min(min, in[i]);
    		}
    		// return max - min;
    		return Mutil.subtract(max, min);
    	}
    
    	/**
    	 * 
    	 *  * @描述: 变异性量数:极差(包含) <br/>
    	 *  * @方法名: range2 <br/>
    	 *  * @param in <br/>
    	 *  * @return <br/>
    	 *  * @返回类型 double <br/>
    	 *  * @创建人 micheal <br/>
    	 *  * @创建时间 2019年1月2日下午10:26:08 <br/>
    	 *  * @修改人 micheal <br/>
    	 *  * @修改时间 2019年1月2日下午10:26:08 <br/>
    	 *  * @修改备注 <br/>
    	 *  * @since <br/>
    	 *  * @throws <br/>
    	 *  
    	 */
    	public static double range2(double[] in) {
    		if (in == null) {
    			throw new java.lang.NumberFormatException();
    		}
    		double max = Double.MIN_VALUE;
    		double min = Double.MAX_VALUE;
    		for (int i = 0; i < in.length; i++) {
    			max = Math.max(max, in[i]);
    			min = Math.min(min, in[i]);
    		}
    		// return max - min + 1;
    		return Mutil.subtract(max, min) + 1;
    	}

     测试代码,打印结果,包含:50.0 ,不包含:51.0

    double[] in4 = { 98, 86, 77, 56, 48 };
    log.info("计算[极差]:" + range(in4));
    log.info("计算[极差]2:" + range2(in4));

     

    展开全文
  • import java.util.Arrays; import java.util.Comparator; import java.util.Scanner; /* * 如果要求最大值的话,那么每次先用最小的连个数相乘的结果+1, * 相反,如果要求最小值的话,每次先用最大的两个数相乘...

    代码:

    package com.hh;
    
    import java.util.Arrays;
    import java.util.Comparator;
    import java.util.Scanner;
    
    /*
     * 如果要求最大值的话,那么每次先用最小的连个数相乘的结果+1,
     * 相反,如果要求最小值的话,每次先用最大的两个数相乘的结果+1.
     */
    public class SequenceMaxAndMin {
    	static Integer m[] =new Integer[3];
    	static Integer n[]=new Integer[3];
    	static Comparator<Integer> cmp = new Comparator<Integer>() {
    		public int compare(Integer i1, Integer i2) {
    			return i2-i1;
    		}
    	};
    	public static void main(String args[]) {
    		System.out.println("输入数组长度:");
    		Scanner sc=new Scanner(System.in);
    		int a=0;
    		a=sc.nextInt();
    		System.out.println("输入数组元素:");
    		for(int i=0;i<a;i++) {
    			m[i]=sc.nextInt();
    			n[i]=m[i];			}
    			//升序排序
    		Arrays.parallelSort(m,0,a);
    		for(int i=1;i<a;i++){
    			m[i]=m[i]*m[i-1]+1;//从小到大排完序之后,先从前边最小的两个数相乘然后存放到数组里
    			Arrays.parallelSort(m,i,a);/*算法的核心部分,由于每次从最小的两个数相乘后的数值
    							  放到原来的数组中有可能会破坏数组从小到大的顺序,
    						  所以再用一个sort排序,使新的数组变得有序,依次循环下去,就会得到最大值。*/	
    		}
    		
    			int max=m[a-1];
    			System.out.println("max"+max);
    			Arrays.sort(n,cmp);//逆序排序
    			for(Integer a1:n) {
    				System.out.println(a1);
    			}
    			for(int i=1;i<a;i++){
    				n[i]=n[i-1]*n[i]+1;/*而求最小值的时候就不用sort每次都排序啦,因为前边两个最大的数乘起来
    								   的数不可能会比后边小的数还要小,所以求最小值得时候会比上边要简单一些*/
    				}
    			
    			 int min=n[a-1];
    			 System.out.println("min:"+min);
    			System.out.println("极差为:"+(max-min));
    	}
    
    }
    
    

    测试结果:
    在这里插入图片描述

    展开全文
  • 数列极差-贪心算法

    千次阅读 2016-11-10 22:52:19
    进行如下操作:在数列中删除其中两个数a和b,然后在数列中的加入一个数a×b+1,如此下去,直至剩下一个数,在所有按这种操作方式最后得到的数中,最大的数记做Max,最小的数记做Min,则该数列的极差定义为M=Max-...
    package com.work.home_3;

    import java.util.Arrays;

    /**
     * 贪心算法-数列极差问题
     * 说明:对于给定的数列,如果按数列中的值从小到大的顺序做运算,则可以得到数列的最大值;
     * 如果按数列中的值从大到小做运算,则可得到数列的最小值。因此,对于给定的数列,先对数列进行排序,然后再进行最大、最小值的计算
     *
     * @author jun
     */
    public class Greedy {
        /*
         * 贪心算法
         */
        public static int greedy(int[] arr) {
            // 对数组arr按升序进行排序
            Arrays.sort(arr);
            System.out.println("\n排序后数列值变为:");
            System.out.println(Arrays.toString(arr) + "\n");
            // 数列最大值
            int max = arr[0];
            // 数列最小值
            int min = arr[arr.length - 1];
            for (int i = 1, j = (arr.length - 2); i < arr.length || j >= 0; i++, j--) {
                max = max * arr[i] + 1;
                min = arr[j] * min + 1;
            }
            System.out.println("最大值 max = " + max);
            System.out.println("最小值 min = " + min);
            // 极差
            return (max - min);
        }
    }

    package com.work.home_3;

    import java.util.Arrays;
    import java.util.Scanner;
    /**
     * 测试函数
     * @author jun
     *
     */
    public class Test {
        public static void main(String[] args) {
            Scanner sc = new Scanner(System.in);
            System.out.println("请输入正整数数列的元素个数 n = ");
            int n = sc.nextInt();
            sc.close();
            // 测试数组
            int[] arr = new int[n];
            // 给数组赋值
            System.out.println("原始数列值为:");
            for (int i = 0; i < arr.length; i++) {
                arr[i] = (int) (Math.random() * 10);
            }
            // 输出数组值
            System.out.println(Arrays.toString(arr));
            //输出数列的极差
            System.out.println("\n数列arr的极差为:" + Greedy.greedy(arr));
        }
    }

    展开全文
  • 极差标准化算法详解

    千次阅读 2020-06-05 10:01:46
    极差标准化变化即为: 极差又bai称范围误差或全距,以R表示,是用来表示统计资料中的变异量数,其最大值与最小值之间的差距,即最大值减最小值后所得之数据。 它是标志值变动的最大范围,它是测定标志变动的...
  • 4-13 数列极差问题 问题描述 在黑板上写了 N 个正数组成的一个数列,进行如下操作:每一次擦去其中 2 个数设为 a 和 b,然后在数列中加入一个数 a*b+1,如此下去直至黑板上只剩下一个数。在所有按这种 操作方式...
  •  * 贪心算法-数列极差问题  * 1. 问题描述:  * N个正数数列,进行如下操作:每一次擦去其中2个数,设a和b,然后在数列中加入一个数ab+1,如此下去直至只剩下一个数。  * 在所有按这种操作方式最后得到的数中...
  • Java 经典算法分析总汇

    千次阅读 2017-05-03 10:56:04
    算法的学习对于培养一个人的逻辑思维能力是有大帮助的,它可以培养 我们养成思考分析问题,解决问题的能力。 如果一个算法有缺陷,或不适合某个问题,执行这个算法将不会解决这个问题。不同的算法可能用不同的时间...
  • java排序算法

    千次阅读 2011-12-03 16:22:49
    Java排序算法(一):概述 排序是程序开发中一种非常常见的操作,对一组任意的数据元素(或记录)经过排序操作后,就可以把他们变成一组按关键字排序的有序队列。 对一个排序算法来说,一般从下面3个方面来...
  • 深入分析Java垃圾收集算法和垃圾收集器前言如何确定无效对象引用计数法(Reference Counting)可达性分析算法(Reachability Analysis)GC Root引用的分类强引用(Strong Reference)软引用(Soft Reference)弱引用(Weak ...
  • Java 查找算法

    万次阅读 2015-07-08 19:49:15
    但是因为寻找插入位置的查找操作的复杂度跟树的高度相关为logn,极差的情况下可能接近于线性查找。 平衡二叉树 平衡二叉树是尽量减少数高的二叉树,其算法中增加了左旋和右旋的操作。插入复杂度会高一些,...
  • 贝壳找房(算法笔试) 极差之和

    千次阅读 2018-09-02 16:36:45
    =N的极差之和,定义为【L,R】的最大值与最小值之差 输入: 5 4 1 8 2 5 输出: 60 思路:外层循环确定起始点以及最大最小值,内层循环用来遍历起点之后的元素,并判断最大最小值。 def computer(data): count =...
  • Java进阶知识 —— 算法时间复杂度

    千次阅读 2018-05-04 10:21:34
    算法时间复杂度 前言 通常,对于一个给定的算法,我们要做 两项分析。第一是从数学上证明算法的正确性,这一步主要用到形式化证明的方法及相关推理模式,如循环不变式、数学归纳法等。而在证明算法是正确的基础...
  • 排序是一个非常常见的应用场景,也是开发岗位面试必问的一道面试题,有人说,如果一个企业招聘开发人员的题目中没有排序算法题,那说明这个企业不是一个“正规”的企业,哈哈,虽然有点戏谑,但是也从侧面证明了排序...
  • java实现页面置换算法

    万次阅读 2007-08-28 21:35:00
    Java语言实现模拟页面置换算法 20045917 连乾云(兰州交通大学数理与软件工程学院 甘肃·兰州 730070) 摘要:在存储管理当中,页面置换算法通常可分为两种:一种基于进程驻留集大小不变;另一种基于驻留集大小可...
  • Java实现数据统计的常用算法

    千次阅读 2019-07-03 11:21:51
    求和、平均值、众数、中位数、中列数、四分位数、极差、四分位数、截断均值、方差、绝对平均差(AAD)、中位数绝对偏差、标准差 的数学方法 package cn.javacodes.utils; import java.util.Arrays; import java....
  • JAVA自定义算法产生正态分布随机数

    万次阅读 2017-09-24 01:15:42
    坐标形式)能够简化计算, 算法描述如下: function getNumberInNormalDistribution(mean,std_dev){ return mean+(randomNormalDistribution()* std_dev); } function randomNormalDistribution...
  • 测试代码,打印结果,标准:1.76, 标准2:1.67, 方差:3.11  double[] in5 = { 5, 8, 5, 4, 6, 7, 8, 8, 3, 6 }; log.info("计算[标准]:" + standardDeviation(in5)); log.info("计算[标准]2:" + ...
  • java实现常见查找算法

    万次阅读 多人点赞 2017-06-15 22:04:44
    // 利用Java工具类Arrays构造长度为f[k]的新数组并指向引用a a = Arrays.copyOf(a, f[k]); // 对新数组后面多余的元素赋值最大的元素 for (int i = high + 1; i [k]; i++) { a[i] = a[high];//当key是是最大值...
  • 基于用户的协同过滤算法JAVA实现的推荐系统

    千次阅读 多人点赞 2020-07-31 20:12:35
    该系统使用java编写的基于用户的协同过滤算法(UserCF) 利用统计学的相关系数经常皮尔森(pearson)相关系数计算相关系数来实现千人千面的推荐系统。 协同过滤推荐算法是诞生最早,并且较为著名的推荐算法。主要的...
  • Java数据结构和算法

    千次阅读 2017-04-11 09:47:38
    如果关键字已知则存取快。插入快 删除慢,如果不知道关键字则存取很慢,对存储空间使用不充分 堆 插入,删除快,对最大数据项的存取很快 对其他项存取很慢 ...
  • JAVA黑白棋之算法浅析

    千次阅读 2011-08-30 22:38:37
     本为主要对我在开发JAVA黑白棋人机算法过程中所用的博弈思想、估值函数、搜索算法分3个方面进行了阐述,由于本人水平有限,如果大家希望了解更多有关黑白棋博弈策略以及人机算法的深入的理论研究,可以参看本文...
  • 预测算法java实现

    千次阅读 2010-09-11 10:23:42
    常见的预测算法有1.简易平均法,包括几何平均法、算术平均法及加权平均法;2.移动平均法,包括简单移动平均法和加权移动平均法;3,指数平滑法,包括一次指数平滑法和二次指数平滑法,三次指数平滑法;...
  • 哈希算法的原理及其 Java 实现一、目的二、运行环境三、基本原理及步骤(I)各种加密算法的原理:① DES 数据加密标准(Data Encryption Standard):算法介绍算法流程优点缺点破解方式适用场景安全性② 3DES(DES ...
  • 贪婪算法: 在每一个阶段,可以认为所做出的的决定是最好的,而不考虑将来的后果。通常,这意味着选择的是某个局部最优。当算法终止时,我们希望局部最优等于全局最优,如果是这样的话,这个算法就是正确的,否则...
  • (java)五大常用算法

    万次阅读 多人点赞 2018-08-31 10:50:15
    算法一:分治法 基本概念 1.把一个复杂的问题分成两个或更多的相同或相似的子问题,再把子问题分成更小的子问题……直到最后子问题可以简单的直接求解,原问题的解即子问题的解的合并。 2.分治策略是对于一个规模...
  • 在实际象棋游戏测试中最多只能跑5层,哎电脑太 评估函数中棋子分值: // enum TYPE{CHE, MA, PAO, BING, JIANG, SHI, XIANG}; 棋子大于10颗,马、兵未过河 int scores[] = {1000, 500, 800, 200, 15000, 100, ...
  • 常见算法汇总( C++,Java,Python实现)

    千次阅读 多人点赞 2021-02-18 09:39:10
    · · · kmp算法是一种字符串匹配算法,用于在一个文本串中查找模式串的位置,出现的次数等;其中求解next数组是核心(只与模式串有关),若记模式串为p,next[i] = j 表示p[i]之前的子串中,存在长度为j的相同前缀和...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 28,058
精华内容 11,223
关键字:

java极差算法

java 订阅