Exercicios projetos Euller

[jpsan]

Olá estou resolvendo os exercícios https://projecteuler.net/, só para treinar um pouco de programação. Para quem não conhece e curte desafios este site é OTIMO!! 
O problema é que eu travei neste exercício. https://projecteuler.net/problem=15

Alguém saberia me dizer como posso resolver??
Desde já obrigado.

 

Obs:O site está em inglês mas é de fácil compreensão 

[dontpanic]

Tentou com recursão?

 

Eu criaria uma função que recebe cordenadas x,y, testa se x,y é igual a NxN (tamanho da matriz).

Se for igual, soma mais 1 a alguma variável que guarda o número de caminhos.

Se não for igual, chama a mesma função recursivamente, duas vezes, passando como parametro (X+1, Y) e (X, Y+1).

[Ansi C]

Já para mim a tradução não me é clara, o exercício é; determina o numero de rotas até NxN; o possível é mover para baixo, e mover para direita. Dentro de uma matriz? A ilustração do exercício é o que mais me confunde.

[jpsan]

dontpanic não entendi o seu raciocínio... como eu vou garantir que não estou repetindo um caminho??
 Mauro Britivaldo imagine os quadrados como os quarteirões de uma cidade. Ele quer saber como chegar do topo do extremo esquerdo, ao extremo direito mais baixo... Os caminhos seriam percorridos pelas "ruas" da cidade. Não sei se consegui explicar bem o exercício :/.
 

Pensei em resolver por grafos ou algo assim... e ir testando os caminhos. Seria uma boa ideia?

[dontpanic]

@jpsan

Meu raciocínio inicial era o seguinte:

0 0 0

0 0 0

0 0 0

Partindo de [0,0] a função ia testar se:

- É igual ao ponto 2,2?

- - Se sim: Soma um caminho a mais

- - Se não: Chama a função novamente, recursivamente, passando agora como parâmetro os pontos [0,1] (direita) e [1,0] (abaixo)

A função repete a mesma coisa com esses dois pontos, testa se é 2,2... se não, os 2 pontos chamam mais 4 pontos. E os 4 pontos chamam mais 8, etc.

É basicamente a mesma função que é usada pra percorrer uma árvore.

O que eu deixei escapar é que esse problema na verdade não é uma árvore... se tratar ele como árvore, eu acabo contando alguns caminhos mais de uma vez.

Por exemplo, o ponto [0,1] iria chamar a função novamente pros pontos [1,1] e [0,2]... e o ponto [1,0] iria chamar a função pro ponto [1,1] e [2,0].

O caminho que passa por [1,1] seria contado duas vezes.

Então essa lógica não ia funcionar.

Daí eu trapaceei um pouco e achei no google um blog onde um matemático explicava esse problema.

E a solução dele é parecida com a minha, só que de trás pra frente... em vez de começar no ponto [0,0], você começa no [2,2], reseta a matriz inteira com o valor 1 e vai percorrendo os caminhos inversos, montando um triangulo de pascal ao somar os valores adjacentes.

Por exemplo:

 0  0  0 0  0  0 0  0  0

Nos pontos [2,0] e [2,1] pro ponto [2,2] só existe um caminho.

Nos pontos [0,2] e [1,2] pro ponto [2,2] também só existe um caminho.

 0  0 [1] 0  0 [1][1][1][1]

No ponto [1,1] existem dois caminhos (a soma dos valores nos pontos adjacentes [2,1] e [1,2])

 0  0  1 0 [2] 1 1  1  1

No ponto [0,1] existem 3 caminhos (soma dos adjacentes --> 2 + 1)

No ponto [1,0] também existem 3 caminhos (mesma coisa)

 0 [3] 1[3] 2  1 1  1  1

E finalmente no ponto [0,0] existem 6 caminhos... mais uma vez, a soma dos adjacentes (3 + 3)

[6] 3  1 3  2  1 1  1  1

O valor que ficar no ponto 0,0 é o resultado que o problema procura.

[Ansi C]

dontpanic não entendi o seu raciocínio... como eu vou garantir que não estou repetindo um caminho??

Mauro Britivaldo imagine os quadrados como os quarteirões de uma cidade. Ele quer saber como chegar do topo do extremo esquerdo, ao extremo direito mais baixo... Os caminhos seriam percorridos pelas "ruas" da cidade. Não sei se consegui explicar bem o exercício :/.

Pensei em resolver por grafos ou algo assim... e ir testando os caminhos. Seria uma boa ideia?

Obrigado por esclarece o texto.