Exercício para pensar
06/04/2023
0
Imagine um número inteiro de 4 dígitos (1000 a 9999). O desafio consiste em encontrar todos os valores deste intervalo que respeitem a seguinte regra:
1 - Represente o seu número em duas partes AABB, onde AA é formado pelo milhar e centena e BB pela dezena e unidade.
Ex.: 2025 -> AA = 20 e BB = 25
2 - Some as duas partes
20 + 25 -> 45
3 - Eleve ao quadrado
45 * 45 = 2025 (mesmo valor do número original)
Como encontrar todos os valores em que isto é verdade?
Arthur Heinrich
Post mais votado
06/04/2023
<?php for($i=1000;$i<=9999;$i++){ $j=intval($i/100); $k=intval(($i/100-$j)*100); $l=($j+$k)**2; if($l==$i){echo "$i => $j $k => ( $j + $k)**2= $l <br>";} }
2025 => 20 25 => ( 20 + 25)**2= 2025 3025 => 30 25 => ( 30 + 25)**2= 3025 9801 => 98 1 => ( 98 + 1)**2= 9801
Frank Hosaka
Mais Posts
06/04/2023
Arthur Heinrich
<?php for($i=1000;$i<=9999;$i++){ $j=intval($i/100); $k=intval(($i/100-$j)*100); $l=($j+$k)**2; if($l==$i){echo "$i => $j $k => ( $j + $k)**2= $l <br>";} }
2025 => 20 25 => ( 20 + 25)**2= 2025 3025 => 30 25 => ( 30 + 25)**2= 3025 9801 => 98 1 => ( 98 + 1)**2= 9801
Este algoritmo segue exatamente o procedimento que eu descrevi e funciona.
Porém, dá para fazer a mesma coisa gastando bem menos recursos computacionais.
06/04/2023
Arthur Heinrich
Por que testar todos os números de 1000 a 9999, se sabemos que, para o número 1000 faremos (10 + 0)^2, que nem chega em 1000?
O que mais podemos fazer para chegar no resultado com o mínimo de esforço?
Como eu disse, é um exercício para pensar.
Existem várias formas de se resolver este problema. Posso citar 3:
1 - Força bruta
2 - Uso mais racional dos recursos analisando o processo (tuning)
3 - Resolvendo matematicamente uma equação do quarto grau, que apresenta uma resposta negativa (que não convém) e 3 positivas.
Como eu postei o desafio sob a tag algoritmo, estou estimulando as pessoas a chegarem na solução 2, tunada. Posso afirmar que ela é bem mais eficiente.
07/04/2023
Frank Hosaka
<?php for($i=1000;$i<=9999;$i++){ $j=intval($i/100); $k=intval(($i/100-$j)*100); $l=($j+$k)**2; if($l>$i){$i=(intval($i/100)+1)*100;if($i>9999){exit;}} if($l==$i){echo "$i => $j $k => ( $j + $k)**2= $l <br>";} } // resultado: 1600 => 15 25 => ( 15 + 25)**2= 1600 2025 => 20 25 => ( 20 + 25)**2= 2025 2500 => 24 26 => ( 24 + 26)**2= 2500 3025 => 30 25 => ( 30 + 25)**2= 3025 3600 => 35 25 => ( 35 + 25)**2= 3600 4900 => 48 22 => ( 48 + 22)**2= 4900 6400 => 63 17 => ( 63 + 17)**2= 6400 8100 => 80 10 => ( 80 + 10)**2= 8100 9801 => 98 1 => ( 98 + 1)**2= 9801
e assim chegamos na conclusão de que o computador só funciona se você tratar com carinho, você não pode abrir o fórum iMasters e o Facebook ao mesmo tempo, mas apenas um aplicativo de cada vez. Mesmo assim, será que é possível corrigir o algoritimo da "força bruta"?
07/04/2023
Frank Hosaka
<?php for($i=1000;$i<=9999;$i++){ $j=intval($i/100); $k=intval(($i/100-$j)*100); $l=($j+$k)**2; if($l==$i){echo "$i => $j $k => ( $j + $k)**2= $l <br>";} if($l>$i){$i=(intval($i/100)+1)*100;if($i>9999){exit;}} } resultado: 2025 => 20 25 => ( 20 + 25)**2= 2025 3025 => 30 25 => ( 30 + 25)**2= 3025 9801 => 98 1 => ( 98 + 1)**2= 9801
07/04/2023
Arthur Heinrich
<?php for($i=1000;$i<=9999;$i++){ $j=intval($i/100); $k=intval(($i/100-$j)*100); $l=($j+$k)**2; if($l==$i){echo "$i => $j $k => ( $j + $k)**2= $l <br>";} if($l>$i){$i=(intval($i/100)+1)*100;if($i>9999){exit;}} } resultado: 2025 => 20 25 => ( 20 + 25)**2= 2025 3025 => 30 25 => ( 30 + 25)**2= 3025 9801 => 98 1 => ( 98 + 1)**2= 9801
Esta otimização é interessante, pois dá uma resetada no segundo componente do número e avança 1 no primeiro.
Porém, nem todas as linguagens permitem manipular a variável de um loop for. Talvez tivesse que mudar para um loop while.
Ex: o número 3428, por exemplo, seria substituído por 3500. Mas o loop termina incrementando o i, que vira 3501. Perderíamos o teste do 3500.
De qualquer forma, ainda testaria muitos valores. Por exemplo, testeria os números 1000 a 1022 até perceber que deveria pular para o 1100.
Dá para fazer ainda melhor.
07/04/2023
Arthur Heinrich
Para que o quadrado de um número tenha 4 dígitos, ele precisa estar entre 32 e 99.
for i = 10 to 99 do for j = 32-i to 99-i do If (i+j)^2 = i*100+j then print i*100+j
Mas dá para ser ainda melhor.
07/04/2023
Arthur Heinrich
Assim, o código:
$j=intval($i/100); $k=intval(($i/100-$j)*100);
poderia ser escrito:
$j=intdiv($i, 100); $k=$i %100;
Como o computador utiliza notação binária, dividir um número por 100 não gera um número simples. A divisão de dois números inteiros se transforma em um número de ponto flutuante e várias conversões precisam ser feitas para que a divisão seja feita e se obtenha um número inteiro, truncando a parte fracionária ao final.
Só para termos uma ideia da diferença, quando o processador 8086 (origem da linha x86) foi criado, ele não possuía funções para aritmética em ponto flutuante. Para isso, era necessário instalar um co-processador 8087.
Mesmo utilizando apenas aritmética com inteiros, uma multiplicação consumia 5 pulsos de clock enquanto a divisão consumia 157 pulsos.
Se pensarmos em computadores mais antigos, como o Apple II, que utilizava o processador 6502, ele possuía apenas 3 registradores de 8 bits e era dotado apenas de uma instrução para somar e outra para subtrair, utilizando 2 bytes. Um número como os do desafio, que vão de 1000 a 9999 precisavam ser armazenados em dois bytes e precisávamos de uma rotina para multiplicar e dividir, feita em Assembly, ou éramos obrigados a utilizar as operações de multiplicação e divisão da linguagem Applesoft Basic, que só trabalhava com ponto flutuante de 10 dígitos de precisão. Qualquer cálculo feito neste computador era muito lento e a rotina da primeira resposta a este desafio demorava 15 minutos para terminar.
10/04/2023
Arthur Heinrich
Eu utilizei 7 métodos.
Do método 1 para o 2, queria mostrar que usar potenciação para elevar ao quadrado é muito pior do que multiplicar o número por ele mesmo.
No método 3 eu substitui as divisões de ponto flutuante por divisões inteiras.
No método 4 implementei a otimização sugerida.
No método 5 utilizei dois loops eliminando as divisões mas sem a otimização.
No método 6 utilizei dois loops eliminando as divisões e com a otimização.
O método 7 utiliza o melhor algoritmo, fazendo um loop pela soma dos termos e não pelo número.
Este problema possui um ciclo fechado.
Número Inteiro (AABB) -> Parcelas (AA e BB) -> Soma (AA + BB) -> Quadrado ( (AA + BB)^2 = AABB)
Sabemos que uma mesma soma sempre gerará o mesmo quadrado. Logo, testar os números 1030, 1129, 1228, 1327, ..., sempre vão produzir a mesma soma.
Logo, se fazemos o loop pelos valores de soma que produzem números de 4 dígitos, vamos analisar apenas os números de 32 a 99 ou 68 loops no nosso algoritmo, ao invés de 9000 no algoritmo da força bruta.
Medi os tempos de execução em pulsos de clock. Seguem os tempos:
Metodo Pulsos Clock Numeros ---------------------------------------- ------------ ---------------- Forτa Bruta - Ponto Flutuante/Potencia 811760 2025, 3025, 9801 Forτa Bruta - Ponto Flutuante/Multiplic. 124728 2025, 3025, 9801 Forτa Bruta - Arit. Inteiros/Multiplic. 93613 2025, 3025, 9801 Forτa Bruta - Arit. Inteiros/Otimizado 21433 2025, 3025, 9801 Forτa Bruta - Dois Loops - Inteiros 6625 2025, 3025, 9801 Forτa Bruta - Dois Loops - Int./Otimiz. 4185 2025, 3025, 9801 Loop pela soma 877 2025, 3025, 9801
Seguem as rotinas utilizadas (linguagem Pascal).
Obs.: As rotinas apenas armazenam os valores encontrados em um array, porque exibir dados na tela consome muito recurso.
procedure Metodo1; var i, a, b, p : Integer; begin for i:=1000 to 9999 do begin a:=Trunc(i/100); b:=Round((i/100-a)*100); p:=Trunc(Power(a+b,2)); if (i=p) then begin R[n]:=i; Inc(n); end; end; end; procedure Metodo2; var i, a, b, p : Integer; begin for i:=1000 to 9999 do begin a:=Trunc(i/100); b:=Round((i/100-a)*100); p:=a+b; p:=p*p; if (i=p) then begin R[n]:=i; Inc(n); end; end; end; procedure Metodo3; var i, a, b, p : Integer; begin for i:=1000 to 9999 do begin a:=i div 100; b:=i mod 100; p:=a+b; p:=p*p; if (i=p) then begin R[n]:=i; Inc(n); end; end; end; procedure Metodo4; var i, a, b, p : Integer; begin i:=1000; while (i<=9999) do begin a:=i div 100; b:=i mod 100; p:=a+b; p:=p*p; if (i=p) then begin R[n]:=i; Inc(n); end; if (p<i) then Inc(i) else i:=((i div 100)+1)*100; end; end; procedure Metodo5; var i, j, a, b, c, p : Integer; begin for i:=10 to 99 do begin a:=32-i; if (a<0) then a:=0;; b:=99-i; for j:=a to b do begin p:=i+j; p:=p*p; c:=i*100+j; if (p = c) then begin R[n]:=p; Inc(n); end; end; end; end; procedure Metodo6; var i, j, a, b, c, p : Integer; begin i:=10; while (i<=99) do begin a:=32-i; if (a<0) then a:=0;; b:=99-i; for j:=a to b do begin p:=i+j; p:=p*p; c:=i*100+j; if (p = c) then begin R[n]:=p; Inc(n); end; if (p>=c) then Break; end; Inc(i); end; end; procedure Metodo7; var i, a, b, p : Integer; begin for i:=32 to 99 do begin p:=i*i; a:=p div 100; b:=p mod 100; if (i = (a+b)) then begin R[n]:=p; Inc(n); end; end; end;
Clique aqui para fazer login e interagir na Comunidade :)