C:带有递归的 Hofstadter Q 序列

Question

我必须编写一个 C 函数，使用递归在屏幕上打印 Hofstadter Q 序列的前 N ​​个元素。

Hofstadter Q序列定义为:

Q(1)=Q(2)=2

Q(n)= Q(n-Q(n-1)) + Q(n-Q(n-2))

我的代码应该没问题，但我不知道在哪里放置 printf 来打印结果。

第一个数字是:1, 1, 2, 3, 3, 4, 5, 5, 6, 6, 6, 8, 8, 8, 10, 9, 10, 11, 11, 12, 12, 12 , 12, 16, 14, 14, 16, 16, 16, 16, 20, 17, 17, 20, 21, 19, 20, 22, 21, 22, 23, 23, 24, 24, 24, 24, 24 、32、24、25、30、28、26、30、30 等

我的代码实际上是:

#include <stdio.h>
int hof(int n);

int main()
{
    int n;
    int flag;

    printf("How many elements to print: ");
    scanf("%d",&n);

    flag=hof(n);

    return 0;
}

int hof(int n) {
    int res;

    if (n < 3) res = 1;
    else res=hof(n-(hof(n-1)))+hof(n-(hof(n-2)));

    return res;
}

谢谢。

Answer 1

您的代码重复计算同一组子序列。这意味着它效率低下，而且代码中没有任何地方可以“插入” printf。

使用memoization ，可以这样做:

#include <stdio.h>
int arr[512];

int hof(int n);
int main(void) {

    int n;
    int flag;

    printf("How many elements to print: ");
    scanf("%d",&n);

    flag=hof(n);

    for(size_t i = 1; arr[i]; i++)
        printf("%d ", arr[i]);

    return 0;
}

int hof(int n){
    int res;

    if (arr[n]) return arr[n];

    if (n < 3) res = 1;
    else res=hof(n-(hof(n-1)))+hof(n-(hof(n-2)));

    arr[n] = res;
    return res;
}

您可以根据需要更改数组大小或使用 malloc() 动态分配。