Fórum Exercício para pensar #619775

06/04/2023

0

Algoritmo Performance

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:
1
2
3
4
5
6
7
<?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>";}
}


1
2
3
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

Gostei + 1

Mais Posts

06/04/2023

Arthur Heinrich

Eu só consegui três números pelo PHP:
1
2
3
4
5
6
7
<?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>";}
}


1
2
3
2025 => 20 25 => ( 20 + 25)**2= 2025
3025 => 30 25 => ( 30 + 25)**2= 3025
9801 => 98 1 => ( 98 + 1)**2= 9801

Ler Mais...



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

Gostei + 0

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

Gostei + 0

07/04/2023

Frank Hosaka

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
<?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

Gostei + 0

07/04/2023

Frank Hosaka

Ah, consegui achar o erro! Eu esqueci de fazer a prova dos nove:

1
2
3
4
5
6
7
8
9
10
11
12
13
<?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

Gostei + 1

07/04/2023

Arthur Heinrich

Ah, consegui achar o erro! Eu esqueci de fazer a prova dos nove:

1
2
3
4
5
6
7
8
9
10
11
12
13
<?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

Ler Mais...



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

Gostei + 0

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.

1
2
3
4
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

Gostei + 0

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:

1
2
$j=intval($i/100);
$k=intval(($i/100-$j)*100);


poderia ser escrito:

1
2
$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

Gostei + 0

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:

1
2
3
4
5
6
7
8
9
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.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
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

Gostei + 0

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

Aceitar