Fibonacci and Counting（水题）

链接：https://ac.nowcoder.com/acm/contest/303/B

来源：牛客网

时间限制：C/C++ 1秒，其他语言2秒

空间限制：C/C++ 262144K，其他语言524288K

64bit IO Format: %lld

题目描述

我们这样定义斐波那契数列，F[1]=1,F[2]=1，当n>2时F[n]=F[n-1]+F[n-2]。

斐波那契数列的前10项为：1,1,2,3,5,8,13,21,34,55。

欧几里得算法求解两个数的最大公约数。我们记gcd(a,b)为整数a与b的最大公约数。

当b=0时，gcd(a,0)=a，否则gcd(a,b)=gcd(b,a%b)。其中%为取余运算。

在算法设计中，求解两个数字公约数的函数往往使用递归进行运算。

我们现在定义count(a,b)为a,b两个整数在使用欧几里得算法求解最大公因数时的递归次数。

例如count(4,8)=3，运算过程如下：

第一次调用gcd函数时进入gcd(4,8)，参数b不为0，所以递归进入gcd(8,4)。

进入gcd(8,4)为函数的第二次调用，参数b不为0，所以递归进入gcd(4,0)。

进入gcd(4,0)为函数的第三次调用，参数b=0。所以递归达到终点，停止递归。

在运算gcd(8,4)时共计进行了3次运算，所以count(8,4)=3。

现在给定一个正整数x，小w想要知道count(F(x),F(x+1))的值，你能告诉他么？

输入描述:

第一行输入一个正整数T(T≤1000)，表示有T组数据。

接下来T行，每行输入一个正整数x(1≤x≤1000000000)。

输出描述:

对于每组数据，依次输出一行一个正整数表示count(F(x),F(x+1))

示例1

输入

复制

输出

复制

题解：不太明白为什么会是这样的规律，只是看数据试了一下

代码：

#include<cstdio>

#include<cstring>

#include<algorithm>

#include<iostream>

using namespace std;

int main()

{

	int N;

	cin>>N;

	int n;

	for(int t=0;t<N;t++)

	{

	   scanf("%d",&n);

	   cout<<n+1<<endl;

	}

	return 0;

}

巴特西

Fibonacci and Counting（水题）

题目描述

输入描述:

输出描述:

输入

输出

最新文章

热门文章