Mostrando postagens com marcador Project Euler. Mostrar todas as postagens
Mostrando postagens com marcador Project Euler. Mostrar todas as postagens

C++ : Project Euler: Problem 21 usando a STL (list)


Problem 21
05 July 2002

Let d(n) be defined as the sum of proper divisors of n (numbers less than n which divide evenly into n).
If d(a) = b and d(b) = a, where a  b, then a and b are an amicable pair and each of a and b are called amicable numbers.

For example, the proper divisors of 220 are 1, 2, 4, 5, 10, 11, 20, 22, 44, 55 and 110; therefore d(220) = 284.
The proper divisors of 284 are 1, 2, 4, 71 and 142; so d(284) = 220.

Evaluate the sum of all the amicable numbers under 10000.



    Primeiro, criamos a função properDivisors(int num), que calcula a soma dos divisores de um número (exceto ele mesmo).
    Depois, a função d(int n) checa o se o valor de n e properDivisors(n) são um par de amicable.

    Aqui encontramos uma pedra no caminho.
    Se primeiro testarmos 220, teremos que 220 e 284 são pares e serão adicionados.
    Porém, ao testar 284, teremos que 284 e 220 são pares e serão novamente adicionados.

    Vamos contornar esse problema usando a STL (Standard Template Library), usando uma lista, a pairList.
    Ela será global. Cada vez que formos testar um números, primeiro devemos checar se ele nao esta na lista.
    Só depois de nos certificarmos que ele não está é que iremos testar se ele forma um amicable.
    Dentro da funçao d(): 'n==j', quer dizer que os números formam um par e que 'n != i' diz que eles não são iguais.

    Para testar se o numero nao esta na lista, usamos a funçao bool testList()
    Ela retorna true, caso o numero estenja na lista e false se nao estiver

    Na função main, ao percorremos de 1 até  10.000, antes de começarmos vamos testar se o dito cujo número esta na lista.
    Assim, ele só vai pra função d() se não estiver.

    Ao final, somamos todos os números que se encontram na lista


------------------------------------------------ 21.cpp
#include <iostream>
#include <list>
using namespace std;

list<int> pairList;
list<int>::iterator iter;

int properDivisors(int num)
{
    int count,
        sum=0;

    for(count=1 ; count <= num/2 ; count++)
    {
        if(num % count == 0)
                sum=sum+count;

    }
            return sum;
}

bool testList(int num)
{
    for(iter = pairList.begin() ; iter != pairList.end() ; iter++)
        if(*iter == num)
            return true;

    return false;
}

int d(int n)
{
    int i,
        j;

    i = properDivisors(n);
    j = properDivisors(i);

    if(n == j && n != i)
        {
            cout<<"d("<<n<<") : "<<i<<endl;
            pairList.push_back(n);
        }
}

int main()
{
    int num,
        sum=0;

    for(num=1 ; num<=10000 ; num++)
        if(! testList(num) )
            d(num);

    for(iter = pairList.begin() ; iter != pairList.end() ; iter++)
                sum+=*iter;

        cout<<endl<<"Soma : "<<sum<<endl;
 }

C++ : Project Euler 18 & Recursão / Recursividade


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.
3
7 4
2 4 6
8 5 9 3
That is, 3 + 7 + 4 + 9 = 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:
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


--------------------

É 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 ;)