网站建设的发展趋势,建设银行官方网站面试详细信息,phpcms做视频网站首页,现在有哪些网站兼职可以做实验一#xff1a;分治与递归
【实验目的】
深入理解分治法的算法思想#xff0c;应用分治法解决实际的算法问题。
【实验性质】
验证性实验#xff08;学时数#xff1a;2H#xff09;
【实验内容与要求】
1、设有n2k个运动员要进行网球循环赛。现要设计一个满足以…实验一分治与递归
【实验目的】
深入理解分治法的算法思想应用分治法解决实际的算法问题。
【实验性质】
验证性实验学时数2H
【实验内容与要求】
1、设有n2k个运动员要进行网球循环赛。现要设计一个满足以下要求的比赛日程表⑴每个选手必须与其他n-1个选手各赛一次⑵每个选手一天只能赛一次⑶循环赛一共进行n-1天。按此要求可将比赛日程表设计成有n行和n列的一个表。表中第一列是选手编号表中第i行和第j列j1处填入第i个选手在第j天所遇到的选手。例如8个选手的日程表安排如右图所示。
要求请设计算法并采用C或C语言编写程序实现上述功能调试运行并对算法的时间复杂度进行分析。
【算法思想及处理过程】 首先通过输入参赛人数n判断n是否合法是否为2的幂次方如果不合法则输出错误信息。 然后输入第一个选手的编号k。 调用roundrob函数传入参数k和n。roundrob函数的作用是生成对阵表。 首先判断n是否为2如果是则直接生成对阵表。对阵表是一个二维数组a每个元素表示某个选手与另一个选手的对阵情况。 如果n不是2递归调用roundrob函数将n除以2传入并分成两个子问题分别解决。 递归结束后对阵表的前一半行和后一半行进行交换生成完整的对阵表。 最后遍历对阵表并输出每个元素的值。 在主函数中先判断n是否合法如果合法则调用roundrob函数生成对阵表并输出。 如果n不合法则直接返回。 【程序代码】 #include stdio.h #includeiostream using namespace std; int a[100][100]{}; void roundrob(int k, int n) { if (n 2) { a[k][0] k 1; a[k][1] k 2; a[k 1][0] k 2; a[k 1][1] k 1; } else { roundrob(k,n / 2); roundrob(k n / 2,n / 2); } for (int i k; i k n / 2; i) { for (int j n / 2; j n; j) { a[i][j] a[i n / 2][j - n / 2]; } } for (int i k n / 2; i k n; i) { for (int j n / 2; j n; j) { a[i][j] a[i - n / 2][j - n / 2]; } } } int determine(int n) { if (n % 2 0) { if (n / 2 1) return 1; determine(n / 2); } else { cout 输入人数不合法 endl; return 0; } } int main() { int n; int k; cout 请输入参赛人数 endl; cin n; if (determine(n) 1) { cout 请输入第一个选手编号 endl; cin k; k k - 1; roundrob(k, n); int i 0, j 0; for (i 0; i n; i) { for (j 0; j n; j) { cout a[i][j] ; } cout endl; } } if (determine(n) 0) { return 0; } } 【运行结果】 程序运行结果截图。 【算法分析】 代码的时间复杂度为O(n^2)其中n为参赛人数。代码中使用递归的方式生成了一个二维数组a数组的大小为n×n。在生成数组a的过程中有两个嵌套的循环每个循环的次数都是n/2因此循环次数总共为n/2 × n/2 n^2/4所以时间复杂度为O(n^2)。另外代码中还有一个determine函数该函数的时间复杂度为O(logn)因为每次递归都将n除以2直到n为偶数。
