《极差的贪心算法实现.ppt》由会员分享，可在线阅读，更多相关《极差的贪心算法实现.ppt（8页珍藏版）》请在三一办公上搜索。
1、极差的贪心算法实现,数列极差问题描述：给定n个正整数数列，进行如下操作：每次删去两个数a和b，添加一个数a*b+1，直到只剩一个数N。在所有这样的N中，有一个最大Max和最小Min，M=Max-Min是极差。设计程序计算M。用贪心算法算法思想：对于给定的数列主要问题是如何求最大值和最小值。设有三个数xn2n3,所以可以得到结论：优先做数列较小值的(a*b+1)运算得到的值大，优先做数列中较大的值的(a*b+1)运算得到的值小。所以贪心算法可以这样设计，先将数列从小到大排列，选出数列中最小的两个数m，n,做n2=m*n,然后把m，n从数列中删除，n1有序插入到数列中，重复上述过程，直到数列中只剩
2、下一个数字，该数字就是所求的最大值；选出数列中最大的两个数a,b做n2=a*b,然后把a，b从数列中删除，n2有序插入到数列中，重复上述过程，直到数列中只剩下一个数字，该数字就是所求的最小值；最后n1-n2就是极差。,#includeusing namespace std;const Size=6;void Change(int*a,int*b)int temp;temp=*a;*a=*b;*b=temp;void input(int*array)cout*array;array+;,void QuickSort(int*array,int len)if(len1)int num=0,i=0,
3、j=len-1,temp=0;while(i!=j)i=0;j=len-1;temp=0;/从后往前找比关键数大的数，交换for(j;jnum;j-)if(arraynumarrayj)Change(,/从前往后查比关键数小的数，交换for(i;inum;i+)if(arraynumarrayi)Change(,long Min(int*a)int t=aSize-1;for(int i=Size-2;i=0;i-)t=t*ai+1;return t;/最大的两个数相乘还是最大的,long Max(int*a)int bSize,t;for(int i=0;iSize;i+)bi=ai;for
4、(int j=1;jSize;j+)t=bj-1*bj+1;for(int m=j+1;m=Size;m+)if(t=bm|m=Size)break;else bm-1=bm;bm-1=t;return bSize-1;,int main()int n=Size,listSize,max,min,i;input(list);QuickSort(list,Size);max=Max(list);min=Min(list);coutmax=maxendl;coutmin=minendl;cout极差M=max-minendl;return 0;,测试例：（1）1,2,3,4,5,6,运行结果：输入6个整数:1 2 3 4 5 6max=1282min=754极差M=528（2）2,3,4,5,6,7运行结果：输入6个整数:2 3 4 5 6 7max=6365min=5193极差M=1172,
