Skip to main content

Display Hosoya’s Triangle

Hosoya's Triangle is a triangle of numbers discovered by the Japanese mathematician Haruo Hosoya in 1981.

Each subsequent row of the triangle is constructed using the previous two rows, where each entry is the sum of the entry directly above it and the entry to the upper left diagonal. So, the first few rows of the Hosoya Triangle are:

Hosoya's Triangle

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
Last updated on by Kalkicode




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