# 算法题：Hosoya三角形介绍和代码实现

## 本文概述

stackoverflow：https://stackoverflow.com/questions/36275039/create-a-hosoyas-triangle-in-java

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

## 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.
?>``````

``````1
1 1
2 1 2
3 2 2 3
5 3 4 3 5``````

## 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
?>``````

``````1
1 1
2 1 2
3 2 2 3
5 3 4 3 5``````

• 回顶