针对数组的两最值算法和求数组中次大值的算法
      对一批数据进行排序，然后找出其中的最大值或最小值，这是基本的数据结构知识。在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个人，也要能是多人），是不是就是这种情况呢？因此在实际应用中求最值，包括最大值，最小值，第二大值，倒数第二小值等，使用集合是最简单的方式，当然若从性能方面来考虑，数组是最好的选择。

源自《改善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());
}

如果你對遺傳算法感興趣或者正在做有關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
]
該函數圖形如下：
從圖像中很容易看出函數在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
我們用累計概率畫出一個餅圖(賭博的輪盤)：
畫好圖后，就開始選擇了。首先我們准備一個骰(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二維繪圖閉關修煉去吧，恕不遠送！！
首先，我們要清楚要繪制怎樣的結果圖。你可以繪制一幅種群平均適應度隨迭代次數的變化，也可以繪制一幅當前代種群的最大適應度，而本次我們繪制的是一幅迄今為止種群中最大適應度隨迭代次數的變化，如下圖：
至於是怎么繪制的 ？其實很簡單，定義一個G(代數)維數組，盛放每一代中迄今為止的最大值，然后用plot繪圖函數繪制即可。

    

假如是一个凸型函数，如何寻找最值呢？
发现图中斜率是单调递减的，二分找到斜率为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