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

Question

The first few rows are:

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
...

I tried in C the following codes:

Try 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;  
}

Its output was something like this (for 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

Try 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;  
}

Its output was like:

1

1 1

1 2 3

3 5 8 13

13 21 34 55 89

89 144 233 377 610

I also tried either of a or b outside the for loop. But nothing seems to work. Is there any way to solve this? Please give the solution in either C, C++ or Python.

OK, so it goes wrong on the fourth number printed - you can just step through that far in your debugger. When it starts the line `1 2 3` that should be `2 1 2` what is are the values of `a` an `b`? What _should_ they be to give you the right result? Is it sufficient to save two elements from the row above? — Useless, Jun 10 '20 at 11:21

norok2 · Accepted Answer · 2020-06-10T15:45:42.633

(EDITED to include an efficient iterative approach in Python).

The triangle you are looking for is the Hosoya's Triangle. A mathematical formulation of this is provided in the 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)

In Python, this could be written simply as a recursive relation like:

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

which can be easily adapted to C if needed:

#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;
}

Here is some code for an iterative solution in Python that generates n rows:

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]

This can be easily transformed into a memory-efficient generator if, for some reasons, only some portion of the triangle is needed:

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]

Thanks a lot @norok2.. Is there a way to implement them without recurison? Because the number can be as huge as 100. — , Jun 10 '20 at 12:07
This answer shows an iterative and a recursive algorithm: https://stackoverflow.com/a/36277349/7655409 — pH 74, Jun 10 '20 at 12:18

score 0 · Answer 2 · 2020-06-10T13:10:01.187

My code in Python without recursion(thanks to @norok2): [It showed BrokenPipe Error in some cases. So I added the signal statement to fix it as per 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

2 Answers2