Pyramid Example

Pyramid

<?php

class Pyramid
{
	/**
	* @var array;
	* Инстанцируемая переменная.
	*/
	private $instance;

	public function __construct()
	{
		if(!$this->instance)
		{
			$this->instance = self::getInstance();
		}	
	}	
    
	/**
	* Инстанцируем данные для пирамиды
	*/

    private static function getInstance()
    {
    		$row;

			$instance;

			//Заполняем массив данными.
			for($i=0;$i < 10;$i++)
			{
			    for($j=0; $j <= $i ;$j++)
			    {
			        $row[$j] = rand();
			    }
			    $instance[] = $row;
			}
			  
			return $instance;
    }
    

    /**
    * Получение суммы рекурсивной функцией.
    */
    private function calcSum($a, $i, $j)
    {	
    	
    	if($i <= count($a))
				$result = $a[$i][$j] + max($this->calcSum($a, $i + 1, $j), $this->calcSum($a, $i + 1, $j + 1));
			
		return $result;
    }

    /**
    * Обратный проход по массиву и вычисление сумм.
    * Максимальной суммой будет так же значение $array[0][0]				
    * Используем для вычисления пути.
    */
    private function setReverseArray($origArray)
    {
    	$array = $origArray;
    	for($i = count($array) - 1; $i >= 0; $i-- )
		{
			for($j = 0; $j <= $i; $j ++)
			{
				$array[$i][$j] = $array[$i][$j] + max($array[$i + 1][$j],$array[$i + 1][$j + 1]);
			}
		}

		return $array;

    }


    /**
    * Проходим рекурсией по вычисленным значениям и выводим путь
    */	
    private function renderPath($reverseArray, $i, $j, $originalArray)
    {
    	// Если последнее значение выводи со знаком =
	    if($i == count($originalArray) - 1)
	    	echo $originalArray[$i][$j] . '=' . $this->getSum();
	    //Иначе +
	    else
	    	echo $originalArray[$i][$j] . '+';	

        //Спускаемся по массиву вычисляя путь 
		if($i < count($reverseArray) -1){

			$max = max($reverseArray[$i + 1][$j],$reverseArray[$i + 1][$j + 1]);

			$search_array = $reverseArray[$i + 1];

			$key = array_keys($search_array, $max);

			$j = $key[0];

			$this->renderPath($reverseArray, $i + 1, $j, $originalArray);
		}
    }

    /*
    * Вывод максимальной суммы	
    */	
    public function getSum()
    {	
	    $array = $this->instance;

	    $i = 0;

		$j = 0;

		$result = $this->calcSum($array, $i, $j);

		return $result;    	
    }

    /**
    * Отображаем путь.	
    */
    public function getPath()
    {	
    	
    	$originalArray = $this->instance;
    	$reverseArray = $this->setReverseArray($originalArray);
    	$i = 0;
    	$j = 0;

    	$this->renderPath($reverseArray, $i, $j, $originalArray);

    }


    /**
    * Вывод пирамиды.	
    */
    public function drawPyramid()
    {
    	$pyArray = $this->instance;

    	echo '<center>';
    	foreach ($pyArray as $pyRow) {
    		foreach ($pyRow as $value) {
    			echo $value . "&nbsp";
    		}
    		echo '</br>';
    	}
    	echo '</center>';
    }


    public function getPyramid()
    {
    	return $this->instance;
    }	

}

$pyramid = new Pyramid;

$pyramid->drawPyramid();

$pyramid->getPath();