Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Password:
  Register

直接计算斐波那契数列

Posted by ycdoit at 2011-09-10 12:59:35 on Problem 2033 and last updated at 2011-09-10 13:00:38
下面,考察一下1111..有一种组合数目。按照最后两位是否是结合的分成两类。比如11可以分成1_1,可以单独当成11。前者属于非结合,后者属于结合。

编码		1	11	111	1111
最后两位结合	0	1	1	2
最后两位非结合	1	1	2	3
总组合数	1	2	3	5
总数刚好是一个斐波那契数列。为什么呢?很简单,当前最后两位组合的数目必定等于上一次非组合的数目,而这次非组合的数目,等于上次两种情况之和。
所以结果呈现的刚好是斐波那契数列。

111118111,被8分成两堆,分别计算111118和111的斐波那契数,相乘就可以。
对于 111128111,就不一样咯,那个28是非法的,故要分成11112,8,111的斐波那契数。同样相乘就可以。
对于11110,我们初始化的时候,就把0前面的1以及自身一起做个标志,比如设为一个特殊字符。这样检测到的时候,直接跳过。

#include <iostream>
#include <cstring>
#include <cstdio>
using namespace std;


const int MaxN = 80;
 __int64 a[MaxN];
void Init()
{
	a[1] = 1;
	a[2] = 2;
	int i;
	for (i = 3; i < MaxN; ++i)
		a[i] = a[i - 2] + a[i - 1];
}

int main()
{

	Init();
	char str[5000];
	__int64 res;
	int i, j, len;
	while (cin >> str, str[0] != '0')
	{
		res = 1;
		len = strlen(str);
		for (i = 0; i < len; ++i)
			if (str[i] == '0')
				str[i-1] = str[i] = 1;
		
		for (i = 0; i < len; ++i)
		{
			if (str[i] > '2' || str[i] == 1)	continue;
			
			for (j = i + 1; j < len && str[j] <= '2' && str[j] != 1; ++j);
			if (j == len || str[j] == 1)	--j;
			else if (str[j] > '6')
			{
				if (str[j-1] == '2')		--j;
			}
			res *= a[j - i + 1];
			i = j;
		}
		cout << res << endl;
	}
	
	return 0;
}

Followed by:

Post your reply here:
User ID:
Password:
Title:

Content:

Home Page   Go Back  To top


All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator