如何使使艾特肯的数组使用C不使用数组？

4szc88ey 于 2023-04-11 发布在其他

关注(0)|答案(2)|浏览(126)

如何在不使用数组的情况下显示Aitken’s array？
Aitken的数组是一个按行读取的数字三角形{a**n，k，n ≥ 0，0 ≤ k ≤ n}，定义为 a0，0=1，a**n，0 = a**n − 1，n−1，a**n，k = a**n，k−1 + a**n−1，k−1。前几行是：

1
1 2
2 3 5
5 7 10 15
15 20 27 37 52

我试过这个：

#include <stdio.h>

int
main()
{
    int i,
     j,
     current = 1,
        next = 1,
        temp;

    printf("%d\n", current);

    for (i = 2; i <= 5; i++) {
        temp = current + next;
        printf("%d ", next);

        for (j = 3; j <= i; j++) {
            current = next;
            next = temp;
            temp = current + next;
            printf("%d ", next);
        }

        printf("\n");
    }

    return 0;
}

来源：https://stackoverflow.com/questions/75952115/how-to-make-to-make-aitken-s-array-using-c-without-using-array

2条答案

按热度按时间

lx0bsm1f1#

警告：* 不是解决方案，但我有模式。

下面，out是输出行。dif是[给定]输出行元素之间的差。

Line 1:
    out 1

Line 2:
    out 1       2
    dif     1

Line 3:
    out 2       3       5
    dif     1       2

Line 4:
    out 5       7       10      15
    dif     2       3       5

Line 5:
    out 15      20      27      37      52
    dif     5       7       10      15

请注意，输出行3的差分行与行2的输出行相同（例如1 2）。
因此，行X的差值是行X-1的输出行。

赞(0）回复(0）举报 2023-04-11

yws3nbqq2#

因此，模式可以由以下函数定义，其中r是（从0开始的）行，i是该行内的偏移量。

f( r=0, i=0       ) = 1
f( r>0, i=0       ) = f( r-1, r-1 )
f( r>0, i in 1..r ) = f( r, i-1 ) + f( r-1, i-1 )

这可以很容易地实现为递归函数，其调用如下：

size_t n = 5;

for ( size_t r = 0; r < n; ++r ) {
   for ( size_t i = 0; i < r; ++i ) {
      printf( "%d ", f( r, i ) );
   }

   printf( "%d\n", f( r, r ) );
}

因为这听起来像是家庭作业，所以我将把f的实现留给您。
一个关于效率的题外话。使用递归（没有memoization）是非常低效的。一个特别高效的解决方案需要使用大小为n的数组，但我们在这里特别排除使用它。

赞(0）回复(0）举报 2023-04-11

我来回答

如何使使艾特肯的数组使用C不使用数组？

2条答案

相关问题

热门标签

最新问答