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.174 ]
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"); ?>
Transformar datas para gravar no banco de dados (MySQL, Postgres e outros)
Função para remover acentuação de uma string
Nenhum comentário foi encontrado.
Passkeys: A Evolução da Autenticação Digital
Instalação de distro Linux em computadores, netbooks, etc, em rede com o Clonezilla
Título: Descobrindo o IP externo da VPN no Linux
Armazenando a senha de sua carteira Bitcoin de forma segura no Linux
Enviar mensagem ao usuário trabalhando com as opções do php.ini
Instalando Brave Browser no Linux Mint 22
vídeo pra quem quer saber como funciona Proteção de Memória:
Encontre seus arquivos facilmente com o Drill
Mouse Logitech MX Ergo Advanced Wireless Trackball no Linux
Compartilhamento de Rede com samba em modo Público/Anônimo de forma simples, rápido e fácil
VMs e Interfaces de Rede desapareceram (12)
Instalação do drive do adaptador wiffi (7)