文章

36

粉丝

505

获赞

55

访问

370.6k

头像
题解:骨牌铺方格
P1029 重庆大学机试题
发布于2020年2月23日 18:42
阅读数 11.8k

有一排格子,我们从左向右码放骨牌。

由于当前可以码放的骨牌是由前一格或者前两格或者前三格的码放方式决定。

那么可以得出来公式:F(n)=F(n-1)+f(n-2)+f(n-3)(变种斐波那契数列?)

F(1)=1,F(2)=2,F(3)=4

那么很容易写出递归代码,这里还用了记忆搜索算法,就是定义一个用来记答案的数组remember[],用来避免重复计算某一F(n)而导致效率很慢

#include<iostream>
using namespace std;
long long remember[1024];
long long f(int i)
{
	if (remember[i])return remember[i];//记忆,提高运行效率,避免重复运算
	if (i == 1)return 1;
	if (i == 2)return 2;
	if (i == 3)return 4;
	return remember[i]=f(i - 1) + f(i - 2) + f(i - 3);
}
int main()
{
	long long ans[1024];//开long long是怕爆
	int n, k = 0;
	do
	{
		cin >> n;
		ans[k++] = f(n);
	} while (n != 0);
	for (int i = 0; i < k - 1; i++)
		cout << ans[i] << endl;
	return 0;
}

 

登录查看完整内容


登录后发布评论

暂无评论,来抢沙发