極差的貪心算法實現(xiàn)

1、精選ppt 極差的貪心算法實現(xiàn)數(shù)列極差問題描述：給定n個正整數(shù)數(shù)列，進(jìn)行如下操作：每次刪去兩個數(shù)a和b，添加一個數(shù)a*b+1，直到只剩一個數(shù)N。在所有這樣的N中，有一個最大Max和最小Min，M=Max-Min是極差。設(shè)計程序計算M。用貪心算法算法思想：對于給定的數(shù)列主要問題是如何求最大值和最小值。設(shè)有三個數(shù)xyn2n3,所以可以得到結(jié)論：優(yōu)先做數(shù)列較小值的(a*b+1)運(yùn)算得到的值大，優(yōu)先做數(shù)列中較大的值的(a*b+1)運(yùn)算得到的值小。所以貪心算法可以這樣設(shè)計，先將數(shù)列從小到大排列，選出數(shù)列中最小的兩個數(shù)m，n,做n2=m*n,然后把m，n從數(shù)列中刪除，n1有序插入到數(shù)列中，重復(fù)上述過程，直

2、到數(shù)列中只剩下一個數(shù)字，該數(shù)字就是所求的最大值；選出數(shù)列中最大的兩個數(shù)a,b做n2=a*b,然后把a(bǔ)，b從數(shù)列中刪除，n2有序插入到數(shù)列中，重復(fù)上述過程，直到數(shù)列中只剩下一個數(shù)字，該數(shù)字就是所求的最小值；最后n1-n2就是極差。精選ppt#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輸入Size個整數(shù):endl;for(int i=0;i*array;array+;精選pptvoid Quick

3、Sort(int *array, int len)if(len1)int num=0,i=0,j=len-1,temp=0;while(i!=j)i=0;j=len-1;temp=0;/從后往前找比關(guān)鍵數(shù)大的數(shù)，交換for(j;jnum;j-)if(arraynumarrayj)Change(&arraynum,&arrayj);num=j;break;精選ppt/從前往后查比關(guān)鍵數(shù)小的數(shù)，交換for(i;inum;i+)if(arraynum=0;i-)t=t*ai+1;return t;/最大的兩個數(shù)相乘還是最大的精選pptlong Max(int *a)int bSize

4、,t;for(int i=0;iSize;i+)bi=ai;for(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;精選pptint 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;精選ppt測試?yán)海?）1,2,3,4,5,6,運(yùn)行結(jié)果：輸入6個整數(shù):1 2 3 4 5 6max=1282min=754極差M=528（2）2,3,4,5,6,7運(yùn)行結(jié)果：輸入6個整數(shù):2 3 4