問題タブ [puzzle]

これらのルールを使って究極の笑いジェネレーターを作りました。あなたはそれをあなたの好きな言語で巧妙な方法で実装できますか？

ルール：

すべての反復で、次の変換が発生します。

数値が 3 で割り切れるかどうかを判断するコードを記述します。関数への入力は 0 または 1 の単一ビットであり、これまでに受け取った数値が 3 で割り切れる数値のバイナリ表現である場合、出力は 1 である必要があります。ゼロ。

例:

これはインタビューの質問に基づいています。論理ゲートの図面をお願いしますが、これはスタック オーバーフローであるため、任意のコーディング言語を受け入れます。ハードウェア実装 (verilog など) のボーナス ポイント。

パート a (簡単):最初の入力は MSB です。

パート b (少し難しい):最初の入力は LSB です。

パート c (難しい): (a) と (b) では、どちらが速くて小さいですか? (理論的には Big-O の意味ではありませんが、実際にはより速く/より小さくなります。) 次に、より遅く/より大きなものを取り、より速く/より小さなものと同じくらい速く/小さくします。

「Celestial Jukebox」のシャッフルをどのように実装しますか?

より正確には、各時刻 t で、0..n(t) の間の一様乱数を返します。これにより、シーケンス全体で繰り返しがなく、n() が時間とともに増加します。

具体的な例として、カタログ内の任意の曲を 0 ベースのインデックス番号で再生できる定額音楽サービスを想定します。インデックス番号の範囲を広げる新しい曲が頻繁に追加されます。目標は、毎回新しい曲を再生することです (カタログに重複がないことを前提としています)。

理想的なソリューションは、既存のハードウェアで実行可能です。8 MB の DRAM に 600 万曲のリストをどのように詰め込むのでしょうか? 同様に、曲数が多いと、O(n) 選択のタイミングが悪化します。

-- LCG ジェネレーターの場合、0..N _{0で部分的に消耗した LCG を指定すると、0..N 1} (N1 > N0) で消耗したシーケンスを繰り返さない別の LCG に変換できます。
-- 特定の曲がすでに再生されているかどうかを確認することは、急速に手に負えなくなっているようですが、これが唯一の方法かもしれません。これに効率的なデータ構造はありますか？

M位置のサークルシフトアレイの最速のアルゴリズムは何ですか？
たとえば、[3 4 5 2 3 1 4]シフトM=2の位置は。である必要があります[1 4 3 4 5 2 3]。

どうもありがとう。

(Rich Bradshaw に感謝)

次のパズルの最適な戦略を探しています。

新しい妖精の王として、王国のカスタード湿地の地図を作成するのはあなたの義務です。
湿地は空気のような霧に覆われ、カスタードの島々が散らばっています。
各ポイントで低くまたは高く飛ぶように指示して、ピクシーを沼地に送ることができます。
ピクシーがカスタードの上に急降下すると、気が散ってシーケンスを完了できません。霧が濃いので、ピクシーが向こう側に来たかどうかしかわかりません。

コーディング用語で..

これは、指定された一連の急降下で妖精が退出したかどうかを返します。

最も簡単な方法は、1 回の急降下だけでシーケンスを渡すことです。これにより、「サイズ」試行ですべてのカスタード島が明らかになります。
カスタードの数に比例したものがいいのですが、次のようなシーケンスに問題があります。

このパズルの他の形式へのリンクも歓迎します。

2 つのパラメーターを受け入れる除算メソッドを作成しようとしています。

ここで、除数が 0 の場合、「ゼロで割ることはできません」というエラーが発生しますが、これは問題ありません。

私がやりたいことは、除数が 0 かどうかを確認し、そうであれば 1 に変換することです。私のメソッドに if ステートメントをたくさん入れずにこれを行う方法はありますか? 多くの if() が混乱を招くと思います。私は数学的にこれを行うべきではないことを知っていますが、これには他の機能があります。

例えば：

if()宣言なしでできるの？

同僚がこのようなコードに出くわし、それがどのようにコンパイルできるか理解できませんでした。

基本的に、メソッドの途中にランダムなURLが貼り付けられていましたが、javac気にしませんでした。

うまくいったので、誰にもわからない場合は回答を投稿しますが、投稿するのは面白かったと思いました。

コードでこの問題を解決するための最良の方法は何ですか？

問題は、私が2ドルの金額（ポットと呼ばれる）を持っていることです。これは3人に割り当てる必要があります。各人は両方のポットから得られる特定の金額を受け取り、レートはほぼ同じでなければなりません。割り当ての合計が多すぎたり少なすぎたりする丸めの問題に遭遇し続けます。

具体的な例を次に示します。

ポット＃1 987,654.32
ポット＃2 123,456.78

人＃1は割り当て量を取得します：345,678.89
人＃2は割り当て量を取得します：460,599.73
人＃3は割り当て量を取得します：304,832.48

私のロジックは次のとおりです（コードはc＃にあります）：

私が得た結果は次のとおりです。

ポット＃1、人＃1 = 307,270.13
ポット＃1、人＃2 = 409,421.99
ポット＃1、人＃3 = 270,962.21
ポット＃1合計= 987,654.33（1ペニーオフ）

ポット＃2、人＃1 = 38,408.76
ポット＃2、人＃2 = 51,177.74
ポット＃2、人＃3 = 33,870.27
ポット＃2合計= 123,456.77（1ペニーオフ）

ポットの合計は、元の合計と一致する必要があります。

私は何かが足りないか、私が取らなければならない余分なステップがあるかもしれないと思います。私は正しい方向に進んでいると思います。

どんな助けでも大歓迎です。

この質問は、1 <= x <= maxval および x(1) + ... + x(ncells) =目標合計。いくつかのより有望な回答をテストしたので、回答賞を Lennart Regebro に授与します。理由は次のとおりです。

1. 彼のルーティンは私のものと同じくらい速い (+-5%)。

2. 彼は、私の元のルーチンのどこかにバグがあることを指摘しました。ありがとう、レナート。

chrispy は、Lennart のものと同等と思われるアルゴリズムを提供しましたが、5 時間後、すっごく、最初にネットワークに到達しました。

備考: Alex Martelli の必要最小限の再帰アルゴリズムは、考えられるすべての組み合わせを作成し、それらすべてをふるいにかけ、どれが穴を通過するかを確認する例です。このアプローチは、Lennart や私のアプローチよりも 20 倍以上時間がかかります。(入力を max_val = 100、n_cells = 5、target_sum = 250 に上げます。私のボックスでは 18 秒対 8+ 分です。) 道徳: 考えられるすべての組み合わせを生成しないのは良いことです。

別の注意: Lennart のルーチンと私のルーチンは、同じ順序で同じ回答を生成します。実際、それらは異なる角度から見た同じアルゴリズムですか? 知らない。

何かが思い浮かびます。たとえば、(8,8,2,1,1) で始まり (4,4,4,4,4) で終わるように回答を並べ替えると (max_val=8, n_cells=5, target_sum で得られるもの) =20)、シリーズは一種の「最も遅い降下」を形成し、最初のものは「ホット」で、最後のものは「コールド」であり、その間に可能な最大数のステージがあります. これは「情報エントロピー」に関連していますか？それを見るための適切な指標は何ですか？熱の降順 (または昇順) で組み合わせを生成するアルゴリズムはありますか? (これは、正規化された std.dev を見ると、短いストレッチで近いですが、私が見る限りではありません。)

Python ルーチンは次のとおりです。

このバグを見つけるのに時間がかかりました...

次の方法を検討してください。

空でないハッシュ セットを使用してメソッドを呼び出しましたが、要素は削除されません。

なぜでしょうか？