题目

26.[填空题]在下面的程序段[1]中，对下划线语句的频度为______。for (int i = 1; i <= n; i++)for (int j = 1; j <= n; j++) {c[i][j] = 0.0;for (int k = 1; k <= n;k++)underline(c[i][j] = c[i][j] + a[i][k] * b[k][j];)

26.[填空题] 在下面的程序段[1]中，对下划线语句的频度为______。 for (int i = 1; i <= n; i++) for (int j = 1; j <= n; j++) { c[i][j] = 0.0; for (int k = 1; k <= n; k++) $\underline{c[i][j] = c[i][j] + a[i][k] * b[k][j];}$

题目解答

答案

要解决这个问题，我们需要分析给定的嵌套循环结构，并计算下划线语句的执行次数。

程序段分析

for (int i = 1; i &lt;= n; i++) {
    for (int j = 1; j &lt;= n; j++) {
        c[i][j] = 0.0;
        for (int k = 1; k &lt;= n; k++) {
            c[i][j] = c[i][j] + a[i][k] * b[k][j];
        }
    }
}

逐层分析

  1. 外层循环 i：

    • 循环变量 i 从 1 到 n，共执行 n 次。

  2. 中层循环 j：

    • 对于每个 i，循环变量 j 从 1 到 n，共执行 n 次。
    • 因此，i 和 j 的组合共执行 n * n 次。

  3. 内层循环 k：

    • 对于每个 i 和 j 的组合，循环变量 k 从 1 到 n，共执行 n 次。
    • 因此，i、j 和 k 的组合共执行 n * n * n 次。

下划线语句的执行次数

下划线语句 c[i][j] = c[i][j] + a[i][k] * b[k][j]; 位于内层循环 k 中，因此它的执行次数等于 i、j 和 k 的组合次数，即 n * n * n。

最终答案

下划线语句的频度为 $n^3$。

解析

考查要点：本题主要考查嵌套循环的时间复杂度分析，需要根据循环结构确定特定语句的执行次数。

解题核心思路：

  1. 逐层分析循环次数：从外层循环到内层循环，分别计算每个循环变量的取值范围。
  2. 乘积法则：若多个循环嵌套，总次数为各层循环次数的乘积。
  3. 定位目标语句位置：确定目标语句所在的最内层循环，其执行次数等于所有外层循环次数的乘积。

破题关键点：

  • 三重循环结构：外层i循环、中层j循环、内层k循环。
  • 下划线语句位于最内层循环，因此其执行次数为i、j、k循环次数的乘积。

循环结构分析

  1. 外层循环（i）：
    i从1到n，共执行n次。
  2. 中层循环（j）：
    对于每个i，j从1到n，共执行n次。
    i和j的组合次数：n × n = n²次。
  3. 内层循环（k）：
    对于每个i和j的组合，k从1到n，共执行n次。
    i、j、k的组合次数：n × n × n = n³次。

下划线语句的频度

下划线语句c[i][j] = c[i][j] + a[i][k] * b[k][j];位于最内层循环k中，因此其执行次数等于所有循环变量组合的总次数，即：
$\text{频度} = n^3$