0

やあみんな。hw の割り当てを理解するのに助けが必要です。私はC ++で始めていますが、あまり知りません。スタックとフィボナッチ数列の基本は知っています。ただし、与えられた問題を正確に理解していないため、問題を解決するためのコードは必要ありませんが、いくつかの手順を明確にするのに役立ちます。ハードウェアは次のとおりです。

「このプロジェクトを完了すると、再帰の使用と C++ での ADT の作成に慣れることができます。

少なくとも 256 要素の最大容量を持つ整数スタック ADT を作成します (レクチャー ノートで指定された IntStack ADT を変更できます)。また、C++ ostream (cout など) に出力される場合は、その内容 (左から右、スタックの一番上が右側) が出力されるように、必要なものをすべて追加します。このスタックは、ゼロより大きい意味のある値のみを保持するように設計する必要があります。ゼロ以下の値は「?」として出力する必要があります。

クラスで説明したフィボナッチ数列の再帰的な実装を書きます。また、呼び出し間で持続するスタック ADT のインスタンスを作成し (ローカル変数にすることはできません)、各ステップで、その段階で値が決定されるまで意味のない値をプッシュし、ポップオフします。 、決定された値をプッシュし、戻る前にスタック全体を出力します。

プログラムは、フィボナッチ数列の位置 N を決定するように要求し、関数呼び出しの結果を出力する必要があります。出力例 (再帰関数からの出力を含む) は次のとおりです。

決定するフィボナッチ数列の位置を入力してください: 5

?-?-?-1
?-?-?-1
?-?-2
?-?-1
?-3
?-?-1
?-?-1
?-2
5

Fibonacci(5) = 5

ここでの出力は正確には何ですか？5番目の位置を計算するときにスタックを出力していますか? また、フィボナッチを C++ のスタックに実装する方法についてのアイデアはありますか? これらの値は、配列、リスト、または問題ではないに格納する必要がありますか? 私は初心者なので、どんな助けでも大歓迎です。ありがとう

4

3 に答える 3

1

はい、これは 5 番目のフィボナッチ数 (たまたま 5 です。これは少し紛らわしいです) を計算していますが、次のフィボナッチ コードを想定して、fibonacci(5) を呼び出したときに計算したものを見てください。

int fibonacci(int n) {
    if (n <= 1) return n;
    else if (n == 2) return 1;
    else return fibonacci(n-1) + fibonacci(n-2);
}

fibonacci(5) を計算するための関数呼び出しは次のとおりです。

f(5)
 -> f(4)
     -> f(3)
         -> f(2)
         -> f(1)
     -> f(2)
 ->f(3)
    -> f(2)
    -> f(1)

これを二分木として見ると、彼らがあなたに与えた出力は、? はそのスタックの深さであり、数値はそのノードの値です。

したがって、関数が行うことを実行するだけで、戻り値が表示されるたびに、戻り値を記述します(その前に ? を付けます)。

  • 返される最初の関数は、深さ 4 の最初の f(2) です: print ?-?-?-1
  • 2 番目の戻り値は、その下の f(1) です: print ?-?-?-1
  • 3 番目の戻り値は、深さ 3 と値 f(2)+f(1)=2 を持つ f(2) と f(1) の親です: print ?-?-2
  • 深さ 0 で値 5 の f(5) を返すまで、これを繰り返します。
于 2011-02-16T15:27:49.457 に答える
0

スタックの印刷はそのままにして、スタックを使用してマーカー (「意味のない」数値) と結果を格納する際の紛らわしい部分に対処します。部分的な擬似コードは次のとおりです。

procedure fib(n)
    push a marker (say a zero) to a global stack
    if n is 1 or 2 then
        result = you_know_what
    else
        calculate fib(n-1)
        pop the stack ==> fib_n_minus_1
        calculate fib(n-2)
        pop the stack ==> fib_n_minus_2
        result = fib_n_minus_1 + fib_n_minus_2
    endif

    pop the marker off the stack and discard
    push the result into the stack
    print the stack
end fib

ここで重要なのは、fib() が値を返さないことです。代わりに、戻り値をグローバル スタックにプッシュします。

于 2011-02-16T16:01:35.057 に答える
0

問題全体を、自分で解決/実装できる小さな部分に分割します。この場合、次の 2 つの主要部分があります。

  1. スタック -- 質問に記載されている詳細に従って、標準のスタック クラスを実装します。それらをすべてポイント形式でリストすると役立つ場合があります。
  2. フィボナッチ -- スタック クラスを使用して、フィボナッチ数列を再帰的に生成します。スタックは、この演習のストレージ メカニズムです。

出力例?-?-?-1は、次のスタック操作として理解できます。

push 0
push 0
push 0
push 1
print
于 2011-02-16T15:36:57.337 に答える