14

Estou fazendo uma aplicação onde preciso encontrar Números Felizes dentro de um determinado intervalo, no caso de 0 a 50, e achei isso na Wikipedia:

Os números felizes são definidos pelo seguinte procedimento. Começando com qualquer número inteiro positivo, o número é substituído pela soma dos quadrados dos seus dígitos, e repetir o processo até que o número seja igual a 1 ou até que ele entre num ciclo infinito que não inclui um ou seja a soma dos quadrados dos algarismos do quadrado de um número positivo inicial. Os números no fim do processo de extremidade com 1, são conhecidos como números feliz, mas aqueles que não terminam com um 1 são números chamados infelizes.

E consta um exemplo de como saber se o número é Feliz:

7 é um número feliz:

inserir a descrição da imagem aqui

Se n não é feliz, a soma dos quadrados nunca dará 1, serão gerados infinitos termos.

Como seria um algoritmo para encontrar esses números no do intervalo citado? Tenho muita dificuldade em trabalhar com potências em JavaScript.

Os números felizes entre 0 e 50 seriam:

1, 7, 10, 13, 19, 23, 28, 31, 32, 44, 49

Eu precisava de um código para chegar a esse resultado.

3 Respostas 3

17

Uma outra forma de fazer, é quebrando a string e utilizando Math.pow em cada um dos "pedaços", por exemplo:

function beHappy(value) {

  let repeat = [];

  /**
   * Verifica se o valor é maior que 1 e se
   * o valor não é repetido, isso irá evitar
   * um loop infinito
   */
  while (value > 1 && !~repeat.indexOf(value)) {
    let result = 0;

    /**
     * Adiciona o valor para na variável
     * repeat para evitar o loop infinito
     */
    repeat.push(value);

    /* Quebra a string em pedaços */
    for (let n of value.toString().split("")) {

      /**
       * Utiliza o Math.pow para calcular a base
       * elevado ao expoente. É o mesmo que n * n
       */
      result += Math.pow(n, 2)
    }

    value = result;
  }

  return value == 1;
}

for (let i = 0; i <= 50; i++) {
  if (beHappy(i)) {
    console.log(i);
  }
}

5
  • Valeu! Ficou muito bom.
    – Sam
    Commented 14/03/2018 às 1:38
  • 1
    Só fiz uma adaptação: var nums = []; if (beHappy(i)) nums.push(i); para criar um array com os resultados
    – Sam
    Commented 14/03/2018 às 1:41
  • Pode explicar o uso de && !~repeat.indexOf(value)?
    – lazyFox
    Commented 14/03/2018 às 9:45
  • @lazyFox O ~ é um operador bitwise. Se o valor de retorno do indexOf for -1, então ~-1 será igual a 0, porque -1é uma seqüência de caracteres de todos os 1 bits. Um pouco difícil de entender? A formula dele é -(x + 1), ou -(-1+1) = 0; -(-2+1) = 1; -(3+1) = -4. A exclamação é para transformar o valor falso em verdadeiro, semelhante o ¬ da tabela verdade. Commented 14/03/2018 às 10:03
  • Muito obrigado @ValdeirPsr
    – lazyFox
    Commented 14/03/2018 às 10:25
15

Adaptado do Rosetta Code para o SOpt:

https://rosettacode.org/wiki/Happy_numbers#JavaScript

Licença da reprodução do documento:

https://www.gnu.org/licenses/fdl-1.2.html

Mudei a faixa para 0-50 e pus os devidos comentários no código.

Basicamente é feito o que foi pedido no enunciado, o único detalhe a mais que importa é o critério para sabermos a hora de parar:

Como a sequência pode ser muito grande, as únicas alternativas que temos é achar o 1, concluindo pela "felicidade" do número, ou achar um resultado repetido, o que caracterizaria um loop "infeliz".

function happy(number) {
    var m, digit ;

    // cycle é onde vamos acumular os resultados de cada passo
    var cycle = [] ;
 
    // enquanto não encontramos o 1, nem uma repetição, vamos insistindo
    while(number != 1 && cycle[number] !== true) {
        // armazenamos o número analisado no array, para detectar repetição
        cycle[number] = true ;
        m = 0 ;
        while (number > 0) { 

            // o % extrai os dígitos 1 a 1
            digit = number % 10 ;

            // e o valor do quadrado é acumulado em m
            m += digit * digit ;
            number = (number  - digit) / 10 ;
        }
        number = m ;
    }
    return (number == 1) ;
}
 
var number = 0 ;
while(number < 50) { 
    if (happy(number)) document.write(number + " ");
    number++;
}

Otimização possível: armazenar os resultados anteriores marcando-os com "feliz" ou "infeliz", pois se no loop de busca surgir algum "feliz", o número de origem é "feliz" também (o oposto também é verdadeiro, se for encontrado algum "infeliz" na busca, o número de origem também é "infeliz")

Leitura recomendada, da Enciclopédia Online de Sequências de Inteiros:

http://oeis.org/A007770

1
  • 1
    Boto fé. Ficou legal. Obg!
    – Sam
    Commented 14/03/2018 às 1:12
13

Como a função para saber se um número é ou não feliz é uma função pura, podemos usar nela memoização.

Uma maneira muito fácil de fazer memoização é com recursão. Note que a própria definição de feliz pode ser interpretada de maneira recursiva:

Se o número em questão for 1, ele é feliz.

Se o número não for 1, então ele é feliz se a soma do quadrado dos seus dígitos for feliz.

No caso, se a recursão não convergir, então isso implica que o número é infeliz (coitadinho =/ ).

Agora, será que, diferentemente da conjectura de Collatz, eu consigo demonstrar que a sequência do somatório dos dígitos de um número converge para laços finitos? Sim, conseguimos. (A ideia de identificar os laços eu pesquei da resposta do @Bacco)

Pegue um número grande. Nós sabemos que ele tem n dígitos. Qualquer número com n dígitos tem como soma máxima do quadrado dos seus dígitos como n*9^2. Basta então verificar que essa soma vai ser menor do que qualquer número de n dígitos. O menor número de n dígitos é 10^(n-1). Então, se para a maior soma de quadrados de dígitos com n dígitos ela for menor do que o menor número de n dígitos, então temos que 10^(n-1) será um limite superior a essa soma, portanto não haverá laços com elemetos maiores que 10^(n-1). Isso também limitado o tamanho máximo do laço para 10^(n-1).

Peguemos com n = 4. O menor número é 1000. A maior soma é 4*81 = 324. Isso significa que qualquer soma feita com 4 dígitos ou menos será sempre limitada a 324. Isso implica que não haverá laços com mais do que 1000 elementos, com todos os elementos limitados a no máximo o número 1000.

Ok, o limite na verdade é bem menor, mas o limite relaxado já é o suficiente para a demonstração

Pegando essa ideia, podemos fazer a função feliz que faz uma verificação recursiva pela felicidade dos números. Para isso, uso um "caminho de migalhas" que, sempre que toco nele, detecto o laço e portanto a infelicidade do número. Também aproveito conhecimento prévio da felicidade alheia e se a soma dos quadrados dos dígitos já for conhecidamente feliz ou infeliz e marco meu caminho de volta com essa medida de felicidade.

No caso, minha memória é posicional e cada posição consiste de um estado. Existem 4 possíveis estados:

  • undefined: memória nova, não tenho nada memoizado para essa posição
  • 'H': feliz =)
  • 'M': triste =/
  • 'S': minha migalha, não sei ainda

Note que para a memoização funcionar corretamente, esse caminho de migalhas impede a execução paralela de descobrimento de novas memórias. Se com essa memoização alguém colocar esse algoritmo para servir duas perguntas sobre a felicidade dos números em paralelo, o resultado não será garantido. E a partir desse ponto a memória deve ser limpa para começar de novo.

Um detalhe importante é que a memoização aqui começa com o caso base já na memória: eu já começo lembrando que 1 ==> 'H'.

Segue a versão mais legível, com trace para verificar a memória e apenas alguns poucos números testados:

function soma_quad_digits(numero) {
  let soma_quad = 0;
  while (numero > 0) {
    let dig = numero % 10;
    numero = Math.floor(numero/10);
    soma_quad += dig*dig;
  }
  return soma_quad;
}

function felicidade_memoizada(numero, memoria) {
  if (memoria[numero] === undefined) {
    console.log("indo atrás da felicidade de " + numero + " (soma do quadrado dos dígitos: " + soma_quad_digits(numero) + ")");
    // memória aqui é indefinida! oba \o/
    memoria[numero] = 'S'; // S de SEARCHING, usado pra marcar loops
    let nova_memoria = felicidade_memoizada(soma_quad_digits(numero), memoria); // busca a nova memória recursivamente
    memoria[numero] = nova_memoria; // fazendo a memoização
    console.log("memorizando que " + numero + " é " + nova_memoria);
    return nova_memoria;
  } else if (memoria[numero] == 'H') { // H de HAPPY
    return 'H'; // sim, achou memória feliz
  } else if (memoria[numero] == 'M') { // M de MAD
    return 'M'; // caí num caso conhecido de infelicidade
  } else if (memoria[numero] == 'S') { // oh, oh... loop
    // nesse caso, na recursão que preencheu como SEARCHING originalmente  vai marcar esse cara como MAD...
    return 'M';
  }
}

let memoria = [];
memoria[1] = 'H'; // definição

let feliz = (n) => felicidade_memoizada(n, memoria) == 'H';

console.log(feliz(2));
console.log(feliz(7));
console.log(feliz(19));
console.log(feliz(23));
console.log(feliz(50));

Agora, poderíamos ter de modo mais elegante a criação da função feliz. Não gostei muito de deixar a variável memoria no escopo global. Podemos usar uma função autoinvocada que retorna a função feliz. Essa versão eu já sacrifico logo todos os comentários e legibilidade:

let feliz = (function() {
  function soma_quad_digits(numero) {
    let soma_quad = 0;
    for (let dig = numero % 10; numero > 0; numero = (numero/10)|0, dig = numero%10) {
      soma_quad += dig*dig;
    }
    return soma_quad;
  }

  function felicidade_memoizada(numero, memoria) {
    if (numero > 10000) {
      return felicidade_memoizada(soma_quad_digits(numero), memoria);
    }
    if (memoria[numero] === undefined) {
      memoria[numero] = 'S';
      return memoria[numero] = felicidade_memoizada(soma_quad_digits(numero), memoria);
    } else if (memoria[numero] == 'H') {
      return 'H';
    } else {
      return 'M';
    }
  }

  let memoria = [];
  memoria[1] = 'H';

  return (n) => felicidade_memoizada(n, memoria) == 'H';
})();

for (let i = 0; i <= 50; i++) {
  if (feliz(i)) {
    console.log(i);
  }
}

Mas, sinceramente, por que nos limitar a apenas 50? Vamos até o limite superior relaxado do laço, que seria 1000?

let feliz = (function() {
  function soma_quad_digits(numero) {
    let soma_quad = 0;
    for (let dig = numero % 10; numero > 0; numero = (numero/10)|0, dig = numero%10) {
      soma_quad += dig*dig;
    }
    return soma_quad;
  }

  function felicidade_memoizada(numero, memoria) {
    if (numero > 10000) {
      return felicidade_memoizada(soma_quad_digits(numero), memoria);
    }
    if (memoria[numero] === undefined) {
      memoria[numero] = 'S';
      return memoria[numero] = felicidade_memoizada(soma_quad_digits(numero), memoria);
    } else if (memoria[numero] == 'H') {
      return 'H';
    } else {
      return 'M';
    }
  }

  let memoria = [];
  memoria[1] = 'H';

  return (n) => felicidade_memoizada(n, memoria) == 'H';
})();

for (let i = 0; i <= 1000; i++) {
  if (feliz(i)) {
    document.write(i + " "); // tentei ficar só no log, mas ficou grande demais...
  }
}

0

Você deve fazer log-in para responder a esta pergunta.

Esta não é a resposta que você está procurando? Pesquise outras perguntas com a tag .