魔方分割数
Posted feedbacks - Scala
Pentium1.6GHzの端末で17分少し掛かりました。
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 | import java.text.SimpleDateFormat
import java.util.Calendar
class CMagicNumber(n:Int) {
val m:Int = n * n
val a:Int = n * (n * n + 1) / 2
def calc:Int = {
def _calc(p:Int,c:Int,s:Int,r:List[Int],g:Int):Int = r match {
case List() => g + 1
case _ => c match {
case 0 => _calc(r.head,1,r.head,r.tail, g)
case _ => r.filter { d => d > p }.foldLeft(g) { (g,d) =>
((c == n - 1) && (s + d == a)) match {
case true => _calc(0,0,0,r.filter { e => e != d },g)
case _ => (d + s >= a) match {
case true => g
case _ => _calc(d,c + 1,s + d,r.filter { e => e != d },g)
}
}
}
}
}
_calc(0,0,0,(1 to m).toList,0)
}
}
object MagicNumber {
def printTime:Unit = println((new SimpleDateFormat("yyyy/MM/dd HH:mm:ss")).format(Calendar.getInstance.getTime))
def main(args:Array[String]):Unit = {
try {
printTime
printf("result:%d\n",(new CMagicNumber(args.length match { case 1 => args(0).toInt; case _ => 5 })).calc)
printTime
} catch {
case e => e.printStackTrace
}
}
}
|

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 ]