极差的贪心算法实现.ppt

极差的贪心算法实现数列极差问题描述：给定n个正整数数列，进行如下操作：每次删去两个数a和b，添加一个数a*b+1，直到只剩一个数N。在所有这样的N中，有一个最大Max和最小Min，M=Max-Min是极差。设计程序计算M。用贪心算法算法思想：对于给定的数列主要问题是如何求最大值和最小值。设有三个数xyn2n3,所以可以得到结论：优先做数列较小值的(a*b+1)运算得到的值大，优先做数列中较大的值的(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)inttemp;temp=*a;*a=*b;*b=temp;voidinput(int*array)cout输入Size个整数:endl;for(inti=0;i*array;array+;voidQuickSort(int*array,intlen)if(len1)intnum=0,i=0,j=len-1,temp=0;while(i!=j)i=0;j=len-1;temp=0;/从后往前找比关键数大的数，交换for(j;jnum;j-)if(arraynumarrayj)Change(&arraynum,&arrayj);num=j;break;/从前往后查比关键数小的数，交换for(i;inum;i+)if(arraynum=0;i-)t=t*ai+1;returnt;/最大的两个数相乘还是最大的longMax(int*a)intbSize,t;for(inti=0;iSize;i+)bi=ai;for(intj=1;jSize;j+)t=bj-1*bj+1;for(intm=j+1;m=Size;m+)if(t=bm|m=Size)break;elsebm-1=bm;bm-1=t;returnbSize-1;intmain()intn=Size,listSize,max,min,i;input(list);QuickSort(list,Size);max=Max(list);min=Min(list);coutmax=maxendl;coutmin=minendl;cout极差M=max-minendl;return0;测试例：（1）1,2,3,4,5,6,运行结果：输入6个整数:123456max=1282min=754极差M=528（2）2,3,4,5,6,7运行结果：输入6个整数:234567max=6365min=5193极差M=1172此课件下载可自行编辑修改，供参考！感谢您的支持，我们努力做得更好！