0314-2019 名情复 编程 P420

编程语言基础 C语言 递归算法 数组操作

C言語プログラミングに関する以下の問に答えよ。ただし，\は¥と同じである。

[1] 次のプログラムの出力結果を示せ。

#include <stdio.h>
int main() {
    int a = 0X0f0f;
    printf("%d %x %x %x\n", a, a%2, a&0X2468, a<<2);
    return 0;
}

[2] $n$ 番目のフィボナッチ数を $a_n$ で表すと，$a_n$ は $a_0=0,a_1=1,n\ge 2$ では
$a_n=a_{n-2}+a_{n-1}$ で定義される。以下は $n$ を標準入力から受け取り，$a_n$ を計算するプログラムである。

#include <stdio.h>
int n;
 
int fib(int k) {
    if(k==0||k== _____(1)_____ ) return _____(2)_____ ;
    else return _____(3)_____ ;
}
 
int fib2(int a1, int a2, int k) {
    if(k== _____(4)_____ ) return a1;
    else return _____(5)_____ ;
}
 
int main() {
    scanf("%d", &n);
    printf("%d %d\n",n,fib(n));
    printf("%d %d\n",n,fib2(0,1,0));
    return 0;
}

1. $a_n$ を再帰法で計算する関数 fib の空欄を適切に埋めよ。
2. fib2 は，fib よりも少ない計算量で $a_n$ を計算する関数である。関数 fib2 の空欄を適切に埋めよ。
3. $n=5$ としてこのプログラムを実行したとき，関数 fib と fib2 が呼び出される回数をそれぞれ答えよ。

[3] 以下の成績表を処理するプログラムを作成する。空欄を適切に埋めよ。また，プログラムの実行結果を示せ。

学籍番号	国語	数学
1	60	100
2	75	40
3	70	70
4	10	0
5	80	70

#include <stdio.h>
int sum(int x[][5], int sid) {
    int i, s= _____(1)_____ ;
    for(i=0; i<2; i++) s += x[i][_____(2)_____];
    return s;
}
 
float mean(int x[][5], int tid) {
    int j; float m=0.0;
    for(j=0; j<_____(3)_____; j++) m +=_____(4)_____;
    return m/5.0;
}
 
int count(int x[][5], int tid) {
    int j, n=0;
    float m;
    m=mean(_____(5)_____, tid);
    for(j=0; j<5; j++) {_____(6)_____}
    return n;
}
 
int main() {
    int scores[][5]=_____(7)_____;
    printf("学籍番号2の国語は%d点です\n", scores[___(8)___][___(9)___]);
    printf("学籍番号3の合計点は%d点です\n", sum(scores, 3));
    printf("国語の平均点は%.1f点です\n", mean(scores, 0));
    printf("数学の点数が平均点以上は%d名です\n", count(scores,_____(10)_____));
    return 0;
}

---

解答：

[1]

$$\boxed{\text{3855 1 408 3c3c}}$$

[2]
1)

$$\boxed{\begin{array}{ll}(1)& \text{1}\\ (2)& \text{k}\\ (3)& \text{fib(k-1) + fib(k-2)}\end{array}}$$ $$\boxed{\begin{array}{ll}(4)& \text{n}\\ (5)& \text{fib2(a2, a1 + a2, k + 1)}\end{array}}$$

fib(5) を呼び出すと，
fib(5) $\to$ fib(4), fib(3)
fib(4) $\to$ fib(3), fib(2)
fib(3) $\to$ fib(2), fib(1)
fib(2) $\to$ fib(1), fib(0)
となり，fib の呼び出し回数は $1+2+3+5+4=15$ 回である。

fib2 の初期呼び出しは fib2(0, 1, 0) であり，$k$ が $0$ から $5$ になるまで再帰的に呼び出されるため，呼び出し回数は $6$ 回である。

$$\boxed{\begin{array}{ll}\text{fib：}& 15\text{回}\\ \text{fib2：}& 6\text{回}\end{array}}$$

[3]

$$\boxed{\begin{array}{ll}(1)& \text{0}\\ (2)& \text{sid - 1}\\ (3)& \text{5}\\ (4)& \text{x[tid][j]}\\ (5)& \text{x}\\ (6)& \text{if(x[tid][j] >= m) n++;}\\ (7)& \text{{{60, 75, 70, 10, 80}, {100, 40, 70, 0, 70}}}\\ (8)& \text{0}\\ (9)& \text{1}\\ (10)& \text{1}\end{array}}$$

実行結果：

$$\boxed{\begin{array}{l}\text{学籍番号2の国語は75点です}\\ \text{学籍番号3の合計点は140点です}\\ \text{国語の平均点は59.0点です}\\ \text{数学の点数が平均点以上は3名です}\end{array}}$$

---

本题考察了C语言中的基础位运算、递归算法以及二维数组的应用。在第一部分，需要将十六进制数转换为十进制输出，并理解模运算、按位与运算以及左移运算的规则。第二部分要求实现计算斐波那契数列的递归函数，并且给出了尾递归的优化形式，要求分析两种算法的时间复杂度（通过函数调用次数体现）。普通的递归会产生大量的重复计算，而尾递归通过参数传递累加结果，可以将时间复杂度从指数级降低到线性级。第三部分结合了一个成绩表的实际场景，考察二维数组的初始化、元素的访问以及基于数组实现的求和、求平均值和条件统计等基本函数编写。在多维数组的初始化中，需要注意行和列的对应关系，并在函数调用中正确传递数组指针及相关索引参数。