极差的贪心算法实现.ppt

《极差的贪心算法实现.ppt》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、极差的贪心算法实现数列极差问题描述：给定n个正整数数列，进行如下操作：每次删去两个数a和b，添加一个数a*b+1，直到只剩一个数N。在所有这样的N中，有一个最大Max和最小Min，M=Max-Min是极差。设计程序计算M。用贪心算法算法思想：对于给定的数列主要问题是如何求最大值和最小值。设有三个数xn2>n3,所以可以得到结论：优先做数列较小值的(a*b+1)运算得到的值大，优先做数

2、列中较大的值的(a*b+1)运算得到的值小。所以贪心算法可以这样设计，先将数列从小到大排列，选出数列中最小的两个数m，n,做n2=m*n,然后把m，n从数列中删除，n1有序插入到数列中，重复上述过程，直到数列中只剩下一个数字，该数字就是所求的最大值；选出数列中最大的两个数a,b做n2=a*b,然后把a，b从数列中删除，n2有序插入到数列中，重复上述过程，直到数列中只剩下一个数字，该数字就是所求的最小值；最后n1-n2就是极差。#includeusingnamespacestd;constSize=6;voidChange(int*a,int*b){

3、inttemp;temp=*a;*a=*b;*b=temp;}voidinput(int*array){cout<<"输入"<>*array;array++;}}voidQuickSort(int*array,intlen){if(len>1){intnum=0,i=0,j=len-1,temp=0;while(i!=j){i=0;j=len-1;temp=0;//从后往前找比关键数大的数，交换for(j;j>num;j--){if(array[num]>array[j]){

4、Change(&array[num],&array[j]);num=j;break;}}//从前往后查比关键数小的数，交换for(i;i=0;i--)t=t*a[i]+1;returnt;}//最大的两个数相

5、乘还是最大的longMax(int*a){intb[Size],t;for(inti=0;i

6、

7、m==Size)break;elseb[m-1]=b[m];}b[m-1]=t;}returnb[Size-1];}intmain(){intn=Size,list[Size],max,min,i;input(list);QuickSort(list,Size);max=Max(list

8、);min=Min(list);cout<<"max="<