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: 2.952 ]
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"); ?>
Entendendo os operadores de atribuição
PHP - Remover acentos e caracteres especiais
Converter String para Minúsculo
Nenhum comentário foi encontrado.
Melhorando o tempo de boot do Fedora e outras distribuições
Como instalar as extensões Dash To Dock e Hide Top Bar no Gnome 45/46
E a guerra contra bots continua
Tradução do artigo do filósofo Gottfried Wilhelm Leibniz sobre o sistema binário
Conheça o firewall OpenGFW, uma implementação do (Great Firewall of China).
Instalando o FreeOffice no LMDE 6
Anki: Remover Tags de Estilo HTML de Todas as Cartas
Colocando uma opção de redimensionamento de imagem no menu de contexto do KDE
Não consigo acessar os modos de desempenho (2)
Ubuntu — tentando iniciar o windows? (0)
[Shell Script] Script para desinstalar pacotes desnecessários no OpenSuse
[Shell Script] Script para criar certificados de forma automatizada no OpenVpn
[Shell Script] Conversor de vídeo com opção de legenda
[C/C++] BRT - Bulk Renaming Tool
[Shell Script] Criação de Usuarios , Grupo e instalação do servidor de arquivos samba