問題タブ [algorithm]

空のスペースに収まる最大の面積を持つ長方形を見つけるための最も効率的なアルゴリズムは何ですか？

画面が次のようになっているとしましょう（「＃」は塗りつぶされた領域を表します）：

考えられる解決策は次のとおりです。

通常、私は解決策を考え出すのを楽しんでいます。今回は自分で手探りで時間を無駄にしないようにしたいと思いますが、これは自分が取り組んでいるプロジェクトに実用的であるためです。よく知られている解決策はありますか？

Shog9は書いた：

入力は配列（他の応答によって暗示される）ですか、それとも任意のサイズの配置された長方形の形式のオクルージョンのリストですか（ウィンドウ位置を処理するときのウィンドウシステムの場合のように）？

はい、画面に配置された一連のウィンドウを追跡する構造があります。また、空か塗りつぶしかを問わず、各エッジ間のすべての領域と、左エッジまたは上端のピクセル位置を追跡するグリッドもあります。この特性を利用する修正された形式があると思います。何か知っていますか？

私は最近、いくつかの基本事項をブラッシュアップしていて、リンクリストのマージソートがかなり良い課題であることに気づきました。優れた実装がある場合は、ここでそれを披露してください。

ログ ファイルの解析が必要なプロジェクトに取り組んでいます。次のようなグループメッセージを受け取る高速なアルゴリズムを探しています:

P1 の温度は華氏 35 度です。

P1 の温度は 40F です。

P3 の温度は華氏 35 度です。

ロガーが停止しました。

ロガーを開始しました。

P1 の温度は 40F です。

printf() の形式で何かを出力します。

アルゴリズムは、メッセージ グループ内のほぼすべてのデータ ロードを認識できるように十分に汎用的である必要があります。

この種のテクノロジーを検索してみましたが、検索する正しい用語もわかりません。

この種のものが好きな人のためのコーディングの問題があります。指定された整数の人間が読める文字列表現を返す関数の実装を (もちろん、選択した言語で) 見てみましょう。例えば：

• humanReadable(1) は「1」を返します。
• humanReadable(53) は「53」を返します。
• humanReadable(723603) は、「723,603」を返します。
• humanReadable(1456376562) は、「10 億 4 億 5600 万 3 億 76005 62」を返します。

特に賢い/エレガントなソリューションのボーナスポイント!

無意味な作業のように思えるかもしれませんが、この種のアルゴリズムには実際のアプリケーションが数多くあります (ただし、10 億もの数値をサポートするのはやり過ぎかもしれません :-)

Google カレンダーに似たものを作成する必要があるため、ユーザーのすべてのイベントを含むイベント テーブルを作成しました。

難しいのは、繰り返し発生するイベントを処理することです。イベント テーブルの行には、イベントの種類を示す event_type フィールドがあります。これは、イベントが単一の日付のみ、または x 日ごとに繰り返し発生するイベントであるためです。 .

主な設計課題は、繰り返し発生するイベントの処理です。

ユーザーが月のビューを使用してカレンダーを表示する場合、特定の月のすべてのイベントを表示するにはどうすればよいですか? クエリは複雑になるので、別のテーブルを作成して、再発するイベントを含むすべてのイベントの行を作成する方が簡単だと思いました。

皆さんはどう思いますか？

荷物があるとします。A 地点から B 地点、B 地点から C 地点、そして最後に C 地点から D 地点に移動する必要があります。5 日以内に到達する必要があり、できるだけ少ない金額で済みます。各レグには 3 つの可能な荷送人があり、各レグにはそれぞれ異なる時間とコストがあります。

プログラムで最適な組み合わせを見つけるにはどうすればよいでしょうか?

これまでの私の最善の試み（3番目または4番目のアルゴリズム）は次のとおりです。

1. 各区間で最長の荷送人を見つける
2. 最も「高価な」ものを排除する
3. 各区間で最も安い荷送人を見つける
4. 総費用と日数を計算する
5. 日数が許容できる場合は終了、そうでない場合は 1 に移動

PHP ですばやくモックアップします (以下のテスト配列は問題なく動作しますが、上記のテスト配列で試してみると、正しい組み合わせが見つからないことに注意してください)。

文字通り、各組み合わせを 1 つずつ (一連のループを使用して) 作成し、それぞれの合計「スコア」を合計して、最高のものを見つけるという、ある種のことを実際に行う必要があると思います....

編集：明確にするために、これは「宿題」の課題ではありません（私は学校にいません）。それは私の現在のプロジェクトの一部です。

要件は (いつものように) 常に変化しています。この問題に取り組み始めた時点で現在の制約が与えられていたとしたら、A* アルゴリズムの変形 (またはダイクストラまたは最短経路またはシンプレックスなど) を使用していたでしょう。しかし、すべてが変形し、変化しており、それが私を今いる場所に導きます.

つまり、これまでに行ったすべてのがらくたを忘れて、パス検索アルゴリズムである、使用すべきだとわかっているものを使用する必要があることを意味していると思います。

この逐次検索アルゴリズム ( The Practice of Programmingから取得) のパフォーマンスは、C のネイティブ ユーティリティを使用して改善できますか? たとえば、i 変数をレジスタ変数に設定した場合などです。

（乗法）ハッシュ関数で使用する乗数を選択する際のアドバイス/ルールはありますか。関数は文字列のハッシュ値を計算しています。

double2 つまたは 2 つのfloat値を比較する最も効率的な方法は何ですか?

単純にこれを行うのは正しくありません:

しかし、次のようなもの：

無駄な処理をしているようです。

よりスマートなフロート比較器を知っている人はいますか?

1 秒あたりの表示フレーム数をゲーム ロジックから独立させるにはどうすればよいでしょうか? これは、ビデオ カードのレンダリング速度に関係なく、ゲーム ロジックが同じ速度で実行されるようにするためです。