xtu oj 1171 Coins

2023-12-16 17:09:50
题目描述

一个均质硬币抛n次,求不存在连续2次为正面的方案数。

输入

每行一个正整数n,n≤40。如果n为0,表示输入结束,不需要处理。

输出

每行输出一个结果,为一个整数。

样例输入
1
2
3
0

样例输出
2
3
5

AC代码

#include<stdio.h>
int dp[45][2]={};//dp[i][0]表示第i次为正面的情况数 
void init(){
	dp[1][0]=1,dp[1][1]=1;
	int i;
	for(i=2;i<=40;i++){
		dp[i][0]=dp[i-1][1];
		dp[i][1]=dp[i-1][0]+dp[i-1][1];
	} 
}
int main(){
	int n;
	init();
	while(scanf("%d",&n)!=EOF){
		if(n==0)break;
		printf("%d\n",dp[n][0]+dp[n][1]);
	}
} 

解题思路:动态规划问题,找规律即可。

或者用循环解决

AC代码

#include<stdio.h>
int f(int n){
	int x=1,y=1;//x正面 ,y反面
	int i,a;
	for(i=2;i<=n;i++){
		a=x;
		x=y;
		y=a+y;
	}
	return x+y;
}
int main()
{
	int n;
	while(scanf("%d",&n)!=EOF){
		if(n==0)break;
		printf("%d\n",f(n));
	} 
}

可以参考前面1331密码这道题,或者前面1354Robot这道题

文章来源:https://blog.csdn.net/m0_75005390/article/details/135033243
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。