在 C 中使用指针的 Nth Fibonacci；递归和数组

Question

目前我有这段代码。它可以工作并且可以做我想做的事。我想知道我是否可以让它变得更好。我并不真正关心用户输入或任何其他 "finish touches," 只是想让代码更高效并且可能对未来的项目更有用。过多的评论仅供个人使用，当我返回旧项目以供参考时，我发现阅读起来更容易。谢谢！

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

void fabonacci(int * fibArr,int numberOfSeries){
    int n;

    //allocate memory size
    fibArr = malloc (sizeof(int) * numberOfSeries);
    //first val, fib = 0
    *fibArr = 0;//100
    fibArr++;
    //second val, fib = 1
    *fibArr = 1;//104
    fibArr++;

    //printing first two fib values 0 and 1
    printf("%i\n%i\n", *(fibArr- 2),*(fibArr- 1));

    //loop for fib arr
    for(n=0;n<numberOfSeries -2;n++,fibArr++){
        //108 looking back at 104 looking back at 100
        //112 looking back at 108 looking back at 104
        *fibArr = *(fibArr-1) + *(fibArr -2);
        //printing fib arr
        printf("%i\n", *fibArr);
    }
}

int main(){
    //can implm user input if want
    int n = 10;
    int *fib;

    //calling 
    fabonacci(fib,n);
}

Answer 1

改进代码的一种方法是让调用者创建数组，并将数组传递给 fibonacci 函数。这消除了 fibonacci 分配内存的需要。请注意，如果需要，调用者可以 allocate/free，或者调用者可以只声明一个数组。

另一个改进是在 fibonacci 函数内部使用数组表示法。您可能认为指针解决方案具有更好的性能。没关系。在溢出 32 位 int 之前，n 的最大值为 47，因此 n 不够大，无法考虑性能。

最后，fibonacci 函数应该保护自己不受 n 错误值的影响。例如，如果 n 为 1，则函数应将 0 放入数组的第一个条目中，并且不要触及任何其他条目。

#include <stdio.h>

void fibonacci(int *array, int length)
{
    if (length > 0)
        array[0] = 0;
    if (length > 1)
        array[1] = 1;

    for (int i = 2; i < length; i++)
        array[i] = array[i-1] + array[i-2];
}

int main(void)
{
    int fib[47];
    int n = sizeof(fib) / sizeof(fib[0]);

    fibonacci(fib, n);

    for (int i = 0; i < n; i++)
        printf("fib[%d] = %d\n", i, fib[i]);
}

Answer 2

您的代码介于两种可能的解释之间，我无法判断您指的是哪一种。如果想让fibonacci(n)只给第n个数，不产生任何外在的副作用，应该这样写：

int fibonacci(int n) {
   int lo, hi;
   lo = 0;
   hi = 1;
   while(n-- > 0) {
     int tmp = hi;
     lo = hi;
     hi = lo + tmp;
   }
   return lo;
}

你不需要 mallocs 或 frees 因为这需要常量，堆栈分配 space.

如果您希望在计算时将整个序列存储在内存中，您可能还需要已经分配内存，因为这允许调用者控制数字的去向。

// n < 0 => undefined behavior
// not enough space allocated for (n + 1) ints in res => undefined behavior
void fibonacci(int *res, int n) {
  res[0] = 0;
  if(n == 0) { return; }
  res[1] = 1;
  if(n == 1) { return; }
  for(int i = 2; i <= n; i++) {
    res[i] = res[i-1] + res[i-2];
  }
}

现在调用者的工作是分配内存：

int main(){
  int fib[10]; // room for F_0 to F_9
  fibonacci(fib, 9); // fill up to F_9

  int n = ...; // some unknown number
  int *fib2 = malloc(sizeof(int) * (n + 2)); // room for (n + 2) values
  if(fib2 == NULL) { /* error handling */ }
  fibonacci(fib2 + 1, n); // leave 1 space at the start for other purposes.
  // e.g. you may want to store the length into the first element
  fib2[0] = n + 1;
  // this fibonacci is more flexible than before
  // remember to free it
  free(fib2);
}

并且您可以包装它以分配 space 本身，同时仍保留更灵活的版本：

int *fibonacci_alloc(int n) {
    int *fib = malloc(sizeof(int) * (n + 1));
    if(fib == NULL) { return NULL; }
    fibonacci(fib, n);
    return fib;
}

在 C 中使用指针的 N​​th Fibonacci；递归和数组

Nth Fibonacci using pointers in C; recursive and array

c

fibonacci

在 C 中使用指针的 Nth Fibonacci；递归和数组