放牧代码和思想
专注自然语言处理、机器学习算法
    时间有限,只有GitHub上的issue能及时处理,大约每周末一次。另外,不要叫我楼主,谢谢。

Google code jam 2008 R1A – Numbers矩阵实现

题目链接在https://code.google.com/codejam/contest/32016/dashboard#s=p2 ,初看此题,第一反应是绝对不会是用浮点数求n次方。随后观察底数,觉得很像高中二项式定理。根据共轭复数(正数)的n次方之和等于一个整数Xn的原理,问题转化为求解Xn。设两个共轭复数的n次方分别为An,Bn,则有Xn=An+Bn,设两个系数求解可以发现Xn=6Xn-1-4Xn-2,有了这个公式,就可以用迭代的思想初步做出解答:

#include <iostream>
#include <iomanip>
using namespace std;
///////////////////////////SubMain//////////////////////////////////

short calculateX(const int &n)
{
	if (n == 0)
	{
		return 2;
	}
	else if (n == 1)
	{
		return 6;
	}
	else
	{
		return (10000 + 6 * calculateX(n - 1) - 4 * calculateX(n - 2)) % 1000;
	}
}

int main(int argc, char *argv[])
{
	freopen("in.txt", "r", stdin);
	freopen("out.txt", "w", stdout);
	int nCases = 0;
	cin >> nCases;
	cin.get();
	for (int i = 0; i < nCases; i++)
	{
		int n = 0;
		cin >> n;
		cout << "Case #" << i + 1 << ": ";
		cout << setfill('0') << setw(3) << calculateX(n) - 1 << endl;
	}
	fclose(stdin);
	fclose(stdout);

	return 0;
}
///////////////////////////End Sub//////////////////////////////////

老实说,写完之后自我感觉良好,厚着脸皮自我感觉代码简洁优雅,每次迭代结果不大于999不会溢出,应该没问题了。但是在跑small的时候就堆栈溢出了,将linker堆栈参数调到最大,依然是StackOverflow。打开任务管理器,好家伙,一个控制台程序吃了一个G的内存,而且程序迭代奇慢无比,瞬间感觉脸红羞愧。

于是思考着将Xn+mXn-1化作等比数列,可惜系数是无理数,如果用浮点数计算后面会产生非常大的误差。这时觉得仅凭高中数学知识没法解决。只好厚着脸皮搜索前人的解法,看到这篇文章http://www.cppblog.com/baby-fly/archive/2009/08/28/94622.html 才茅塞顿开。等比数列解决不了的,就用矩阵吧。我在这篇文章的基础上进行了改进,全部使用2 * 2的矩阵,写出最终的代码:

#include <iostream>
#include <iomanip>
using namespace std;
///////////////////////////SubMain//////////////////////////////////

class CMatrix
{
public:
	int m[4];
	CMatrix(int x1 = 6, int x2 = -4, int x3 = 1, int x4 = 0)
	{
		m[0] = x1;
		m[1] = x2;
		m[2] = x3;
		m[3] = x4;
	}

	CMatrix operator*(const CMatrix & other)
	{
		CMatrix r;
		r.m[0] = (m[0] * other.m[0] + m[1] * other.m[2] + 1000 * 1000) % 1000;
		r.m[1] = (m[0] * other.m[1] + m[1] * other.m[3] + 1000 * 1000) % 1000;
		r.m[2] = (m[2] * other.m[0] + m[3] * other.m[2] + 1000 * 1000) % 1000;
		r.m[3] = (m[2] * other.m[1] + m[3] * other.m[3] + 1000 * 1000) % 1000;
		return r;
	}

	CMatrix power(int n)
	{
		if (n == 1)
		{
			return *this;
		}
		CMatrix temp = this->power(n / 2);
		if (n % 2 == 0)
		{
			
			return temp * temp;
		}
		else
		{
			return temp * temp * *this;
		}
	}
};

int solve(int n)
{
	CMatrix m;
	m = m.power(n - 1) * CMatrix(6, 0, 2, 0);
	return m.m[0] - 1;
}

int main(int argc, char *argv[])
{
	freopen("in.txt", "r", stdin);
	freopen("out.txt", "w", stdout);
	int nCases = 0;
	cin >> nCases;
	cin.get();
	for (int i = 0; i < nCases; i++)
	{
		int n = 0;
		cin >> n;
		cout << "Case #" << i + 1 << ": ";
		cout << setfill('0') << setw(3) << solve(n) % 1000 << endl;
	}
	fclose(stdin);
	fclose(stdout);
	
	return 0;
}
///////////////////////////End Sub//////////////////////////////////

知识共享许可协议 知识共享署名-非商业性使用-相同方式共享码农场 » Google code jam 2008 R1A – Numbers矩阵实现

分享到:更多 ()

评论 欢迎留言

  • 昵称 (必填)
  • 邮箱 (必填)
  • 网址

我的开源项目

HanLP自然语言处理包基于DoubleArrayTrie的Aho Corasick自动机