問題タブ [programming-pearls]
For questions regarding programming in ECMAScript (JavaScript/JS) and its various dialects/implementations (excluding ActionScript). Note JavaScript is NOT the same as Java! Please include all relevant tags on your question; e.g., [node.js], [jquery], [json], [reactjs], [angular], [ember.js], [vue.js], [typescript], [svelte], etc.
debugging - デバッグと二分探索
コラム 2 (「AHA! アルゴリズム」) の「プログラミング パール」では、ソートやツリー トラバーサルなどのさまざまなプロセスでバイナリ検索がどのように役立つかについて説明しています。ただし、バイナリ検索は「プログラムのデバッグ」で使用できると述べています。誰かがこれがどのように行われるか説明してもらえますか?
algorithm - M位置のサークルシフトNサイズ配列の最速アルゴリズム
M位置のサークルシフトアレイの最速のアルゴリズムは何ですか？
たとえば、[3 4 5 2 3 1 4]シフトM=2の位置は。である必要があります[1 4 3 4 5 2 3]。
どうもありがとう。
c - このビット並べ替えコードのビット操作はどのように機能しますか?
Jon Bentley は、著書「プログラミング パール」のコラム 1 で、ビット ベクトルを使用してゼロ以外の正の整数のシーケンスをソートする手法を紹介しています。
ここからプログラム bitsort.c を取得し、以下に貼り付けました。
関数 clr、set、および test が何をしているかを理解し、以下で説明します: (ここで間違っている場合は修正してください)。
- clr は i 番目のビットをクリアします
- set は i ビットを設定します
- テストは i 番目のビットの値を返します
さて、関数がどのように機能するのかわかりません。これら 3 つの関数で発生しているすべてのビット操作を把握することはできません。
c - プログラミングパールのqsort関数にエラーがありますか？
それは私だけですか、それともプログラミングパールのこのコードは間違っています（クイックソートは2つのconst voidを望んでいますか？）もしそうなら、私の解決策は正しいですか？謝罪、ただ学んで...
これは解決策ですか？
algorithm - 重複しない最長部分文字列
最長の重複しない部分文字列の (最適な?) アルゴリズムを誰かが知っているのだろうか。
たとえば、文字列で
アバゼッドバデス
最も長く繰り返されるのは「BAD」です。ちなみに、そのような結果がない場合、アルゴリズムはそのようなことが発生したことを警告する必要があります。私の推測では、これには接尾辞ツリーが含まれていると思います。
きっとこれはどこかにすでに存在しているに違いない。助けてくれてありがとう！
algorithm - 最大40億intを含むソートされていない配列の中から欠落している32ビット整数を見つけます
これはで説明されている問題Programming pearlsです。著者が説明した二分探索法がわかりません。誰かが詳しく説明するのを手伝ってもらえますか？ありがとう。
編集：私は一般的に二分探索を理解することができます。この特殊なケースで二分探索を適用する方法がわかりません。別の番号を選択できるように、欠落している番号が特定の範囲内にあるかどうかを判断する方法。英語は私の母国語ではありません。それが著者をよく理解できない理由の1つです。だから、平易な英語を使ってください:)
編集：あなたの素晴らしい答えとコメントをありがとうございました！この質問を解決することから私が学んだ最も重要な教訓は、バイナリ検索はソートされた配列だけでなく適用されるということです！
c++ - 最小合計部分ベクトルのアルゴリズム
パール列 8 のプログラミングで見つかった問題は次のとおりです。
実数ベクトル x[n] を指定して、連続するサブベクトルで見つかった最大和を計算します。
提供される最終的なソリューションは、次のような O(n) の複雑さです。
最小合計を提供するために上記のアルゴリズムを変更する方法を知りたいです。
algorithm - "Programming Pearls" 二分探索ヘルプ
これがどのように機能するのか理解できないようです。
質問:
最大 40 億の 32 ビット整数をランダムな順序で含むシーケンシャル ファイルが与えられた場合、ファイルにない 32 ビット整数を見つけます (少なくとも 1 つ欠落している必要があります)。
答え:
この二分探索を、各整数を表す 32 ビットで見ると役に立ちます。アルゴリズムの最初のパスでは、(最大で) 40 億個の入力整数を読み取り、先頭の 0 ビットを持つものを 1 つの順次ファイルに書き込み、先頭の 1 ビットを持つものを別のファイルに書き込みます。
これらのファイルの 1 つには最大で 20 億の整数が含まれているため、次にそのファイルを現在の入力として使用し、プローブ プロセスを繰り返しますが、今回は 2 番目のビットで行います。
では、ファイルを何度も分割する (バイナリ検索) ことで、実際にどのようにして 32 ビット整数が見つからないのでしょうか?
algorithm - プログラミング パール: 1 つの整数が少なくとも 2 回現れることを見つける
セクション 2.6 と問題 2 にあります。元の問題は次のようなものです。
「4,300,000,000 個の 32 ビット整数を含むシーケンシャル ファイルが与えられた場合、少なくとも 2 回出現するものをどのように見つけることができますか?」
この演習に対する私の質問は、上記の問題のトリックは何か、この問題はどのような一般的なアルゴリズム カテゴリに属しているのかということです。
algorithm - Maximum Countiguous Negative Sum または Mnimum Positive Subsequence Sum 問題
最大部分列和を解くベントレーの美しいプロラミング パール問題については、誰もが聞いたことがあるでしょう。
M より小さい条件最大部分列を追加するとどうなるでしょうか?