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

本文概述

斐波那契三角形或Hosoya三角形是基于斐波那契数的三角形排列。每个数字都是上面左对角线或右对角线上两个数字的和。前几行是:

Hosoya三角形1

这个三角形中的数字遵循递归关系

Hosoya三角形2

与斐波那契数的关系

三角形中的条目满足标识

Hosoya三角形3

因此,最外面的两条对角线是斐波那契数,而中间垂直线上的数字是斐波那契数的平方。三角形中所有其他的数都是两个不同的大于1的斐波那契数的乘积。行和是第一个卷积的斐波那契数。

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

维基百科:https://en.wikipedia.org/wiki/Hosoya%27s_triangle

给定一个整数n,任务是打印Hosoya的大小为n的三角形。

例子:

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

下面是打印Hosoya的高度为n的三角形的实现:

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

下面是使用动态编程打印高度为n的Hosoya三角形的实现:

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

微信公众号
手机浏览(小程序)
0
分享到:
没有账号? 忘记密码?