洛谷刷题_P1255 数楼梯

题目

P1255 数楼梯

题目链接

https://www.luogu.com.cn/problem/P1255

知识点

斐波那契数列

斐波那契数列指的是这样一个数列：1、1、2、3、5、8、13、21、34、……，在数学上，斐波那契数列以如下被以递推的方法定义：F(0)=0，F(1)=1, F(n)=F(n - 1)+F(n - 2)（n ≥ 2，n ∈ N*）

题解

这道题先算一下前几阶楼梯的走法

• 1阶：1种走法，就是1；
• 2阶：2种走法，分别是1 1，2；
• 3阶：3种走法，分别是1 1 1，1 2，2 1；
• 4阶：5种走法，分别是1 1 1 1，1 2 1，2 1 1，1 1 2，2 2；

可以发现，它就是一个斐波那契数列。

首先尝试：

#include <stdio.h>
int main ()
{
	int n;
	int a=1,b=2,c=0;
	scanf("%d",&n);
	for(int i=3;i<=n;i++)
	{
		c=a+b;
		a=b;
		b=c;
	}
	printf("%d",c);
	return 0;
}

发现只有30分，看了N的范围是1≤N≤5000。猜想可能后面的数会很大，再用long long的类型试一下。

#include <stdio.h>
int main ()
{
	int n;
	long long a=1,b=2,c=0;
	scanf("%d",&n);
	for(int i=3;i<=n;i++)
	{
		c=a+b;
		a=b;
		b=c;
	}
	printf("%lld",c);
	return 0;
}

变成40了，看样子就是数据范围的问题。long long还不够的话应该是就是要用到高精度了。

final code:

#include<stdio.h>
#include<cstring>
int a[5005],b[5005],c[5005];
int len=1,n=1;
void Fibo()
{
	a[1]=1,b[1]=2;
	for(int i=3;i<=n;i++)
	{
		for(int j=1;j<=len;j++)
		{
			c[j]=a[j]+b[j];
		}
		for(int j=1;j<=len;j++)
		{
			if(c[j]>9)
			{
				c[j+1]+=c[j]/10;
				c[j]=c[j]%10;
				if(j+1>len) len++;
			}
		}
		for(int j=1;j<=len;j++) a[j]=b[j];
		for(int j=1;j<=len;j++) b[j]=c[j];
	}	
}
int main ()
{
	memset(a,0,sizeof(a));
	memset(b,0,sizeof(b));
	memset(c,0,sizeof(c));
	scanf("%d",&n);
	if(n<3)
	{
		printf("%d",n);
		return 0;
	}
	Fibo();
	for(int i=len;i>0;i--)
	{
		printf("%d",c[i]);
	}
	return 0;	
}

参考文章

https://blog.csdn.net/qq_41857193/article/details/79686852