跳到主要内容

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

标签：

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 ] に整数 mm (1<m≤401 < m \le 40) を埋めて main 関数を実行したときに 23 行目の printf 文を実行する時に cntr が保持する値を mm の式で表せ。

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

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

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

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

考点​

  • 斐波那契递归：追踪递归调用树、返回值及调用计数。
  • 记忆化：缓存已计算子问题，避免指数数量的重复计算。
  • 动态规划：用两个连续状态迭代生成下一项，将空间压缩为常数级。
  • 复杂度比较：比较朴素递归、记忆化递归和迭代实现的时间与空间开销。
  • 数组初始化边界：根据目标下标限定必要的缓存初始化范围。

Kai​

Note: The order of the evaluation of the arguments to any function in C is not defined by C standard (undefined behaviour), a compiler may choose to evaluate either from left-to-right or right-to-left, which means that the program provided by ソースコード1 and ソースコード2 is somehow "wrong".

In the following Kais, we assume that arguments of printf are evaluated from left-to-right.

(1)​

13, 41

(2)​

55, 11

(3)​

cntr = m + 1

(4)​

再帰的にフィボナッチ数を計算する場合、同じフィボナッチ数を何度も計算する必要があります。 たとえば、fib1(5) を計算する際には、fib1(4) と fib1(3) を計算し、さらにfib1(4) を計算するために fib1(3) と fib1(2) を計算します。 メモ化を用いる場合、一度計算したフィボナッチ数を保存しておき、再度同じ値を計算する必要がなくなります。

In the recursive calculation, a large number of overlapping subproblems are computed multiple times, resulting in an exponential time complexity of O(2n)O(2^n). In contrast, memoization eliminates the redundant calculations by storing the results of subproblems, reducing the time complexity to O(n)O(n).

(5)​

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

(6)​

  • [ 空欄 (ア) ]: p+q
  • [ 空欄 (イ) ]: q
  • [ 空欄 (ウ) ]: tmp
本页目录