魔方分割数
Posted feedbacks - Smalltalk
Squeak Smalltalk で。
1GHz PowerPC で、n = 4 は 1.5 秒、n = 5 では５時間強でした。例によってブロック（ラムダ式）とそれに付随する環境の逐次コピー（copy fixTemps）により再帰処理モドキをしているので、ブロックがクロージャで実装されている今どきの普通の Smalltalk なら、同じ処理でもここまで遅くはならないと思います。念のため。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 | | nn nums sum rec count |
nn := 5.
nums := 1 to: nn * nn.
sum := nums sum / nn.
count := {0}.
rec := [:prev :rest |
rest size = nn ifTrue: [count at: 1 incrementBy: 1] ifFalse: [
rest combinations: nn atATimeDo: [:comb |
| next |
next := rest copyWithoutAll: comb.
(next first > comb first and: [comb sum = sum])
ifTrue: [rec copy fixTemps value: prev, {comb copy} value: next]]]].
{[rec copy fixTemps value: OrderedCollection new value: nums] timeToRun.
count first} "=> #(19161770 3245664) "
|
xsd
#4702()
Rating8/8=1.00
たとえば、N=3のときは、
(1) { 1, 5, 9 }, { 2, 6, 7 }, { 3, 4, 8 }
(2) { 1, 6, 8 }, { 2, 4, 9 }, { 3, 5, 7 }
の2通りの方法があります。
ここで指定されたNに対して、何通りのグループ分けの方法があるかを数えるプログラムを作ってください。
(何通りかという値だけが出力されればよいのですが、予め計算してある結果を返すのはダメですよ。)
また、N=5を指定したときの実行時間もあわせて教えてください。
なお、数え上げるときの注意として、
・{ 1, 5, 9 } と { 1, 9, 5 }は同じもの
・{ 1, 5, 9 }, { 2, 6, 7 }, { 3, 4, 8 }と
{ 1, 5, 9 }, { 3, 4, 8 }, { 2, 6, 7 }は同じもの
とすることに注意してください。
[ reply ]