蓝桥杯2019年第十届真题-Fibonacci 数列与黄金分割-题解（C++代码）

2533 阅读 9 评论 0 点赞

原题链接：蓝桥杯2019年第十届省赛真题-Fibonacci 数列与黄金分割

认真分析一下题目
“Fibonacci 数列有一个特殊的性质，前一项与后一项的比值，F[i]/F[i + 1]， 会趋近于黄金分割。”
### 一、思路
**会趋近于黄金分割**
由于这个数据规模1 ≤ N ≤ 2000000000可能会溢出，加上题目说会趋近于黄金分割，我就有个大胆的想法：会不会在某个范围内，得出的结果都不一样，出了这个范围，结果都是一样呢？
然后我就循环计算出前1~50的计算结果
![](/image_editor_upload/20200323032839_22417.png)
通过计算结果可以发现，1~19的计算结果都不一样，但是20以及20之后的计算结果，都是0.61803399，所以可以直接忽略数据精度问题了。
### 二、关于Fibonacci 数列（斐波那契）

```cpp
斐波那契是这样一个数列：0、1、1、2、3、5、8、13、21、34、……（从第三项开始，每一项都是前两项的和），斐波那契数列以如下被以递推的方法定义：F(0)=0，F(1)=1, F(n)=F(n - 1)+F(n - 2)（n ≥ 2，n ∈ N*）
```
**从第三项开始，每一项都是前两项的和**
```cpp
/*
 * 斐波那契数列动态规划法
 * */
double fibo(long n){
    if(n < 1) return -1;
    long F[n + 1];
    F[1] = 1;
    F[2] = 1;
    for (int i = 3; i <= n; ++i) F[i] = F[i - 1] + F[i - 2];
    return F[n];
}
```
动态规划思路：将数列预先缓存进数组里，需要取哪项，取出来即可。

------------

```cpp
/*
 * 斐波那契数列递归法
 * */
double fibo(long n){
    if(n == 1 || n == 2) return 1;
    return fibo(n - 1) + fibo(n - 2);
}
```
不过，展开递归法的递归树，会发现重复了很多子问题，效率太低，不建议使用（但是在此题也足够用）
![](/image_editor_upload/20201214090020_43676.jpg)

------------
### 三、C++保留小数
```cpp
#include <iostream>
#include <iomanip>//引入iomanip头
using namespace std;
int main(){
    double a = 4,b = 3;
    cout << setiosflags(ios::fixed) << setprecision(8) << (a / b) <<endl;//保留八位小数
}
```
setiosflags与setprecision合用，可以控制小数点右边的数字个数。

------------

### ****通过以上推论，可以得到以下代码****

```cpp
#include <iostream>
#include <iomanip>
using namespace std;
double fibo(long n){
    if(n < 1) return -1;
    long F[n + 1];
    F[1] = 1;
    F[2] = 1;
    for (int i = 3; i <= n; ++i) F[i] = F[i - 1] + F[i - 2];
    return F[n];
}
int main(){
    long num;
    cin >> num;
    if (num < 20) cout << setiosflags(ios::fixed) << setprecision(8) << (fibo(num) / fibo(num + 1)) <<endl;//保留八位小数
    else cout << "0.61803399" << endl;
}
```

0.0分

18 人评分

本文分类：题解列表
浏览次数：2533 次浏览
发布日期：2020-03-23 15:32:01
本文链接：https://blog.dotcpp.com/a/68368

上一篇 > 蓝桥杯基础练习VIP-矩阵乘法-题解(C++代码)
下一篇 > 蓝桥杯算法提高VIP-字符串跳步-题解(C语言代码)

C语言网提供由在职研发工程师或ACM蓝桥杯竞赛优秀选手录制的视频教程，并配有习题和答疑，点击了解：

一点编程也不会写的：零基础C语言学练课程

解决困扰你多年的C语言疑难杂症特性的C语言进阶课程

从零到写出一个爬虫的Python编程课程

只会语法写不出代码？手把手带你写100个编程真题的编程百练课程

信息学奥赛或C++选手的必学C++课程

蓝桥杯ACM、信息学奥赛的必学课程：算法竞赛课入门课程

手把手讲解近五年真题的蓝桥杯辅导课程

评论列表共有 9 条评论

三个月仅可修改一次 2年前回复TA

@陌 高精度矩阵快速幂说不定可以（逃）

鼬殇 4年前回复TA

@鼬殇 嗯嗯AC了，谢谢

打不了弟批 4年前回复TA

@鼬殇 把float a[N];改成double a[N];，这是精度问题

鼬殇 4年前回复TA

#include<iostream>
#include<stdio.h>
using namespace std;
const int N = 101;
float a[N];
int n;
int main(){
    cin>>n;
    a[1]=1,a[2]=1;
    for(int i=3;i<=25;i++){
        a[i]=a[i-1]+a[i-2];
    }
    if(n<25){
        printf("%.8f",a[n]/a[n+1]);
    }else{
        cout<<"0.61803399";
    }
    return 0;
}

大佬，我这思路和你一样，为啥错误。。。

鼬殇 4年前回复TA

一样的思路，为啥我的错误。。。。

Goooood 4年前回复TA

牛啊老哥！

小刘 4年前回复TA

nb老哥666

打不了弟批 4年前回复TA

@陌 没想到，会了教我

陌 4年前回复TA

这脑回路。。我就想不到，有没有什么算法可以解决，这有点投机了

蓝桥杯2019年第十届真题-Fibonacci 数列与黄金分割-题解（C++代码）

数位dp#2491: 信息学奥赛一本通T1587-Windy 数(C++)

点进来你会后悔的

简简单单的循环

简单的回文数

评论列表 共有 9 条评论

发表评论 取消回复

评论列表共有 9 条评论

发表评论取消回复