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.969 ]
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"); ?>
Data em extenso para Cabeçalho
Nenhum comentário foi encontrado.
Atualizar o macOS no Mac - Opencore Legacy Patcher
Crie alias para as tarefas que possuam longas linhas de comando - bash e zsh
Criando um gateway de internet com o Debian
Configuração básica do Conky para mostrar informações sobre a sua máquina no Desktop
Aprenda a criar músicas com Inteligência Artificial usando Suno AI
Instalando Zoom Client no Ubuntu 24.04 LTS
Instalando Zoom Client no Fedora 40
Instalando Navegador Firefox no Debian 12
Bloqueando propagandas no Youtube e outros sites com o uBlocker Origin
Configurando static ipv6 em placa de rede eth0[DUVIDA] (1)
Sistema da Coréia do Norte - Red Star OS (59)
Comando interno CD não funciona (16)
Dificuldade em ler binário (12)
Em que pasta/arquivo ficam as configurações das janelas em derivados d... (2)