問題タブ [collatz]

私はHaskellを学んでいて、型システムを理解しようとして立ち往生しています。

入力に対してシリーズ「HalforThreePlusOne」の長さを返す関数を作成しようとしています。これが再帰的アプローチを使用した関数での私の試みです（関数は積分入力に対してのみ有効です）：

これは、GHC6.12.3でこのファイルを読み込もうとしたときに発生するエラーです。

take (truncate (5/2)) [1,2,3]動作するので、このエラーメッセージを理解できません。どこが間違っているのですか？

「プログラミングの課題」の本の「3n+1問題」の実行に問題があります。

私はグーグルで見つけたJavaのすべてのソリューションを試しましたが（Stack Overflowのソリューションも）、1つも機能しませんでしたが、すべて「間違った答え」と報告されています。また、動作するC ++ソリューションを見つけ、それをJavaに翻訳しました。同じこと、「間違った答え」です。

私はJava送信用のプログラミングチャレンジのテンプレートを使用しています。アルゴリズムが正しいことを誓うことができます。考えられる唯一の問題は、入力の読み取りまたは出力の書き込みのコードにありますが、理解できません。アウト。これが私のコードです、どんな助けでも大歓迎です：

Java を使用して約 5 分で Collat​​z 予想アルゴリズムを解くことができました (いいえ、証明しようとしませんでした)。

Web アプリを作成するために C# を学習しているので、同じことを行うのに問題が発生しています。ユーザーに数値を入力し、ボタンをクリックして、出力をテキストボックスに出力するだけです。

Click私が使用しているボタンイベントハンドラーメソッドは次のとおりです。

コラッツ法は次のとおりです。

VS.net デバッガーを使用して 2 のような数値を入力すると編集すると、出力もエラーも発生しません。私は永遠に待っているだけです。無限ループだったらそのうちエラーになるよね？

いいえ、これは宿題の問題ではありません (JAVA でやったのは 2 年前のことですが :)) 私は独学で C# を学んでいます。

これはインタビューの質問で、Project Euler Problem 14に関連しているようです。

コラッツ予想によると、次のようにすると

最終的には 1 になります。

例えば、5 -> 16 -> 8 -> 4 -> 2 -> 1

予想が正しいと仮定すると、各数値には連鎖長があります。つまり、1 になるまでに必要なステップ数です (1 の連鎖長は 0 です)。

ここで、問題に自然数 n、m、および自然数 k が与えられ、1 と n の間のすべての数を見つけるアルゴリズムを与えます。これらの数の連鎖の長さは <= k です。また、これらの数字のチェーンには 1 から m までの数字のみを含める必要があるという制限もあります (つまり、m を超えることはできません)。

簡単な方法は、力ずくでそれを実行し、それをメモ化と組み合わせることです。

インタビュアーは、O(S) 時間アルゴリズムがあると言いました。ここで、S は出力する必要のある数値の数です。

誰がそれが何であるか知っていますか？

コラッツ予想のステートメントをユーザーが入力できる整数に適用する簡単なプログラムを作成しようとしています。

ただし、次の行に構文エラーがあると言っています。

この行で何が間違っているのかわかりません。

また、まだテストできていないので、これはうまくいくように見えますか?

私はコラッツ予想を使用して数学フェア プロジェクトに取り組んでいます。ウィキペディアでここで見つけることができるように、逆グラフを作成したいと考えていますが、コードのどこかを台無しにしていて、すべてが表示されていないことがわかりました。値を逆にします (例: 配列から 1 つの奇数の値を見つけ、次に同じ値 *2 を見つけますが、それを超えることはありません)。

ネタバレ注意：これはプロジェクトオイラーの問題14に関連しています。

次のコードの実行には約15秒かかります。1秒で実行される非再帰的なJavaソリューションがあります。このコードをもっとそれに近づけることができるはずだと思います。

私はプロファイルを作成し+RHS -p、割り当てられたメモリが大きく、入力が大きくなるにつれて大きくなることに気づきました。n = 100,0001GBには割り当てられます（！）、13GBには割り当てn = 1,000,000られます（!!）。

繰り返しになり-sstderrますが、多くのバイトが割り当てられたものの、合計メモリ使用量は1 MBで、生産性は95％以上だったので、おそらく13GBは赤字です。

私はいくつかの可能性を考えることができます：

1. 何かが必要なほど厳密ではありません。私はすでに発見 しましfoldl1'たが、多分私はもっとする必要がありますか？厳密としてマークすることは可能collatz ですか（それも意味がありますか？

2. collatz末尾呼び出しの最適化ではありません。あるべきだと思いますが、確認する方法がわかりません。

3. コンパイラーはいくつかの最適化を行っていないはずです。たとえば、一度に2つの結果collatz（最大および現在）のみをメモリーに入れる必要があります。

助言がありますか？

これは、なぜこのHaskell式がとても遅いのかとほぼ同じです。ただし、高速Javaソリューションではメモ化を実行する必要がないことに注意してください。それに頼ることなくこれをスピードアップする方法はありますか？

参考までに、私のプロファイリング出力は次のとおりです。

そして-sstderr：

そして、Javaソリューション（私のものではなく、メモ化が削除されたProject Eulerフォーラムから取得）：

私はSchemeでコラッツ予想を書きました：

これは末尾再帰呼び出しですが、呼び出すとスタック オーバーフローが発生します (C 121):

適切な末尾再帰がオーバーフローを引き起こすのはなぜですか? ご覧のとおり、Scheme インタープリターとして Guile を使用しています (バージョン 1.8.7)。

Haskell で単純な dp アルゴリズムを実装しようとしています (これは Project Euler の Collat​​z 予想問題用です)。同等の c++ は次のとおりです。

Haskell で書いたコードは次のようになりました。

(ここでは状態モナドを再実装しているだけだと思いますが、今のところ気にしないでください。) solve を呼び出すコードは、最大で K=1e6 のパラメーターに与えることができる最大値を見つけようとします。

上記のコードは、スタック オーバーフローで失敗します。これは、非常に大きな未評価のサンクを構築するため、当然のことです。なので使ってみた

foldl' 内で、K=1e5 の正しい答えを計算します。しかし、これは K=1e6 では失敗します (12 秒でスタック オーバーフロー)。それから私は使ってみました

解決の最後の行で、これは違いはありませんでした（スタックオーバーフローはまだです）。それから私は使ってみました

おそらく、deepseq がマップ mem '' 全体をウォークスルーし、アルゴリズムの時間の複雑さが n*log(n) ではなく 2 次になるため、これは非常に遅くなります。

これを実装する正しい方法は何ですか? 計算全体を厳密にする方法がわからず、計算のどの部分でスタックオーバーフローが発生するのかよくわかりませんが、マップであると思われます。たとえば、配列を使用できますが、ここで何が間違っているのかを理解したいと思います。

Haskell でProject Euler #14の解決にしばらく取り組んでいますが、何らかの理由でそれを機能させることができません。少し前にGroovyを使用して問題を解決しましたが、ここでも基本的に同じ方法を使用していると思います。しかし、プログラムは最初の 10,000 の長さを見つけるだけでも信じられないほど遅く実行され、その理由について今では本当に迷っています。メモ化を正しく使用していると思いますが、GHCI の小さなデータ セットでもメモリが不足しています。

これが私がこれまでに思いついたものです。

map collatz [1..1000000]問題の答えを得るために実行しmap collatz [1..10000]ていましたが、メモリ不足エラーが発生し、実行が完了するまでに数秒かかりました。

このプログラムの問題点について誰かが私に洞察を与えることができれば、それは素晴らしいことです! 私は多くのことを試しましたが、行き詰まっており、手を必要としています。

ありがとう！