問題タブ [puzzle]

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

問題は、私が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 ルーチンは次のとおりです。

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

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

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

なぜでしょうか？

でレイアウトを設定しJFrameてsetLayoutからそれgetLayoutを取得すると、別のが得られますLayoutManager。ここで何が起こっているの？

与える

しかし、私が置き換えるJFrameと、JPanel

数か月前に面接の準備のために書いていたコードを見つけました。

私が持っていたコメントによると、それはこの問題を解決しようとしていました:

セント単位のドル価値 (例: 200 = 2 ドル、1000 = 10 ドル) が与えられた場合、そのドル価値を構成するコインのすべての組み合わせを見つけます。ペニー (1¢)、ニッケル (5¢)、ダイム (10¢)、クォーター (25¢) のみが許可されています。

たとえば、100 が与えられた場合、答えは次のようになります。

これは、反復と再帰の両方の方法で解決できると思います。私の再帰的な解決策は非常にバグが多く、他の人がこの問題をどのように解決するのか疑問に思っていました。この問題の難しい部分は、可能な限り効率的にすることでした。

簡単なレベルでは手でプレイできますが、難しいレベルではコンピューター プログラムで解決することを意図したパズル ゲームを作成しています。パズルは、六角形のボード上の塗りつぶしです。ここでプロトタイプを試すことができます。

_{(出典: hacker.org )}

パズルの仕組みは次のとおりです。上から色を選択すると、左上のタイルから塗りつぶしが始まります。これにより、ボードが徐々に単色に変換されます。課題は、特定の数の手でこれを行うことです。

これに似たパズルをいくつか作成しましたが、キーは、作成方法を知らずに解決するのが難しいボードを生成するアルゴリズムを使用することです. たとえば、ここでは塗りつぶしを逆にしてボードを作成する場合があります。塗りつぶしがなくなるまで、ソリッド ボードから逆方向に作業します。これにかかったステップ数がわかっているので、これを解の下限として設定できます。

私が直面している問題は、このアプローチを試みると、上限が高すぎることです。ランダムに移動しても、この手数以内にパズルを解くのは簡単です。

解決策ではないアプローチは、ランダムなボードを生成し、それを最適に解決して、これをターゲットに設定することです。ポイントは、最適に解くことが NP 時間または少なくともハード P であるパズルを作成することです。

だから私が探しているのは、非常に難しいボードを生成できるアルゴリズムであり、それらを解決することは、ボードが大きくなるにつれて深刻な課題になります.

URL クエリ文字列で 50 桁の 10 進数の整数 ID を使用している Web サイトに遭遇しましたが、これは少し過剰に思えます。

最小の 50 桁の 10 進数は1.0 x 10^49、別名:

1. バイナリ表現には何ビットが含まれますか?
2. 符号なし 32 ビット整数または 64 ビット整数の範囲制限を考慮して、このような大きな 10 進数を 2 進数に変換するにはどうすればよいでしょうか?

私は純粋なプログラマーの好奇心からだけ質問します - これは大学の質問でも、仕事の問題でも、面接のパズルでもありません!

再帰を使用して、配列を 2 つの部分に分割し、両方の部分の合計が等しくなるインデックスを見つけます。

カットとはナイフのように切るという意味です。結果に対してインデックス <= を持つすべてのセルの合計は、結果に対してインデックス > を持つすべてのセルと等しくなければなりません。セルを除外したり、両側の一部にすることはできません。

配列には、任意の整数 (つまり、正、負、ゼロ) が含まれます。

そのようなインデックスがない場合は、-1.

ヒープ オブジェクトを割り当てることはできません。

1 回のパスで実行する必要があります。

再帰を使用する必要があります (つまり、ループ構造は使用できません)。

任意の言語または疑似コードにすることができます。

これを追加するのを忘れました: 配列を変更することはできません

夜は 4 人の男性が橋を渡らなければなりません。橋を渡る場合は、1 人または 2 人の男性が懐中電灯を携帯する必要があります。懐中電灯は前後に歩く必要があります。投げることはできません。各人は異なる速度で歩きます。1 つは交差するのに 1 分かかり、さらに 2 分、さらに 5 分、最後の 10 分です。2 人の男性が一緒に横断する場合は、より遅い男性のペースで歩かなければなりません。トリックはありません-男性はすべて同じ側から始まり、懐中電灯は遠くを照らすことができず、誰も運ぶことができません.

そして問題は、それらがすべて横断できる最速の速度はどれかということです。私は基本的に、この種の問題に対する一般化されたアプローチを探しています。これはフィボナッチ数列で解決できると友人から言われましたが、その解決策はすべての人に当てはまるわけではありません。

在宅ワークではありませんのでご注意ください。

これは退屈な学術的なOOPの質問の1つですが、宿題ではありません。初心者プログラマーから、OOPに関する愚かな教科書の例の1つについて質問を受けました。

SquareクラスとCubeクラスを設計していると想像してください。どちらがどちらを継承する必要がありますか？

私は関係を見ます、しかしそれが何であるか、私は本当に見ることができません！

OOPを念頭に置いて論理的な議論をしていただけませんか。