数列极差

数列极差问题1、问题描述：N个正数数列，进行如下操作：每一次擦去其中2个数，设a和b，然后在数列中加入一个数ab+1，如此下去直至黑板上只剩下一个数。在所有按这种操作方式最后得到的数中，最大的数记为MAX，最小的数记为MIN，则该数列的极差M定义为M=MAX-MIN。2、要解决的问题：在数列极差问题中，问题的难点是求出MAX,MIN的值。因为在N个正整数组成的数列中，用穷举法的话每次要去2个数的选择有很多，所以不可能每种选择的结果都计算出来，这样的话计算量非常大。所以我们主要解决的问题是找出一个方法求出MAX,MIN的值。3、分析问题：贪心算法最重要的两个性质是：贪心选择性质和最优子结构性质。贪心选择性质是所求问题的整体最优解可以通过一系列局部最优的选择，也就是贪心选择来达到。而最优子结构性质是指一个问题的最优解包含其子问题的最优解。问题的关键就是MAXMIN值的求解问题，所以首先看下怎么样来求MAXMIN值。设有三个数xyz,且xyz，按问题描述来做的话，结果有下面三种情况：num1=（x*y+1）*z+1=xyz+z+1,num2=(x*z+1)*y+1=xyz+y+1，num3=(y*z+1)*x+1=xyz+x+1。很容易看出num1num2num3。所以我们可以得出结论：优先选择数列中最小的2个数进行（a*b+1）运算得到的值大，优先选择数列中最大的2个数进行（a*b+1）运算得到的值小。我们可以把整体的MAX，MIN值通过一系列局部求MAX,MIN值来求我们想要的结果。我们在看下用贪心策略求解的合理性：假设经（N－3）次运算后得到3个数：xymax（maxxy），其中max是（N－2）个数经（N－3）次运算后所得的最大值，此时最大值m＝（x*y＋1）×max＋1。若经（N－2）次变换后所得的3个数为：xyz（zxy）且z不为（N－2）次变换后的最大值，即z＜max则所求得的最大值为：m’＝（x*y+1）*z+1，此时m－m’＝（1+x*y）（max－z）＞0所以此时不为最优解。所以若使第k（1≤k≤N－1）次变换后所得值最大，必使（k－1）次变换后所得值最大（符合贪心策略的最优子结构性质），在进行第k次变换时，只需取在进行（k－1）次变换后所得数列中的两最小数x，y进行运算，再把结果插入到数列即可。（符合贪心策略的贪心选择性质）。4、算法设计：根据对问题的分析我们可以这样设计贪心算法：①现将数列a[n]按从小到大进行排列。voidquicksort(intlow,inthigh)//用快速排序对数列按冲小到大进行排序{intmid=a[(low+high)/2],i=low,j=high,t;while(i=j){while(a[i]mid)i++;while(a[j]mid)j--;if(i=j){t=a[i];a[i]=a[j];a[j]=t;i++;j--;}}if(lowj)quicksort(low,j);if(highi)quicksort(i,high);}②进行最大值的计算：选出a[n]中最小的两个数进行（a*b+1）运算，在把运算结果按从小到大插入到数列中。一直这样运算，最后就可以得出MAX值。具体代码实现：i=2;while(i=n)//求max值{max=a[i-1]*a[i]+1;//对数列中的数进行贪心选择，选最小的2个数进行计算if(i==n)break;j=i;while(a[j+1]max&&j+1=n)//把计算结果插入到数列中{a[j]=a[j+1];j++;}a[j]=max;i++;}③进行最小值的计算：选出a[n]中最大的两个数进行（a*b+1）运算，在把运算结果按从小到大插入到数列中。一直这样运算，最后就可以得出MIN值。具体代码实现：i=n-1;while(i=1)//求min值{min=b[i+1]*b[i]+1;//对数列中的数进行贪心选择，选最大的2个数进行计算if(i==1)break;j=i;while(b[j-1]min&&j-1=1)//把计算结果插入到数列中{b[j]=b[j-1];j--;}b[j]=min;i--;}④最后该数列的极差M=MAX-MIN。5、时间复杂性对于快速排序，它的平均复杂度是O(NlogN)。求max和min值需要n-1次的计算，总共需要O(NlogN)计算时间。因此，关于用贪心算法求解n个数的数列极差问题的计算时间为O(NlogN)。6、运行结果：我们取n=3，依次输入3个数，例如,111。按照求数列极差的方法最后求出来的结果是max=3,min=3,max-min=0。程序运行的结果和实际运算结果一致。