Essa interessante questão de computação/programação/matemática foi retirada do site projecteuler.net , é a questão 18.
http://projecteuler.net/problem=18
Leia:
--------------------
Problem 18
31 May 2002
By starting at the top of the triangle below and moving to adjacent numbers on the row below, the maximum total from top to bottom is 23.
Começando do topo do triângulo abaixo e movendo-se apenas para números adjacentes da fileira abaixo, a sequência que tem maior soma resulta em 23.
Pois, 3 + 7 + 4 + 9 = 23.
Find the maximum total from top to bottom of the triangle below:
Ache a sequência de soma máximo do topo até a base do triângulo abaixo:
Começando do topo do triângulo abaixo e movendo-se apenas para números adjacentes da fileira abaixo, a sequência que tem maior soma resulta em 23.
3
7 4
2 4 6
8 5 9 3
That is, 3 + 7 + 4 + 9 = 23.7 4
2 4 6
8 5 9 3
Pois, 3 + 7 + 4 + 9 = 23.
Find the maximum total from top to bottom of the triangle below:
Ache a sequência de soma máximo do topo até a base do triângulo abaixo:
75
95 64
17 47 82
18 35 87 10
20 04 82 47 65
19 01 23 75 03 34
88 02 77 73 07 63 67
99 65 04 28 06 16 70 92
41 41 26 56 83 40 80 70 33
41 48 72 33 47 32 37 16 94 29
53 71 44 65 25 43 91 52 97 51 14
70 11 33 28 77 73 17 78 39 68 17 57
91 71 52 38 17 14 91 43 58 50 27 29 48
63 66 04 68 89 53 67 30 73 16 69 87 40 31
04 62 98 27 23 09 70 98 73 93 38 53 60 04 23
95 64
17 47 82
18 35 87 10
20 04 82 47 65
19 01 23 75 03 34
88 02 77 73 07 63 67
99 65 04 28 06 16 70 92
41 41 26 56 83 40 80 70 33
41 48 72 33 47 32 37 16 94 29
53 71 44 65 25 43 91 52 97 51 14
70 11 33 28 77 73 17 78 39 68 17 57
91 71 52 38 17 14 91 43 58 50 27 29 48
63 66 04 68 89 53 67 30 73 16 69 87 40 31
04 62 98 27 23 09 70 98 73 93 38 53 60 04 23
--------------------
É possível resolver por força bruta. Força bruta é simplesmente sair somando todos os casos possíveis (obedecendo as regras no caso é a adjacência) e depois calcular a maior soma.
Força bruta pode funcionar para este caso, pois o triângulo possui somente 15 linhas e 16384.
Se o triângulo tivesse mais linhas, como centenas, seria invável resolver este problema.
Irei propor uma solução mais elegante, que é por recursão.
A grande ideia da questao é tirar a últma linha da pirâmide e fazer a penúltima receber os maiores valores possiveis, baseados na última linha.
Recursão nada mais é do que fazer pequenos cálculos várias vezes.
Vamos resolver este caso resolvendo o caso do menor triângulo possível. Isso mesmo, pegando de 3 em 3 números, podemos calcular
o valor total da rota de soma máximo.
Vamos começar com o menor caso:
1
2 3
A maior rota é 1+3=4
Vamos colocar o valor da maior rota na ponta do triângulo e zerar a última linha, pois ela nao nos interessa mais.Assim
1 4
2 3 = 0 0
Vamos pegar um caso mais complexo:
1
2 3
4 5 6
Temos nessa figura, dois pequenos triângulos:
2 3 7 9
4 5 e 5 6 = 0 0 e 0 0
Vamos colocar esses dois triângulos menores no maior:
1
7 9
0 0 0
Agora vamos desconsiderar a última linha:
1
7 9 1 10
0 0 0 = 7 9 = 0 0 = 10
Então, a ideia é essa. Pegar os pequenos triangulos das duas linhas debaixo. A penultima linha vai mudar seus valores para o valor máximo da rota desse 'triangulozinho' e a última linha vai ser zerada. Então, se antes ela tinha n linhas, agora terá só n-1
Para obter o resultad, vamos isso até n-1=1
Ou seja, até sobrar só o elemento do topo, so uma linha (n-1=1, enta n=2)
A função pra calcular a maior rota desse triangulozinho é:
int triangle(int a, int b, int c)
{
if( (a+b)>= (a+c) )
return (a+b);
else
return (a+c);
}
Onde o triânguluzinho é:
a
b c
Agora vamos pra parte trabalhosa, que é a funçã que recebe a pirâmide de n linhas e transforma ela em uma de (n-1) linhas.
Depois, chama ela própria e transforma essa pirâmide de (n-1) linhas em uma de (n-2), até sobrar só uma linha, que é a do topo, que é a rota máxima.
Vamos chamar nossa função de :
int sum(int linha)
{
}
Que recebe o número de linhas da pirâmide.
Para melhorar a visualização da pirâmide, vamos considerar ela como uma matriz 16x16 (assim, lidaremos com linhas e colunas variando de 1 até 15, e ignoramos a linha e coluna 0).
Vamos chamar essa matriz/pirâmide assim:
#define rows 16
int num[rows][rows]=
{
{ 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0},
{ 0,75, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0},
{ 0,95,64, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0},
{ 0,17,47,82, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0},
{ 0,18,35,87,10, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0},
{ 0,20, 4,82,47,65, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0},
{ 0,19, 1,23,75, 3,34, 0, 0, 0, 0, 0, 0, 0, 0, 0},
{ 0,88, 2,77,73, 7,63,67, 0, 0, 0, 0, 0, 0, 0, 0},
{ 0,99,65, 4,28, 6,16,70,92, 0, 0, 0, 0, 0, 0, 0},
{ 0,41,41,26,56,83,40,80,70,33, 0, 0, 0, 0, 0, 0},
{ 0,41,48,72,33,47,32,37,16,94,29, 0, 0, 0, 0, 0},
{ 0,53,71,44,65,25,43,91,52,97,51,14, 0, 0, 0, 0},
{ 0,70,11,33,28,77,73,17,78,39,68,17,57, 0, 0, 0},
{ 0,91,71,52,38,17,14,91,43,58,50,27,29,48, 0, 0},
{ 0,63,66, 4,68,89,53,67,30,73,16,69,87,40,31, 0},
{ 0, 4,62,98,27,23, 9,70,98,73,93,38,53,60, 4,23}
};
No início: linha=15
Vamos considerar um iteiro chamado 'zerar' para representar a linha que vai ser zerada, ou seja:
zerar = linha
Note que cada triangulinho tem dois números na última linha (linha 'zerar') e um número da penúltima linha (linha 'zerar-1).
Vamos alterar os valores da linha 'zerar-1' usando a função trangle(int, int, int)
Na penúltima linha, pegamos o elemento 1 até o elemento de número 15, ou de número 'zerar'.
Vamos chamar cada elemento da penúltima linha de 'element'.
Então, para substituir cada elemento da penúltima linha, fazemos o seguinte laço:
for(int element = 1 ; element<zerar ; element++)
{
num[zerar-1][element]=triangle( num[zerar-1][element], num[zerar][element],num[zerar][element+1]);
}
Depois, vamos pegar a última linha, a linha 'zerar' e zerá-la! (ela nao vai mais servir, ja extraímos o máximo dela)
for(int i=1 ; i<=zerar ; i++)
num[zerar][i]=0;
Pronto, a última linha se foi e a penúltima possui os maiores valores possíves. Adeus linha 15.
Mas, como zerar a linha 14 agora?
Recursão! É só chamar a sum de novo, mas dessa vez com uma linha a menos!
Ou seja, em vez de consirderarmos que a matriz é 15x15, vamos considerar que ela seja 14x14, pois estamos ignorando a última linha, que agra é toda nula.
Ou seja, fazermos: sum(linha-1);
dentro da própria função sum(linha)
Isso é recursão, pois vai ficar sempre zerando a última, mas...sempre?
Nâo, quando : linha-1=1 , a recursão pára.
Ou seja, linha=2 , a recursão pára.
Pra usamos um if:
if(linha==2)
{
//num[1][1]=triangle(num[1][1], num[2][1], num[2][2])
num[linha-1][linha-1]= triangle( num[linha-1][linha-1], num[linha][linha-1], num[linha][linha]);
num[linha][linha-1]=num[linha][linha]=0;
return 1;
}
Para melhor visualizar o que acontece, criamos a função imprime:
void imprime(int num[][rows])
{
for(int i=1 ; i<rows ; i++)
{
for(int j=1 ; j<rows ; j++)
cout<<setw(3)<<num[i][j]<<" ";
cout<<endl;
}
cout<<endl<<endl;
}
Para pirâmides maiore, nao use a função imprime, ela vai atrapalhar, deixando muito lento.
A resposta é simplesmente o elemento: num[1][1]
Então, o programa completo fica:
--------------------------------18.cpp
#include <iostream>
#include <iomanip>
using namespace std;
#define rows 16
int num[rows][rows]=
{
{ 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0},
{ 0,75, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0},
{ 0,95,64, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0},
{ 0,17,47,82, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0},
{ 0,18,35,87,10, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0},
{ 0,20, 4,82,47,65, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0},
{ 0,19, 1,23,75, 3,34, 0, 0, 0, 0, 0, 0, 0, 0, 0},
{ 0,88, 2,77,73, 7,63,67, 0, 0, 0, 0, 0, 0, 0, 0},
{ 0,99,65, 4,28, 6,16,70,92, 0, 0, 0, 0, 0, 0, 0},
{ 0,41,41,26,56,83,40,80,70,33, 0, 0, 0, 0, 0, 0},
{ 0,41,48,72,33,47,32,37,16,94,29, 0, 0, 0, 0, 0},
{ 0,53,71,44,65,25,43,91,52,97,51,14, 0, 0, 0, 0},
{ 0,70,11,33,28,77,73,17,78,39,68,17,57, 0, 0, 0},
{ 0,91,71,52,38,17,14,91,43,58,50,27,29,48, 0, 0},
{ 0,63,66, 4,68,89,53,67,30,73,16,69,87,40,31, 0},
{ 0, 4,62,98,27,23, 9,70,98,73,93,38,53,60, 4,23}
};
void imprime(int num[][rows])
{
for(int i=1 ; i<rows ; i++)
{
for(int j=1 ; j<rows ; j++)
cout<<setw(3)<<num[i][j]<<" ";
cout<<endl;
}
cout<<endl<<endl;
}
int triangle(int a, int b, int c)
{
if( (a+b)>= (a+c) )
return (a+b);
else
return (a+c);
}
// vamos fazer as linhas sumirem, debaixo para cima
// alinha que esta acima da ultima vai mudar, vai receber o resultado de seu respectivo pequeno triangulo de cada elemento
int sum(int linha)
{
imprime(num);
if(linha==2)
{
num[linha-1][linha-1]= triangle( num[linha-1][linha-1], num[linha][linha-1], num[linha][linha]);
num[linha][linha-1]=num[linha][linha]=0;
imprime(num);
return 1;
}
else
for(int zerar = linha ; zerar > 2 ; zerar--) //aqui ele vai pegar a linha, e usar a de cima pra formar o triangle e zerar a linha lines
{
//cada elemento da linha acima da zerar, receberao novos valores, atraves da funçao triangle
for(int element = 1 ; element<zerar ; element++)
{
num[zerar-1][element]=triangle( num[zerar-1][element], num[zerar][element],num[zerar][element+1]);
imprime(num);
}
//agora vams zerar os elementos da linha zerar
for(int i=1 ; i<=zerar ; i++)
num[zerar][i]=0;
imprime(num);
}
sum(linha-1);
}
int main()
{
sum(15);
}
------------------------------------------------------------
Recursão é complicado mesmo no começo.
Só lendo não dá pra aprender. Tem que quebrar a cabeça e tentar, é só assim que vai ;)