Exercício para pensar
Só para descontrair, um exercício que exige algum raciocínio. Quando eu era jovem, este exercício mudou a minha vida.
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?
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
Curtidas 0
Melhor post
Frank Hosaka
06/04/2023
Eu só consegui três números pelo PHP:
<?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
GOSTEI 1
Mais Respostas
Arthur Heinrich
06/04/2023
Eu só consegui três números pelo PHP:
<?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.
GOSTEI 0
Arthur Heinrich
06/04/2023
Uma possível otimização.
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.
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.
GOSTEI 0
Frank Hosaka
06/04/2023
Usando o tuning (ou seja, fazer o processador trabalhar até onde for preciso), consegui 9 possibilidades:
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"?
<?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"?
GOSTEI 0
Frank Hosaka
06/04/2023
Ah, consegui achar o erro! Eu esqueci de fazer a prova dos nove:
<?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
GOSTEI 1
Arthur Heinrich
06/04/2023
Ah, consegui achar o erro! Eu esqueci de fazer a prova dos nove:
<?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.
GOSTEI 0
Arthur Heinrich
06/04/2023
Um outro tipo de otimização seria alterar o uso da divisão por uma multiplicação, o que permitiria utilizar aritimética com inteiros, muito mais eficiente.
Para que o quadrado de um número tenha 4 dígitos, ele precisa estar entre 32 e 99.
Mas dá para ser ainda melhor.
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.
GOSTEI 0
Arthur Heinrich
06/04/2023
Pesquisando um pouco, reparei que o PHP possui uma função para efetuar divisão de inteiros, com resultado inteiro, diretamente.
Assim, o código:
poderia ser escrito:
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.
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.
GOSTEI 0
Arthur Heinrich
06/04/2023
Agora que já dei um tempo suficiente para quem quisesse exercitar o raciocínio, vou colocar abaixo um comparativo de alguns algoritmos, para mostrar as consequências de vícios de programação e más escolhas de algoritmos.
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:
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.
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;
GOSTEI 0