問題タブ [collatz]

1 つの引数 (正の整数) を受け取り、

• 偶数の場合は 2 で割る、または
• 3 倍し、奇数の場合は 1 を加算します

結果の数値を返します。

次に、1 つの引数 (正の整数) を受け取り、それを 1 に達するまで (その時点で停止する) 前の関数に繰り返し渡す別の関数。この関数は、それを 1 に減らすのにかかったステップ数を返します。

次に、2 つの引数 a と b (両方とも a <= b の正の整数) を取り、範囲内の任意の単一の数値 (エンドポイントを含む) を 1 に減らすために必要な反復コラッツ ステップの最大数を返す別の関数。(Collat​​z ステップは前の関数を指します)。

そして最後に、2 つの引数 a と b (両方とも a <= b の正の整数) を取り、1 に削減されるコラッツ ステップの最大数を取る a と b (エンドポイントを含む) の間の数を返す別の関数。

これらの関数はコラッツ問題に関係しており、非常に興味深いと思います。後続の関数は、明らかに以前に定義された他の関数を借用します。

これをSchemeコードでどのように示すことができるでしょうか?

私はUvaの3n+1の問題を解決していますが、裁判官が私の答えを拒否している理由がわかりません。制限時間を超えていません。これまでに試したすべてのテストケースは正しく実行されました。

http://xkcd.com/710/にインスパイアされたコード ゴルフです。

チャレンジ

0 より大きい正の整数を指定すると、その数値の雹のシーケンスを出力します。

ヘイルストーン シーケンス

詳細については、ウィキペディアを参照してください。

• 偶数の場合は2で割ります。
• 奇数なら3倍にして1足すればいい。

これを出た数だけ1になるまで繰り返す（1以降続くと の無限ループに入る1 -> 4 -> 2 -> 1...）

コードで説明するのが最善の方法である場合もあるので、ウィキペディアからいくつか引用します

このコードは機能しますが、追加の課題を追加しています。プログラムは、スタック オーバーフローに対して脆弱であってはなりません。したがって、反復または末尾再帰のいずれかを使用する必要があります。

また、大きな数を計算でき、言語にまだ実装されていない場合のボーナスポイント。(または、固定長整数を使用して大きな数のサポートを再実装する場合)

テストケース

また、コード ゴルフには、完全なユーザー入力と出力が含まれている必要があります。

次の反復シーケンスは、正の整数のセットに対して定義されます。

n ->n/2 (n は偶数) n ->3n + 1 (n は奇数)

上記のルールを使用して 13 から開始すると、次のシーケンスが生成されます。

13 40 20 10 5 16 8 4 2 1 このシーケンス (13 で始まり 1 で終わる) には 10 個の項が含まれていることがわかります。まだ証明されていませんが (コラッツ問題)、すべての開始数は 1 で終わると考えられています。

100 万未満の開始番号で、最も長いチェーンを生成するのはどれですか?

注: チェーンが開始されると、条件は 100 万を超えることが許可されます。

ブルートフォース法を使用して、これに対する解決策をCでコーディングしてみました。ただし、113383 を計算しようとすると、プログラムが停止するようです。アドバイスしてください :)

私はプロジェクトオイラー問題14を怠惰な方法で解決しようとしています。残念ながら、私は不可能なことをしようとしているかもしれません。両方とも怠惰な怠惰なシーケンスを作成しますが、まだ計算されていない値をどういうわけか「先読み」します。

正確さをテストするために私が書いた非遅延バージョンは次のとおりです。

これは機能しますが、本当に遅いです。もちろん、私はそれを覚えることができます：

しかし、私が本当にやりたかったのは、怠惰なシーケンスの限界を理解するためにかゆみを掻き、次のような関数を書くことでした。

これから要素をプルすると、n> 2のスタックオーバーフローが発生します。これは、レイジーリストの10番目の要素の値を知るためにn=3で「将来を見据える」必要がある理由を考えると理解できます。 1（* 3 n））=10。

怠惰なリストはメモ化よりもはるかにオーバーヘッドが少ないので、この種のことが、さらに遅延した評価またはキューイングによって何らかの形で可能かどうかを知りたいですか？

私はC でProject Euler #14に取り組んでおり、基本的なアルゴリズムを理解しました。ただし、必要に応じて 2,000,000 など、大きな数の場合は耐えられないほど遅くなります。既知のシーケンスを保存する方法があるはずですが、シーケンスを何度も生成する必要があるためだと思います (たとえば、16 になると、以前の経験から、次の数字は 8、4、2 であることがわかります)。 、次に 1)。

C の固定長配列でこれを行う方法は正確にはわかりませんが、良い方法があるに違いありません (これは驚くほど効率的であると確信しています)。前もって感謝します。

これが私が現在持っているものです。

私はHaskellとプログラミング全般に不慣れです。nから一連のコラッツ数を生成する関数を定義しようとしています。私は持っている：

これを GHCi で実行すると、次のエラーが発生します。

これが何を意味するのかわかりません。問題は、リストに「1」を追加しているようです。この問題が発生する理由は

正しい Collat​​z シーケンスに続く "1" の無限シーケンスを生成します。でも、

nから"1" を除くすべてのコラッツ数を生成します。私は何を間違っていますか？

以下のプログラムを作ってみたところ、最初はうまくいきました。

これが行うことになっているのは、開始番号を入力することであり、偶数の場合はQ/2. 奇数の場合は3Q+1、結果を に格納しQます。これがコラッツ予想であり、この反復を続けると、どの数字から始めても常に 1 になるというものです。最初の数字の中には、到達するまでにより多くのステップを必要とするものもあれば、より少ないステップしか必要としないものもあります。

問題：

プログラムが多数の反復を行った後、エラーが表示され、デバッグを押すと、カーソルがQinの上に移動することがありますif Q≠1。

なぜこれが起こり続けるのか知っていますか？ありがとう。