私はレゴブロックの任意の配列を持っています。3つのレゴブロックで作られたフィギュアもあります. 現在のレゴ ブロックの配列から作成できるフィギュアの組み合わせの数を知りたいです。
誰かが私に参考文献を持っているので、この問題を解決できますか?
どのアルゴリズムを使用できますか? 私が使用できる理論はありますか？
あなたが提供できる助けを前もって感謝します。
/ハンス
編集: この質問は、数学スタック交換で再質問されました。
質問する
3203 次
2 に答える
5
このような問題、または少なくともその一般的なケースは、実際にはまだ未解決の研究課題であると思いますか? あなたはここで本当の数学的研究を行っています。;)
Søren Eilers、Mikkel Abrahamsen、および Bergfinnur Durhuus は、LEGO の組み合わせを数える問題、つまり、6 つの同一の 4x2 レゴ ブロックを配置できる一意の方法の数を数える問題に取り組みました。インスピレーションを得るために、彼らの作品 (Java コードを含む) を見ることができるかもしれません。
テキストにざっと目を通すと、彼らは 2 つの別々の方法で問題を解決したようです。
- 再帰的なブロック配置およびカウント アルゴリズムの使用。
- 力ずくで行う - 空間内で 6 つのレンガをあらゆる可能な位置に配置しようとします (レンガが接触していない場合でも)。
ヒント: レンガの数が少ない場合でも、可能な組み合わせの数は多くなります。これがLEGOの楽しいところです。
于 2012-04-10T19:12:30.513 に答える
1
予想される計算の複雑さに応じて、動的計画法を使用できます。
x1,x2,...xk を組み合わせ 1 の x1 コピー、組み合わせ 2 の x2 コピー ....
F([]) = F([x1=0]+F([x1=1]...
F([x1]) = F( [x1,x2=0]) + F( [x1,x2=1])....
このソリューションの複雑さは O(n^k) です。ここで、n はレンガの数、k は図形の数です。
于 2012-04-10T22:24:25.490 に答える