编程论坛 → C++教室

斐波那契数列求高手解答。

莱昂肯尼迪发布于 2011-05-16 20:58， 3655 次点击

1．问题描述（功能要求）：
Fibonacci数列的计算公式如下：
fib（1） = 1；
fib（2） = 1；
fib（n） = fib（n-1） + fib（n-2）；
（1）简单变量“数据平移”方法计算Fibonacci数列的第n项（正整数n通过键盘输入）：说明变量old1=1，old2=1，newItem；新的Fibonacci项newItem总是“距它最近”的前两项（old1与old2）的累加和。而后通过“old1=old2; old2=newItem;”进行所谓的“数据平移”。接着计算另一个新的Fibonacci项newItem，依次循环，直到求出数列的第n项时为止。
（2）使用数组求出Fibonacci数列的第n项（正整数n通过键盘输入）并显示在屏幕上：说明数组f用来存放Fibonacci数列的各项之值，且仅初始化前两个元素f[0]=1，f[1]=1，而后通过f[i]=f[i-2]+f[i-1]；依次计算出f[2]到f[n-1]（注意f[n-1]恰为所要求出的第n项）并将该值显示在屏幕上。
2．其它要求：
（1）只能使用C/C++语言，源程序要有适当的注释，使程序容易阅读
（2）至少采用文本菜单界面（如果能采用图形菜单界面更好）
（3）学生可自动增加新功能模块
（4）完成系统总结报告以及系统使用说明书。

我大一，学的不好，斐波那契数列一些简单的基本算法我会，但是这些要求太蛋疼了。这是我们的课程设计题目，希望哪个高手能帮我解决一下！

11 回复

#2

lianjiecuowu2011-05-26 16:48

#include <iostream>
using namespace std;
int main()
{
    int f1=1;
    int f2=1;
    int i;
    int m;
    cout<<"please enter m:"<<endl;
    cin>>m;
    cout<<f1<<" "<<f2<<endl;
    for(i=2;i<m;i++)
    {
                    f2=f1+f2;
                    f1=f2-f1;
                    cout<<f2<<endl;
                    }
                    cout<<i<<endl;
                    system("pause");

    }

我也是大一的啊，嘿嘿

#3

lz10919149992011-05-27 11:58

程序代码：

#include <cstdio>
#include <ctime>

unsigned int fib_recursive(int);
unsigned int fib_iteration(int);

int main() {
    clock_t exec_time = clock();
    printf("%u\n", fib_recursive(40));
    printf("fib_resursive() execution time : %.3f\n", (exec_time = clock() - exec_time) / 1.0 / CLOCKS_PER_SEC);
    printf("%u\n", fib_iteration(40));
    printf("fib_iteration() execution time : %.3f\n", (clock() - exec_time) / 1.0 / CLOCKS_PER_SEC);
    return 0;
}

unsigned int fib_recursive(int n) {
    if(n == 1 || n == 2)
        return 1;
    return fib_recursive(n - 1) + fib_recursive(n - 2);
}

unsigned int fib_iteration(int n) {
    unsigned int start1 = 1, start2 = 1, fib = start2;
    while(n-- > 2) {
        fib = start1 + start2;
        start1 = start2;
        start2 = fib;
    }
    return fib;
}

只有本站会员才能查看附件，请登录

迭代和递归两种方式，可以看出递归的效率非常差。

[ 本帖最后由 lz1091914999 于 2011-5-27 12:00 编辑 ]

#4

棋局2011-05-29 12:44

嗯，确实，不仅要能编程，而且编程要讲究高效率的实现，尤其是进行复杂运算时。

#5

莱昂肯尼迪2011-05-30 09:31

回复 3楼 lz1091914999

。。。
效率问题太高深了，还不是我该研究的。。
貌似你的回答没解决我的问题阿。。

#6

lucky5635912011-05-30 10:59

太简单了吧，用递归，传入n

#7

lz10919149992011-05-30 12:59

核心问题都帮你解决了，还需要其它的吗？

#8

laoyang1032011-05-31 09:34

程序代码：

#include<iostream>
using namespace std;
int f(int n,int dep)
{
    for(int i = 0;i<dep;i++)
        printf(" ");
    printf("f(%d)\n",n);
    if(n==1||n==2)
    return 1;
    else
    return f(n-1,dep+1)+f(n-2,dep+1);
}
void main()
{
    int i=1,n;
    cin>>n;
    printf("%d\n",f(n,0));
}

看一下你的递归的深度

#9

莱昂肯尼迪2011-06-06 05:58

回复 7楼 lz1091914999

核心问题？
核心问题是那个什么文本菜单。。。斐波那契数列基本算法我会。。但是那个什么文本菜单的要求我很困惑。

#10

爱德华2011-06-06 15:44

#11

lucky5635912011-06-07 08:56

这问题很简单呐!

#12

zpjm2011-06-09 08:30

第一种方法：
#include <iostream>
using namespace std;
int sum(int n);
int main()
{
    int n;
    cout<<"请输入你要求的第n个 Fibonacci 数：n="<<endl;
    cin>>n;
    cout<<"第n个 Fibonacci 数为："<<sum(n)<<endl;
    system （”pause”）;
    return 0;
}
int sum(int n)
{
    if(n==1)
       return 1;
    else if(n==2)
       return 1;
    else
       return sum(n-1) + sum(n-2);
}
第二种方法：
#include <iostream>
using namespace std;
int x;
int f(int x)
{
switch (x)
{
case 0 : return 0;
break;
case 1 : return 1;
break;
default : return f(x-2) + f(x-1);
break;
}
}
int main()
{
cin >> x ;
cout  <<"第n个 Fibonacci 数为："<<f(x)<<endl;
system ("pause");
return 0;

}

1