首页 > 试题广场 >

斐波那契

[编程题]斐波那契
  • 热度指数：270 时间限制：C/C++ 1秒，其他语言2秒 空间限制：C/C++ 256M，其他语言512M
  • 算法知识视频讲解
\,\,\,\,\,\,\,\,\,\,小红特别喜欢斐波那契数列，所以他想问你，在前 个斐波那契数中（保证 n \leq 66），谁包含数位 的次数最多（如果有多个就输出最小的）。
\,\,\,\,\,\,\,\,\,\,

\,\,\,\,\,\,\,\,\,\,我们定义斐波那契数列如下：\operatorname{Fib}_n = \begin{cases}<br />1&1\le n \le 2\\<br />\operatorname{Fib}_{n-1}+\operatorname{Fib}_{n-2}&3 \le n<br />\end{cases} ，第 i 个斐波那契数即 {\rm Fib}_i 。
\,\,\,\,\,\,\,\,\,\,例如，前 个斐波那契数为 ，包含数位 的次数最多的为 （包含 次）。

输入描述:
\,\,\,\,\,\,\,\,\,\,在一行上输入两个整数 n,k \left( 1\le n \le 66;\ 0\le k \le 9\right) 。


输出描述:
\,\,\,\,\,\,\,\,\,\,在一行上输出一个整数，代表最小的包含数位 k 最多的斐波那契数。保证一定存在这样的数字。
示例1

输入

5 2

输出

2

说明

该样例已在题目中加以解释。
示例2

输入

30 6

输出

6765

说明


备注:
算法知识视频讲解
添加回答
C++
牛客925889402号头像 牛客925889402号
#include <iostream>
#include <vector>
#include <string>
using namespace std;

int main()
{
    int n, k;
    cin >> n >> k;

    vector<long long> fib(n);
    fib[0] = 1;
    if(n > 1)
    {
        fib[1] = 1;
    }
    for(int i = 2; i < n; ++i)
    {
        fib[i] = fib[i - 1] + fib[i - 2];
    }

    int k_count = -1;//初始化包含k的最大次数
    long long k_max = -1;//初始化包含k的最大次数的那个斐波那契数

    for(int i = 1; i <= n; i++)
    {
        string str = to_string(fib[i]);
        int count = 0;//初始化包含k的次数
        for(char c : str)//遍历字符串每一个字符
        {
            if(c - '0' == k)//如果当前字符的值为k
            {
                count++;
            }
        }
        if(count > k_count)
        {
            k_count = count;
            k_max = fib[i];
        }
        else if(count == k_count && fib[i] < k_max)
        {
            k_max = fib[i];
        }
    }

    cout << k_max << endl;
    return 0;
}
// 64 位输出请用 printf("%lld")
发表于 2025-08-20 23:35:00 回复(0)
牛客173487860号头像 牛客173487860号 
#include <bits/stdc++.h>

using namespace std;

signed main() {
    int n, k;
    cin >> n >> k;

    vector<long long> fib(n + 1);

    for (int i = 1; i <= n; i++) {
        if (i <= 2) fib[i] = 1;
        else fib[i] = fib[i - 1] + fib[i - 2];
    }

    long long ma = -0x3f3f3f3f3f3f3f3f, maid = 0;

    for (int i = 1; i <= n; i++) {
        long long x = fib[i], cnt = 0;

        while (x) {
            cnt += (x % 10 == k);
            x /= 10;
        }

        if (cnt > ma) {
            ma = cnt;
            maid = fib[i];
        }
    }

    cout << maid << '\n';

	return 0;
}

发表于 2025-07-22 13:25:00 回复(0)
提交观点

问题信息

数组 模拟 饿了么 基础数学
难度：
2条回答 136浏览

热门推荐

相关试题

斐波那契

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号