Exemplo de recursividade: gerador de sequências de tamanho e soma dos elementos fixos

Descrição

Esconder código-fonte

<?php
/**
*  Programa    : sequencia.php
*  Versão      : 1.0.0
*  Objetivo    : Geração de sequências de números cujas quantidades e soma dos elementos
*                   sejam definidos por parâmetro
*  Observações :
*       1-A sequência deve estar em ordem crescente e não ter números repetidos
*       2-Deve ser definido também um intervalo permitido para os elementos da sequencia
*
*  Histórico:
*       lp (Luís Pessoa); 11/06/2015; criação
*/

/**
*   definição da classe
*
*/
class GeradorSequencia {

    /**
    *  parâmetros de entrada para a sequência (input)
    *     tamanho, limites inferior e superior e soma
    */
    private $tamanho;
    private $limiteInferior;
    private $limiteSuperior;
    private $soma;

    /**
    *  atributos de controle e armazenamento
    *     tamanho, limites inferior e superior e soma
    */
    // matriz para armazenar as sequencias de saída
    private $arrSequencias;

    // se for true (default), emite detalhes de etapas do processo
    private $flagProcess;


    /**
    *  Construtor
    */
    function __constructor() {
        $this->flagProcess = true;
        $this->arrSequencias = array();
    }

    /**
    *  Função para impressão de informações sobre o processo
    *     caso o $this->flagProcess seja true
    */
    function setFlagProcess($fg) {  $this->flagProcess = $fg; }

    /**
    *  Função echo acrescida de retorno de linha
    */
    function echoEol($texto) { echo($texto . PHP_EOL); }

    /**
    *  Função para impressão de informações sobre o processo
    *     caso o $this->echoProcess seja true
    */
    private function echoProcess($texto) {
        if ( $this->flagProcess ) { $this->echoEol($texto); }
    }

    /**
    *  Função chamada em caso de erro de input de dados
    */
    function inputErro($mensagem) { exit($mensagem); }

    /**
    *  Função de input e validação dos parâmetros da sequencia
    */
    function input($t,$li,$ls,$s) {

        // validação
        $this->validInput($t,$li,$ls,$s);

        // default de echo de processo true
        $this->setFlagProcess(true);

        // parâmetros ok
        $this->tamanho=$t;
        $this->limiteInferior=$li;
        $this->limiteSuperior=$ls;
        $this->soma=$s;
    }

    /**
    *  Função de validação dos parâmetros da sequencia
    */
    private function validInput($t,$li,$ls,$s) {
        // testa se os parâmetros foram informados e são inteiros maiores que 0
        if (! ( isset($t) && isset($li) && isset($ls) && isset($s) )) {
            $this->inputErro("parametros devem ser todos informados");
        }

        if (! ( $t && $li && $ls && $s )) {
            $this->inputErro("um ou mais parametros inválidos ou iguais a 0");
        }

        if (! ( is_int($t) && is_int($li) && is_int($ls) && is_int($s) )) {
            $this->inputErro("parametros devem numéricos e inteiros");
        }

        // teste se os parametros estão ok
        if ($t < 3 ) { $this->inputErro("tamanho minimo para a sequencia é 3"); }
        if ($li >= $ls ) { $this->inputErro("limite superior deve ser meior que o inferior"); }
        if ($s < ($ls + $li) )  {
            $this->inputErro("soma deve ser maior que a soma dos limites inferior e superior");
        }
    }

    /**
    *  imprime os dados de input e controle
    */
    function printInput() {
        $this->echoEol('-----------------------');
        $this->echoEol('Infomaçoes do processo ');
        $this->echoEol('');
        $this->echoEol('Tamanho:         '  . $this->tamanho);
        $this->echoEol('Limite Inferior: '  . $this->limiteInferior);
        $this->echoEol('Limite Superior: '  . $this->limiteSuperior);
        $this->echoEol('Soma:            '  . $this->soma);
        $this->echoEol('');
        $this->echoEol('Echo do processo: ' . (($this->flagProcess) ? 'Sim' : 'Não') );
        $this->echoEol('');
    }

    // geração das sequencias
    // a brincadeira começa aqui
    function createSequences() {

        // primeiro valida os parâmetros da sequência
        $this->validInput($this->tamanho,$this->limiteInferior,$this->limiteSuperior,$this->soma);

        // inicializa a matriz de sequencias
        $this->arrSequecias=array();


        // inicia sequencias com cada elemento do intervalo
        for($i=$this->limiteInferior; $i <= $this->limiteSuperior; $i++ ) {
            // verifica se as sequências restantes atenderão o critério de tamanho
            if ( $this->tamanho > ( $this->limiteSuperior - $i) ) {
                $this->echoProcess("Não é possível contruir sequencias a partir deste ponto " . $i );
                $this->echoProcess('Não atende a critério do tamanho definido = ' . $this->tamanho);
                break;
            }

            // verifica se as sequências restantes atenderão o critério da soma
            // obs: fórmula é a mesma de uma pa
            $soma_restante = (( $this->limiteSuperior + $i ) * ( $this->limiteSuperior - $i + 1 ) ) / 2;
            if ( $soma_restante < $this->soma ) {
                $this->echoProcess("Não é possível fazer contruir sequencias a partir deste ponto " . $i );
                $this->echoProcess('Não atende a critério da soma definida = ' . $this->soma);
                break;
            }

            // o elemento corrente forma o primeiro elemento da sequência
            $sequencia_base=array($i);

            // obtêm todas as sequencias que começam com  o elemento $i
            // e que satisfaçam os critérios de tamanho e soma definos em
            // $this->soma e $this->tamanho
            $this->fillSequences($sequencia_base,$i);
        }
    }

    // preenche a sequência a partir do elemento atual
    // (uso de recursividade)
    private function fillSequences($sequenciaBase,$elementoAtual) {
        for($i=($elementoAtual+1); $i <= $this->limiteSuperior; $i++ ) {
            // guarda a sequencia base
            $sequencia_aux=$sequenciaBase;

            // obtem tamanho da sequencia e soma dos elementos
            $soma_sequencia=array_sum($sequencia_aux) + $i;
            $tam_sequencia=count($sequencia_aux) + 1;

            // passou soma ou tamanho, descarta
            if ( ( $soma_sequencia > $this->soma ) || ( $tam_sequencia > $this->tamanho ) ) {
                break;
            }

            // critério de soma e tamanho ok?
            // Sim: armazena, não: descarta
            if ( $soma_sequencia == $this->soma ) {
                if ( $tam_sequencia == $this->tamanho ) {
                    $sequencia_aux[]=$i;
                    $this->arrSequencias[]=$sequencia_aux;
                    break;
                } else {
                    break;
                }
            }

            // Se sequência ainda não estiver completa, chama o processo de novo
            // (recursividade), se atingiu o tamanho descarta
            if ( $soma_sequencia < $this->soma ) {
                if ( $tam_sequencia < $this->tamanho ) {
                    // coloca o elemento na matriz e chama de novo
                    $sequencia_aux[]=$i;
                    $this->fillSequences($sequencia_aux,$i);
                } else {
                    break;
                }
            }
        }
    }

    /**
    *  imprime as sequências
    */
    function printOutput() {
        $this->echoEol('-----------------------');
        $this->echoEol('Resultados ');
        $this->echoEol('');
        $this->echoEol('Número de Sequências: '  . count($this->arrSequencias));
        $this->echoEol('');

        if ( count($this->arrSequencias) > 0 ) {
            foreach( $this->arrSequencias as $arr_seq) {
                $this->echoEol(implode('-',$arr_seq));
            }
        }

    }

    /**
    *  Retorna o array de sequências
    */
    function getSequences() { return $this->arrSequencias; }
}

$objSeq = new GeradorSequencia();

// define sequencia e imprime
$objSeq->input(4,5,28,87);
$objSeq->printInput();

// gera sequencias
$objSeq->createSequences();

// resultados
$objSeq->printOutput();
$objSeq->echoEol("ok");

?>