問題タブ [ackermann]

これが何であるかについては、おそらく多くの説明は必要ありません。私の本当の問題は、プログラムの終了です。トレースされた戻り値と、値をステップ実行するためにメイン関数で使用しているネストされた for ループを出力しました。これが発生する理由はわかりませんが、ループを最後に通過してから実際に終了するまでに、プログラムがさらに約 10 分かかります。ループ インデックスは (事前チェックのために) 増加していますが、私の Ackermann 関数は明らかに余分な反復を実行していません (いずれにせよ実行したいわけではありません)。一方、唯一の論理的な説明は、ループが壊れていないということですが、もしそうなら、私のアッカーマン関数は新しい b 値を返すはずです。したがって、これについて私が考えることができる唯一の他の原因は、私のデータ構造をクリアしてメモリヒープをフラッシュするのに長いガベージコレクションを取ります。慣れていない人のために説明すると、ここでの考え方は、伝統的に非常に面倒な再帰関数として提示されていたものを反復関数として実装することです。再帰的に:

正の整数 m と n が与えられた場合: m = 0 の場合、n + 1 を返します。それ以外の場合、n = 0 の場合、Ackermann(m - 1, 1) を返します。それ以外の場合は Ackermann(m - 1, Ackermann(m, n - 1)) を返します。したがって、スタックを使用して再帰関数呼び出しをエミュレートし、ヒープからメモリを使用でき、実行時間を制限する呼び出しスタックのサイズに依存しないようにするというアイデアを繰り返します。計算が終了してから、プログラムがユーザーが正常に終了するポイントに到達するまでの間に、これらの長い遅延を引き起こしているフローの何かを見落としているのではないかと心配しています。

これが私のコードです：

考え？補足として、これは c# ですが、この動作は MinGW でコンパイルされた C++ でも発生します。

次のコードを C で書きました。これを末尾再帰実装と呼ぶことはできますか?

末尾再帰でない場合は、そうする方法を提案してください。Ackermann の末尾再帰バージョンへの参照は、C/C++/Java または非関数型プログラミング言語で適切です。

OCaml の Y コンビネータを理解しようとしています。hereからいくつかのコードを取得し、それを使用して Ackermann 関数を記述しようとしています。リンクの例では、関数に必要な引数は 1 つだけです。アッカーマン関数には 2 つの引数が必要なため、構文エラーが発生し続けます。私がこれまでに持っているコードは

機能させるにはどうすればよいですか？ありがとう。

このバージョンの Ackermann の関数を見つけて、MIT Scheme Lisp でコーディングしようとしましたが、成功しませんでした。

アッカーマン関数 A(m,n)

m=0のとき

A(m,n)=n+1

m>0かつn=0の場合

A(m,n)=A(m-1,1)

m>0かつn>0の場合

A(m,n)=A(m-1,A(m,n-1))

（ここにあります http://www.gfredericks.com/sandbox/arith/ackermann）

私のスキームコード:

今いくつかの結果：

(acker2 0 0) 値: 1

(acker2 0 1) 値: 2

(acker2 0 2) 値: 3

(acker2 2 2) オブジェクト 2 は適用されません

(acker2 1 23) オブジェクト 1 は適用されません

(acker2 8 0) オブジェクト 7 は適用されません

解決策は何ですか？

アルゴリズムの分析のクラスでは、クラスカルのアルゴリズムの次の疑似コードが提示されます。

彼は、ばらばらな集合の森について、次のように述べています。

m 個の MAKE-SET、UNION、および FIND-SET 操作のシーケンス (n は MAKE-SET 操作) は、最悪の場合の時間O(m α (n)) .

ステップ 2 とステップ 5 ～ 8 の複雑さを計算するために使用されます。

接続された G の場合: |E| ≥ |V| -1; m = O(V + E)、n = O(V);

ステップ 2、5 ～ 8: O((V + E) α(V)) = O(E α(V))

α(V) = O(lg V) = O(lg E); O(E lg E) ----- // α(V) はどのように等しいのでしょうか?

Kruskal: ステップ 3、5-8、およびステップ 4: O(E lg E)

観察: |E| < |V|2 -> lg E = O(lg V)

したがって、クラスカルの複雑さ: O(E lg V)

私はこの「alpha(n)」/「α(n)」関数の背後にあるロジックを理解しようとしましたが、私が読んだことから、単純化すると、アッカーマン関数は信じられないほど急速に指数関数的に成長する関数であると思われます。逆は、対数的に信じられないほどゆっくりと成長するものです。

私の解釈が正しければ、「α(n)」は何を表しているのでしょうか? MAKE-SET操作はせいぜいO(lg n)ということですか? 逆アッカーマンの使用はどのように/なぜ必要なのですか? この操作は V 回 (頂点ごとに) 実行されるという印象を受けました。これに続いて、α(V) も O(lg V) = O(lg E) と簡略化されますが、これは、最大で α(V) を O(lg V) で表すことができるということですか?

また、なぜ|E| < |V|^2 -> lg E = O(lg V)ステートメントが作成されましたが、|E| であることはどのようにわかりますか? < |V|^2?

私の質問は本当に要約すると、私の講師が両方とも O(E log V) であると述べたときに、素集合の「森」表現がリンクリストで実装されたものよりも効率的であるように見えるのはなぜですか? したがって、フォレストで互いに素なセットを実装することの難しさが増していることに意味はありますか?