魔方分割数
Posted feedbacks - C#
N=5のとき、答えは3245664通り。PemmtiumM 1GHz, メモリ768MBのノートPCでは、TimeSpan = 00:03:07.3363606でした。
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 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 | List<List<int>> list = new List<List<int>>();
int counter = 0;
int Solve(int n)
{
List<int> numbers = new List<int>();
for (int i = 0; i < n * n; i++) numbers.Add(i + 1);
int sum = (1 + n * n) * n / 2;
List<int> empty = new List<int>();
MakeList(numbers, empty, sum, n);
Count(numbers, list);
return counter;
}
void MakeList(List<int> src, List<int> dst, int sum, int c)
{
if (c == 1)
{
if (src.Contains(sum))
{
dst.Add(sum);
list.Add(dst);
}
return;
}
for (int i = 0; i < src.Count; i++)
{
List<int> src2 = src.GetRange(i + 1, src.Count - i - 1);
List<int> dst2 = dst.GetRange(0, dst.Count);
dst2.Add(src[i]);
MakeList(src2, dst2, sum - src[i], c - 1);
}
return;
}
void Count(List<int> s, List<List<int>> src)
{
for (int i = 0; i < src.Count; i++)
{
List<int> s2 = s.GetRange(0, s.Count);
src[i].ForEach(delegate(int n) { s2.Remove(n); });
if (s2.Count == 0)
{
counter++;
}
else
{
List<List<int>> src2
= src.GetRange(i + 1, src.Count - i - 1)
.FindAll(delegate(List<int> l)
{
return !l.Exists(delegate(int n)
{
return src[i].Contains(n);
});
});
Count(s2, src2);
}
}
}
|
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 ]