c - Tribonacci 数和时间/空间复杂度 - C

Question

嘿伙计们，我编写了一个程序，它接受输入并计算 Tribonacci数量:

/* 
 * File:   main.c
 * Author: Hanna
 *
 * Created on October 13, 2018, 10:25 PM
 */

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


unsigned long Tribonacci(int n)
{  if (n < 3)
       return 1;
    if (n >= 3)
        return Tribonacci(n - 1) + Tribonacci(n - 2) + Tribonacci(n - 3);
}

int main () {
   char number[100];
   char *ptr;
   long num;

    while (1){
        printf("Please enter the integer number n>3: ");
        fgets(number, 10, stdin);
        num = strtol(number, &ptr, 10);
        printf("Tribonacci number is %ld\n", Tribonacci(num));
    }

   return(0);
}

由于某种原因，它给出了错误的答案。示例:

N=24 should give 755476, instead it gives 978793

我不知道为什么。 Tribonnaci() 函数似乎没问题。另外，这是否优化了空间和时间复杂度？

注意:我需要使用递归。

Answer 1

编码错误:Tribonacci(0) 为 0。

// if (n < 3) return 1;
if (n < 3)
   return (n > 0);

... for n = 0, 1, 2, ... are 0, 1, 1, 2, 4, ...

<小时/>

Also, is this optimizing space and time complexity?

没有。最好不要重新计算。

下面是在线性时间内计算 Tribonacc(n) 的版本。使用递归。

typedef struct {
  unsigned long tn, tnm1, tnm2;
} Tribonacci_T;

static Tribonacci_T Tribonacci_helper(int n) {
  if (n < 3) {
    return (Tribonacci_T) {.tn = n > 0, .tnm1 = n > 1, .tnm2 = n > 2};
  }
  Tribonacci_T t = Tribonacci_helper(n - 1);
  return (Tribonacci_T) {.tn = t.tn + t.tnm1 + t.tnm2, .tnm1 = t.tn, .tnm2 = t.tnm1};
}

unsigned long Tribonacci(int n) {
  return Tribonacci_helper(n).tn;
}