Posted on by Kalkicode
Code Pattern

Display Hosoya’s Triangle

In this article, we will discuss Hosoya's Triangle, a mathematical concept that generates a triangular pattern of numbers. We will explain the problem statement, provide a suitable example, present the algorithm and pseudocode, and explain the resultant output. The time complexity of the code will also be discussed.

Hosoya's Triangle

Introduction

Hosoya's Triangle is a triangular array of numbers where each number is the sum of two specific preceding numbers. It is named after Haruo Hosoya, a Japanese mathematician. The triangle exhibits interesting patterns and properties, making it a fascinating topic of study.

Problem Statement

The problem is to generate and display Hosoya's Triangle of a given size. The size represents the number of rows in the triangle. Each element in the triangle is the sum of specific preceding elements, following certain rules based on the row and column indices.

Example:

Let's consider generating Hosoya's Triangle of size 5 and size 7 to illustrate the problem statement.

Size 5:
				1
			1		1
		2		1		2
	3		2		2		3
5		3		4		3		5
Size 7:
						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

Algorithm and Pseudocode

The algorithm to generate Hosoya's Triangle involves the following steps:

  1. Create a function to calculate the sum of specific preceding elements based on row and column indices.
  2. Create a function to display the generated triangle.
  3. Create a function to set the default values of the resulting array.
  4. Create a function to generate the triangle by iterating over rows and columns and using the sum_result function.
  5. Call the triangle generation function with the desired size.

The pseudocode representation of the algorithm is as follows:

sum_result(result[], row, col, size):
    ans = 0
    if col < row:
        if row - 1 >= 0:
            ans += result[(row - 1) * size + col]
        if row - 2 >= 0:
            ans += result[(row - 2) * size + col]
    else:
        if row - 1 >= 0 and col - 1 >= 0:
            ans += result[(row - 1) * size + (col - 1)]
        if row - 2 >= 0 and col - 2 >= 0:
            ans += result[(row - 2) * size + (col - 2)]
    return ans

show(result[], size):
    for i = 0 to size:
        for j = i + 1 to size:
            print tab
        for j = 0 to size and j <= i:
            print result[(i * size) + j]
        print newline

set_default(result[], size):
    for i = 0 to size:
        result[i] = 0

hosoyas_triangle(size):
    capacity = size * size
    result[capacity]
    counter = 1
    set_default(result, capacity)
    result[0] = 1
    for i = 1 to size:
        for j = 0 to size:
            result[(i * size) + j] = sum_result(result, i, j, size)
    show(result, size)

Code Solution

Here given code implementation process.

//C Program 
//Display Hosoya’s Triangle
#include <stdio.h>

#include <stdlib.h>

int sum_result(int result[], int row, int col, int size)
{
	int ans = 0;
	if (col < row)
	{
		// Compare horizontal element
		if (row - 1 >= 0)
		{
			ans += result[(row - 1) * size + col];
		}
		if (row - 2 >= 0)
		{
			ans += result[(row - 2) * size + col];
		}
	}
	else
	{
		// Compare diagonal elements
		if (row - 1 >= 0 && col - 1 >= 0)
		{
			ans += result[(row - 1) * size + (col - 1)];
		}
		if (row - 2 >= 0 && col - 2 >= 0)
		{
			ans += result[(row - 2) * size + (col - 2)];
		}
	}
	return ans;
}
//Display result of hosoyas triangle
void show(int result[], int size)
{
	for (int i = 0; i < size; ++i)
	{
		for (int j = i + 1; j < size; ++j)
		{
			printf("\t");
		}
		for (int j = 0; j < size && j <= i; ++j)
		{
			printf("%d\t\t", result[(i * (size)) + j]);
		}
		printf("\n");
	}
}
//Set default value of resultant array
void set_default(int result[], int size)
{
	for (int i = 0; i < size; ++i)
	{
		result[i] = 0;
	}
}
void hosoyas_triangle(int size)
{
	printf("\n ROW  SIZE : %d\n", size);
	// Number of spaces are required to store hosoyas triangle element
	int capacity = (size * size);
	// Used to store result of hosoyas triangle
	int result[capacity];
	int counter = 1;
	set_default(result, capacity);
	//Set the value of first element
	result[0] = 1;
	for (int i = 1; i < size; ++i)
	{
		for (int j = 0; j < size; ++j)
		{
			//Store the result of top diagonal closest element
			result[(i * (size)) + j] = sum_result(result, i, j, size);
		}
	}
	show(result, size);
}
int main()
{
	//Test Cases
	hosoyas_triangle(5);
	hosoyas_triangle(7);
	return 0;
}

Output

 ROW  SIZE : 5
				1
			1		1
		2		1		2
	3		2		2		3
5		3		4		3		5

 ROW  SIZE : 7
						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
// Java Program
// Display Hosoya’s Triangle
class MyPattern
{
	public int sum_result(int[] result, int row, int col, int size)
	{
		int ans = 0;
		if (col < row)
		{
			// Compare horizontal element
			if (row - 1 >= 0)
			{
				ans += result[(row - 1) * size + col];
			}
			if (row - 2 >= 0)
			{
				ans += result[(row - 2) * size + col];
			}
		}
		else
		{
			// Compare diagonal elements
			if (row - 1 >= 0 && col - 1 >= 0)
			{
				ans += result[(row - 1) * size + (col - 1)];
			}
			if (row - 2 >= 0 && col - 2 >= 0)
			{
				ans += result[(row - 2) * size + (col - 2)];
			}
		}
		return ans;
	}
	//Display result of hosoyas triangle
	public void show(int[] result, int size)
	{
		for (int i = 0; i < size; ++i)
		{
			for (int j = i + 1; j < size; ++j)
			{
				System.out.print("\t");
			}
			for (int j = 0; j < size && j <= i; ++j)
			{
				System.out.print(result[(i * (size)) + j] + "\t\t");
			}
			System.out.print("\n");
		}
	}
	//Set default value of resultant array
	public void set_default(int[] result, int size)
	{
		for (int i = 0; i < size; ++i)
		{
			result[i] = 0;
		}
	}
	public void hosoyas_triangle(int size)
	{
		System.out.print("\n ROW SIZE : " + size + "\n");
		// Number of spaces are required to store hosoyas triangle element
		int capacity = (size * size);
		// Used to store result of hosoyas triangle
		int[] result = new int[capacity];
		int counter = 1;
		set_default(result, capacity);
		//Set the value of first element
		result[0] = 1;
		for (int i = 1; i < size; ++i)
		{
			for (int j = 0; j < size; ++j)
			{
				//Store the result of top diagonal closest element
				result[(i * (size)) + j] = sum_result(result, i, j, size);
			}
		}
		show(result, size);
	}
	public static void main(String[] args)
	{
		MyPattern obj = new MyPattern();
		//Test Cases
		obj.hosoyas_triangle(5);
		obj.hosoyas_triangle(7);
	}
}

Output

 ROW SIZE : 5
				1
			1		1
		2		1		2
	3		2		2		3
5		3		4		3		5

 ROW SIZE : 7
						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
// C++ Program
// Display Hosoya’s Triangle
#include<iostream>

using namespace std;
class MyPattern
{
	public: int sum_result(int result[], int row, int col, int size)
	{
		int ans = 0;
		if (col < row)
		{
			// Compare horizontal element
			if (row - 1 >= 0)
			{
				ans += result[(row - 1) *size + col];
			}
			if (row - 2 >= 0)
			{
				ans += result[(row - 2) *size + col];
			}
		}
		else
		{
			// Compare diagonal elements
			if (row - 1 >= 0 && col - 1 >= 0)
			{
				ans += result[(row - 1) *size + (col - 1)];
			}
			if (row - 2 >= 0 && col - 2 >= 0)
			{
				ans += result[(row - 2) *size + (col - 2)];
			}
		}
		return ans;
	}
	//Display result of hosoyas triangle
	void show(int result[], int size)
	{
		for (int i = 0; i < size; ++i)
		{
			for (int j = i + 1; j < size; ++j)
			{
				cout << "\t";
			}
			for (int j = 0; j < size && j <= i; ++j)
			{
				cout << result[(i *(size)) + j] << "\t\t";
			}
			cout << "\n";
		}
	}
	//Set default value of resultant array
	void set_default(int result[], int size)
	{
		for (int i = 0; i < size; ++i)
		{
			result[i] = 0;
		}
	}
	void hosoyas_triangle(int size)
	{
		cout << "\n ROW SIZE : " << size << "\n";
		// Number of spaces are required to store hosoyas triangle element
		int capacity = (size *size);
		int *result = new int[capacity];
		int counter = 1;
		this->set_default(result, capacity);
		//Set the value of first element
		result[0] = 1;
		for (int i = 1; i < size; ++i)
		{
			for (int j = 0; j < size; ++j)
			{
				//Store the result of top diagonal closest element
				result[(i *(size)) + j] = this->sum_result(result, i, j, size);
			}
		}
		this->show(result, size);
	}
};
int main()
{
	MyPattern obj =  MyPattern();
	//Test Cases
	obj.hosoyas_triangle(5);
	obj.hosoyas_triangle(7);
	return 0;
}

Output

 ROW SIZE : 5
				1
			1		1
		2		1		2
	3		2		2		3
5		3		4		3		5

 ROW SIZE : 7
						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
// C# Program
// Display Hosoya’s Triangle
using System;
class MyPattern
{
	public int sum_result(int[] result, int row, int col, int size)
	{
		int ans = 0;
		if (col < row)
		{
			// Compare horizontal element
			if (row - 1 >= 0)
			{
				ans += result[(row - 1) * size + col];
			}
			if (row - 2 >= 0)
			{
				ans += result[(row - 2) * size + col];
			}
		}
		else
		{
			// Compare diagonal elements
			if (row - 1 >= 0 && col - 1 >= 0)
			{
				ans += result[(row - 1) * size + (col - 1)];
			}
			if (row - 2 >= 0 && col - 2 >= 0)
			{
				ans += result[(row - 2) * size + (col - 2)];
			}
		}
		return ans;
	}
	//Display result of hosoyas triangle
	public void show(int[] result, int size)
	{
		for (int i = 0; i < size; i++)
		{
			for (int j = i + 1; j < size; j++)
			{
				Console.Write("\t");
			}
			for (int j = 0; j < size && j <= i; j++)
			{
				Console.Write(result[(i * (size)) + j] + "\t\t");
			}
			Console.Write("\n");
		}
	}
	//Set default value of resultant array
	public void set_default(int[] result, int size)
	{
		for (int i = 0; i < size; i++)
		{
			result[i] = 0;
		}
	}
	public void hosoyas_triangle(int size)
	{
		Console.Write("\n ROW SIZE : " + size + "\n");
		// Number of spaces are required to store hosoyas triangle element
		int capacity = (size * size);
		int[] result = new int[capacity];
		
		set_default(result, capacity);
		//Set the value of first element
		result[0] = 1;
		for (int i = 1; i < size; i++)
		{
			for (int j = 0; j < size; j++)
			{
				//Store the result of top diagonal closest element
				result[(i * (size)) + j] = sum_result(result, i, j, size);
			}
		}
		show(result, size);
	}
	public static void Main(String[] args)
	{
		MyPattern obj = new MyPattern();
		//Test Cases
		obj.hosoyas_triangle(5);
		obj.hosoyas_triangle(7);
	}
}

Output

 ROW SIZE : 5
				1
			1		1
		2		1		2
	3		2		2		3
5		3		4		3		5

 ROW SIZE : 7
						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
<?php
// Php Program
// Display Hosoya’s Triangle
class MyPattern
{
	public 	function sum_result( & $result, $row, $col, $size)
	{
		$ans = 0;
		if ($col < $row)
		{
			// Compare horizontal element
			if ($row - 1 >= 0)
			{
				$ans += $result[($row - 1) *$size + $col];
			}
			if ($row - 2 >= 0)
			{
				$ans += $result[($row - 2) *$size + $col];
			}
		}
		else
		{
			// Compare diagonal elements
			if ($row - 1 >= 0 && $col - 1 >= 0)
			{
				$ans += $result[($row - 1) *$size + ($col - 1)];
			}
			if ($row - 2 >= 0 && $col - 2 >= 0)
			{
				$ans += $result[($row - 2) *$size + ($col - 2)];
			}
		}
		return $ans;
	}
	//Display result of hosoyas triangle
	public 	function show( & $result, $size)
	{
		for ($i = 0; $i < $size; ++$i)
		{
			for ($j = $i + 1; $j < $size; ++$j)
			{
				echo("\t");
			}
			for ($j = 0; $j < $size && $j <= $i; ++$j)
			{
				echo($result[($i *($size)) + $j] ."\t\t");
			}
			echo("\n");
		}
	}
	//Set default value of resultant array
	public 	function set_default( & $result, $size)
	{
		for ($i = 0; $i < $size; ++$i)
		{
			$result[$i] = 0;
		}
	}
	public 	function hosoyas_triangle($size)
	{
		echo("\n ROW SIZE : ". $size ."\n");
		// Number of spaces are required to store hosoyas triangle element
		$capacity = ($size *$size);
		// Used to store result of hosoyas triangle
		$result = array_fill(0, $capacity, 0);
		$this->set_default($result, $capacity);
		//Set the value of first element
		$result[0] = 1;
		for ($i = 1; $i < $size; ++$i)
		{
			for ($j = 0; $j < $size; ++$j)
			{
				//Store the result of top diagonal closest element
				$result[($i *($size)) + $j] = $this->sum_result($result, $i, $j, $size);
			}
		}
		$this->show($result, $size);
	}
}

function main()
{
	$obj = new MyPattern();
	//Test Cases
	$obj->hosoyas_triangle(5);
	$obj->hosoyas_triangle(7);
}
main();

Output

 ROW SIZE : 5
				1
			1		1
		2		1		2
	3		2		2		3
5		3		4		3		5

 ROW SIZE : 7
						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
// Node Js Program
// Display Hosoya’s Triangle
class MyPattern
{
	sum_result(result, row, col, size)
	{
		var ans = 0;
		if (col < row)
		{
			// Compare horizontal element
			if (row - 1 >= 0)
			{
				ans += result[(row - 1) *size + col];
			}
			if (row - 2 >= 0)
			{
				ans += result[(row - 2) *size + col];
			}
		}
		else
		{
			// Compare diagonal elements
			if (row - 1 >= 0 && col - 1 >= 0)
			{
				ans += result[(row - 1) *size + (col - 1)];
			}
			if (row - 2 >= 0 && col - 2 >= 0)
			{
				ans += result[(row - 2) *size + (col - 2)];
			}
		}
		return ans;
	}
	//Display result of hosoyas triangle
	show(result, size)
	{
		for (var i = 0; i < size; ++i)
		{
			for (var j = i + 1; j < size; ++j)
			{
				process.stdout.write("\t");
			}
			for (var j = 0; j < size && j <= i; ++j)
			{
				process.stdout.write(result[(i *(size)) + j] + "\t\t");
			}
			process.stdout.write("\n");
		}
	}
	//Set default value of resultant array
	set_default(result, size)
	{
		for (var i = 0; i < size; ++i)
		{
			result[i] = 0;
		}
	}
	hosoyas_triangle(size)
	{
		process.stdout.write("\n ROW SIZE : " + size + "\n");
		// Number of spaces are required to store hosoyas triangle element
		var capacity = (size *size);
		// Used to store result of hosoyas triangle
		var result = Array(capacity).fill(0);
		this.set_default(result, capacity);
		//Set the value of first element
		result[0] = 1;
		for (var i = 1; i < size; ++i)
		{
			for (var j = 0; j < size; ++j)
			{
				//Store the result of top diagonal closest element
				result[(i *(size)) + j] = this.sum_result(result, i, j, size);
			}
		}
		this.show(result, size);
	}
}

function main(args)
{
	var obj = new MyPattern();
	//Test Cases
	obj.hosoyas_triangle(5);
	obj.hosoyas_triangle(7);
}
main();

Output

 ROW SIZE : 5
				1
			1		1
		2		1		2
	3		2		2		3
5		3		4		3		5

 ROW SIZE : 7
						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
#  Python 3 Program
#  Display Hosoya’s Triangle
class MyPattern :
	def sum_result(self, result, row, col, size) :
		ans = 0
		if (col < row) :
			#  Compare horizontal element
			if (row - 1 >= 0) :
				ans += result[(row - 1) * size + col]
			
			if (row - 2 >= 0) :
				ans += result[(row - 2) * size + col]
			
		else :
			#  Compare diagonal elements
			if (row - 1 >= 0 and col - 1 >= 0) :
				ans += result[(row - 1) * size + (col - 1)]
			
			if (row - 2 >= 0 and col - 2 >= 0) :
				ans += result[(row - 2) * size + (col - 2)]
			
		
		return ans
	
	# Display result of hosoyas triangle
	def show(self, result, size) :
		i = 0
		j = 0
		while (i < size) :
			j = i + 1
			while (j < size) :
				print("\t", end = "")
				j += 1
			
			j = 0
			while (j < size and j <= i) :
				print(result[(i * (size)) + j] ,"\t\t", end = "")
				j += 1
			
			print("\n", end = "")
			i += 1
		
	
	# Set default value of resultant array
	def set_default(self, result, size) :
		i = 0
		while (i < size) :
			result[i] = 0
			i += 1
		
	
	def hosoyas_triangle(self, size) :
		print("\n ROW SIZE : ", size )
		#  Number of spaces are required to store hosoyas triangle element
		capacity = (size * size)
		result = [0] * capacity
		self.set_default(result, capacity)
		# Set the value of first element
		result[0] = 1
		i = 1
		while (i < size) :
			j = 0
			while (j < size) :
				# Store the result of top diagonal closest element
				result[(i * (size)) + j] = self.sum_result(result, i, j, size)
				j += 1
			
			i += 1
		
		self.show(result, size)
	

def main() :
	obj = MyPattern()
	# Test Cases
	obj.hosoyas_triangle(5)
	obj.hosoyas_triangle(7)


if __name__ == "__main__": main()

Output

 ROW SIZE :  5
				1
			1 		1
		2 		1 		2
	3 		2 		2 		3
5 		3 		4 		3 		5

 ROW SIZE :  7
						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
#  Ruby Program
#  Display Hosoya’s Triangle
class MyPattern

	def sum_result(result, row, col, size)
	
		ans = 0
		if (col < row)
		
			#  Compare horizontal element
			if (row - 1 >= 0)
			
				ans += result[(row - 1) * size + col]
			end
			if (row - 2 >= 0)
			
				ans += result[(row - 2) * size + col]
			end
		else
		
			#  Compare diagonal elements
			if (row - 1 >= 0 && col - 1 >= 0)
			
				ans += result[(row - 1) * size + (col - 1)]
			end
			if (row - 2 >= 0 && col - 2 >= 0)
			
				ans += result[(row - 2) * size + (col - 2)]
			end
		end
		return ans
	end
	# Display result of hosoyas triangle
	def show(result, size)
	
		i = 0
		j = 0
		while (i < size)
		
			j = i + 1
			while (j < size)
			
				print("\t")
				j += 1
			end
			j = 0
			while (j < size && j <= i)
			
				print(result[(i * (size)) + j] ,"\t\t")
				j += 1
			end
			print("\n")
			i += 1
		end
	end
	# Set default value of resultant array
	def set_default(result, size)
	
		i = 0
		while (i < size)
		
			result[i] = 0
			i += 1
		end
	end
	def hosoyas_triangle(size)
	
		print("\n ROW SIZE  :", size ,"\n")
		#  Number of spaces are required to store hosoyas triangle element
		capacity = (size * size)
		result = Array.new(capacity) {0}
		self.set_default(result, capacity)
		# Set the value of first element
		result[0] = 1
		i = 1
		while (i < size)
		
			j = 0
			while (j < size)
			
				# Store the result of top diagonal closest element
				result[(i * (size)) + j] = self.sum_result(result, i, j, size)
				j += 1
			end
			i += 1
		end
		self.show(result, size)
	end
end
def main()

	obj = MyPattern.new()
	# Test Cases
	obj.hosoyas_triangle(5)
	obj.hosoyas_triangle(7)
end
main()

Output

 ROW SIZE  :5
				1		
			1		1		
		2		1		2		
	3		2		2		3		
5		3		4		3		5		

 ROW SIZE  :7
						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		
// Scala Program
// Display Hosoya’s Triangle
class MyPattern
{
	def sum_result(result: Array[Int], row: Int, col: Int, size: Int): Int = {
		var ans: Int = 0;
		if (col < row)
		{
			// Compare horizontal element
			if (row - 1 >= 0)
			{
				ans += result((row - 1) * size + col);
			}
			if (row - 2 >= 0)
			{
				ans += result((row - 2) * size + col);
			}
		}
		else
		{
			// Compare diagonal elements
			if (row - 1 >= 0 && col - 1 >= 0)
			{
				ans += result((row - 1) * size + (col - 1));
			}
			if (row - 2 >= 0 && col - 2 >= 0)
			{
				ans += result((row - 2) * size + (col - 2));
			}
		}
		return ans;
	}
	//Display result of hosoyas triangle
	def show(result: Array[Int], size: Int): Unit = {
		var i: Int = 0;
		var j: Int = 0;
		while (i < size)
		{
			j = i + 1;
			while (j < size)
			{
				print("\t");
				j += 1;
			}
			j = 0;
			while (j < size && j <= i)
			{
				print("" +result((i * (size)) + j) + "\t\t");
				j += 1;
			}
			print("\n");
			i += 1;
		}
	}
	//Set default value of resultant array
	def set_default(result: Array[Int], size: Int): Unit = {
		var i: Int = 0;
		while (i < size)
		{
			result(i) = 0;
			i += 1;
		}
	}
	def hosoyas_triangle(size: Int): Unit = {
		print("\n ROW SIZE : " + size + "\n");
		// Number of spaces are required to store hosoyas triangle element
		var capacity: Int = (size * size);
		var result: Array[Int] = Array.fill[Int](capacity)(0);
		set_default(result, capacity);
		//Set the value of first element
		result(0) = 1;
		var i: Int = 1;
		while (i < size)
		{
			var j: Int = 0;
			while (j < size)
			{
				//Store the result of top diagonal closest element
				result((i * (size)) + j) = sum_result(result, i, j, size);
				j += 1;
			}
			i += 1;
		}
		show(result, size);
	}
}
object Main
{
	def main(args: Array[String]): Unit = {
		var obj: MyPattern = new MyPattern();
		//Test Cases
		obj.hosoyas_triangle(5);
		obj.hosoyas_triangle(7);
	}
}

Output

 ROW SIZE : 5
				1
			1		1
		2		1		2
	3		2		2		3
5		3		4		3		5

 ROW SIZE : 7
						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
// Swift Program
// Display Hosoya’s Triangle
class MyPattern
{
	func sum_result(_ result: [Int], _ row: Int, _ col: Int, _ size: Int) -> Int
	{
		var ans: Int = 0;
		if (col < row)
		{
			// Compare horizontal element
			if (row - 1 >= 0)
			{
				ans += result[(row - 1) * size + col];
			}
			if (row - 2 >= 0)
			{
				ans += result[(row - 2) * size + col];
			}
		}
		else
		{
			// Compare diagonal elements
			if (row - 1 >= 0 && col - 1 >= 0)
			{
				ans += result[(row - 1) * size + (col - 1)];
			}
			if (row - 2 >= 0 && col - 2 >= 0)
			{
				ans += result[(row - 2) * size + (col - 2)];
			}
		}
		return ans;
	}
	//Display result of hosoyas triangle
	func show(_ result: [Int], _ size: Int)
	{
		var i: Int = 0;
		var j: Int = 0;
		while (i < size)
		{
			j = i + 1;
			while (j < size)
			{
				print("\t", terminator: "");
				j += 1;
			}
			j = 0;
			while (j < size && j <= i)
			{
				print(result[(i * (size)) + j] ,"\t\t", terminator: "");
				j += 1;
			}
			print("\n", terminator: "");
			i += 1;
		}
	}

	func hosoyas_triangle(_ size: Int)
	{
		print("\n ROW SIZE : ", size ,"\n", terminator: "");
		// Number of spaces are required to store hosoyas triangle element
		let capacity: Int = (size * size);
		var result: [Int] = Array(repeating: 0, count: capacity);
		
		//Set the value of first element
		result[0] = 1;
		var i: Int = 1;
		while (i < size)
		{
			var j: Int = 0;
			while (j < size)
			{
				//Store the result of top diagonal closest element
				result[(i * (size)) + j] = self.sum_result(result, i, j, size);
				j += 1;
			}
			i += 1;
		}
		self.show(result, size);
	}
}
func main()
{
	let obj: MyPattern = MyPattern();
	//Test Cases
	obj.hosoyas_triangle(5);
	obj.hosoyas_triangle(7);
}
main();

Output

 ROW SIZE :  5
				1
			1 		1
		2 		1 		2
	3 		2 		2 		3
5 		3 		4 		3 		5

 ROW SIZE :  7
						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

Resultant Output Explanation

The resultant output is the generated Hosoya's Triangle of the given size. Each number represents the sum of specific preceding numbers, following the rules mentioned in the problem statement. The triangle is displayed in a tabular format, with appropriate spacing to form the triangular shape.

Time Complexity

The time complexity of the algorithm can be analyzed as follows:

  • The sum_result function has a constant time complexity as it performs a fixed number of comparisons and additions.
  • The show function has a time complexity of O(n^2), where n is the size of the triangle. It includes two nested loops iterating up to size, resulting in quadratic time complexity.
  • The set_default function has a time complexity of O(n), as it iterates over the array once.
  • The hosoyas_triangle function consists of nested loops iterating up to size, resulting in a time complexity of O(n^2).

Overall, the time complexity of the code is O(n^2) due to the nested loops used to generate and display the triangle.

Finally

In this article, we discussed Hosoya's Triangle, a triangular pattern of numbers generated by summing specific preceding elements. We explained the problem statement, provided examples, presented the algorithm and pseudocode, and explained the resultant output. Additionally, we analyzed the time complexity of the code. Hosoya's Triangle is an intriguing mathematical concept with various applications and properties worth exploring further.

Comment

Please share your knowledge to improve code and content standard. Also submit your doubts, and test case. We improve by your feedback. We will try to resolve your query as soon as possible.

New Comment