問題タブ [non-recursive]

機能があります

非再帰的なスタイルでそれを書き直す方法は？多分、それはいくつかのアルゴリズムの実装ですか？

名前順に並べられた要素ジェネリックの型をバイナリツリーに挿入するためのコードを作成しました。しかし、それが正しいとは思わないでください。

訂正を提案してもらえますか？

重複の可能性:
再帰と反復

再帰関数と非再帰関数の違いは何ですか? 正確にはフィボナッチ。

時間と記憶に関係する答えを探しています。

別のブランチ (完全に異なるフォルダー構造を持つ) からマージした SVN ブランチ (私のブランチ) のコピーをローカルでチェックアウトしました。したがって、基本的には (古いファイルの) 削除と (新しいファイルの) 追加がたくさんあります。

マージをリポジトリ (ブランチ) にコミットしようとすると、Tortoise は次のように言います。

このコミットは再帰的ではなく、コミット用に選択された移動/名前変更されたフォルダーがあります。このような移動/名前変更は、常にリポジトリで再帰的に実行されます。それでもコミットしますか?

このコミットを続行してもよろしいですか? そうでない場合、問題がないようにするにはどうすればよいですか？

また、追加したいくつかのファイルについては、追加後に変更を加えました (これが性質に影響する場合)。

私はstackoverflowを検索してきましたが、私の質問に対する満足のいく答えを見つけることができませんでした.

Miller の論文Recursive Make Considered Harmfulは、コミュニティでよく知られています。基本的に、私は何年もの間、プロジェクトのビルドを管理するために非再帰的な makeを使用してきました。これまでのところ、非再帰的な make に関する私の経験は本当にポジティブなものでした。

他の人に光を当てるために、約 200 万行のコードを含む C++ コード ベースの構築に成功しました。依存関係を正しく管理できました。非再帰的アプローチの優れた点は、並列ビルドを利用できることです。

私は、このレポートのデータが少なくとも 5 つの大規模プロジェクトと一致していることを証明しました。しかし、私は非再帰的な make の makefile を手動で作成/移植してきました。

ご想像のとおり、大規模なプロジェクトの場合、これには多くの作業が伴います。さらに、主要な課題は、新しいチーム メンバーが既存のメイクファイルを理解/変更/デバッグするのが非常に難しいことです。

だから私の質問はこれです: コミュニティの誰かが非再帰的なメイクを行うことができるツール/スクリプトを知っていますが、抽象化のより高いレベルでメイクファイルを管理しますか? 単純な入力仕様から最終的な非再帰的なメイクファイルを生成するためのスクリプトまたはツールを誰かが作成したかどうかを理解したいと思います。

困惑している練習問題があります-再帰を使用せずに二分木の葉ノードの数を取得することです。ノードをスタックに渡すなどのアイデアを見てきましたが、複数のブランチがある場合にそれを行う方法がわかりません。誰でもポインタを提供できますか?

最近、より複雑なアルゴリズム、正確には Tarjan のアルゴリズムの一部として非再帰的 DFS を実装する必要がありました。再帰的な実装は非常に洗練されていますが、大きなグラフには適していません。反復バージョンを実装したとき、それが最終的にいかに洗練されていないものになってしまったかにショックを受け、何か間違ったことをしたのではないかと思いました。

反復 DFS には 2 つの基本的なアプローチがあります。まず、ノードのすべての子を一度にスタックにプッシュできます (はるかに一般的なようです)。または、1 つだけプッシュすることもできます。誰もがそうしているように見えるので、最初のものに焦点を当てます。

このアルゴリズムにはさまざまな問題がありましたが、最終的には、効率的に行うには、1 つではなく 2 つではなく 3 つのブール値フラグが必要であることに気付きました (必ずしも 3 つの明示的なブール変数が必要であるとは限りません。情報を間接的に保存することもできます)。通常は整数である変数の特別な値を使用しますが、何らかの方法でこれら 3 つの情報にアクセスする必要があります.3 つのフラグは: 1) 訪問済みです。これは、子が非常に冗長にスタックにプッシュされるのを防ぐためでした。2) 完了。同一ノードの重複処理を防止する。3) 昇順/降順。子がすでにスタックにプッシュされているかどうかを示します。擬似コードは次のようになります。

いくつかのメモ: 1) 技術的に昇順/降順は必要ありません。子がすべて完了しているかどうかを確認するだけでよいからです。しかし、密なグラフではかなり非効率的です。

2) 主なキッカー: 訪問/完了は必要ないように見えるかもしれません。これが（私が思うに）あなたがそれを必要とする理由です。スタック上でそれらを訪問するまで、訪問済みのものをマークすることはできません。もしそうなら、物事を間違った順序で処理することができます。たとえば、A が B と C にリンクされ、B が D にリンクされ、D が C にリンクされているとします。次に、A から B と C をスタックにプッシュします。B から D をスタックにプッシュします。スタックにプッシュするときに訪問したものをマークしている場合は、ここで C をスタックにプッシュしません。しかし、これは間違っています。このグラフでは、A からではなく、D から C にアクセスする必要があります (A が C の前に B にアクセスすると仮定)。したがって、それらを処理するまで、訪問したものをマークしません。ただし、スタックに C が 2 回あります。したがって、完全に完了したことを示す別のフラグが必要なので、C を 2 回処理する必要はありません。

このすべてを回避して、巻き戻しと巻き戻しの両方のアクションをサポートする完全に正しい非再帰的 DFS を作成する方法がわかりません。しかし、本能的にそれは不器用に感じます。より良い方法はありますか？私がオンラインで調べたほとんどすべての場所で、非再帰的 DFS を実際に実装する方法について、実際に行うことができ、非常に基本的なアルゴリズムを提供していると述べています。アルゴリズムが正しい場合 (同じノードへの複数のパスを適切にサポートするという点で) はまれですが、ワインディングとアンワインドの両方で処理を適切にサポートすることはめったにありません。

バイナリツリー内の特定のノードの祖先（親の親）を出力する非再帰的なプログラムを作成する必要があります。どのロジックを使用する必要がありますか？

行列[n,n]が与えられた場合、[0,0]から[n,n]に非再帰的に到達できる方法の数を調べたいと思います。

私のアプローチは

1. これまでに移動した行、列、パスを格納するスタクト ​​ノードを作成する
2. ノードをキューに追加する
3. 空でなくなるまでキューを繰り返します。行をインクリメントし、列をインクリメントします。キューに追加する
4. 行=n、列=nの場合はパスを出力します

質問

1. 行、列、パスを保存する別の方法はありますか
2. n が非常に大きい場合、キューにノードを格納することが問題になる可能性があります。どうすればこれを回避できますか?

私は再帰的な解決策を探していません。多くのインタビュー フォーラムでこのような質問を目にするので、これが正しいアプローチかどうかを知りたいと思います。

以下はノードの構造と機能です

交互に増加する順序でスタックを逆にする最もエレガントな方法 (少ないコード?) は何ですか? (非再帰的)

元。