[每日一题] 64. 斐波那契凤尾(fib数列、setw与setfill函数)

数列、setw与setfill函数)"/>

[每日一题] 64. 斐波那契凤尾(fib数列、setw与setfill函数)

1. 题目来源

链接：斐波那契凤尾
来源：牛客网

2. 题目说明

NowCoder号称自己已经记住了1-100000之间所有的斐波那契数。
为了考验他，我们随便出一个数n，让他说出第n个斐波那契数。当然，斐波那契数会很大。因此，如果第n个斐波那契数不到6位，则说出该数；否则只说出最后6位。

输入描述：

输入有多组数据。
每组数据一行，包含一个整数n (1≤n≤100000)。

输出描述：

对应每一组数据，输出在给定的日期范围（包含开始和结束日期）内能赚多少钱。

示例：

输入
1
2
3
4
100000
输出
62
29

3. 题目解析

题目要求输出斐波那契数列的第n项，最容易写的方法就是用循环求出每一项了。而它要求的是后六位，那么我们 只需要存储后六位就行了。在此先求斐波那契数列在100000以内的每一项的后六位，然后需要的时候直接输出数组里的对应值即可。
以下代码用通常的循环法解决。值得注意的一点，C++在输出位数上的设置要用到C++的两个输出控制，setw(位数)，和setfill(指定字符)。

4. 代码展示

// write your code here cpp
#include <bits/stdc++.h>using namespace std;int main() {int fib[100001];fib[0] = 1;fib[1] = 1;// 提前计算斐波那契数列，只保留后6位for (int i = 2; i <= 100000; ++i) {fib[i] = fib[i - 1] + fib[i - 2];fib[i] = fib[i] % 1000000;  // 由于只是相加，所以只要后六位不影响下一个数的结果}int n;while (cin >> n) {if (n < 29)cout << fib[n] << endl;else// printf("%06d\n", fib[n]);cout << setw(6) << setfill('0') << fib[n] <<  endl;}return 0;
}