数列极差问题.doc

数列极差问题 在黑板上写了N个正整数组成的一个数列，进行如下操作： 每次擦去其中的两个数a和b，然后在数列中加入一个数a×b＋1，如此下去直至黑板上 剩下一个数，在所有按这种操作方式最后得到的数中，最大的为max，最小的为min， 则该数列的极差定义为M＝max－min。 请你编程，对于给定的数列，计算极差。 输入 输入包含多个测试集。每个测试集的第一个数N表示 正整数序列长度（0＜＝N＜＝50000），随后是N个正整数。N为0表示输入结束。 输出 每个结果一行 输入样例 3 1 2 3 0 输出样例 2 来源：/ojs/show.php?Proid=1062Contestid=0 必威体育精装版评论发表评论 您尚未登录本站，不能发表评论，请登录 或者 注册 成为本站会员 评论人: 红色的狐狸??发布时间: 2012-3-11 15:06:06 我觉的每次擦去的两个数为最小的，所得的为最大值，每次擦去的为两个最大的，得到的为最小值；例如：1?2?3?4?5?=》3?3?4?5=》10?4?5=》10?21=》211得到最大值；1?2?3?4?5=》1?2?3?21=》1?2?64=》1?129=》130得到最小值，差值为211-130=81代码如下： #include?stdio.h #include?stdlib.h int?Partitition(int?*a,int?low,int?high){ ????a[0]=a[low]; ????int?pivotkey=a[low]; ????while(lowhigh){ ????????while(lowhigha[high]pivotkey){ ????????????high--; ????????} ????????a[low]=a[high]; ????????while(lowhigha[low]=pivotkey){ ????????????low++; ????????} ????????a[high]=a[low]; ????} ????a[low]=a[0]; ????return?low; } void?Qsort(int?*a,int?low,int?high){ ????if(lowhigh){ ????????int?pivotkey=Partitition(a,low,high); ????????Qsort(a,low,pivotkey-1); ????????Qsort(a,pivotkey+1,high); ????} } int?Max(int?*a,int?n){ ????int?i2,t; ????while(n!=1){ ????????t=a[1]*a[2]+1; ????????i2=3; ????????while(ta[i2]i2=n){ ????????????a[i2-2]=a[i2++]; ????????} ????????a[i2-2]=t; ????????while(i2=n){ ????????????a[i2-1]=a[i2]; ????????????i2++; ????????} ????????a[i2-1]=0; ????????n=n-1; ????} ????return?a[1]; } int?Min(int?*a,int?n){ ????int?i=3; ????int?t=a[1]*a[2]+1; ????for(;i=n;i++){ ????????t=a[i]*t+1; ????} return?t; } int?main() { ????int?a[100],b[100],n,i=1; ????int?c[10]; ????printf(请输入测试数n\n); ????scanf(%d,n); ????if(n=1){ ????????printf(输入有误); ????????return?0; ????} ????printf(请输入n个测试数\n); ????scanf(%d,a[i]); ????while(a[i]) ????????scanf(%d,a[++i]); ????Qsort(a,1,n); ????for(i=1;i=n;i++){ ????????printf(%d?,a[i]); ????} ????i=1; ????for(i=n;i=1;i--){ ????????b[i]=a[n-i+1]; ????} ????int?max=Max(a,n); ????int?min=Min(b,n); ????printf(最大的极差为:%d\n,max-min); ????return?0; } 评论人: py102356??发布时间: 2011-10-