315题:“更省电”的电子表

综合编程 guozi

原题链接: https://projecteuler.net/problem=315

这个题目比较长,下面简单描述一下。

有一个数字表,显示数字的方式可以看原题,其实是老式计算器那个样子,也像小时候做的奥数题,拿火柴棍摆正正方方的数字。给它一个输入,比如说137,首先它会显示137,然后计算137各个数字之和,得到11,然后显式11,再计算得到2,显示2。

显示数字或者是不显示,都需要一次转换,比如显示4,要4次转换,比如显示8然后什么都不显示,需要7次转换。

Sam的表显示的方式很直接:比如输入137,显示137,再关掉,一共需要(2 + 5 + 4) × 2 = 22次转换,137各个数字之和是11,显示11再关掉,(2 + 2) × 2 = 8次转换,最后的数字2,需要(5) × 2 = 10次转换。一共需要40次转换。

Max的表稍微智能一点:

比如137变成11的时候,3和1是有公共部分的,7和1也是有公共部分的,那么在关掉137的时候,对应下个数字的地方就不关掉了,显示下一个数字的时候就不需要再打开,用此方法较少转换的次数。

打开137,2 + 5 + 4 = 11次转换,关掉的时候,11的那4个地方不关闭,那么关闭需要7次转换;显示11不需要打开了,关闭11显示2,第二个1的右上角那一个也不要关闭,所以关闭11需要3次转换,打开2,只需要4次转换而不是5次,关闭2需要5次转换。总共需要30次转换。

相比Sam的少了10次。

题目的输入是10 ^ 7 和 2 * 10 ^ 7之间的所有质数,求省下来的转换次数。

其实这个题目看似很难,如果找对了关键点,其实很简单。

所谓省下来的次数,就是2个数字直接重叠的那一部分,比如0和8重叠就是整个0,6条边,2和4就重叠了两条边。

于是乎,我写了一个二维数组表示任意两个数字之间的重叠个数。

private static int[,] Overlap = new int[10, 10]
{
	{ 6,2,4,4,3,4,5,4,6,5},
	{ 2,2,1,2,2,1,1,2,2,2},
	{ 4,1,5,4,2,3,4,2,5,4},
	{ 4,2,4,5,3,4,4,3,5,5},
	{ 3,2,2,3,4,3,3,3,4,4},
	{ 4,1,3,4,3,5,5,3,5,5},
	{ 5,1,4,4,3,5,6,3,6,5},
	{ 4,2,2,3,3,3,3,4,4,4},
	{ 6,2,5,5,4,5,6,4,7,6},
	{ 5,2,4,5,4,5,5,4,6,6}
};

万一认为计算的时候搞错了呢?我又搞了个函数检查一下,我把数字的边从上到下,从左到右编号。比如数字1的两条边就是3,6,数字7的边就是1,2,3,6。然后计算数字的重叠部分,看看和我手写的矩阵是否一致。我第一遍运算的时候,还真发现矩阵里面的一个错误。

private static void Check()
{
	var digital = new List<list>();
	digital.Add(new List() { 1, 2, 3, 5, 6, 7 });
	digital.Add(new List() { 3, 6 });
	digital.Add(new List() { 1, 3, 4, 5, 7 });
	digital.Add(new List() { 1, 3, 4, 6, 7 });
	digital.Add(new List() { 2, 3, 4, 6 });
	digital.Add(new List() { 1, 2, 4, 6, 7 });
	digital.Add(new List() { 1, 2, 4, 5, 6, 7 });
	digital.Add(new List() { 1, 2, 3, 6 });
	digital.Add(new List() { 1, 2, 3, 4, 5, 6, 7 });
	digital.Add(new List() { 1, 2, 3, 4, 6, 7 });
	for (int i = 0; i < 10; i++)
	{
		for (int j = 0; j < 10; j++)
		{
			int overlap = digital[i].Intersect(digital[j]).Count();
			if (overlap != Overlap[i, j])
			{
				Console.WriteLine(i + "t" + j + "t" + overlap);
			}
		}
	}
}</list

接着往下想,给两个数字,比如137和11,如何得到重叠部分呢?很简单,从最后一位开始比就可以了,最后一位的两个数字,去查矩阵,很容易得到重叠的值,然后再考察倒数第二位。。。代码如下:

private static int GetCount(int num1, int num2)
{
	int count = 0;

	while (num1 > 0 && num2 > 0)
	{
		count += Overlap[num1 % 10, num2 % 10];
		num1 /= 10;
		num2 /= 10;
	}

	return count;
}

能够比较两个数字了,那么给定要给输入,一个几百万大的质数,求各个数字之后,对比两个数字之间的重叠值,然后再计算数字之和的数字之和,再对比重叠值,循环到个位数即可。

private static int GetCount(int p)
{
	int count = 0;
	while (p >= 10)
	{
		int sum = p.ToString().Select(c => c-'0').Sum();
		count += GetCount(p, sum);
		p = sum;
	}

	return count * 2;
}

为什么要乘以2呢?因为从第一个数字过渡到第二个数字,比如11到2,重叠部分是1,关闭11的时候可以少关闭1,显示2的时候又可以少打开1,所有要乘以2。

万事俱备,最后,拿到10 ^ 7 和 2 * 10 ^ 7之间的所有质数,遍历求和即可。

public static int GetAnswer()
{
	Check();

	int count = 0;
	var primes = Utils.GenPrimes(20000000).Where(p => p > 10000000);

	foreach (var p in primes)
	{
		count += GetCount((int)p);
	}

	return count;
}
稿源:guozi (源链) | 关于 | 阅读提示

本站遵循[CC BY-NC-SA 4.0]。如您有版权、意见投诉等问题,请通过eMail联系我们处理。
酷辣虫 » 综合编程 » 315题:“更省电”的电子表

喜欢 (0)or分享给?

专业 x 专注 x 聚合 x 分享 CC BY-NC-SA 4.0

使用声明 | 英豪名录