数値のバイナリ ツリーは、2 つの関数をある開始値に再帰的に適用することによって生成されaます。
a, f(a), g(a), f(f(a)), g(f(a)), f(g(a)), g(g(a)), ...
limitこのシーケンスでa までのすべての値が何回発生するかをカウントする必要がありますが、これはg(x) > f(x) > x常に保持される可能性があります。アルゴリズムは簡単です: で初期化されたコレクションから始めて、要素をとでa置き換えます。xf(x)g(x)limit
唯一の問題は、カウンターとして 1 バイトしか使用しない場合でも、使用しているメモリの約 5 倍のメモリが必要になることです。
DFSで仮想メモリを使ってみたのですが、局所性が悪く、プログラムが今年で終了するのではないかと思います。常に最小の要素を置き換えて数値を生成すると、非常に優れた局所性が得られますが、( BFSと同様に) コレクションは雑草のように成長し、メモリ消費は以前よりもさらに悪化します。
計算全体を 5 回繰り返すことで問題を解決しnまし(n-1)*limit/5たn*limit/5。より良い解決策はありますか？