循环赛日程表 循环赛日程表 递归

原文地址:循环赛日程表(转)作者:落子不悔

一、 实验题目

设有n位选手参加网球循环赛,循环赛共进行n-1天,每位选手要与其他n-1位选手比赛一场,且每位选手每天必须比赛一场,不能轮空。试按此要求为比赛安排日程。

二、实验目的

1.深刻理解并掌握“分治算法”的设计思想;

2.提高应用“分治算法”设计技能;

3.理解这样一个观点:用递归方法编写的问题解决程序具有结构清晰,可读性强等优点,且递归算法的设计比非递归算法的设计往往要容易一些,所以当问题本身是递归定义的,或者问题所涉及到的数据结构是递归定义的,或者是问题的解决方法是递归形式的时候,往往采用递归算法来解决。

三、实验要求

1.实现《网球循环赛》问题的分治算法,并进行算法时间复杂性分析。

2.对实现的分治算法进行改进;

3.对上述改进后算法进行时间复杂性分析,通过实验结果分析对比,得出自己的结论和总结。

四、实验过程

1、算法一:

#include<stdio.h>

#define N 64

void GameTable(int k,int a[][N])

{

//n=2^k(k>=1)个选手参加比赛,二维数组a表示日程安排,数组下标从1开始

int n=2;//k=0,两个选手比赛日程可直接求得

//求解两个选手比赛日程,得到左上角元素

a[1][1]=1;a[1][2]=2;

a[2][1]=2;a[2][2]=1;

int i,j,t;

for(t=1;t<k;t++)//迭代处理,依次处理2^2,....,2^k个选手比赛日程

{

int temp=n;n=n*2;

//填左下角元素

for(i=temp+1;i<=n;i++)

for(j=1;j<=temp;j++)

a[i][j]=a[i-temp][j]+temp;//左下角 元素和左上角元素的对应关系

//将左下角元素抄到右上角

for(i=1;i<=temp;i++)

for(j=temp+1;j<=n;j++)

a[i][j]=a[i+temp][(j+temp)%n];

//将左上角元素抄到右下角

for(i=temp+1;i<=n;i++)

for(j=temp+1;j<=n;j++)

a[i][j]=a[i-temp][j-temp];

}

for(i=1;i<=n;i++)//显示日程表

for(j=1;j<=n;j++)

{

printf("- ",a[i][j]);

if(j==n)

printf("n");

}

}

void main()

{

int a[N][N];

int k;

printf("输入选手的个数:(注意为2的平方)");

scanf("%d",&k);

GameTable(k,a);

}

2、结果验证

当两个选手,即k=1时

当4个选手时,即k=2

当8个选手,即k=3

当16个选手时,即k=16

时间复杂度分析:

迭代处理的循环体内部3个循环语句,每个循环语句都是一个嵌套的for循环,且它们的执行次数相同,基本语句是最内层循环体的赋值语句,即填写比赛日程表的元素。基本执行语句的执行次数是:

T(n)=

所以时间复杂度为O(4k)

改进的算法:

#include<iostream>

using namespacestd;

const int SIZE =50;

inta[SIZE][SIZE];

void copy(intn);

void tournament(int n);

int odd(int n);//判断奇偶性

void makecopy(int n);//makecopy与copy算法类似,但是区分了n/2为奇数或偶数的情形

void copyodd(intn); //实现n/2为奇数时的复制

voidmain()

{

intn;

inti,j;

cin >>n;

tournament(n);

if(odd(n))// n为奇数和偶数输出情况不同,要分别考虑

{

for(i = 1; i<=n;i++)

{

for(j = 1; j<=n+1;j++)

if(a[i][j] ==n+1)

cout <<"0";

else

cout << a[i][j]<< "";

cout <<endl;

}

}

else

{

for(i = 1; i<=n;i++)

{

for(j = 1; j<=n;j++)

cout << a[i][j]<< "";

cout <<endl;

}

}

}

void copy(intn)

{

int m =n/2;

for(int i = 1; i<=m;i++)

for(int j = 1; j<=m;j++)

{

a[i][j+m] = a[i][j] +m;

a[i+m][j] =a[i][j+m];

a[i+m][j+m] =a[i][j];

}

}

void tournament(intn)

{

if(n ==1)

{

a[1][1] =1;

return;

}

if(odd(n))

{

tournament(n+1);

return;

}

循环赛日程表 循环赛日程表 递归

tournament(n/2);

makecopy(n);

}

int odd(intn)

{

if(n%2==1)

return1;

else return 0;

}

void makecopy(intn) //makecopy与copy算法类似,但是要区分n/2为奇数或偶数的情形

{

if(n/2 > 1 &&odd(n/2))

copyodd(n);

else

copy(n);

}

void copyodd(intn)//实现n/2为奇数时的复制

{

intb[SIZE];

int m =n/2;

for(int i = 1; i<=m;i++)

{

b[i] =m+i;

b[m+i] =b[i];

}

for(i = 1; i<=m;i++)

{

for(int j=1; j<=m+1;j++)

{

if(a[i][j] >m)

{

a[i][j]=b[i];

a[m+i][j] = (b[i] +m)%n;

}

else

a[m+i][j] = a[i][j] +m;

}

for(j = 2; j<=m;j++)

{

a[i][m+j] =b[i+j-1];

a[b[i+j-1]][m+j] =i;

}

}

}

结果验证:

当参赛人数为偶数 8时

当参赛人数为奇数 7时

时间复杂度:O(4k)

  

爱华网本文地址 » http://www.aihuau.com/a/25101015/251462.html

更多阅读

递归法与回溯法一 php递归法

  看过这样一道题,问,“程序结构化设计的三种基础结构,顺序、选择、循环是不是必须的?”当然,你知道这样一个论断,只要有这三种就足够了;但是能不能更少呢?答案是“可以”,原因就是递归能取代循环的作用,例如下面的对一个数组里面元素求和的

背包问题算法 背包问题递归

0/1背包问题 1. 问题描述 给定一个载重量为m,n个物品,其重量为wi,价值为vi,1<=i<=n,要求:把物品装入背包,并使包内物品价值最大 2. 问题分析 在0/1背包问题中,物体或者被装入背包,或者不被装入背包,只有两种选择。 循环变量i,j意义:前i个物品能

学习4--递归函数、级别、结合律、区间套

自同构性结构与级别自同构性结构:走势的最基本结构,在不同级别上(从最低级别到最高级别),其表现的几何形态是相同的。这就是自同构性结构。股票走势,归根结底是不可复制的,但股票走势的绝妙之处就在于,不可复制的走势,却毫无例外地复制着自同

理解递归的工作原理 怎么理解递归

为了理解递归的工作原理,你需要追踪递归调用的执行过程,所以让我们来进行这项工作。追踪一个递归函数的执行过程的关键是理解函数中所声明的变量是如何存储的。当函数被调用时,它的变量的空间是创建于运行时堆栈上的。以前调用的函数的

转载 快速排序法VB和VBA版、递归法版 vba 数组排序函数

先从数据序列中选一个元素,并将序列中所有比该元素小的元素都放到它的右边或左边,再对左右两边分别用同样的方法处之直到每一个待处理的序列的长度为1, 处理结束。在当前无序区R[1..H]中任取一个数据元素作为比较的"基准"(不妨记为X

声明:《循环赛日程表 循环赛日程表 递归》为网友女人高傲点分享!如侵犯到您的合法权益请联系我们删除