challenge 魔方分割数

1 .. N^2までの数をN個の数字の和が等しいN個のグループに分けたいと思います。

たとえば、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 }は同じもの
とすることに注意してください。

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
        }
    }
}

Index

Feed

Other

Link

Pathtraq

loading...