一个Fibonacci算法，不知道到底是哪里出错了，要怎么改啊 - C++教室 - C++论坛

已结贴√ 问题点数：3 回复次数：3

一个Fibonacci算法，不知道到底是哪里出错了，要怎么改啊

#include "stdio.h"
#define true 1
#define false 0
typedef int keytype;
typedef int datatype;
typedef struct{
    keytype key;
    datatype other;
}rectype;
int fibonacci(n)
int n;
{    if(n==0)
        return(0);
    else
        if(n==1)
            return(1);
        else
            return (fibonacci(n-1)+fibonacci(n-2));
}
int fibosrch(rectype R[],keytype k,int n)
    {    int i,p,q,s,t,flag1,flag2;
        i=fibonacci(n-1);
        p=fibonacci(n-2);
        q=fibonacci(n-3);
        s=n+1-(i+p);
        if(k>R[i].key)
            i=i+s;
        flag1=false;
        while((i)&&(!flag1))
        {    if(R[i].key==k)
                flag2=1;
            else
                if(R[i].key<k)
                    flag2=2;
                else
                    if(R[i].key>k)
                        flag2=3;
            switch(flag2)
            {case 1:flag1=true;
                    break;
             case 2:if(q==0)
                    i=0;
                    else
                    {i=i-q;
                     t=p;
                     p=q;
                     q=t-q;
                    }
                    break;
             case 3:if(p==1)
                        i=0;
                    else
                    {    i=i+q;
                        p=p-q;
                        q=q-p;
                    }
                    break;
             default;
            }
        }
        return (i);
    }
int main()
{    int a,i,k;
    rectype R[15];
    scanf("%d",&k);
    for(i=1;i<=15;i++)
        scanf("%d",R[i].key);
    a=fibosrch(R,k,15);
    printf("%d",a);
    return 0;
}
代码是按照课本原样输入的，都不知道怎么改了。。。错了好多。到底是为什么出错呢？？

搜索更多相关主题的帖子: Fibonacci　算法　

第 2 楼

得分:3

程序代码：

#include <iostream>
#define true 1
#define false 0
using namespace std;
typedef int keytype;
typedef int datatype;
typedef struct{    
    keytype key;
    datatype other;
}rectype;

int fibonacci(int n)        //递归实现Fibonacci
{   
    if(n==0)
        return(0);
    else
        if(n==1)
            return(1);
        else
            return (fibonacci(n-1)+fibonacci(n-2));
}
int fibosrch(rectype R[],keytype k,int n)
    {   
        int i,p,q,s,t,flag1,flag2;
        i=fibonacci(n-1);
        p=fibonacci(n-2);
        q=fibonacci(n-3);
        s=n+1-(i+p);
        if(k>R[i].key)
            i=i+s;
        flag1=false;
        while((i)&&(!flag1))
        {   if(R[i].key==k)
                flag2=1;
            else if(R[i].key<k)
                flag2=2;
            else if(R[i].key>k)
                flag2=3;
            switch(flag2)
            {case 1:flag1=true;
                    break;
             case 2:if(q==0)
                        i=0;
                    else
                    {
                        i=i-q;
                        t=p;
                        p=q;
                        q=t-q;
                    }
                    break;
             case 3:if(p==1)
                        i=0;
                    else
                    {   i=i+q;
                        p=p-q;
                        q=q-p;
                    }
                    break;
             default:;
            }
        }
        return (i);
    }
int main(void)
{   
    int a,i,k;
    rectype R[15];
    cin>>k;
    for(i=1;i<=15;i++)
        cin>>R[i].key;
    a=fibosrch(R,k,15);
    cout<<a;
    return 0;
}

可以运行了，不过看不出来是什么功能的！请描述下，学习学习。

满眼生机转化钧；天工人巧日争新。

第 3 楼

得分:0

回楼上的~~
Fibonacci数的定义为f0=0,f1=1,fi=f(i-1)+f(i-2)(i≥2)。由此得Fibonacci        数列为0，1，1，2，3，5，8，13，21，34，55，89，144，……
设数组F中元素按关键字值从小到大顺序排列，并假定元素个数n比某个Fibonacci    树fi小1，即n=fi-1。第一次用待查关键字k与F[f（i-1）]，Key比较，其算法描述    如下：
①    若k=F[f(i-1)],Key，则检索成功，F[f(i-1)]为k所在记录。
②    若k<F[f(i-1)],Key，则下一次的检索范围为下标1到f(i-1)，序列长度为f(i-1)。
③    若k>F[f(i-1)],Key，则下一次的检索范围为下标f(i+1)+1到fi-1，序列长度为（fi-1）-（f(i-1)+1）+1=fi-f(i-1)-1=f(i-2)-1
设F是顺序存储的线性表且满足F[1]，key≤F[2]，key≤…≤F[n]。key,k是已知的关键字值，在F中检索关键字值为k的记录。若找到返回其下标值，否则返回0.
是这个功能，
改是改好了，但是为什么运行时候会出现错误啊？
输入2个数字后就会出现错误

第 4 楼

得分:0

没有问题啊，不过你的查询好像少个循环吧，我还是没看出来怎么查找。
代码重新粘下：

程序代码：

#include <iostream>
#define true 1
#define false 0
using namespace std;
typedef int keytype;
typedef int datatype;
typedef struct{    
    keytype key;
    datatype other;
}rectype;

int fibonacci(int n)        //递归实现Fibonacci
{   
    if(n==0)
        return(0);
    else
        if(n==1)
            return(1);
        else
            return (fibonacci(n-1)+fibonacci(n-2));
}
int fibosrch(rectype R[],keytype k,int n)
    {   
        int i,p,q,s,t,flag1,flag2;
        i=fibonacci(n-1);
        p=fibonacci(n-2);
        q=fibonacci(n-3);
        s=n+1-(i+p);
        if(k>R[i].key)
            i=i+s;
        flag1=false;
        while((i)&&(!flag1))
        {   if(R[i].key==k)
                flag2=1;
            else if(R[i].key<k)
                flag2=2;
            else if(R[i].key>k)
                flag2=3;
            switch(flag2)
            {case 1:flag1=true;
                    break;
             case 2:if(q==0)
                        i=0;
                    else
                    {
                        i=i-q;
                        t=p;
                        p=q;
                        q=t-q;
                    }
                    break;
             case 3:if(p==1)
                        i=0;
                    else
                    {   i=i+q;
                        p=p-q;
                        q=q-p;
                    }
                    break;
             default:;
            }
        }
        return (i);
    }
int main(void)
{   
    int a,i,k;
    rectype R[15];
    cout<<"请输入要查询的数据："<<endl;
    cin>>k;
    cout<<"请输入15个升序的数据："<<endl;
    for(i=1;i<=15;i++)
    {
        cout<<"第"<<i<<"个数据：";
        cin>>R[i].key;
    }
    a=fibosrch(R,k,15);
    cout<<"下表值为："<<a<<endl;
    return 0;
}

[ 本帖最后由 ciweitou163 于 2010-6-1 15:25 编辑 ]

满眼生机转化钧；天工人巧日争新。