El triángulo de Fibonacci o triángulo de Hosoya es una disposición triangular de números basada en los números de Fibonacci. Cada número es la suma de los dos números anteriores, ya sea en la diagonal izquierda o en la diagonal derecha. Las primeras filas son:
Los números en este triángulo siguen las relaciones de recurrencia
Relación con los números de Fibonacci
Las entradas en el triángulo satisfacen la identidad
Por lo tanto, las dos diagonales más externas son los números de Fibonacci, mientras que los números en las líneas verticales del medio son los cuadrados de los números de Fibonacci. Todos los demás números en el triángulo son el producto de dos números de Fibonacci distintos mayores que 1. Las sumas de las filas son los primeros números de Fibonacci convolucionados .
Fuentes: Stackoverflow , Wikipedia
Dado un número entero positivo n . La tarea es imprimir el triángulo de Hosoya de tamaño n.
Ejemplos:
Input : n = 4 Output : 1 1 1 2 1 2 3 2 2 3 Input : n = 5 Output : 1 1 1 2 1 2 3 2 2 3 5 3 4 3 5
A continuación se muestra la implementación de la impresión del triángulo de altura n de Hosoya:
C++
// CPP Program to print Hosoya's
// triangle of height n.
#include <bits/stdc++.h>
using namespace std;
int Hosoya(int n, int m)
{
// Base case
if ((n == 0 && m == 0) ||
(n == 1 && m == 0) ||
(n == 1 && m == 1) ||
(n == 2 && m == 1))
return 1;
// Recursive step
if (n > m)
return Hosoya(n - 1, m)
+ Hosoya(n - 2, m);
else if (m == n)
return Hosoya(n - 1, m - 1)
+ Hosoya(n - 2, m - 2);
else
return 0;
}
// Print the Hosoya triangle of height n.
void printHosoya(int n)
{
for (int i = 0; i < n; i++) {
for (int j = 0; j <= i; j++)
cout << Hosoya(i, j) << " ";
cout << endl;
}
}
// Driven Program
int main()
{
int n = 5;
printHosoya(n);
return 0;
}
Java
// Java Program to print Hosoya's
// triangle of height n.
import java.util.*;
class GFG {
static int Hosoya(int n, int m)
{
// Base case
if ((n == 0 && m == 0) ||
(n == 1 && m == 0) ||
(n == 1 && m == 1) ||
(n == 2 && m == 1))
return 1;
// Recursive step
if (n > m)
return Hosoya(n - 1, m)
+ Hosoya(n - 2, m);
else if (m == n)
return Hosoya(n - 1, m - 1)
+ Hosoya(n - 2, m - 2);
else
return 0;
}
// Print the Hosoya triangle of height n.
static void printHosoya(int n)
{
for (int i = 0; i < n; i++)
{
for (int j = 0; j <= i; j++)
System.out.print(Hosoya(i, j)
+ " ");
System.out.println("");
}
}
/* Driver program to test above function */
public static void main(String[] args)
{
int n = 5;
printHosoya(n);
}
}
// This code is contributed by Arnav Kr. Mandal.
Python3
# Python3 code to print Hosoya's
# triangle of height n.
def Hosoya( n , m ):
# Base case
if ((n == 0 and m == 0) or
(n == 1 and m == 0) or
(n == 1 and m == 1) or
(n == 2 and m == 1)):
return 1
# Recursive step
if n > m:
return Hosoya(n - 1, m)
+ Hosoya(n - 2, m)
elif m == n:
return Hosoya(n - 1, m - 1)
+ Hosoya(n - 2, m - 2)
else:
return 0
# Print the Hosoya triangle of height n.
def printHosoya( n ):
for i in range(n):
for j in range(i + 1):
print(Hosoya(i, j) , end = " ")
print("\n", end = "")
# Driven Code
n = 5
printHosoya(n)
# This code is contributed by Sharad_Bhardwaj
C#
// C# Program to print Hosoya's
// triangle of height n.
using System;
class GFG {
static int Hosoya(int n, int m)
{
// Base case
if ((n == 0 && m == 0) ||
(n == 1 && m == 0) ||
(n == 1 && m == 1) ||
(n == 2 && m == 1))
return 1;
// Recursive step
if (n > m)
return Hosoya(n - 1, m)
+ Hosoya(n - 2, m);
else if (m == n)
return Hosoya(n - 1, m - 1)
+ Hosoya(n - 2, m - 2);
else
return 0;
}
// Print the Hosoya triangle of height n.
static void printHosoya(int n)
{
for (int i = 0; i < n; i++)
{
for (int j = 0; j <= i; j++)
Console.Write(Hosoya(i, j)
+ " ");
Console.WriteLine("");
}
}
/* Driver program to test above function */
public static void Main()
{
int n = 5;
printHosoya(n);
}
}
// This code is contributed by vt_m.
PHP
<?php
// PHP Program to print Hosoya's
// triangle of height n.
function Hosoya(int $n, int $m)
{
// Base case
if (($n == 0 && $m == 0) ||
($n == 1 && $m == 0) ||
($n == 1 && $m == 1) ||
($n == 2 && $m == 1))
return 1;
// Recursive step
if ($n > $m)
return Hosoya($n - 1,$m) +
Hosoya($n - 2, $m);
else if ($m == $n)
return Hosoya($n - 1, $m - 1) +
Hosoya($n - 2, $m - 2);
else
return 0;
}
// Print the Hosoya
// triangle of height n.
function printHosoya( $n)
{
for ( $i = 0; $i < $n; $i++)
{
for ( $j = 0; $j <= $i; $j++)
echo Hosoya($i, $j) , " ";
echo "\n";
}
}
// Driven Code
$n = 5;
printHosoya($n);
// This code is contributed by anuj_67.
?>
Javascript
<script>
// JavaScript program to implement
// the above approach
function Hosoya(n, m)
{
// Base case
if ((n == 0 && m == 0) ||
(n == 1 && m == 0) ||
(n == 1 && m == 1) ||
(n == 2 && m == 1))
return 1;
// Recursive step
if (n > m)
return Hosoya(n - 1, m)
+ Hosoya(n - 2, m);
else if (m == n)
return Hosoya(n - 1, m - 1)
+ Hosoya(n - 2, m - 2);
else
return 0;
}
// Print the Hosoya triangle of height n.
function printHosoya(n)
{
for (let i = 0; i < n; i++)
{
for (let j = 0; j <= i; j++)
document.write(Hosoya(i, j)
+ " ");
document.write("<br/>");
}
}
// Driver code
let n = 5;
printHosoya(n);
// This code is contributed by sanjoy_62.
</script>
Producción:
1 1 1 2 1 2 3 2 2 3 5 3 4 3 5
A continuación se muestra la implementación de la impresión del triángulo de altura n de Hosoya usando Programación Dinámica:
C++
// CPP Program to print Hosoya's triangle of height n.
#include <bits/stdc++.h>
#define N 5
using namespace std;
// Print the Hosoya triangle of height n.
void printHosoya(int n)
{
int dp[N][N];
memset(dp, 0, sizeof(dp));
// base case.
dp[0][0] = dp[1][0] = dp[1][1] = 1;
// For each row.
for (int i = 2; i < n; i++) {
// for each column;
for (int j = 0; j < n; j++) {
// recursive steps.
if (i > j)
dp[i][j] = dp[i - 1][j] + dp[i - 2][j];
else
dp[i][j] = dp[i - 1][j - 1] + dp[i - 2][j - 2];
}
}
// printing the solution
for (int i = 0; i < n; i++) {
for (int j = 0; j <= i; j++)
cout << dp[i][j] << " ";
cout << endl;
}
}
// Driven Program
int main()
{
int n = 5;
printHosoya(n);
return 0;
}
Java
// JAVA Code for Hosoya Triangle
import java.util.*;
class GFG {
static int N = 5;
// Print the Hosoya triangle
// of height n.
static void printHosoya(int n)
{
int dp[][] = new int[N][N];
// base case.
dp[0][0] = dp[1][0] = 1;
dp[1][1] = 1;
// For each row.
for (int i = 2; i < n; i++)
{
// for each column;
for (int j = 0; j < n; j++)
{
// recursive steps.
if (i > j)
dp[i][j] = dp[i - 1][j] +
dp[i - 2][j];
else
dp[i][j] = dp[i - 1][j - 1] +
dp[i - 2][j - 2];
}
}
// printing the solution
for (int i = 0; i < n; i++)
{
for (int j = 0; j <= i; j++)
System.out.print(dp[i][j] + " ");
System.out.println("");
}
}
/* Driver program*/
public static void main(String[] args)
{
int n = 5;
printHosoya(n);
}
}
// This code is contributed by Arnav Kr. Mandal.
Python3
# Python3 Program to print # Hosoya's triangle of height n. N = 5 # Print the Hosoya triangle # of height n. def printHosoya(n): dp = [[0 for i in range(N)] for i in range(N)] # base case. dp[0][0] = dp[1][0] = dp[1][1] = 1 # For each row. for i in range(2, n): # for each column for j in range(n): # recursive steps. if (i > j): dp[i][j] = (dp[i - 1][j] + dp[i - 2][j]) else: dp[i][j] = (dp[i - 1][j - 1] + dp[i - 2][j - 2]) # printing the solution for i in range(n): for j in range(i + 1): print(dp[i][j], end = ' ') print() # Driver Code n = 5 printHosoya(n) # This code is contributed # by sahilshelangia
C#
// C# Code for Hosoya Triangle
using System;
class GFG {
static int N = 5;
// Print the Hosoya triangle
// of height n.
static void printHosoya(int n)
{
int [,]dp = new int[N,N];
// base case.
dp[0,0] = dp[1,0] = 1;
dp[1,1] = 1;
// For each row.
for (int i = 2; i < n; i++)
{
// for each column;
for (int j = 0; j < n; j++)
{
// recursive steps.
if (i > j)
dp[i,j] = dp[i - 1,j] +
dp[i - 2,j];
else
dp[i,j] = dp[i - 1,j - 1]
+ dp[i - 2,j - 2];
}
}
// printing the solution
for (int i = 0; i < n; i++)
{
for (int j = 0; j <= i; j++)
Console.Write(dp[i,j] + " ");
Console.WriteLine("");
}
}
/* Driver program*/
public static void Main()
{
int n = 5;
printHosoya(n);
}
}
// This code is contributed by Vt_m.
PHP
<?php
// PHP Program to print Hosoya's triangle of height n.
$N=5;
// Print the Hosoya triangle of height n.
function printHosoya($n)
{
global $N;
$dp=array_fill(0,$N,array_fill(0,$N,0));
// base case.
$dp[0][0] = $dp[1][0] = $dp[1][1] = 1;
// For each row.
for ($i = 2; $i < $n; $i++) {
// for each column;
for ($j = 0; $j < $n; $j++) {
// recursive steps.
if ($i > $j)
$dp[$i][$j] = $dp[$i - 1][$j]
+ $dp[$i - 2][$j];
else
$dp[$i][$j] = $dp[$i - 1][$j - 1]
+ $dp[$i - 2][$j - 2];
}
}
// printing the solution
for ($i = 0; $i < $n; $i++) {
for ($j = 0; $j <= $i; $j++)
echo $dp[$i][$j]." ";
echo "\n";
}
}
// Driven Program
$n = 5;
printHosoya($n);
// This code is contributed by mits
?>
Javascript
<script>
// Javascript Program to print Hosoya's
// triangle of height n.
var N = 5
// Print the Hosoya triangle of height n.
function printHosoya(n)
{
var dp = Array.from(Array(N),
()=> Array(N).fill(0));
// base case.
dp[0][0] = dp[1][0] = dp[1][1] = 1;
// For each row.
for (var i = 2; i < n; i++) {
// for each column;
for (var j = 0; j < n; j++) {
// recursive steps.
if (i > j)
dp[i][j] = dp[i - 1][j] +
dp[i - 2][j];
else
dp[i][j] = dp[i - 1][j - 1] +
dp[i - 2][j - 2];
}
}
// printing the solution
for (var i = 0; i < n; i++) {
for (var j = 0; j <= i; j++)
document.write( dp[i][j] + " ");
document.write("<br>");
}
}
// Driven Program
var n = 5;
printHosoya(n);
</script>
Producción:
1 1 1 2 1 2 3 2 2 3 5 3 4 3 5