2018-941

2018-941-学硕-其他-数组

1.已知k阶斐波那契数列的定义为：

​ $f_0=0,f_1=0,…f_{k-2}=0,f_{k-1}=1,$

​ $f_n=f_{n-1}+f_{n-2}+…+f_{n-k},n=k,k+1,…$

（1）试编写求$k$阶斐波那契序列的第$m$项值的非递归函数$F(k,m)$

（2）计算$F(5,8)$的值

• 算法思想：$k$阶斐波那契数列从第$0$项到$k-2$项全为$0$，$k-1$项为$1$，从第$k$项开始每项为前$2$项之和

int F(int k,int m){
    int f = 1, a = 0, b = 0;//a为第一项f0=1
    if(m ≤ (k-2)){//k阶斐波那契数列，k-1项为1（第二项），k-2项为0（第二项），所以m≥k-2
        return 0;
    }
    for(int j = k-1;j < m;j++){
        b = f;
        f = f + a;
        a = b;
    }
    return f;
}

• C语言可执行代码

#include <stdio.h>
#include <stdbool.h>
#include <stdlib.h>

int F(int k, int m) {
    int f = 1, a = 0, b = 0;//a为第一项f0=1
    if (m <= (k - 2)) {//k阶斐波那契数列，k-1项为1（第二项），k-2项为0（第二项），所以m≥k-2
        return 0;
    }
    for (int j = k - 1; j < m; j++) {
        b = f;
        f = f + a;
        a = b;
    }
    //printf("%d", f);
    return f;
}

bool IsDescendant(int L[], int R[], int n, int u, int v) {
    if(!v){
        //return printf("%s","没有");
        return false;
    }
    else{
        if(L[v] == u || R[v] == u){
            //return printf("%s","有");
            return true;
        }else if(IsDescendant(L, R, n, u, L[v]) || IsDescendant(L, R, n, u, R[v])){
            //return printf("%s","有");
            return true;
        }else{

            //return printf("%s","没有");
            return false;
        }
    }
}

int main() {
    int Fibonacci = F(1, 4);
    printf("Fibonacci: %d\n",Fibonacci);
    int n =6,u=4,v=2;
    int A[] = {0,2,4,0,0,0};
    int B[] = {0,3,5,0,0,0};
    bool status = IsDescendant(A,B,n,u,v);
    printf("是否为子孙: %d",status);
    return 0;
}

2.假定用两个一维数组$L[1:n]$和$R[1:n]$作为有$n$个结点二叉树的存储结构，$L[i]$和$R[i]$分别指示结点$i$的左儿子和右儿子，$0$表示空。试写一个算法判断结点u是否为结点$v$的子孙

//递归方法
bool IsDescendant(int L[],int R[],int n,int u,int v){
   int flag = 0;
   if(!v){
       return false;
   }else{
       if(L[v] == u || R[v] ==  u){
           return true;
       }else if(Dencendant(L,R,n,u,L[v]) || Dencendant(L,R,n,u,R[v])){
           return true;
       }else{
           return false;
       }
   }
}

//非递归方法
bool IsDescendant(int L[],int R[],int n,int u,int v){
    int Queue[MaxSize];
    int rear = -1,front = -1,p;
    if(L[v] != 0 && u != v){
        Queue[++rear] = L[v];//v的左孩子入队
    }
    if(R[v] != 0 && u != v){
        Queue[++rear] = R[v];//v的右孩子入队
    }
    while(front != rear){//队不为空时
        p = Queue[++front];
        if(p == u){
            return true;
        }else{
            if(L[p] != 0){
                Queue[++rear] = L[p];
            }
            if(R[p] != 0){
                Queue[++rear] = R[p];
            }
        }
    }
    return false;
}

• C语言可执行代码

#include <stdio.h>
#include <stdbool.h>
#include <stdlib.h>

int F(int k, int m) {
    int f = 1, a = 0, b = 0;//a为第一项f0=1
    if (m <= (k - 2)) {//k阶斐波那契数列，k-1项为1（第二项），k-2项为0（第二项），所以m≥k-2
        return 0;
    }
    for (int j = k - 1; j < m; j++) {
        b = f;
        f = f + a;
        a = b;
    }
    //printf("%d", f);
    return f;
}
//递归
bool IsDescendant(int L[], int R[], int n, int u, int v) {
    if(!v){
        //return printf("%s","没有");
        return false;
    }
    else{
        if(L[v] == u || R[v] == u){
            //return printf("%s","有");
            return true;
        }else if(IsDescendant(L, R, n, u, L[v]) || IsDescendant(L, R, n, u, R[v])){
            //return printf("%s","有");
            return true;
        }else{

            //return printf("%s","没有");
            return false;
        }
    }
}
//非递归
bool IsDescendant1(int L[],int R[],int n,int u,int v){
    int Queue[50];
    int rear = -1,front = -1,p;
    if(L[v] != 0 && u != v){
        Queue[++rear] = L[v];//v的左孩子入队
    }
    if(R[v] != 0 && u != v){
        Queue[++rear] = R[v];//v的右孩子入队
    }
    while(front != rear){//队不为空时
        p = Queue[++front];
        if(p == u){
            return true;
        }else{
            if(L[p] != 0){
                Queue[++rear] = L[p];
            }
            if(R[p] != 0){
                Queue[++rear] = R[p];
            }
        }
    }
    return false;
}
int main() {
    int Fibonacci = F(1, 4);
    printf("Fibonacci: %d\n",Fibonacci);
    int n =6,u=4,v=2;
    int A[] = {0,2,4,0,0,0};
    int B[] = {0,3,5,0,0,0};
    bool status = IsDescendant(A,B,n,u,v);
    bool status1 = IsDescendant1(A,B,n,u,v);
    printf("（非递归）是否为子孙: %d",status);
    printf("（递归）是否为子孙: %d",status1);
    return 0;
}