Exercício para pensar

06/04/2023

0

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?
Arthur Heinrich

Arthur Heinrich

Responder

Post mais votado

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

Frank Hosaka

Frank Hosaka
Responder

Mais Posts

06/04/2023

Arthur Heinrich

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.
Responder

06/04/2023

Arthur Heinrich

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.
Responder

07/04/2023

Frank Hosaka

Usando o tuning (ou seja, fazer o processador trabalhar até onde for preciso), consegui 9 possibilidades:

<?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"?
Responder

07/04/2023

Frank Hosaka

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
Responder

07/04/2023

Arthur Heinrich

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.
Responder

07/04/2023

Arthur Heinrich

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.

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.
Responder

07/04/2023

Arthur Heinrich

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:

    $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.
Responder

10/04/2023

Arthur Heinrich

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:

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;

Responder

Utilizamos cookies para fornecer uma melhor experiência para nossos usuários, consulte nossa política de privacidade.

Aceitar