名古屋大学 情報学研究科 情報システム学専攻 2023年8月実施 専門 問6

标签：

• Nagoya-University
• Fibonacci-Memoization

Author

祭音Myyura

Description

出典：名古屋大学公表問題。

ソースコード 1, 2 はどちらもフィボナッチ数を計算するC言語プログラムである。 ソースコード 1 の fib1 はフィボナッチ数を再帰的に計算し、ソースコード 2 の fib2 にはメモ化が導入されている。 本問では 32 ビットの符号付き整数でオーバーフローが発生しない範囲として、40 番目までのフィボナッチ数のみを扱うこととする。 以下の全ての問いに答えよ。

(1) ソースコード 1 の [ 空欄 A ] に 7 を埋めて main 関数を実行したときに標準出力に印字される実行結果を書け。

(2) ソースコード 2 の [ 空欄 B ] に 10 を埋めて main 関数を実行したときに標準出力に印字される実行結果を書け。

(3) ソースコード 2 の [ 空欄 B ] に整数 $m$ ($1 < m \le 40$) を埋めて main 関数を実行したときに 44 行目の printf 文を実行する時に cntr が保持する値を $m$ の式で表せ。

(4) ソースコード 1 の [ 空欄 A ] とソースコード 2 の [ 空欄 B ] に同じ整数を埋めたとき、一般にソースコード 2 の main 関数の実行はソースコード 1 の main 関数の実行よりも効率的である。その理由を150字以内（英語の場合、100 words以内）で説明せよ。

(5) ソースコード 2 の 43 行目の配列 memo の初期化は 44 行目の fib2(n) の計算において参照されることがない要素も含めて初期化している。[ 空欄 B ] に与えた整数 $m$ について適切にフィボナッチ数を計算するために必要な要素のみを -1 で初期化するように 43 行目を変更せよ。解答では 43 行目に記述するコードを記すこと。

ソースコード１: フィボナッチ数を再帰的に計算するＣ言語プログラム

#include <stdio.h>

int cntr=0;

int fib1(int n) {
    int z;
    cntr++;
    if (n<=0)
        z=0;
    else if (n==1)
        z=1;
    else
        z=fib1(n-1)+fib1(n-2);
    return z;
}

int main() {
    int n=[ 空欄 A ];
    printf("%d,%d",fib1(n),cntr);
    return 0;
}

ソースコード２: メモ化を用いてフィボナッチ数を計算するＣ言語プログラム

#include <stdio.h>

int cntr=0;
int memo[41];

int fib2(int n) {
    int z;
    if(memo[n]>=0) return memo[n];
    cntr++;
    if(n<=0)
        z=0;
    else if(n==1)
        z=1;
    else
        z=fib2(n-1)+fib2(n-2);
    memo[n]=z;
    return z;
}

int main() {
    int i, n=[ 空欄 B ];
    for(i=0; i<41; i++) memo[i]=-1;
    printf("%d,%d",fib2(n),cntr);
    return 0;
}

(6) 関数呼び出しを用いずにフィボナッチ数を計算する関数 fib3 を, 下記の関数定義の中の [ 空欄 (ア) ], [ 空欄 (イ) ], [ 空欄 (ウ) ] を埋めて完成せよ. ただし, 任意の整数 $m\ (0 \le m \le 40)$ について, fib3(m) の返り値が fib1(m) の帰り値と一致すること。

int fib3(int n) {
    int i, p=0, q=1, tmp;
    for(i=0; i<n; i++) {
        tmp=[ 空欄 (ア) ];
        p=[ 空欄 (イ) ];
        q=[ 空欄 (ウ) ];
    }
    return p;
}

题目描述

源代码 1 和 2 都计算斐波那契数。fib1 采用直接递归，fib2 使用数组 memo 进行记忆化；全局变量 cntr 记录实际展开计算的次数。仅考虑 32 位有符号整数不溢出的前 40 项。完整程序见上文。

回答下列问题。

1. 在源代码 1 的空格 A 中填入 7，写出执行 main 的标准输出。
2. 在源代码 2 的空格 B 中填入 10，写出执行 main 的标准输出。
3. 在 B 中填入整数 $m$（$1<m\le40$），用 $m$ 表示执行 printf 时 cntr 的值。
4. 当 A、B 填入同一整数时，通常源代码 2 比源代码 1 高效。用不超过 150 个日文字符或 100 个英文单词说明原因。
5. 源代码 2 当前把 memo[0] 至 memo[40] 全部初始化为 -1。改写第 22 行，只初始化计算 fib2(m) 确实可能访问的元素。
6. 填写循环函数 fib3 中的空格 (ア)、(イ)、(ウ)，使任意 $0\le m\le40$ 都满足 fib3(m) == fib1(m)，且不使用函数调用完成迭代计算。

Kai

(1)

C11 では、fib1(n) の実行と、別の実引数である cntr の読取りの先後は未規定である。従って、出力は 13,41 または 13,0 となる。fib1(7) の終了後には cntr == 41 であり、cntr をその後に読み取る場合の出力は次のとおりである。

13,41

呼出し回数 $C_n$ は $C_0=C_1=1$、$C_n=1+C_{n-1}+C_{n-2}$ を満たすので、$C_7=41$ である。

(2)

同じ理由で、出力は 55,11 または 55,0 となる。fib2(10) の終了後に cntr を読み取る場合は、次の出力になる。

55,11

初めて計算する引数は $0,1,\ldots,10$ の 11 個で、それぞれ一度だけ cntr++ を実行する。

(3)

printf の関数本体が実行される時点では、実引数中の fib2(m) は計算済みであり、変数そのものの値は

$$\mathrm{cntr}=m+1$$

である。ただし、printf に渡される第 3 引数は、先に読み取られた 0 である可能性もある。関数本体の実行と呼出し側での値の読取りは、不定順序で順序付けられる（indeterminately sequenced）。C11 草案 §6.5.2.2 第 10 段落

(4)

単純再帰では同じ引数の値を繰り返し計算する。メモ化では計算結果を保存して再利用するため、各引数を一度だけ計算すればよく、計算量が指数時間から線形時間に減る。

(5)

$m>1$ では memo[0] から memo[n] までを初期化する。

for(i=0; i<=n; i++) memo[i]=-1;

$m=0,1$ も含め、実際に参照する要素だけを初期化するなら、次の 1 行でよい。

for(i=(n<=1 ? n : 0); i<=n; i++) memo[i]=-1;

(6)

• [ 空欄 (ア) ]: p+q
• [ 空欄 (イ) ]: q
• [ 空欄 (ウ) ]: tmp

$i$ 回の反復後に $p=F_i$、$q=F_{i+1}$ が成り立つので、終了時の返り値は $F_n$ となる。