問題タブ [ackermann]
For questions regarding programming in ECMAScript (JavaScript/JS) and its various dialects/implementations (excluding ActionScript). Note JavaScript is NOT the same as Java! Please include all relevant tags on your question; e.g., [node.js], [jquery], [json], [reactjs], [angular], [ember.js], [vue.js], [typescript], [svelte], etc.
algorithm - Grossman & Zeitman のアルゴリズムを理解する
Grossman & Zeitman が発行した論文「本質的に反復的なアッカーマン関数の計算」を読みました。この論文では、アッカーマン関数を最適化するアルゴリズムが提示されています。
アッカーマン関数が部分列 A(m,n) で結果を生成することはわかっています。
m=0: 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17,...
m=1: 2, 3, 4 , 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18,...
m=2: 3, 5, 7, 9, 11, 13, 15, 17, 19, 21, 23, 25, 27, 29, 31, 33,...
m=3: 5, 13, 29, 61, 125, 253, 509, 1021, 2045, 4093, 8189, 16381, 32765 、65533、...
m=4: 13、65533、...
Next配列は、各サブシーケンスのどこにいるかを追跡し、Goal配列は、計算されたばかりの値を次のサブシーケンスに転送する前に到達する必要がある場所を追跡することであると述べられています。そして、それが行うのは、値に 1 をインクリメントすることだけです。
2 つの配列が現在地/移動先をどのように示しているのか理解するのが難しいと思いますか? で停止したときの正確な意味を正確に特定するのに苦労していnext[m] = n + 1ます。なぜ具体的にこの値なのですか? アルゴリズムをトレースしてみましたが、どのように機能するのかまだわかりません。このアルゴリズムはボトムアップの実装としてカウントされますか?
これは、値、現在、および両方の配列を出力する Java コードです。