Calculando o MMC de N números.

[André D. Molin 15]

Implementei um algoritmo de fatoração por números primos, e o resto foi fácil.

 

 

<?php
abstract class Arithmetic {
   /**
    * Retorna o mínimo múltiplo comúm dos valores contidos no array $numbers.
    * 
    * @param array $numbers A matriz de números.
    * @return int O mínimo múltiplo comúm.
    */
   static public function mmc( array $numbers ) {
       $ret = 1;

       foreach( array_unique( $numbers ) as $number )
           $ret *= array_product( array_unique( self::prime_factoring( (int) $number ) ) );

       return $ret;
   }

   /**
    * Decompõe $number em seus fatores primos.
    * 
    * @param int $number O número.
    * @return array Matriz bidimensional contendo os fatores.
    */
   static private function prime_factoring( $number ) {        
       $ret     = array();
       $checker = 2;

       while( ( $checker * $checker ) <= $number ) {
           if ( ( $number % $checker ) == 0 ) {
               $ret[]   = $checker;
               $number /= $checker;
           } else {
               ++$checker;
           }
       }

       if ( $number != 1 )
           $ret[] = $number;

       return $ret;
   }
}

 

 

Utilizando:

 

echo Arithmetic::mmc( array( 2, 6, 6, 8 ) );

 

Retorna:

 

24

[William Bruno 1501]

muito legal André.

E bem 'didático' até o código, se fosse para 'estudo' mesmo, seria interessante implementar sem usar funções prontas.(as array_)

 

 

geralmente, uso um construtor privado, qndo quero impedir que a classe seja instanciada.

fez a classe como abstrata, prevendo futuras heranças ?

[André D. Molin 15]

fez a classe como abstrata, prevendo futuras heranças ?

Não, fiz isso porque a classe contém apenas um método publico, e esse método é estático. Então não há a mínima necessidade de instanciar essa classe, por isso defini ela como abstrata.

 

geralmente, uso um construtor privado, qndo quero impedir que a classe seja instanciada.

:)

 

E bem 'didático' até o código, se fosse para 'estudo' mesmo, seria interessante implementar sem usar funções prontas.(as array_)

Se o PHP me ofereçe suporte a elas nativamente, não hesitarei em usar. Além do mais, elas são escritas em C, que são MUITO mais rapidas do que se fossem em PHP. Na minha pessoal opinião (rs), não vejo motivo para reinventar a roda.

[William Bruno 1501]

Na minha pessoal opinião (rs), não vejo motivo para reinventar a roda.

 

concordo ^_^

 

é como eu disse: 'se fosse apenas para estudo'.

geralmente qndo você tá tendo aula de alguma linguagem, é interessante pensar no algorítmo por trás das rotinas, por isso por exemplo em exercícios de Java, usar a class Math é 'proibido'.

 

numa situação 'real', é melhor usar oque for mais prático, e não ficar 'reinventando'. ^_^

[André D. Molin 15]

Hmm, para estudo pode até ser legal, mas sei lá. Tipo, estudar o funcionamento de funções separadamente, e não num código que pode possivelmente entrar em produção.

Mas legal mesmo, vamos ver se agente faz um topico para postar coisas assim :).

[Daniel Ribeiro 4]

Gostei bastante da implementação, principalmente por utilizar técnicas peculiares para resolver problemas simples como o dos números primos.

 

Tente seguir neste caminho e implementar outras funções para resolver problemas matemáticos básicos.

 

A minha sugestão é uma função que receba dois (2) números N e M e retorne se eles são primos entre eles (co-primos).

[André D. Molin 15]

Atendendo a seu pedido Daniel, segue a classe atualizada contando com esse método:

 

 

<?php
abstract class Arithmetic {
   /**
    * Retorna o mínimo múltiplo comúm dos valores contidos no array $numbers.
    * 
    * @param array $numbers A matriz de números.
    * @return int O mínimo múltiplo comúm.
    */
   static public function mmc( array $numbers ) {
       $ret = 1;

       foreach( array_unique( $numbers ) as $number )
           $ret *= array_product( array_unique( self::prime_factoring( (int) $number ) ) );

       return $ret;
   }

   /**
    * Retorna um booleano dizendo se os valores contidos no array $numbers são
    * co-primos entre si.
    * 
    * @param array $numbers A matriz de números.
    * @return bool Se os números contidos em $numbers são co-primos entre sí.
    * 
    */
   static public function coprime( array $numbers ) {
       if ( count( $numbers ) < 2 )
           throw new InvalidArgumentException( '$numbers deve conter dois ou mais elementos.' );

       $numbers = array_map( create_function( '$x', 'return Arithmetic::prime_factoring( (int) $x );' ), $numbers );

       return (bool) empty( call_user_func_array( 'array_intersect', $numbers ) );
   }

   /**
    * Decompõe $number em seus fatores primos.
    * 
    * @param int $number O número.
    * @return array Matriz bidimensional contendo os fatores.
    */
   static public function prime_factoring( $number ) {        
       $ret     = array();
       $checker = 2;

       while( ( $checker * $checker ) <= $number ) {
           if ( ( $number % $checker ) == 0 ) {
               $ret[]   = $checker;
               $number /= $checker;
           } else {
               ++$checker;
           }
       }

       if ( $number != 1 )
           $ret[] = $number;

       return $ret;
   }
}

 

 

Eu ainda fiz poucos testes com esse novo método, creio que você possa ir fazendo isso. Para utilizar é bem simples:

 

var_dump( Arithmetic::coprime( array( 5, 10 ) ) );
var_dump( Arithmetic::coprime( array( 20, 21 ) ) );
var_dump( Arithmetic::coprime( array( 8, 9, 15, 55 ) ) );
var_dump( Arithmetic::coprime( array( 30, 42, 70, 105 ) ) );

 

Dá para você utilizar o método com 2 parâmetros ou mais, menos que isso não tem lógica rs. Ela irá retornar um booleano (true ou false) dizendo se aqueles números são ou não primos entre si.

 

Qualquer dúvida só responder aqui.

[Daniel Ribeiro 4]

Muito interessante, André.

 

Agora, vamos analisar a implementação:

 

1) Se você pensa em otimizar o código a nível de performance, o PHP leva, no mínimo, três (3) vezes mais tempo para chamar as funções da maneira implementada (call_user_func_array) do que da maneira simples, diretamente as declarando.

 

2) Sobre a mesma implementação, não será possível passar parâmetros por referência.

 

3) E agora um desafio: faça a análise desses algorítmos, principalmente o dos números primos, e descubra em qual classe assimptótica eles se encontram, e se podem ser otimizados na tabela de classes.

 

;)

[André D. Molin 15]

1) Se você pensa em otimizar o código a nível de performance, o PHP leva, no mínimo, três (3) vezes mais tempo para chamar as funções da maneira implementada (call_user_func_array) do que da maneira simples, diretamente as declarando.

 

Tem reviews/links/testes que me mostrem isso? Fiquei curioso.

 

2) Sobre a mesma implementação, não será possível passar parâmetros por referência.

 

Tá. Só colocar um & lá no método, fechou.

 

3) E agora um desafio: faça a análise desses algorítmos, principalmente o dos números primos, e descubra em qual classe assimptótica eles se encontram, e se podem ser otimizados na tabela de classes.

 

Me ensina isso?

[Daniel Ribeiro 4]

1) Se você pensa em otimizar o código a nível de performance, o PHP leva, no mínimo, três (3) vezes mais tempo para chamar as funções da maneira implementada (call_user_func_array) do que da maneira simples, diretamente as declarando.

 

Tem reviews/links/testes que me mostrem isso? Fiquei curioso.

 

2) Sobre a mesma implementação, não será possível passar parâmetros por referência.

 

Tá. Só colocar um & lá no método, fechou.

 

3) E agora um desafio: faça a análise desses algorítmos, principalmente o dos números primos, e descubra em qual classe assimptótica eles se encontram, e se podem ser otimizados na tabela de classes.

 

Me ensina isso?

 

1) A própria documentação do PHP registra isso.

 

2) Já tentou fazer isso? Veja se funciona.

 

3) Análise de algorítmos é um assunto bastante complexo, interessantíssimo de ser estudado em uma série de posts como as do João sobre orientação a objetos. Pretendo começar a escrever sobre isso em breve. Uma série com vários capítulos compostos de muita matemática, teoria e desafios didáticos. Mas só pra dar um gostinho e pra encaminhar você na direção correta, estude o conceito de análise assimptótica. Verás que as primeiras análises didáticas são feitas em cima de algorítmos de ordenação e busca binária. Otimização de algorítmos é algo muito interessante de se especializar.

[André D. Molin 15]

1) A própria documentação do PHP registra isso.

 

Devo ser muito ruim para achar algo, não encontrei =/. Me mande um link por favor.

 

2) Já tentou fazer isso? Veja se funciona.

 

 

    /**
    * Retorna um booleano dizendo se os valores contidos no array $numbers são
    * co-primos entre si.
    * 
    * @param array $numbers A matriz de números.
    * @return bool Se os números contidos em $numbers são co-primos entre sí.
    * 
    */
   static public function coprime( array &$numbers ) {
       if ( count( $numbers ) < 2 )
           throw new InvalidArgumentException( '$numbers deve conter dois ou mais elementos.' );

       $numbers = array_map( create_function( '$x', 'return Arithmetic::prime_factoring( (int) $x );' ), $numbers );

       return count( call_user_func_array( 'array_intersect', $numbers ) ) == 0;
   }

 

 

 

$array = array( 20, 21 );

var_dump( Arithmetic::coprime( $array ) );
var_dump( $array );

 

 

3) Análise de algorítmos é um assunto bastante complexo, interessantíssimo de ser estudado em uma série de posts como as do João sobre orientação a objetos. Pretendo começar a escrever sobre isso em breve. Uma série com vários capítulos compostos de muita matemática, teoria e desafios didáticos. Mas só pra dar um gostinho e pra encaminhar você na direção correta, estude o conceito de análise assimptótica. Verás que as primeiras análises didáticas são feitas em cima de algorítmos de ordenação e busca binária. Otimização de algorítmos é algo muito interessante de se especializar.

 

Me ajuda então, não sei nem por onde começar.

[Daniel Ribeiro 4]

1) A própria documentação do PHP registra isso.

 

Devo ser muito ruim para achar algo, não encontrei =/. Me mande um link por favor.

 

2) Já tentou fazer isso? Veja se funciona.

 

 

 /** * Retorna um booleano dizendo se os valores contidos no array $numbers são * co-primos entre si. * * @param array $numbers A matriz de números. * @return bool Se os números contidos em $numbers são co-primos entre sí. * */ static public function coprime( array &$numbers ) { if ( count( $numbers ) < 2 ) throw new InvalidArgumentException( '$numbers deve conter dois ou mais elementos.' ); $numbers = array_map( create_function( '$x', 'return Arithmetic::prime_factoring( (int) $x );' ), $numbers ); return count( call_user_func_array( 'array_intersect', $numbers ) ) == 0; }

 

 

 

$array = array( 20, 21 ); var_dump( Arithmetic::coprime( $array ) ); var_dump( $array );

 

 

3) Análise de algorítmos é um assunto bastante complexo, interessantíssimo de ser estudado em uma série de posts como as do João sobre orientação a objetos. Pretendo começar a escrever sobre isso em breve. Uma série com vários capítulos compostos de muita matemática, teoria e desafios didáticos. Mas só pra dar um gostinho e pra encaminhar você na direção correta, estude o conceito de análise assimptótica. Verás que as primeiras análises didáticas são feitas em cima de algorítmos de ordenação e busca binária. Otimização de algorítmos é algo muito interessante de se especializar.

 

Me ajuda então, não sei nem por onde começar.

 

1) http://br.php.net/manual/pt_BR/function.call-user-func-array.php#97473

 

2) Você não entendeu o que eu quis dizer. Quando me refiro ao problema dos parâmetros por referência, quero dizer algo como:

 

function ref(&$foo) {
...
}

call_user_func_array('ref', array($foo));

 

Para este caso é que o problema persiste.

 

3) Estou começando a escrever aquela série de que te falei. Em breve poderemos estudar juntamente com o resto da comunidade.

[André D. Molin 15]

1) http://br.php.net/ma...array.php#97473

 

Hm, pensei que fosse algo oficial.

 

2) Você não entendeu o que eu quis dizer. Quando me refiro ao problema dos parâmetros por referência, quero dizer algo como:

 

Sim, nesse caso não funciona. E no meu?

 

3) Estou começando a escrever aquela série de que te falei. Em breve poderemos estudar juntamente com o resto da comunidade.

 

Obrigado. Com certeza irei ler.

[Daniel Ribeiro 4]

Mas sem dúvida, André, as implementações estão muito bem feitas, especialmente por seguirem um padrão diferente, como já havia lhe dito. Vamos seguir essa proposta e exercitar ainda mais tudo isso.

 

Tenho algumas sugestões, mas vamos com uma de cada vez:

 

Conhece o desafio da Torre de Hanoi? Implemente um algorítmo que retorne a sequência necessária de movimentos para realocar de 2 a 4 argolas. A partir de 5 argolas, devido ao fato de ser um algorítmo exponencial, a coisa começa a ficar complicada. É nesse ponto que entra a análise de performance e otimização. Mas chegamos lá depois. Faça o básico primeiro. Lembre-se, é matemática teórica! Outra dica: utilize recursividade.

 

Se achar que o desafio foge um pouco do sentido do tópico, pensamos em outra coisa.

[Daniel Ribeiro 4]

É... acho que ficou fora do escopo do tópico essa última sugestão...

 

Faz o seguinte André, implementa a função pra retornar a sequência de Fibonacci aí... é rapidinho e legal.