2

次の質問は、GRE コンピューター サイエンス テスト 2001で出題されました。

Q-67: 次のC コードを考えてください。 

int f(int x) {
    if(x<1) {
        return 1;
    } else {
        return f(x-1)+g(x);
    }
}

int g(int x) {
    if(x<2) {
        return 1;
    } else {
        return f(x-1)+g(x/2);
    }   
}


次のうち、x の関数としての f(x) の成長を最もよく表しているのはどれですか?

(A)対数 (B)線形 (C) 2 次 (D) 3 次 (E)指数

ちなみに、正解は(E) Exponential (解答解説に記載) です。しかし、それを解決するための正確な方法はわかりません。

上記の再帰関係を解決できる人はいますか? 別のアプローチはありますか？

あなたの意見を共有してください。

4

1 に答える 1

2

f(x) >= f(x-1)+f(x-1) for x>1これは のように簡略化できると思います g(x) = f(x-1)+g(x/2) >= f(x-1) for x>1。最初の不等式はちょうどf(x) >= 2*f(x-1)であり、ここから簡単に導き出すことができます(少なくともf(x) >= 2^x*f(1)の値は、 1 ずつ大きくなるたびに 2 倍になります)。fx

于 2013-04-11T14:03:48.680 に答える