神奇的数列

[编程题]神奇的数列

热度指数：572 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 32M，其他语言64M
算法知识视频讲解

定义数列 f_n+2 = f_n+1 + f_n，数列中任何一个元素都是正整数。从定义可以看出，不同的f₁、f₂会产生不同的数列。

假设给定一个数字x（2 <= x <= 2³²)，给出这个数字出现在位置i（i >= 3, 数列下标从1开始）的数列个数。

输入描述:

数字x

输出描述:

每行为两个数字，空格分隔，第一个数字为x在数列中的位置i，第二个数字为符合条件的数列个数，即f₁、f₂的组合种数。若存在多行，则按照i由小到大的顺序输出

示例1

输入

输出

3 2
4 1

说明

以下数列包含3，分别为
1 1 2 3 5 ...
1 2 3 5 8 ...
2 1 3 4 7 ...

其中3出现在数列第三位的数列有两个，出现在第四位的数列有一个，因此输出为：
3 2
4 1

算法知识视频讲解

石郎

发表于 2020-07-14 11:10:24

转载自：https://zhuanlan.zhihu.com/p/159238355 首先，我们可以看x在数列的3个位置上出现了多少次，然后再看x在数列4,5......位置上出现了多少次。现在问题变成了如何确定在位置start上出现了多少次呢？想解决这个问题，需要找到斐波那契数列的规律，假展开全文