一点一点前进...

0%

欧拉项目 | 题目61 | 找出唯一具有循环性质的6个四位数定形数集合的元素和

发表于 分类于 ， Disqus：

题目如下：

三角形数，四角形数，五角形数，六角形数，七角形数和八角形数都是定形数，他们分别由以下公式产生：
三角形数 P3,n=n(n+1)/2 1, 3, 6, 10, 15, …
四角形数 P4,n=n2 1, 4, 9, 16, 25, …
五角形数 P5,n=n(3n−1)/2 1, 5, 12, 22, 35, …
六角形数 P6,n=n(2n−1) 1, 6, 15, 28, 45, …
七角形数 P7,n=n(5n−3)/2 1, 7, 18, 34, 55, …
八角形数 P8,n=n(3n−2) 1, 8, 21, 40, 65, …

三个四位数形成的有序集合: 8128, 2882, 8281,有三个有趣的性质：

这个集合是循环的：每个数的后两位数是下一个数的前两位数，包括第三个和第一个的关系。
三种定形数中的每一种都能被这三个数中的一个不同的数代表：三角形数 (P3,127=8128), 四角形数 (P4,91=8281), 和五角形数 (P5,44=2882)。
这是唯一具有以上性质的四位数的集合。

找出唯一的一个六个四位数的循环集合，使得从三角形数到八角形数中的每一种都能由该集合中的一个不同的数代表。

求这个集合中元素之和。

首先，我们应该初始化这六个数组。同时排除倒数第二位为0的数字，因为这种数不可能在循环集合里面（不可能有数字以0开始）。

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
private static void Initialize(
	out List<int> P3, out List<int> P4, out List<int> P5,
	out List<int> P6, out List<int> P7, out List<int> P8)
{
	P3 = new List<int>();
	P4 = new List<int>();
	P5 = new List<int>();
	P6 = new List<int>();
	P7 = new List<int>();
	P8 = new List<int>();
	int n = 1;
	while (true)
	{
		if (n * (n + 1) / 2 > 10000)
		{
			break;
		}

		P3.Add(n * (n + 1) / 2);
		P4.Add(n * n);
		P5.Add(n * (3 * n - 1) / 2);
		P6.Add(n * (2 * n - 1));
		P7.Add(n * (5 * n - 3) / 2);
		P8.Add(n * (3 * n - 2));

		n++;
	}

	P3 = P3.Where(Meet).ToList();
	P4 = P4.Where(Meet).ToList();
	P5 = P5.Where(Meet).ToList();
	P6 = P6.Where(Meet).ToList();
	P7 = P7.Where(Meet).ToList();
	P8 = P8.Where(Meet).ToList();
}

private static bool Meet(int i)
{
	if (i <= 1000 || i >= 10000)
	{
		return false;
	}

	if ((i / 10) % 10 == 0)
	{
		return false;
	}

	return true;
}

循环集合，不管最终的数字顺序是怎么样的，都可以看作是从P3开始，最后循环到P3。当然，你也可以从P4什么的开始，都一样的。
我的思路是遍历P3数组，然后再遍历其他的数组，若P3里面数字的后两位等于其他数组中的前两位，就把他们拼接起来组成新的集合M1，M1中都是可能的解。
再接着，遍历M1和剩余数组，这里剩余数组指的是排除P3和某个数组之后的其他数组。比如第一次遍历P4的某个数拼接在P3的某个数后面，那么这里的剩余数组就是指P5，P6，P7和P8。和第一次遍历一样，继续拼接可能的字符串，组成集合M2。
以此类推。最后，每个数组贡献一个数字，拼接成了一个满足题意的字符串。

为了能知道在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
private class OrderedSet : ICloneable
{
	public OrderedSet(string content)
	{
		this.Content = content;
	}

	public string Content { get; set; }
	public bool Has4 { get; set; }
	public bool Has5 { get; set; }
	public bool Has6 { get; set; }
	public bool Has7 { get; set; }
	public bool Has8 { get; set; }

	public object Clone()
	{
		OrderedSet other = new OrderedSet(this.Content);
		other.Has4 = this.Has4;
		other.Has5 = this.Has5;
		other.Has6 = this.Has6;
		other.Has7 = this.Has7;
		other.Has8 = this.Has8;

		return other;
	}
}

我把P3的数组扔到一个队列中，作为循环的初始：

1
2
3
4
5
Queue<OrderedSet> cur = new Queue<OrderedSet>();
foreach (var i in P3)
{
	cur.Enqueue(new OrderedSet(i.ToString()));
}

然后进行五次遍历，把P4到P8五个数组拼接到后面，代码有点丑。。。

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
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
for (int i = 0; i < 5; i++)
{
	Queue<OrderedSet> next = new Queue<OrderedSet>();

	foreach (var orderedSet in cur)
	{
		if (!orderedSet.Has4)
		{
			foreach (var j in P4)
			{
				if (orderedSet.Content.EndsWith(j.ToString().Substring(0, 2)))
				{
					OrderedSet other = (OrderedSet)orderedSet.Clone();
					other.Content = orderedSet.Content + j.ToString().Substring(2, 2);
					other.Has4 = true;
					next.Enqueue(other);
				}
			}
		}

		if (!orderedSet.Has5)
		{
			foreach (var j in P5)
			{
				if (orderedSet.Content.EndsWith(j.ToString().Substring(0, 2)))
				{
					OrderedSet other = (OrderedSet)orderedSet.Clone();
					other.Content = orderedSet.Content + j.ToString().Substring(2, 2);
					other.Has5 = true;
					next.Enqueue(other);
				}
			}
		}

		if (!orderedSet.Has6)
		{
			foreach (var j in P6)
			{
				if (orderedSet.Content.EndsWith(j.ToString().Substring(0, 2)))
				{
					OrderedSet other = (OrderedSet)orderedSet.Clone();
					other.Content = orderedSet.Content + j.ToString().Substring(2, 2);
					other.Has6 = true;
					next.Enqueue(other);
				}
			}
		}

		if (!orderedSet.Has7)
		{
			foreach (var j in P7)
			{
				if (orderedSet.Content.EndsWith(j.ToString().Substring(0, 2)))
				{
					OrderedSet other = (OrderedSet)orderedSet.Clone();
					other.Content = orderedSet.Content + j.ToString().Substring(2, 2);
					other.Has7 = true;
					next.Enqueue(other);
				}
			}
		}

		if (!orderedSet.Has8)
		{
			foreach (var j in P8)
			{
				if (orderedSet.Content.EndsWith(j.ToString().Substring(0, 2)))
				{
					OrderedSet other = (OrderedSet)orderedSet.Clone();
					other.Content = orderedSet.Content + j.ToString().Substring(2, 2);
					other.Has8 = true;
					next.Enqueue(other);
				}
			}
		}
	}

	cur = next;
}

好了，离胜利还有两步了。
第一步，遍历cur集合中的字符串，根据题目要求，最后两位和开头两位是相等的：

1
2
3
4
5
6
7
8
List<string> results = new List<string>();
foreach (var orderedSet in cur)
{
	if (orderedSet.Content.Substring(0, 2).Equals(orderedSet.Content.Substring(12, 2)))
	{
		results.Add(orderedSet.Content);
	}
}

题目已经告诉我们结果是唯一的了，这时，results集合里面应该只有一个元素。
最后一步，得到了这六个数字，求和即可。