形成一个斐波那契三角形，使得每个数字都是左对角线或右对角线上两个数字的总和

Question

前几行是：

1
1 1
2 1 2
3 2 2 3
5 3 4 3 5
8 5 6 6 5 8
13 8 10 9 10 8 13
21 13 16 15 16 13 21
34 21 26 24 25 24 26 21 34
...

我在 C 中尝试了以下代码：

尝试 1：

#include<stdio.h>    
#include<stdlib.h>  
int main(){  
   int a=0,b=1,i,c,n,j;    
system("cls");  
    printf("Enter the limit:");    
    scanf("%d",&n);    
    for(i=1;i<=n;i++)    
    {    
        a=0;    
        b=1;    
        printf("%d\t",b);    
        for(j=1;j<i;j++)    
        {    
            c=a+b;    
            printf("%d\t",c);    
            a=b;    
            b=c;    

        }    
        printf("\n");    
    }    
return 0;  
}

它的输出是这样的（对于 limit 9）：

1
1   1   
1   1   2   
1   1   2   3   
1   1   2   3   5   
1   1   2   3   5   8   
1   1   2   3   5   8   13  
1   1   2   3   5   8   13  21  
1   1   2   3   5   8   13  21  34

尝试 2：

#include<stdio.h>    
#include<stdlib.h>  
int main(){  
   int a=0,b=1,i,c,n,j;    
system("cls");  
    printf("Enter the limit:");    
    scanf("%d",&n);    
    a = 0; b=1;
    for(i=1;i<=n;i++)    
    {        
        printf("%d\t",b);    
        for(j=1;j<i;j++)    
        {    
            c=a+b;    
            printf("%d\t",c);    
            a=b;    
            b=c;    

        }    
        printf("\n");    
    }    
return 0;  
}

它的输出是这样的：

1

1 1

1 2 3

3 5 8 13

13 21 34 55 89

89 144 233 377 610

我还在 for 循环之外尝试了 a 或 b。但似乎没有任何效果。有什么办法可以解决这个问题吗？请用 C、C++ 或 Python.

给出解决方案

Answer 1

(已编辑 以在 Python 中包含有效的迭代方法。

您要查找的三角形是Hosoya's Triangle。 original paper:

中提供了此的数学公式

H(0, 0) = H(1, 0) = H(1, 1) = H(2, 1) = 1
H(i, j) = H(i − 1, j − 1) + H(i − 2, j − 2)  (j >= 2)
        = H(i − 1, j) + H(i − 2, j)   (otherwise)

在Python中，这可以简单地写成递归关系，如：

def hosoya(i, j):
    if j > i:
        raise ValueError('Must be: j <= i')
    elif (i, j) in {(0, 0), (1, 0), (1, 1), (2, 1)}:
        return 1
    elif j >= 2:
        return hosoya(i - 1, j - 1) + hosoya(i - 2, j - 2)
    else:
        return hosoya(i - 1, j) + hosoya(i - 2, j)


for i in range(10):
    for j in range(i + 1):
        print(hosoya(i, j), end=' ')
    print()
# 1 
# 1 1 
# 2 1 2 
# 3 2 2 3 
# 5 3 4 3 5 
# 8 5 6 6 5 8 
# 13 8 10 9 10 8 13 
# 21 13 16 15 15 16 13 21 
# 34 21 26 24 25 24 26 21 34 
# 55 34 42 39 40 40 39 42 34 55

如果需要，可以很容易地适应 C：

#include <stdio.h>

const int NUM_ROWS = 10;

int hosoya(int i, int j)
{
    if (j > i)
    {
        return 0;
    }
    else if ((i == 0 && j == 0) || (i == 1 && j == 0) || (i == 1 && j == 1) || (i == 1 && j == 1))
    {
        return 1;
    }
    else if (j >= 2)
    {
        return hosoya(i - 1, j - 1) + hosoya(i - 2, j - 2);
    }
    else
    {
        return hosoya(i - 1, j) + hosoya(i - 2, j);
    }
}

int main(void)
{
    int i, j;
    for (i = 0; i < NUM_ROWS; ++i)
    {
        for (j = 0; j < i + 1; ++j)
        {
            printf("%d ", hosoya(i, j));
        }
        printf("\n");
    }
    return 0;
}

这是 Python 中生成 n 行的迭代解决方案的一些代码：

def gen_hosoya(n):
    result = [[1], [1, 1], [2, 1, 2]]
    for i in range(2, n):
        next_row = []
        for j in range(2):
            next_row.append(result[-1][j] + result[-2][j])
        for j in range(2, i + 2):
            next_row.append(result[-1][j - 1] + result[-2][j - 2])
        result.append(next_row)
    return result


for row in gen_hosoya(10):
    print(row)
# [1]
# [1, 1]
# [2, 1, 2]
# [3, 2, 2, 3]
# [5, 3, 4, 3, 5]
# [8, 5, 6, 6, 5, 8]
# [13, 8, 10, 9, 10, 8, 13]
# [21, 13, 16, 15, 15, 16, 13, 21]
# [34, 21, 26, 24, 25, 24, 26, 21, 34]
# [55, 34, 42, 39, 40, 40, 39, 42, 34, 55]
# [89, 55, 68, 63, 65, 64, 65, 63, 68, 55, 89]

如果由于某些原因只需要三角形的一部分，这可以很容易地转换成内存高效的生成器：

def gen_next_row(buffer, i):
    next_row = []
    for j in range(2):
        next_row.append(buffer[-1][j] + buffer[-2][j])
    for j in range(2, i + 2):
        next_row.append(buffer[-1][j - 1] + buffer[-2][j - 2])
    buffer.pop(0)
    buffer.append(next_row)
    return next_row


def gen_hosoya(first, second=None):
    if second is None:
        first, second = 0, first
    buffer = [[1], [1, 1], [2, 1, 2]]
    for i, next_row in enumerate(buffer):
        if i in range(first, second):
            yield next_row
    buffer.pop(0)
    for i in range(2, first):
        gen_next_row(buffer, i)
    for i in range(first, second):
        yield gen_next_row(buffer, i)


for row in gen_hosoya(10, 12):
    print(row)
# [144, 89, 110, 102, 105, 104, 104, 105, 102, 110, 89, 144]
# [233, 144, 178, 165, 170, 168, 169, 168, 170, 165, 178, 144, 233]

Answer 2

我在 Python 中的代码没有递归（感谢 @norok2）：[在某些情况下显示 BrokenPipe 错误。所以我添加了信号语句来根据 this.]

修复它

from signal import signal, SIGPIPE, SIG_DFL
signal(SIGPIPE, SIG_DFL)
n = int(input())
dp = [[0 for i in range(n)] for j in range(n)]
dp[0][0] = 1
dp[1][0] = 1
dp[1][1] = 1
dp[2][0] = 2
dp[2][1] = 1
dp[2][2] = 2
for i in range(3,n):
    for j in range(i+1):
        if j-2>=0:
            dp[i][j] = dp[i-1][j-1]+dp[i-2][j-2]
        else:
            dp[i][j] = dp[i-1][j]+dp[i-2][j]

for i in dp:
    for j in i:
        if j:
            print(j , end = ' ')
    print()

形成一个斐波那契三角形，使得每个数字都是左对角线或右对角线上两个数字的总和

Form a fibonacci triangle such that each number is the sum of two numbers above in either left diagonal or the right diagonal

c

c++

python

fibonacci