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

Publicado por Luis Henrique Pessoa (última atualização em 30/06/2015)

[ Hits: 3.111 ]

Download sequencia.php




Compartilho um programinha em PHP que gera sequências de números (em ordem crescente e não repetidos) que têm uma coisa em comum: possuem número de elementos e soma destes fixos e determinados pelo usuário.

Exemplo:

- S: Soma das dos elementos = 12
- Ni: Valor mínimo permitido (inclusive) = 1
- Nf: Valor máximo permitido (inclusive) = 6
- L: Quantidade de números da sequencia = 4

Resulta:

- 1+2+3+6 = 12
- 1+2+4+5 = 12

1+5+6 - não imprime pois tem 3 números e não 4, embora totalize também 12.

O programa possui a classe GeradorSequencia e esta possui os seguintes métodos principais:

- input: para entrar com os parâmetros da sequência: tamanho, intervalos inferior e superior para os números da sequência e soma dos números da sequência.
- createSequences: cria sequência a partir de cada número do intervalo fornecido em input.
- fillSequences: preenche as sequências criadas por createSequences. Aqui ocorre o uso da recursividade.

Não levei muito em consideração aspectos como performance e recomendações de codificação. Serve apenas como exemplo didático para uso da recursividade para conseguir resolver uns problemas computacionais.

  



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");

?>

Scripts recomendados

Crivo de Eratóstenes Simples em PHP

Trasnmitir arrays pelo link

Descobrir qual SO o usuário que está acessando o seu site/software está utilizando

Banners rotativos simples

Converter String para Maiúsculas


  

Comentários

Nenhum comentário foi encontrado.


Contribuir com comentário




Patrocínio

Site hospedado pelo provedor RedeHost.
Linux banner

Destaques

Artigos

Dicas

Tópicos

Top 10 do mês

Scripts