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 ]
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.
<?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"); ?>
Crivo de Eratóstenes Simples em PHP
Descobrir qual SO o usuário que está acessando o seu site/software está utilizando
Converter String para Maiúsculas
Nenhum comentário foi encontrado.
Compartilhando a tela do Computador no Celular via Deskreen
Como Configurar um Túnel SSH Reverso para Acessar Sua Máquina Local a Partir de uma Máquina Remota
Configuração para desligamento automatizado de Computadores em um Ambiente Comercial
Como renomear arquivos de letras maiúsculas para minúsculas
Imprimindo no formato livreto no Linux
Vim - incrementando números em substituição
Efeito "livro" em arquivos PDF
Como resolver o erro no CUPS: Unable to get list of printer drivers
Não to conseguindo resolver este problemas ao instalar o playonelinux (1)
Excluir banco de dados no xampp (1)
[Python] Automação de scan de vulnerabilidades
[Python] Script para analise de superficie de ataque
[Shell Script] Novo script para redimensionar, rotacionar, converter e espelhar arquivos de imagem
[Shell Script] Iniciador de DOOM (DSDA-DOOM, Doom Retro ou Woof!)
[Shell Script] Script para adicionar bordas às imagens de uma pasta