Sabendo que os quadrados perfeitos se localizam em intervalos bem definidos:
- Q1 = 0 + 1 = 1
- Q2 = 1 + 3 = 4
- Q3 = 4 + 5 = 9
- Q4 = 9 + 7 = 16
- Q5 = 16 + 9 = 25
Simplificando:
- Q1 = 1
- Qn = Qn-1 + 2n - 1
Podemos imprimir a sequência, sem depender de sqrt
, o que faz desta a forma mais rápida (só que não... nem sempre é assim) de processar tal sequência:
function QuadradoPerfeito(n) {
var out = '';
var x = 1;
for (var i = 3; ; i += 2)
for (var j = 0; j < i; j++) {
if (x > n) return out;
out += x + (j == 0 ? ' QUADRADO PERFEITO' : '') + '<br>';
x++;
}
}
document.body.innerHTML = QuadradoPerfeito(100);
Mas dois laços aninhados... não é mais lento?
Apesar de ter dois loops aninhados, a quantidade total de cálculos feitos é linear, pois a condição de saída está sobre a variável x
, que é incrementada em cada passagem.
Além disso, o browser é capaz de otimizar esses laços aninhados de tal forma,
que mesmo refazendo o código com um único laço, o resultado ainda fica mais lento,
entretanto fica bem mais fácil de entender a lógica.
Ai vai uma simulação do que acontece ao chamar o método com n=20
:
i=3:
j=0: x=1 // QUADRADO PERFEITO
j=1: x=2
j=2: x=3
i=5:
j=0: x=4 // QUADRADO PERFEITO
j=1: x=5
j=2: x=6
j=3: x=7
j=4: x=8
i=7:
j=0; x=9 // QUADRADO PERFEITO
j=1; x=10
j=2; x=11
j=3; x=12
j=4; x=13
j=5; x=14
j=6; x=15
i=9:
j=0; x=16 // QUADRADO PERFEITO
j=1; x=17
j=2; x=18
j=3; x=19
j=4; x=20
Versão com um único loop, cedida pelo @Bacco
Baseado nos comentários sobre quantidade de loops, @Bacco fez uma versão que tem exatamente a mesma lógica, mas num laço só.
Mas atenção: este laço único não é melhor em termos de performance do que os laços duplos apresentados no início desta resposta! Essa versão serve para ajudar o pessoal com menos experiência a visualizar a lógica.
function QuadradoPerfeito(n) {
var out = '';
var x = 1;
var s = 1;
var i;
for ( i = 1; i <= n ; i++ ) {
out += i;
if ( i == x ) {
out += ' QUADRADO PERFEITO';
x = i + (s += 2 );
}
out += ' <br>';
}
return out;
}
document.body.innerHTML = QuadradoPerfeito(100);
function QuadradoPerfeito() { document.write( "1 2 3 4 QUADRADO PERFEITO 5 6 7 8 9 QUADRADO PERFEITO 10 11 12 13 14 15 16 QUADRADO PERFEITO 17 18 19 20 21 22 23 24 25 QUADRADO PERFEITO 26 27 28 29 30 31 32 33 34 35 36 QUADRADO PERFEITO 37 38 39 40 41 42 43 44 45 46 47 48 49 QUADRADO PERFEITO 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 QUADRADO PERFEITO 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 QUADRADO PERFEITO 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 QUADRADO PERFEITO" ) }
:P