备战蓝桥杯！加油🙌

蓝桥杯-入门训练 Fibonacci数列

问题描述
Fibonacci数列的递推公式为：Fn=Fn-1+Fn-2，其中F1=F2=1。

当n比较大时，Fn也非常大，现在我们想知道，Fn除以10007的余数是多少。

说明：在本题中，答案是要求Fn除以10007的余数，因此我们只要能算出这个余数即可，而不需要先计算出Fn的准确值，再将计算的结果除以10007取余数，直接计算余数往往比先算出原数再取余简单。

样例输入
22

样例输出
7704

数据规模与约定
1 <= n <= 1,000,000。

---

有关Fibonacci数列的题目，瞬间想到要用递归，二话不说直接上手写了提交。然后就运行超时了，虽然是第一题，貌似也没那么简单。

以下是我的原本代码，外加 GetTickCount 来测试使用时间，结果看底下图片。

//运行环境VS2013
#include <iostream>
#include <Windows.h>
using namespace std;
DWORD t1, t2;
long long fibonacci(long long n)
{
    if (n == 1 || n == 2) return 1;
    else return fibonacci(n - 1) + fibonacci(n - 2);
}
int main()
{
    while (1)
    {
        int n;
        cout << "Cin>>";
        cin >> n;
        t1 = GetTickCount();
        cout << "The result : " << int(fibonacci(n) % 10007) << endl;
        t2 = GetTickCount();
        cout << "Spend time: " << t2 - t1 << " ms" << endl;
    }
    system("pause");
    return 0;
}

运行结果：

当我随机输入到44时，耗费时间长达16s😭。当然题目直接就说了不需要推算出这个值再计算它的余数，当n越大时，Fibonacci值越大，外加递归肯定耗费时间。

本题核心算法

Fn = F(n-1) + F(n-2);

Fn % 10007 = (F(n-1) + F(n-2)) % 10007;

一目了然，然后使用数组存取计算的值，省的使用递归一遍遍计算了。

更新代码：

//运行环境VS2013
#include <iostream>
using namespace std;
int main()
{
    int n, i;
    cout << "Cin>>";
    cin >> n;
    int f[1000000];//这里VS2013不会通过，注意该小点
    f[1] = f[2] = 1;
    for (i = 3; i <= n; i++)
    {
        f[i] = (f[i - 1] + f[i - 2]) % 10007;
    }
    cout << "The result : " << f[n] << endl;
    return 0;
}

当输入值较大时运行时间还是很快的。

本题感悟

1. 要多注意题目提示，注意题目给出的数据规模。

2. 当遇到类似Fibonacci数列反复使用前面的值时，使用数组存取。

蓝桥杯-入门训练 圆的面积

本题目主要考察使用C++头文件iomanip来控制输出精度。题目专门提到四舍五入保留7位小数。

本题要点

iomanip的应用

• setiosflags(ios::fixed) 设置浮点数以固定的小数位数显示。

• setiosflags(ios::scientific) 设置浮点数以科学计数法的形式（指数）显示。

• setprecision(n) 设置浮点数的精度为n位。使用一般十进制输出时，n代表有效数字。而使用上面的fixed或者scientific形式输出时，n为小数的个数。

• 当然这些会自动四舍五入。

参考链接： C++ iostream 输入输出流格式控制

程序示例

#include <iostream>
#include <iomanip>
using namespace std;
int main()
{
    double a = 3.123456971261;
    cout << a << endl;//3.12346。  默认格式输出（6位有效数字）
    cout<<setprecision(4)<<a<<endl;//3.123。  4位有效数字
    cout<<setiosflags(ios::fixed)<<setprecision(5)<<a<<endl;//3.12346。  5位小数部分
    cout<<fixed<<setprecision(5)<<a<<endl;//3.12346。  5位小数部分。与上一部同样的表示
    cout<<setiosflags(ios::scientific)<<setprecision(2)<<a<<endl;
    return 0;
}

蓝桥杯-入门训练 序列求和

问题描述：

求1+2+3+…+n的值。

数据规模与约定

1 <= n <= 1,000,000,000。

本题要点

1. 这里显然要使用等差数列的求和公式。 Sn = n*a1 + n*(n-1)*d/2

2. 同时由于数据规模非常大，int类型是无法存储的（int类型一般最大是2^31-1 大约2亿的一个值)。所以结果要使用long long类型。

3. int类型的值采用求和公式计算，其结果永远都只能是int类型，不可能越变到long long型。