ディスクを使用せずに、数値の非常に大きな部分 (C/C++ で最大の整数型の最大値、たとえば 2^20 を超える) でサイクル長を見つける可能性はありますか? 最良の状況は、標準入力から到着したときにそれらを順次分析することですが、それは不可能であり、メモリに保存する必要があると確信しています。しかし、私が間違っていることを願っています。数値は整数で、標準入力から取得されます。
例: 入力: ( 1 2 3 ... (1 2 3 の 2^20 トリプル) ... 1 2 3) 望ましい結果: 3
編集
サイクルを周期と考えてみましょう (f(x) = f(x+t) for some t) - t の値を探します
オペレーティング メモリが少なすぎてすべての数値を格納できず (数値は 2^20 を超える可能性があります)、gmp 型である可能性があると仮定しましょう。
これは十分に研究された問題であり、リソースと制約が正確に何であるかに応じて、かなりの数のアルゴリズムがあります。
http://en.wikipedia.org/wiki/Cycle_detection
すべてをメモリに格納する必要はありませんが (基本アルゴリズムでは 2 つのポインター/インデックスのみ)、シーケンスに複数回アクセスできる必要があります。
以下も参照してください。
周期の長さを見つける標準的な方法は、シーケンスが整数のアルファベット上の文字列 S であると想像し、文字列 SS (文字列 S の連結) で S が見つかる左端の位置 (0 より大きい) を見つけることです。それ自体で）。つまり、 の場合、文字列 の位置で S が見つかるように、ゼロより大きいS = 'abcabc'最初の位置を見つける必要があります。この場合、これは 3 であり、それが期間の長さです。iiSS = 'abcabcabcabc'
これは、線形パフォーマンスを備えた任意の文字列検索アルゴリズムで実行でき、最新のコンピューターで 2^20 の数値に対して完全に正常に動作するはずです。ただし、数値をメモリに保存することを避けることができるとは思えません。