精华内容
下载资源
问答
  • 针对数组的两最值算法数组次大值的算法

    针对数组的两最值算法和求数组中次大值的算法

          对一批数据进行排序,然后找出其中的最大值或最小值,这是基本的数据结构知识。在Java中我们可以通过编写算法的方式,也可以通过数组先排序再取值的方式来实现。下面以求最大值为例,解释一下多种算法。
    (1)自行实现,快速查找最大值
            先来看用快速查找法取最大值的算法,其代码如下:

    /**
     * 自行实现,快速查找最大值
     * 先来看用快速查找法取最大值的算法
     * 这是我们经常使用的最大值算法,也是速度最快的算法。
     * 它不要求排序,只要遍历一遍数组即可找出最大值。
     * @author Administrator
     *
     */
    public class FindTheBigest {
    	 public static void  BigestOfAarray(int[] data){
    	        int Bigest=data[0];
    	       for(int a:data){
    	    	   Bigest=Bigest>a?Bigest:a;
    	      }
    	     System.out.println(Bigest);
    	   }
    	 public static void main(String[] args){
    		 int[] arr = new int[]{10,23,56,8,7,15};		 
    		 BigestOfAarray(arr);
    	 }
    }
    (2)先排序,后取值
    对于求最大值,也可以采用先排序后取值的方式,同样比较简单,代码如下:

    import java.util.Arrays;
    /**
     * 先排序,后取值
     * 对于求最大值,也可以采用先排序后取值的方式
     * @author Administrator
     *
     */
    public class FindTheBigest2 {
    	public  void BigestOfAarray(int[] data) {
    		int[] Temp= data;
    		Arrays.sort(Temp);
    		System.out.println(Temp[Temp.length-1]);
    	}
    	public static void main(String[] args) {
    		int[] arr = new int[] { 10, 23, 56, 8, 7, 15 };
    		FindTheBigest2 gtg= new FindTheBigest2();
    		gtg.BigestOfAarray(arr);
    	}
    }
          从效率上来讲,当然是自己写快速查找法更快一些了,只用遍历一遍就可以计算出最大值。但在实际测试中我们发现,如果数组数量少于1万,两者基本上没有差别,在同一个毫秒级别里,此时就可以不用自己写算法了,直接使用数组先排序后取值的方式。
    如果数组元素超过1万,就需要依据实际情况来考虑:自己实现,可以提升性能,先排序后取值,简单,通俗易懂。排除性能上的差异,两者都可以选择,甚至后者更方便一些,也更容易想到。
          现在问题来了,在代码中为什么要先创建一个临时数组呢?那是因为数组也是一个对象,不拷贝不就改变了原有数组元素的顺序吗?除非数组元素的顺序无关紧要。
         接着往下思考,如果要查找仅次于最大值的元素(也就是老二),该如何处理呢?要注意,数组的元素是可以重复的。最大值可能是多个,所以单单一个排序然后取倒数第二个元素是解决不了问题的。
    此时,就需要一个特殊的排序算法了,先要剔除重复数据,然后再排序。不然,自己写算法也可以实现,但是集合类已经提供了非常好的方法,要是再使用数组自己写算法就显得有点过时了。数组不能剔除重复数据,但Set集合却是可以的,而且Set的子类TreeSet还能自动排序。代码如下:

    import java.util.Arrays;
    import java.util.List;
    import java.util.TreeSet;
    /**
     * 如果要查找仅次于最大值的元素(也就是老二)
     * @author Administrator
     *
     */
    public class FindTheSecond {
    	public static void getSecond(Integer[] data){
            // 转换为列表
         List<Integer> dataList=Arrays.asList(data);
          // 转换为TreeSet删除得复元素并升序排列
        TreeSet<Integer> ts=new TreeSet<Integer>(dataList);
         // 取得比最大值小的最大值,也就是老二了
        System.out.println(ts.lower(ts.last()));
    	}
    	public static void main(String[] args) {
    		Integer[] arr = new Integer[] { 10, 23, 56, 8, 7, 15 };
    		getSecond(arr);
    	}
    }
    
          剔除重复元素并升序排列,这都是由TreeSet类实现的,然后可再使用lower方法寻找小于最大值的值。大家看,上面的程序非常简单吧?那如果是我们自己编写代码会怎么样?那至少要遍历数组两遍才能计算出老二的值,代码的复杂度将大大提升。
          也许你会说,这个要求有点变态,怎么会有这样的需求?不,有这样的需求很正常,比如在学校按成绩排名时,如果一个年级有1200人,只要找出最高的三个分数(可不一定就是3个人,也要能是多人),是不是就是这种情况呢?因此在实际应用中求最值,包括最大值,最小值,第二大值,倒数第二小值等,使用集合是最简单的方式,当然若从性能方面来考虑,数组是最好的选择。

    展开全文
  • 分治策略求最值 的源码 算法设计与分析一书所提到的问题的C++实现.可以做为参考.自己做的程序,不好了请见谅...
  • 遗传算法求最值

    2017-08-20 12:24:14
    初始种群 遗传算法
  • 数组中最值算法

    2012-12-26 11:12:11
    一个数组的最大值[/color] [color=blue](1)自行实现,快速查找最大值[/color] [code="java"] public static int max(int[] data){ int max=data[0]; for(int i:data){ max=max>i?max:...
    源自《改善java程序的151建议》

    [color=red]1.求一个数组中的最大值[/color]
    [color=blue](1)自行实现,快速查找最大值[/color]

    public static int max(int[] data){
    int max=data[0];
    for(int i:data){
    max=max>i?max:i;
    }
    return max;
    }

    [color=blue](2)先排序,后取值[/color]
    public static int max(int[] data){
    Arrays.sort(data.clone());
    return data[data.length-1];
    }

    第二种方法中为何要先data.clone()再排序?因为数组也是对象,如果不拷贝那就把原来的数组的顺序改不了。
    方法一可以提升性能,而先排序后取值简单通俗易懂。从效率上讲,方法一快些。但实际测试中发现如果数组中数据少于一万,二者基本没啥差别

    [color=red]2.求一个数组中的第二大值[/color]
    因为数组中的值是可以重复的,所以最大值可能有多个,故不能取倒数第二个值。需用一个特殊的算法先剔除重复的值,再进行排序
    public static int secondMax(Integer[] data){
    List<Integer> dataList=Arrays.asList(data);
    //用treeset删除重复并排序
    TreeSet<Integer> ts=new TreeSet<Integer>(dataList);
    //取到比最大值小的,即第二大的值
    return ts.lower(ts.last());
    }
    展开全文
  • java 遗传算法求最值

    2012-05-03 08:39:02
    这个是我根据C\C++版本的遗传算法改编的java版本的遗传算法,经测试程序效果非常的好,欢迎下载。
  • 之前說明: 本文用一個實際的二進制編碼求解一元函數最值的代碼例子闡明基本遺傳算法的運行機理 。 本文會用Matlab代碼寫明關鍵之處的算子,源碼的下載 請帶好大挪移令和靈石進傳送陣目標函...

    如果你對遺傳算法感興趣或者正在做有關GA的研究,不妨關注博客右側專欄 → 智能計算-深入遺傳算法 ,一步一步深入算法,分享算法每一個流程模塊(如選擇策略,交叉機制等等)的眾多參考觀點。代碼和Demo咱從來不缺。

    寫在之前

    說明: 本文用一個實際的二進制編碼求解一元函數最值的代碼例子闡明基本遺傳算法的運行機理 。 本文會用Matlab代碼寫明關鍵之處的算子,源碼的下載 請帶好大挪移令和靈石進傳送陣

    目標函數分析

    目標函數如下:

    max:F(x)=x+10sin(5x)+7cos(4x),x∈[0,10]m

    a

    x

    :

    F

    (

    x

    )

    =

    x

    +

    10

    s

    i

    n

    (

    5

    x

    )

    +

    7

    c

    o

    s

    (

    4

    x

    )

    ,

    x

    [

    0

    ,

    10

    ]

    該函數圖形如下:

    7c3e753e7a773154959d5962ceb7ba5f.png

    從圖像中很容易看出函數在x∈[0,10]x

    [

    0

    ,

    10

    ] 上的最值Fmax≈24.8F

    m

    a

    x

    24.8 ,Fmin≈−12F

    m

    i

    n

    12 ,並且在x≈3.2x

    3.2 附近,有一個局部極大值。

    初步分析與算法流程

    本文列在入門篇,所以求解函數選用最為簡單的一元函數,並且定義域無負值。而所采用的遺傳算法也采用最傳統的算法思想與最傳統的算子:二進制編碼,賭輪(輪盤賭)選擇算子,多基因交叉,多基因變異。

    算法流程:

    Created with Raphaël 2.1.2

    開始

    生成初始種群

    計算適應度

    選擇,交叉,變異

    新種群

    是否滿足停止准則?

    End

    yes

    no

    生成初始種群:編碼VS解碼

    初始參數,種群的規模,也是個體的數量NP=80N

    P

    =

    80 , 迭代次數G=100G

    =

    100 。

    因為是一元函數,變量只有一個,所以采用二進制編碼,精度(個體基因位數)設置為L=20L

    =

    20 。也就是說,初始種群實際上就是一個隨機生成的由0和1組成的NP∗LN

    P

    L 的二維矩陣 。MATLAB代碼如下:

    f=randi([0,1],NP,L); %隨機獲得初始種群矩陣

    這樣,每個個體都是由20位的0和1基因組成,我們知道,其實每個個體就是函數的一個變量,在進行求解適應度時,需要將該變量帶入函數運算,這時,就需要將二進制編碼的個體解碼成在定義域內的十進制,解碼的原理和對應法則大家可以看如下的MATLAB代碼:

    for i=1:NP

    U =f(i,:);

    m=0;

    for j=1:L

    m=U(j)*2^(j-1)+m;

    end

    x(i)=Xx+m*(Xs-Xx)/(2^L-1); %x(i)為[0,10]內的實數

    end

    關於適應度函數

    ​ 適應度函數是為了更好的編寫代碼,更好的參與選擇、交叉和變異算子而在目標函數的基礎上做的一系列改進,本文要求解的目標函數非常普通,而且本文求解的是最大值,即,個體的目標函數值越大,說明該個體越好,適應度就越好,所以就直接把目標函數當做適應度函數,本文提到的適應度函數就是目標函數。

    ​ 需要提一下的是,源碼中對適應度值做了歸一化的處理。大家可不用理會 。

    思考:若本文求的是最小值呢?目標函數能不能直接當適應度函數用?

    回答: 不可以。我們所說的目標函數的概念是待優化的函數,而適應度函數是適應度的變化函數。如果求解目標函數的最小值,則目標函數值越小的,適應度越高,所以適應度函數的設計就應該考慮把目標函數做取反,或者取倒數操作 。

    關於 適應度函數的設計我們放到深入遺傳算法系列時再說。

    選擇策略

    ​ 在遺傳算法中,選擇策略用的最多的就是輪盤賭選擇,也叫賭輪選擇或者適應度比例選擇法 。輪盤賭選擇的原理並不難理解,我們這里給出一個簡單的理解,詳細的探討將留在”深入遺傳算法系列“中 。

    ​ 假設我們有4個個體個體:A 個體:B 個體:C 個體:D,其適應度、選擇概率、累計概率如下表所示 :

    個體

    適應度

    選擇概率

    累計概率

    A

    10

    0.1

    0.1

    B

    40

    0.4

    0.5

    C

    30

    0.3

    0.8

    D

    20

    0.2

    1

    我們用累計概率畫出一個餅圖(賭博的輪盤):

    99dadcc5137cf06be95312cb600e1942.png

    畫好圖后,就開始選擇了。首先我們准備一個骰(tou)子,隨機拋入輪盤中,落入0.0~0.1區域就選中個體A,落入0.1~0.5區域就選中個體B,落入0.5~0.8區域就選中個體C,落入0.8~1.0區域就選中個體D。 一共拋種群規模NP次,選出NP個個體組成新的種群。

    ​ 以上的思想就是輪盤賭的思想,其實還有另一個方式玩這個游戲,就是把骰子固定不動,我們轉NP次輪盤,骰子指向哪個區域,就選中對應區域的個體。貌似這種方式只是變換了一下參考系而已。

    ​ 用代碼實現上述的思想,也就會有兩種方式,希望大家在看別的代碼實現的時候能夠搞清楚是哪兩種方式。下面是MATLAB代碼實現: (用的是輪盤轉,骰子不動的思維方式)

    sum_Fit = sum(Fit) ;

    fitvalue = Fit ./sum_Fit ; %選擇概率,將Fit的每個元素除以sum_Fit

    fitvalue = cumsum(fitvalue) ; %累積概率

    ms = sort (rand(NP,1)) ; %產生NP個0~1之間的隨機數,並且升序排序

    fiti =1;

    newi=1;

    while newi<=NP %輪盤開始轉,一共轉NP次

    if(ms(newi)

    nf(newi,:) = f(fiti , :) ; % 把個體給新的種群

    newi = newi + 1;

    else

    fiti=fiti +1;

    end

    end

    交叉與變異機制

    交叉,選出兩個個體,通過交叉概率Pc確定是否需要交叉,如果交叉,則兩個個體某些對應基因位上的基因進行交換即可。

    變異,每個個體通過變異概率Pm確定是否需要變異,如果變異,則某些基因位取反即可。

    附上交叉代碼:

    for i = 1:2:NP % 從1到NP ,每隔兩個

    p = rand ;

    if p

    q=randi([0,1],1,L);

    for j =1:L

    if q(j) == 1

    temp=nf(i+1,j);

    nf(i+1,j) = nf(i,j);

    nf(i,j) = temp;

    end

    end

    end

    end

    附上變異代碼:

    i = 1;

    while i<=round(NP*Pc) % 四舍五入

    h=randi([1,NP],1,1) ; %隨機選取一個需要變異的染色體

    for j = 1:round(L*Pc)

    g = randi([1,20],1,1);%隨機選取需要變異的基因數

    %g=rand;

    nf(h,g) = ~ nf(h,g);

    end

    i=i+1;

    end

    精英策略的重要性

    所謂的精英策略是指: 上一代最好的個體不經過選擇、交叉、變異,直接復制到下一代中。不要小看精英策略,實踐證明,經營策略是增強算法收斂的最主要,最強大的手段,是經過理論證實。如果算法中缺乏精英策略,會嚴重影響收斂速度。

    MATLAB繪圖得出結果

    什么 ?你還不會用MATLAB畫圖,太out了!趕緊帶好大挪移令進傳送陣-三個實例搞定MATLAB二維繪圖閉關修煉去吧,恕不遠送!!

    首先,我們要清楚要繪制怎樣的結果圖。你可以繪制一幅種群平均適應度隨迭代次數的變化,也可以繪制一幅當前代種群的最大適應度,而本次我們繪制的是一幅迄今為止種群中最大適應度隨迭代次數的變化,如下圖:

    2133bb206cb176ad0139b84088bfaa0b.png

    至於是怎么繪制的 ?其實很簡單,定義一個G(代數)維數組,盛放每一代中迄今為止的最大值,然后用plot繪圖函數繪制即可。

    展开全文
  • 三分算法求最值

    2018-05-05 11:48:00
    (似乎这个图,是可行的) 下面介绍一种普遍凹凸型函数的做法——三分法 如图,mid=(left+right)/2,mmid=(mid+right)/2 如果,f(mid)< f(mmid),则[left,mid]可以被舍弃了,left=mid;  else ...

    假如是一个凸型函数,如何寻找最值呢?

    发现图中斜率是单调递减的,二分找到斜率为0的点?(似乎在这个图中,是可行的)

    下面介绍一种普遍求凹凸型函数的做法——三分法

     

    如图,mid=(left+right)/2,mmid=(mid+right)/2

    如果,f(mid)< f(mmid),则[left,mid]可以被舍弃了,left=mid;

       else   ,则[mmid,right]可以被舍弃了,right=mmid;

    直到最后剩下3个点,找出最值就行了

     //凹函数     
     ll l1=0,r1=l,mid,mmid;
            
            while(l1<r1-2)
            {
                mid=(l1+r1)/2;
                mmid=(mid+r1)/2;
                
                if(fun(mid)>fun(mmid))
                    l1=mid;
                else r1=mmid;
            }
        mid=(l1+r1)/2;
        printf("%lld\n",min(fun(mid),min(fun(l1),fun(r1))));    

    题目链接

     

    java代码,用C++写要注意超long long

     1 import java.math.BigDecimal;
     2 import java.util.Scanner;
     3 import java.util.HashMap;
     4 import java.math.BigInteger;
     5 public class Main{
     6     static BigInteger min2(BigInteger x,BigInteger y)
     7     {   
     8         if(x.compareTo(y)==1) return y;
     9         else return x;
    10     }
    11     static BigInteger[] d= new BigInteger[200005];
    12     static BigInteger[] f= new BigInteger[200005];
    13     static BigInteger[] pre= new BigInteger[200005];
    14     static BigInteger[] suf= new BigInteger[200005];
    15     static BigInteger a,b,m;
    16     public static void main(String[] args) {
    17         Scanner cin = new Scanner(System.in);
    18         int l;
    19         m=cin.nextBigInteger();
    20         l=cin.nextInt();
    21         pre[0]=BigInteger.valueOf(0);
    22         for(int i=1;i<=l;i++)
    23             {
    24             d[i]=cin.nextBigInteger();
    25             f[i]=cin.nextBigInteger();
    26             pre[i]=pre[i-1].add(d[i].multiply(d[i]).multiply(f[i]));
    27             }
    28         suf[l+1]=BigInteger.valueOf(0);
    29         for(int i=l;i>=1;i--)
    30             {
    31                 suf[i]=suf[i+1].add(m.multiply(f[i]));
    32             }
    33          
    34         int q;
    35         q=cin.nextInt();
    36         while(q--!=0)
    37         {
    38              
    39             a=cin.nextBigInteger();
    40             b=cin.nextBigInteger();
    41             int l1=0,r1=l,mid,mmid;
    42             while(l1<r1-2)
    43             {
    44                 mid=(l1+r1)/2;
    45                 mmid=(mid+r1)/2;
    46                 if(a.multiply(pre[mid]).add(b.multiply(suf[mid+1])).compareTo(a.multiply(pre[mmid]).add(b.multiply(suf[mmid+1])))==1)
    47                     l1=mid;
    48                 else r1=mmid;
    49             }
    50             mid=(l1+r1)/2;
    51             System.out.println(min2(a.multiply(pre[mid]).add(b.multiply(suf[mid+1])),min2(a.multiply(pre[l1]).add(b.multiply(suf[l1+1])),a.multiply(pre[r1]).add(b.multiply(suf[r1+1])))));
    52              
    53              
    54         }
    55     }        
    56     
    57                 
    58                 
    59 }
    View Code

     

    转载于:https://www.cnblogs.com/lnu161403214/p/8994255.html

    展开全文
  • 翻看一本非常基础的数据结构实验指导书...已知R[1..n]为整形数组,设计实现递归的算法:(1)出R最值  (2)出RN个数的和  (3)RN个数的平均值 代码的实现: #include using namespace std;
  • 前提 ...伪算法 MINIMUM(A) min=A[1] for i = 2 to A.length if min > A[i] min = A[i] return min MAXIMUM(A) max=A[1] for i = 2 to A.length if max < A[i] max = A[i] return
  • 1.梯度方向 对多元函数的参数偏导,得到函数增加或减小最快的方向。具体来说,对于函数f(x,y),点(x0,y0),沿着梯度向量的方向就是(∂f/∂x0,∂f/∂y0)T的方向是f(x,y)增加最快的地方。...3.y=cos(x)(0,2...
  • 算法要求两个实参类型完全一致。 1、max()和min() #define debug qDebug()<< int main(int argc, char *argv[]) { QList<int> list1{26,33,44,66,77,99,33}; QList<int> list2{22,33,44,66,...
  • Java我们可以通过编写算法的方式,也可以通过数组先排序再取值的方式来实现。下面以最大值为例,解释一下多种算法。 (1)自行实现,快速査找最大值 先来看用快速査找法取最大值的算法,其代码如下: 1 public...
  • ST算法是一个用倍增来区间最值算法,倍增是一个与二分类似的思想的一个东西,倍增简而言之也就是区间长度按1,2,4,8..... 我们先用nlog(n)的复杂度打出一个最大值表,后面我们可以通过O(1)的 复杂度来直接...
  • 遗传算法求取目标函数F(s)=21.5+x1*sin(4*pi*x1)+x2*sin(20*pi*x2)最值,采用精英保留测量,结果准确。人工智能课程设计,自己原创,MATLAB调试通过。
  • 建议64:多种最值算法,适时选择. 对一批数据进行排序,然后找出其中的最大值或最小值,这是基本的数据结构知识。Java我们可以通过编写算法的方式,也可以通过数组先排序再取值的方式来实现。下面以最大值为例...
  • 遗传算法求函数最值.的matlab实现
  • 几种函数最值算法

    千次阅读 2017-11-13 16:32:26
    1、遗传算法 2、粒子群算法 3、模拟退火 4、蚁群算法
  • 《蚁群算法代码(函数最值)》由会员分享,可在线阅读,更多相关《蚁群算法代码(函数最值)(4页珍藏版)》请人人文库网上搜索。1、function F=F(x1,x2) %目标函数 F=-(x1.2+2*x2.2-0.3*cos(3*pi*x1)-0.4*cos(4*pi*...
  •  给定一个长度为N 的数组,有q个询问,每个询问是求在数组的一段区间内那个元素的因子的个数最大,比如24的因子的个数就是8。  Input  首先是一个整数t,表示有t组测试数据,每组测试数据的第一行是一个整数N(1...
  • 遗传算法以一种群体的所有个体为对象,并利用随机化...参数编码、初始群体的设定、适应度函数的设计、遗传操作设计、控制参数设定五个要素组成了遗传算法的核心内容,此程序利用Python实现遗传算法求函数最值问题。
  • 一个遗传算法的实例,用matlab写的,包含画图,求解一元函数的最大值。
  • 动态规划算法中,它是将问题划分为一个一个的子问题,与子问题相关的变量的一组取值,称之为一个“状态”,一个状态对应于一个子问题,所谓“状态”下的值,即为该状态下子问题的解。我们则定义一数组(数组维数与...
  • Python实现遗传算法求函数最值

    千次阅读 2020-04-28 20:18:13
    Python实现遗传算法求函数最值 详细源代码:GA.py 1、算法过程图解 2、详细过程举例说明 (1)待求解方程 (2)确定编码方案 主要是确定编码长度: def segment_length(self): length = [] precision =[] for...
  • matlab求最值(极值)

    万次阅读 多人点赞 2016-09-25 18:26:55
    根据我看过的材料来说 ,求最值(极值)无非有下面几种情况。 1、简单函数的单一最值(极值) clear clc t=-100:0.001:100;%初值:增量:终值 symsx; y=x/(x*x+1); f=inline(y);%内联函数 max=max(f(t)) min=...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 16,433
精华内容 6,573
关键字:

在求最值的算法中