ランダムな考えが頭に浮かびました（もちろん、チョコレートバーを共有していたときです！）. この問題を解決するための一般的なアルゴリズムがあるかどうか疑問に思っていました。
問題は次のようになります。
情報
1. 小さな正方形が長方形のマトリックスに配置されたチョコレート バーが
あります。 2. 部屋には n 人がいます。
問題次の制限が与えられた
場合にバーを人々の間で均等に共有できる最適な構成 (pxq) を出力するアルゴリズムを作成してください
。1 つの軸に沿って完全に作成される3. 分割の総数は n を超えることはできません (これは、バー全体を小さな断片に分割しようとして小さな断片を分割しようとするような非効率的な解決策を思いとどまらせるためです) 4. p または q は等しくありません。 yx は、片側に 1 つのバーがあれば問題は簡単に解決できるという回答の 1 つを指摘しました。ただし、これは実際の状況では適切な解決策ではありません。これは、この問題を解決するための意図でした:)例n, n-1, n-2...., 2, 1
n = 4 の場合、最適な構成は 4 x 3 です。
~~~~ ~~~~ ~~~~ ~~~~
| | | | |
~~~~ ~~~~ ~~~~ ~~~~
| | | | |
~~~~ ~~~~ ~~~~ ~~~~
| | | | |
~~~~ ~~~~ ~~~~ ~~~~
この構成は次のように分けることができます:
縦軸に沿って 3 つの休憩で 4 人
横軸に沿って 2 つの休憩で 3 人
真ん中に 1 つの休憩で 2 人他
の経験的な解決策は次のとおりです。該当する場合、バーのサブセット。これをよりよく説明するために、次のような 2 x 2 のチョコレート バーがあるとします。(n, p, q) = (1, 1, 1); (2, 2, 1); (3, 3, 2); (4, 4, 3); (5, 5, 12); (6, 6, 10) OR (6, 5, 12)
~~~~ ~~~~
| | |
~~~~ ~~~~
| | |
~~~~ ~~~~
従来の知恵では、このバーを 4 つの部分に分割するには、2 つのブレーク (中央の垂直軸 - 下と横) を作成する必要があると言われています。ただし、現実の世界 (チョコレート バーの場合) では、最初に半分に分割し、次にそれぞれの半分を別々に分割します。これにより、バー全体で 1 つのブレークと、バーの 2 つの異なるサブセットで 2 つのブレークの合計 3 つのブレークが作成されます。
私はインターネット上のどこにも解決策を見つけることができませんでした - これがプログラミング関連の質問ではない、または解決策が既に存在すると誰かが感じた場合は、遠慮なく質問を閉じてください =)