問題タブ [array-algorithms]

すべて正で、数値 N より小さいことがわかっている要素を含む配列があるとします。

すべての要素の合計が正確に N になるサブセットが配列内にあるかどうかを調べるアルゴリズムの一般的で高レベルの説明を誰かが教えてくれませんか?

特に効率的である必要はありません。私が扱っているセットは非常に小さいです。

2 人のプレーヤーを含むゲームの最適化を扱う問題があります。したがって、多数の辺といくつかの頂点を持つ無向連結グラフがあります。各プレイヤーはエッジを削除する必要があり、頂点が孤立している場合、スコアが 1 増加し、別のエッジを削除する必要があります。グラフは、いわゆる「隣接行列」で表されます。配列内のそれぞれについて、2 つの頂点間の接続があります。たとえば、三角形がある場合、次の配列があります。

0 1 1 最初の行

1 0 1 秒の行

1 1 0 3行目

行は頂点に対応し、列は他の頂点への可能な接続に対応します。ブルートフォースを適用するために再帰関数を使用するように割り当てられています。私はこの関数のコードを書くために多くのことを考えました。いくつかのコードを実装し、コンパイルして実行しました。機能しない理由がまったくわかりません。この関数の私のコード:

マトリックス::マトリックス() {

}

}

}

bestescore と slechtstescore はオランダ語で最高スコアと最悪スコアを意味します。berekenScore は、エッジが削除された後に獲得されるポイント数を調整し、それを huidigScore に保存します。つまり、基本的には 0、1、または 2 です。

この関数を int main で呼び出します。

次の隣接行列を使用して実行しました。

5

0 1 1 1 1
1 0 1 0 0
1 1 0 0
1 0 0 0
1 0 0 0 0

「スコア」を 5 回だけ出力するため、関数内の for ループを無視しているように見えます。また、bestescore は一度数百万の値に設定され、次に 5 に設定されます。私は経験豊富なプログラマーではないので、何かに欠けている..??

シャッフルされたカードのデッキを生成するメソッドを書くとしましょう。非常に簡単にするために、スートを無視すると、52 枚のカードがあります。

1 つのアルゴリズムは次のようになります。

• 最初の要素に 1、2 番目の要素に 2 というように、52 要素の配列を設定します。
• X 回反復する for ループを作成し、反復ごとにランダムに 2 枚のカードを選んで交換します。
• X が大きいほど、シャッフルはランダム化されます。

別のアルゴリズム:

• 前のように配列にデータを入力します。
• 26 回反復する for ループを作成し、反復ごとに 2 つの乱数を選択し、これらの 2 つの数値を、新たに選択した数値を格納する別の 52 要素配列の連続する先頭に配置します。
• 各反復で、新しい配列に追加された元の配列から 2 枚のカードを削除します。

シャッフルにはより良いアルゴリズムがあることは知っていますが、これら2つに関しては、どちらが優れているのですか?またその理由は何ですか?

アイテムの配列 (〜 5000 アイテム、各アイテムは英単語) と、アイテムのペア間の距離関数があります。グループ内のすべてのアイテムが距離基準を満たす配列内のアイテムのグループを検索したい (たとえば、アイテムのすべてのペアの距離が 2 より小さい)。通常、グループはできるだけ大きくする必要がありますが、これに関する正式な定義や厳密な要件はありません。

私の実装言語は PHP ですが、これを効率的に処理できるアルゴリズムに関する一般的なアドバイスを探しています。

更新:頂点がアイテムであるグラフを作成することでこれを解決できると思います。距離の制約を満たすアイテム間にエッジがあります。グラフを作成したら、Bron–Kerbosch のようなアルゴリズムを実行して、すべての最大クリークをリストできます。これがうまくいった場合は更新しますが、その間にあなたの考えを自由に追加してください.

median-of-medians アルゴリズムでは、配列をサイズ 5 のチャンクに分割する必要があります。アルゴリズムの発明者がどのようにしてマジック ナンバー '5' を思いついたのか疑問に思っています。他の何か？

この例で再帰がどのように機能するかを理解しようとしているだけです。誰かがこれを分解してくれれば幸いです。基本的に配列内の最大要素を返す次のアルゴリズムがあります。

ここで再帰呼び出しがどのように機能するか理解できません。2 番目の呼び出しが行われているときに、最初の再帰呼び出しは常に実行されますか? 誰かが私にこれを説明してくれれば、本当に感謝しています。どうもありがとう！