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.269 ]
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"); ?>
Simulado semelhante ao do vol em PHP!
gerador de tabelas em html v2.2
Converter String para Maiúsculas
Nenhum comentário foi encontrado.
Automatizando digitação de códigos 2FA no browser
Resolver problemas de Internet
Como compartilhar a tela do Ubuntu com uma Smart TV (LG, Samsung, etc.)
Como converter imagens PNG/JPEG para SVG em linha de comando
Fez porcaria no teu repositório Git? Aprenda a restaurar uma versão anterior do seu código!
Restaurando Fontes de Download do Hydra no Linux
Atualizando "na marra" o YT-DLP quando começa a dar erro de downloads
Como instalar o WPS com interface e corretor ortográfico em PT-BR no Arch Linux
Meu Linux Mint não mostra nenhuma opção de WiFi (1)
Linux mint não desliga corretamente mesmo mexendo no grub (2)