注册 登录
编程论坛 → C++教室

斐波那契数列

叶落归苏 发布于 2019-12-21 19:56， 3521 次点击
Fibonacci数列的前几项为：1，1，2，3，5，8，13。

其规律是第i项是第i-1项与第i-2项的加和。

现在你的任务是对于给定的两个数字x和y，找到Fib[x]与Fib[y]的最小公倍数，其中Fib[i]为Fibonacci数列的第i项，F[1] = F[2] = 1。

应金老师的要求，你们可以尽情暴力这道题了。

Input
本题为多组数据输入。

每组数据只有两个整数x和y(0 < x,y <= 35)。

Output
输出一个整数代表Fib[x]与Fib[y]的最小公倍数。

Sample Input
1 2

1 3

Sample Output
1

2

#include <iostream>
using namespace std;
int F(int n)
{
   int F[47];
   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 hcf(int x, int y)
{
    if(x%y==0) return y;
    else return hcf(y,x%y);
}
int lcd(int x, int y)
{
    int c;
    c=x*y/hcf(x,y);
    return c;
}
int main()
{
    int a,b,n,m,x,y;
    while(cin >> a >> b)
    {x=F(a);
    y=F(b);
    n = hcf(x,y);
    m = lcd(x,y);
    cout << m << endl;}
    return 0;
}
样例都能过，但交上去就是答案错误，，，

[此贴子已经被作者于2019-12-21 20:08编辑过]

12 回复
#2
rjsp2019-12-21 22:59
每组数据只有两个整数x和y (0 < x,y <= 35)
先在网上搜一下 Fib(35) 是多少，比如这个网站 http://www.
得知
Fib(34) = 5702887
Fib(35) = 9227465
又因为相邻两个斐波那契数的最大公约数是1（由“辗转相减法求最大公约数”可直接看出来）
所以 Fib[x]与Fib[y]的最小公倍数 的最大值是 5702887*9227465=52623190191455
打开任意一个计算器，计算 ln(52623190191455)/ln(2) = 45.58
所以我们有了第一个结论：结果类型最小是 uint64_t。

x*y/hcf(x,y);
x*y 是不是会溢出也需要测试，既然不能确定，那为什么不写成 x/hcf(x,y)*y ？

int hcf(int x, int y)
int lcd(int x, int y)
C++ 标准模板库中有 std::gcd 和 std::lcm，即便你想自己写，也先看看别人是怎么实现的




[此贴子已经被作者于2019-12-22 11:36编辑过]
#3
叶落归苏2019-12-22 01:01
回复 2楼 rjsp
试了一下，还是答案错误😭
#4
叶落归苏2019-12-22 01:04
回复 2楼 rjsp
#include<stdio.h>
int main()
{
    int x, y;
    int num[36] = {0,1,1};
    for(int i = 3; i<=35; i++)
    {
        num[i] = num[i-1] + num[i-2];
    }
    while(~scanf("%d %d", &x, &y))
    {
        int temp;
        if(x<y)
        {
            temp = x;
            x = y;
            y = temp;
        }
        for(int i=num[x]; i>0; i++)
            if(i%num[x]==0 && i%num[y]==0)
            {
                printf("%d\n", i);
                break;
            }
    }
}
这个是一个学长讲的，但是超时了，，，，
#5
rjsp2019-12-22 01:07
以下是引用叶落归苏在2019-12-22 01:01:17的发言：

试了一下，还是答案错误😭

你在说什么？
#6
knhsss2019-12-22 04:50
寻找有能力的开发 开发绝地求生游戏的某一方面的东西 有意可联系QQ643093820 你有实力我可以给你带来财富
#7
叶落归苏2019-12-22 13:17
回复 5楼 rjsp
就是按你的方法改，提交上去wrong answer了。。。
#8
rjsp2019-12-22 15:39
以下是引用叶落归苏在2019-12-22 13:17:24的发言：

就是按你的方法改，提交上去wrong answer了。。。


你连修改后的代码都不肯给，我怎么可能知道你哪里写错了？别浪费大家的时间行不行

当然，这不是你的错，而是这个论坛缺少拉黑功能。
你可能不希望我回答你的提问，但我没法知道这一点;
而我可能希望以后避开你的提问，可时间一长就会忘了。
#9
叶纤2019-12-22 18:16
#include <iostream>
using namespace std;
int F(int n)
{
   int F[47];
   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 hcf(int x, int y)
{
    if(x%y==0) return y;
    else return hcf(y,x%y);
}
int lcd(int x, int y)
{
    int c;
    c=x/hcf(x,y)*y ;


    return c;
}
int main()
{
    int a,b,n,m,x,y;
    while(cin >> a >> b)
    {x=F(a);
    y=F(b);
    n = hcf(x,y);
    m = lcd(x,y);
    cout << m << endl;}
    return 0;
}
//我是照着版主大大的原话改你的程序的可以运行
#10
rjsp2019-12-22 18:54
回复 9楼 叶纤
    int c;
    c=x/hcf(x,y)*y ;
这里 x/hcf(x,y)*y 可能会溢出，int存不下。
输入 34 35 试试看结果
#11
叶纤2019-12-22 19:15
回复 10楼 rjsp
真的不可以啊，我变成长整形也不可以，应该怎么做啊？不过我挺佩服楼主写代码很厉害，我也尝试了用自己的办法写这题，（还没写完），版主大大可以花时间回答怎么解决吗？
#12
rjsp2019-12-22 19:41
真的不可以啊，我变成长整形也不可以 ------ 谁说变成长整形就可以的呀？我说的是uint64_t，而C/C++并没有规定long是多长，可能小于64bits，也可能大于64bits。
版主大大可以花时间回答怎么解决吗 ------ 你的代码就是9楼的代码吗？如果是的话，我在10楼已经回答了“x/hcf(x,y)*y 可能会溢出，int存不下”。

程序代码：
#include <iostream>
using namespace std;

unsigned hcf( unsigned a, unsigned b ) // std::gcd
{
    while( b!=0 )
    {
        unsigned t = a;
        a = b;
        b = t%b;
    }
    return a;
}
unsigned long long lcd( unsigned a, unsigned b ) // std::lcm
{
    return a/hcf(a,b)*1ull*b;
}

int main( void )
{
    unsigned fib[36] = { 0, 1 };
    for( size_t i=2; i!=36; ++i )
        fib[i] = fib[i-2] + fib[i-1];

    for( unsigned x,y; cin>>x>>y; )
    {
        unsigned long long r = lcd( fib[x], fib[y] );
        cout << r << '\n';
    }
}
#13
叶纤2019-12-22 20:07
回复 12楼 rjsp
大大，你的迷妹已经是N+1了，我现在知识基础是你的万分之一还不到，还有你说的九楼十楼我真的去数十楼九楼是谁了。代码收藏下，回家慢慢啃。谢谢版主大大的指导
1
©2025, BC-CN.NET
电脑版