2018安徽大学计算机机试1

2018安徽大学计算机机试1

问题描述

给定一个函数：
F(0)=0;
F(1)=1;
F(n)=F(n-1)+F(n-2),n>1
程序输入一个整数n，0 < n<100000,输入F(n)的值，结果对854562545取余。

解决思路

可以用递归的方法进行迭代相加，但由于数据比较大，用递归调用函数栈会消耗大量时间，所以用循环迭代相加的方式代替递归。

代码

语言：c

#include<stdio.h>
int main()
{long i,n,f1,f,f0;f0=0;f1=1;scanf("%ld",&n);if(n==0){printf("0n");return 0;}if(n==1){printf("1n");return 0;}for(i=2;i<=n;i++){f=(f0+f1)%854562545;f0=f1;f1=f;}
printf("%ldn",f);
return 0;
}