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
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。 如若内容造成侵权/违法违规/事实不符,请联系我的编程经验分享网邮箱:veading@qq.com进行投诉反馈,一经查实,立即删除!
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。 如若内容造成侵权/违法违规/事实不符,请联系我的编程经验分享网邮箱:veading@qq.com进行投诉反馈,一经查实,立即删除!