魔方分割数
Posted feedbacks - Ruby
とりあえず単純に
(1)合計が平均値になる組み合わせを生成
(2)(1)から要素が重ならない組み合わせを生成
N=4で62秒（PenM 1.7GHz）、解は392
N=5はこのやり方では無理ですね。
(1)合計が平均値になる組み合わせを生成
(2)(1)から要素が重ならない組み合わせを生成
N=4で62秒（PenM 1.7GHz）、解は392
N=5はこのやり方では無理ですね。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 | def gen_comb(list,n)
if n==0
yield([])
else
(list.size-n+1).times do |i|
gen_comb(list[i+1..-1],n-1) do|ls|
yield([list[i]]+ls)
end
end
end
end
def comb_num(list,n,sum)
ret=[]
gen_comb(list,n) do |a|
ret<<=a if (a.inject(0){|r,e| r+=e})==sum
end
ret
end
def comb_array(list,n)
ret=[]
gen_comb(list,n) do |a|
ret<<=a if a.inject{|r,e| break unless (r&e).empty?;r+=e}
end
ret
end
def maho(n)
m=n**2
sum=m*(m+1)/2/n
comb_array(comb_num((1..m).to_a,n,sum),n)
end
start_time = Time.now
puts maho(4).size
puts Time.now-start_time
|
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 ]