1

Galera, estou fazendo o seguinte desafio:

A seguinte sequência iterativa é definida pelo conjunto de inteiros positivos onde:

n -> n/2 (se n é par) n -> 3n + 1 (se n é impar)

Usando as regras acima e começando pelo número 13, nós geraríamos a seguinte sequência:

13 40 20 10 5 16 8 4 2 1

O que pode ser observado dessa sequência (começando no 13 e terminando no 1) é que ela contém 10 itens. Embora ainda não esteja matematicamente provado, é esperando que, dado um numero inteiro positivo qualquer, a sequencia sempre chegará em 1.

Qual inteiro positivo abaixo de 1 milhão, produz a sequência com mais itens?

OBS: seu código precisa executar em menos de 5 segundos para o caso de 1 milhão.

Porém não consigo fazer o script rodar em menos de 13 segundos.

jpklzm$ time php teste.php 
Resposta: 837799
Iterações: 525
real    0m13.737s
user    0m13.203s
sys 0m0.117s

Como posso fazer para melhorar a performance desse script?

<?php
$count = 1;
$hicount = 0;
$hicountOwner = 0;
$n = 0;
for($i = 1; $i < 1000000; $i++){
  $n = $i;
  while($n != 1){
    $n = ($n % 2 === 0) ? $n/2 : ($n * 3) + 1;
    $count++;
  }
  if($count > $hicount){
    $hicount = $count;
    $hicountOwner = $i;
  }
  $count = 1;
}
echo 'Resposta: ',$hicountOwner,PHP_EOL;
echo 'Iterações: ',$hicount;
?>
10
  • Não tem nada no enunciado que precisa ser PHP. Precisa?
    – Maniero
    Commented 28/09/2016 às 2:32
  • 1
    O maior não seria 837799 com 525 iterações? Pois 999904 perfaz em 259. Além do mais, diversos números retornam quantidade igual. Qual desses deve ter prioridade? Todos ou o primeiro que encontrar? Commented 28/09/2016 às 8:36
  • 2
    Não precisa mudar quase nada. O problema é o count sendo resetado no ponto errado. Só de bater o olho no código vi que esse trecho estava errado e testei. Então pude ver que é o $count. Commented 28/09/2016 às 16:40
  • 1
    Adicione o $count = 1; uma linha acima do while($n != 1){ Commented 28/09/2016 às 16:41
  • 1
    Então remova o $count = 1 que está dentro da condicional. Commented 28/09/2016 às 16:42

1 Resposta 1

1

Então galera, eu consegui cumprir o desafio. Fiz um cache para armazenar os dados de operações que já haviam sido feitas para outros número e com isso consegui reduzir a execução do código para 1.5s.

Aqui está o código para quem quiser dar uma olhada:

<?php
ini_set('memory_limit', '-1');
$limit = 1000000;
$hicount = 0;
$hicountOwner = 0;
$n;
$cache = array(0);

for ($i = 0; $i < sizeof($cache); $i++) {
    $cache[$i] = -1;
}
$cache[1] = 1;

for ($i = 1; $i <= $limit; $i++) {
    $n = $i;
    $j = 0;
    while ($n != 1 && $n >= $i) {
        $j++;
        $n = ($n % 2 === 0) ? $n/2 : ($n * 3) + 1;
    }
    $cache[$i] = $j + $cache[$n];
    if ($cache[$i] > $hicount) {
        $hicount = $cache[$i];
        $hicountOwner = $i;
    }
}
echo 'Resposta: ',$hicountOwner,PHP_EOL;
echo 'Iterações: ',$hicount;
?>

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 .