算法设计赛程问题

计算机算法设计与分析一赛程问题1.赛程表的制定. 陈 聪100020032得分排序 姜 珍100020113场地和裁判的分配 张凤霞100020504重播选择 许玲洁10002042 刘 滔100020185选出最优球员 吴美荣100020392011-12-23二结论三参考资料一赛程问题1.赛程表的制定a. 问题的背景设有n=2k个球队要进行球赛。现要设计一个满足以下要求的比赛日程表：（1） 每个球队必须与其他n-1个选手各赛一次；（2） 每个球队一天只能赛一次；（3） 循环赛一共进行n-1天。b. 提出问题每支球队不可以一天赛两场，在整场赛事前，先制定赛程表。避免重复。c.解决问题任何可以用计算机求解的问题所需的计算时间都与其规模有关。问题的规模越小，解题所需的计算时间往往也越短，从而也较容易处理。分治法的设计思想，将一个难以直接解决的大问题，分割成一些规模较小的相同问题，以便各个击破，分而治之。如果原问题可分割成k个子问题，1k=n，且这些子问题都可解，并可利用这些子问题的解求出原问题的解，那么这种分治法就可行的。由分治法产生的子问题往往是原问题的较小模式，这就为使用递归技术提供方便。在这种情况下，反复应用分治手段，可以使子问题与原问题类型一致而而其规模去不断缩小，最终使子问题缩小到很容易求出其解。分治法的基本思想是将一个规模为n的问题分解为k个规模较小的子问题，这些子问题互相独立且与原问题相同。递归地解这些子问题，然后将各子问题的解合并到原问题的解。在用分治法设计算法时，最好是子问题的规模大致相同。即将一个问题分成大小相等的k个子问题的处理方法是行之有效的。一个分治法将规模为n的问题分成k个规模为n/m的子问题去解。按分治策略，可以将所有的球队分成两半，n个球队的比赛日程表就可以通过为n/2个球队设计的比赛日程表来决定。递归的用这种一分为二的策略对球队进行分割，直到只剩下两只球队时，比赛日程表的制定就变得简单了。算法描述如下void Table(int k ,int* *a)int n=1;for(int i =1;i=k;i+) n*=2;for(int i=1;i=n;i+) a1i=i;int m=1;for(int s=1;s=k;s+)n/=2;for(int t=1;t=n;t+)for(int i=m+1;i=2*m;i+)for(int j=m+1;j=2*m;j+)aij+(t-1)*m*2=ai-mj+(t-1)*m*2-m; aij+(t-1)*m*2-m=ai-mj+(t-1)*m*2;m*=2;2.分数排序a. 问题的背景比赛胜一场得5分，负一场得0分，平一场得2分。每天更新赛后各球队的得分情况，根据最新得分总和，进行排名。b. 提出问题排序的算法很多，我们从算法的平均时间复杂度、最坏时间复杂度以及算法所需的辅助存储空间三方面出发，对各种排序方法加以比较。找出最为合适的算法。就平均时间性能而言，快速排序是所有排序方法中最好的。c. 解决问题快速排序的基本思想是：从待排序记录序列中选取一个记录，其关键字设为k1,然后将其余关键字小于k1的记录移到前面，而将关键字大于k1的记录移到后面，结果将待排序记录序列分为两个子表，最后将关键字为k1的记录插到其分界线的位置处。这个过程称为一趟快速排序。通过一次划分后，就以关键字为k1的记录为分界线，将待排序的序列分成了俩个子表，且前面子表中所有记录的关键字均不大于k1，而后面子表中的所有记录的关键字均不小于k1。对分割后的子表继续按上述原则进行分割，直到所有子表的表长不超过1为止，此时待排序记录序列就变成了一个有序表。算法描述如下：void QKSort(RecordType r, int low, int high)if(lowhigh) pos=QKPass(r, low, high); QKSort(r, low, pos-1);QKSort(r, pos+1, high);int QKPass(RecordType r, int left, int right) x=rleft; low=left; high=right; while(lowhigh) while(low=x.key) high-; if(lowhigh) rlow=rhigh; low+; while( lowhigh & rlow.keyx.key) low+; if(low=0,c=0,d=m.d称为该随机序列的种子。如何选取该方法中的常数b,c和m直接关系到所产生的随机序列的随机性能。从直观上看，m应取的充分大，因此可取m为机器大数，另外应取gcd(m,d)=1,因此可取b为一素数。为了在设计随机化算法时便于产生所需的随机数，建立一个随机数类。该类包含一个需由用户初始化的种子randseed。给定初始化种子后即可产生与之相应的随机序列。种子是一个无符号的整数，可由用户定义也可以由系统时间自动产生。函数Random的输入参数n16)%n);double RandomNumber: fRandom(void) Return Random(maxshort) /double(maxshort);4.重播选择a.问题的背景每场球赛都可以重播，重播球赛也能满足广大观众的需求，但是电视台的播放档期不能足够给所有球赛重播。所以怎样选择重播的比赛是个有待解决的问题。b.提出问题电视台重播第i场球赛可直接盈利wi元，每场球赛只能重播一次不能反复播放，而这场球赛受亲睐度vi ，可是电视台空闲的档期有限，电视台最多可重播球赛总数为c次。怎样选择才能使收视率和直接盈利得到最优解。c.解决问题 此问题的形式化描述是，给定c0, wi 0, vi 0,1=i=n,要求找出一个n元向量（x1,x2,.,xn）,x2在0，1范围之类，1=i=n,使得wi xi=c(1=i=n),而且vi xi 达到最大。因此,重播选择是一个特殊的整数规划问题： Maxvixi(1=i=n) wixi=c(1=i=n) ,xi在0，1范围之类, 1=i=n最优结构具有最优子结构性质。设（y1,y2,yn）是所给重播选择的最优解，则（y2,y3,yn）是下面相应子问题的一个最优解： Maxvixi(1=i=n) wixi=c-wiy1(2=i=n), xi在0，1范围之类, 2=iviyi, (2=i=n),且w1y1+wizi=c,(2=i=n).因此 V1y1+vizi(2=i viyi(1=i=n) W1y1+wizi(2=i=n)=c这说明（y1,z2,zn）是所给重播选择的一个更优解，从而（y1,y2,yn）不是所给重播选择的最优解，此为矛盾。设所给重播选择的子问题 Maxvkxk(i=k=n) wkxk=j(i=k=n),xk在0，1范围之类，i=k=wi m(i,j)=m(i+1,j) 0=j=wn m(n,j)=0 o=jwn基于以上讨论，当我i（1=i=n）为正整数时，用二维数组m来存储m(i,j)的相应值，可设计解重播选择的动态规划算法如下： templatevoid Knapsack(Type v,int w,int c,int n,Type * m) int jMax=min(wn-1,c); for(int j=0;j=jMax;j+) mnj=0; for(int j=wn;j1;i-) jMax=min(wi-1,c); for(int j=0;j=jMax;j+) mij=mi+1j; for(intj=wi;j=w1) m1c=max(m1c,m2c-w1+v1); template void Traceback(Type *m,int w,int c,int n,int x) for(i=1;in;i+) if(mic=mi+1c) xi=0; else xi=1;c-=wi; xn=(mnc)?1:0; 按上述算法Knapsack计算后，m1c给出所要求的重播选择的最优值。相应的最优值可由算法Traceback计算如下。如果m1c= m2c，则x1=0，否则x1=1.当x1=0时，有m2c继续构造最优解。当x1=1时，有m2c-w1继续构造最优解。依次类推，可构造出相应的最优解（x1，x2，.，xn）。计算复杂性分析从计算m（i，j）的递归式容易看出，上述算法Knapsack需要O（nc）计算时间，而Traceback需要O（n）计算时间。上述算法Knapsack有两个较明显的缺点，其一是算法要求所给重播某球赛可盈利Wi（1in）是整数。其次，当c很大时，算法需要的计算时间较多。templateType Knapsack（int n，Type c，Type v，Type w，Type* *p，int x） int *head=new intn+2； headn+1=0;p00=0;p01=0;int left=0,right=0,next=1;headn=1;for(int i=n;i=1;i-)int k=left;for(int j=left;jc) break;Type y=pj0+wi,m=pj1+vi;while(k=right&pk0y)pnext0=pk0;pnext+1=pk+1;if(k=right&pk0=y)if(mpnext-11) pnext0=y;pnext+1=m;while(k=right&pk1=pnext-11) k+;while(k=right)pnext0=pk0;pnext+1=pk+1;left=right+1;right=next-1;headi-1=next;Taceback(n,w,v,p,head,x);return pnext-11;templatevoid Traceback(int n,Type w,Type v，Type* *p，int *head,int x) Type j=phead0-10,m=phead0-10; for(int i=1;i=n;i+) xi=0; for(int k=headi+1;k=headi-1;k+) if(pk0+wi=j&pk1+vi=m) xi=1;j=pk0;m=pk1;break;5选出最优球员a.问题的背景每一届球赛都会涌现出很多优秀球员，众多观众喜欢的球员各不相同。为了表彰平行、技术兼优的球员，为其他球员作为好榜样，特此，开展选出最优球员的活动（选出的最终结果仅供参考）。b.提出问题先由广大网友从网上推选出自己喜欢的球员，再由活动策划人从中选出人气最高的前20位。最后按顺序由这20位球员各选出一位自己最不看好的球员，被选中球员淘汰，由这位被淘汰的球员选出下一个被淘汰的球员，最后只剩下一位，即为最优球员。c.解决问题为了解决这一问题，可以用一个长度为20的数组作为线性存储结构，并把该数组看成是一个首尾相接的环形结构，那么每被淘汰的球员，就要在该数组的相应位置做一个删除标记，该单元以后就不再作为计数单元。这样做不仅算法较复杂，而且效率低下，还要移动大量的元素。而用单循环链表来解决这一问题，实现的方法相对要简单得多。首先要定义链表结点，单循环链表的结点结构与一般单链表的结点结构完全相同，只是数据域用一个整数来表示位置；然后将它们组成一个具有20个结点的单循环链表。接下来从位置为1的结点开始数，数到第k(事先定义好的密码)个结点，就将下一个结点从循环链表中删去，然后再从删去结点的下一个结点开始数起，数到第k个结点，再将其下一个结点删去，如此进行下去，直至剩下1个结点为止，即最佳球员。不失一般性，将20改为一个任意输入的正整数n，而报数上限也为一个任选的正整数k。这样，该算法描述如下： typedef struct node int data; struct node * next; ListNode,* LinkList;void main() LinkList R=NULL; int n, k; LinkList InitRing(int n, LinkList R); /函数说明 LinkList DeleteDeath(int n,int k,LinkList R); void Outing(int n,LinkList R); printf(“输入总人数n及报数上限k :j”); scanf(“%d%d”,&n,&k); R=InitRing(n, k, R); OutRing(n, R); /* 建立单循环链表函数 */LinkList InitRing(int n,LinkList R) ListNode *p,*q; int i; R=q=(ListNode *)malloc(sizeof(ListNode); for(i=1;idata=i; q-next=p; q=p;p-data=n;p-next=R;R=p;return R; /* 生者与死者选择函数 */LinkList DeleteDeath(int n,int k,LinkList R) int i, j; ListNode *p, *q; p=R; printf(“抛入大海者的编号如下：n”); for(i=1;i=n/2;i+) /删除一半的结点 for(j=1;jnext; q=p-next; /q为被删除结点 p-next=q-next; /删除q指向的结点 printf（”4d”,q-data）; if(i % 10=0) printf(“n”); free(q); printf(“n”); R=p; return R;/* 输出所有生者函数 */void OutRing(int n,LinkList R ) int I; ListNode *p; p=R; printf(“幸存者的编号如下：n”); for(i=1;inext) printf(“%4d”,p-data); if(i % 10=0) printf(“n”); printf(“n”);二结论我们从赛程表的制定、分数排序、场地和裁判的分配、重播选择和最优球员选择这五个方面解决赛程问题。通过赛程问题的解决，让我们对许多算法有更深的了解。三参考资料1.计算机算法设计与分析 王晓东2.数据结构c语言篇 耿国华