杭电OJ——1041 Computer Transformation

发布时间：2020-12-14 04:06:08 所属栏目：大数据来源：网络整理

导读：Computer Transformation Problem Description A sequence consisting of one digit,the number 1 is initially written into a computer. At each successive time step,the computer simultaneously tranforms each digit 0 into the sequence 1 0 and eac

Computer Transformation

Problem Description

A sequence consisting of one digit,the number 1 is initially written into a computer. At each successive time step,the computer simultaneously tranforms each digit 0 into the sequence 1 0 and each digit 1 into the sequence 0 1. So,after the first time step,the sequence 0 1 is obtained; after the second,the sequence 1 0 0 1,after the third,the sequence 0 1 1 0 1 0 0 1 and so on.?

How many pairs of consequitive zeroes will appear in the sequence after n steps??

Input

Every input line contains one natural number n (0 < n ≤1000).

Output

For each input n print the number of consecutive zeroes pairs that will appear in the sequence after n steps.

Sample Input

2
3

Sample Output

1
1

Source

Southeastern Europe 2005

Recommend

JGShining

1?题目意思很明确：step 0：1

step 1：01
step 2：1001
step 3：0110 1001
step 4：1001 0110 0110 1001
step 5：0110 1001 1001 0110 1001 0110 0110 1001...通过自己推算，我们可以发现规律：从4开始，第n串中00的来源主要有两部分：
1. 第n-2串中00的数目
2. 第n-2串中1的数目而第n串中1的数目=2^(n-1)
因此，递推公式为：

C(n)=C(n-2)+2^(n-3) 其中n>=4。

?其中用到了大数的处理，整体来说不难！我们先打表，之后再输出即可！话说这杭电第一页上的题目怎么有那么多水题，受不了了，下一次做一点有技巧性的题目吧！

代码如下：

#include <iostream>
#include <string>
using namespace std;
const int SIZE = 1001;
const int BASE = 10;
string result[SIZE];
string two("2");

void initial()
{
	int mcarry,temp,carry;
	int k;
	string tempResult;
	result[1] = "0";
	result[2] = "1";
	result[3] = "1";
	result[4] = "3";
	for (int i = 5; i < SIZE; ++i)
	{
		mcarry = 0;
		for (int j = 0; j < two.length(); ++j)  /*先做乘法,求出2^(n-3)*/
		{
			temp = 2 * (two[j] - '0') + mcarry;
			mcarry = temp / BASE;  /*乘法进位*/
			temp = temp % BASE;    
			tempResult += (temp + '0');
		}
		if (mcarry != 0)  /*进位不为0*/
		{
			tempResult += (mcarry + '0');
		}

		two = tempResult;  /*存储计算结果*/
		tempResult.clear();

		int minLength = two.length() > result[i - 2].length() ?  result[i - 2].length() : two.length();
		carry = 0;

		for (k = 0; k < minLength; ++k)   /*然后做加法f(n) = f(n -2) + 2^(n - 3)*/
		{
			temp = (two[k] - '0') + (result[i - 2][k] - '0') + carry;
			carry = temp / BASE;  /*加法进位*/
			temp = temp % BASE;
			result[i] += (temp + '0');
		}
		/*两个数可能长短不一,所以要比较再相加*/
		if (minLength < two.length())
		{
			for(; k < two.length(); k++)
			{
				temp = (two[k] - '0') + carry;
				carry = temp / BASE;
			    temp = temp % BASE;
			    result[i] += (temp + '0');
			}
		}
		if(minLength < result[i - 2].length())
		{
            for(; k < result[i - 2].length(); ++k)
			{
				temp = (result[i - 2][k] - '0') + carry;
				carry = temp / BASE;
			    temp = temp % BASE;
			    result[i] += (temp + '0');
			}
		}
		if (carry != 0)   /*进位不为0*/
		{
			result[i] += (carry + '0');
		}
		tempResult.clear();
	}
}
int main()
{
	int n;
	initial();  /*先打表*/
	while (scanf ("%d",&n) != EOF)
	{
		for(int i = result[n].length(); i > 0; --i)
		cout << result[n][i - 1];   /*这一步很关键，由于数据是倒着存的,所以要反着输出*/
		cout << endl;
	}
	system ("pause");
	return 0;
}

（编辑：李大同）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!