广工2015数据结构Anyview答案

### 广工2015数据结构Anyview答案解析 #### 题目解析与解答概览 根据提供的文件信息，下面将详细解析文件中提到的几个编程问题及其解决方案。 ### 1. 三整数非递增排序 **题目描述**：编写一个算法，如果三个整数 `a`、`b` 和 `c` 的值不是依次非递增的，则通过交换，令其为非递增。 **代码实现**： ```cpp void swap(int *m, int *n); void Descend(int &a, int &b, int &c) { /* 通过交换，令a >= b >= c */ if (a <= b) swap(&a, &b); if (a <= c) swap(&a, &c); if (b <= c) swap(&b, &c); } void swap(int *m, int *n) { int temp; temp = *m; *m = *n; *n = temp; } ``` **分析**：这段代码实现了一个简单的排序算法，确保三个整数按照非递增顺序排列。首先定义了一个`swap`函数用于交换两个整数的值。然后定义了`Descend`函数来实现非递增排序逻辑。该函数首先检查三个整数是否满足非递增条件，如果不满足，则通过调用`swap`函数进行相应的交换操作。 ### 2. 一元多项式求值 **题目描述**：编写算法求一元多项式 \( P(x) = a_0 + a_1x + a_2x^2 + \cdots + a_nx^n \) 的值 \( P(x_0) \)，并确定算法中每一语句的执行次数和整个算法的时间复杂度。 **代码实现**： ```cpp float Polynomial(int n, int a[], float x) { /* 求一元多项式的值P(x)。 */ /* 数组a的元素a[i]为i次项的系数，i=0, ..., n */ int i; float sum = 1.0 * a[0], temp = 1.0; if (n > 0) { for (i = 1; i <= n; i++) { temp *= x; sum += 1.0 * a[i] * temp; } } return sum; } ``` **分析**：这个算法实现了多项式的求值功能。它首先初始化变量`sum`为多项式的常数项，接着通过循环逐项累加多项式的各项值。时间复杂度为\(O(n)\)，其中\(n\)为多项式的最高次数。 ### 3. k阶裴波那契序列求值 **题目描述**：已知k阶裴波那契序列的定义为 \( f(0) = 0, f(1) = 0, \ldots, f(k-2) = 0, f(k-1) = 1 \)；\( f(n) = f(n-1) + f(n-2) + \cdots + f(n-k) \)，\( n = k, k+1, \ldots \)。编写求k阶裴波那契序列的第m项值的函数算法，k和m均以值调用的形式在函数参数表中出现。 **代码实现**： ```cpp Status Fibonacci(int k, int m, int &f) { /* 求k阶斐波那契序列的第m项的值f */ int i, j, sum, s[100]; if (m < 0 || k < 2) return ERROR; if (m < k - 1) f = 0; else if (m == k - 1) f = 1; else { for (i = 0; i < k - 1; i++) s[i] = 0; s[i] = 1; for (i = k; i <= m; i++) { sum = 0; for (j = i - k; j <= i; j++) sum += s[j]; s[i] = sum; } f = s[m]; } return OK; } ``` **分析**：这个函数通过动态规划的方式求解k阶裴波那契序列的第m项值。它首先初始化前k-1项为0，第k项为1。然后利用一个辅助数组`s`来存储中间结果，最终得到第m项的值。时间复杂度为\(O(m)\)。 ### 4. 特殊序列求值 **题目描述**：编写算法，计算 \( i! \times 2^i \) 的值并存入数组 `a[0..n-1]` 的第 \( i-1 \) 个分量中 (\( i = 1, 2, \ldots, n \))。假设计算机中允许的整数最大值为 `MAXINT`，则当对某个 \( k \) (\( 1 \leq k \leq n \)) 使得 \( k! \times 2^k \) 超过 `MAXINT` 时，应按出错处理。注意选择你认为较好的出错处理方法。 **代码实现**： ```cpp Status Series(int a[], int n) { /* 求i! * 2^i序列的值并依次存入长度为n的数组a； */ /* 若所有值均不超过MAXINT，则返回OK，否则OVERFLOW */ int j, index = 1, stage = 1; for (j = 1; j <= n; j++) { stage *= j; index *= 2; a[j - 1] = stage * index; if (a[j - 1] > MAXINT) return OVERFLOW; } return OK; } ``` **分析**：此算法计算特殊序列的值，并将其存储在数组中。它使用两个辅助变量`stage`和`index`分别计算阶乘部分和指数部分。在每次循环中，计算当前项的值，并检查是否超过了`MAXINT`，如果超过则返回`OVERFLOW`，否则继续计算直至完成。时间复杂度为\(O(n)\)。 ### 5. 田径对抗赛成绩统计 **题目描述**：假设有A、B、C、D、E五个高等院校进行田径对抗赛，各院校的单项成绩均已存入计算机并构成一张表，表中每一行的形式为：项目名称 性别 校名 成绩 得分。编写算法，处理上述表格，以统计各院校的男、女总分和团体总分，并输出。 **代码实现**： ```cpp void Scores(ResultType *result, ScoreType *score) { /* 求各校的男、女总分和团体总分,并依次存入数组score */ /* 假设比赛结果已经储存在result[]数组中, */ /* 并以特殊记录{"", male, "", "", 0}（域score=0） */ /* 表示结束 */ int i, j; for (i = 0; result[i].schoolname != ''; i++) { for (j = 0; j < 5; j++) { if (result[i].schoolname == 'A' + j) { if (result[i].gender == male) score[j].malescore += result[i].score; else score[j].femalescore += result[i].score; score[j].totalscore = score[j].malescore + score[j].femalescore; break; } } } } ``` **分析**：这个算法通过遍历比赛结果记录，根据学校名称和性别分类统计各校的男、女总分以及团体总分。时间复杂度主要取决于比赛结果记录的数量，即\(O(N)\)，其中\(N\)为记录数量。 以上是题目中的主要知识点及解析。这些算法涵盖了基本的数据结构操作和常见问题解决方法，对于理解数据结构和算法设计具有重要意义。