Desafio-Caminhos de uma matriz

[ExtendUrSenses]

Começando na esquina superior esquerda de uma matriz 2x2, é só podendo se movimentar a direita e abaixo,tem exatamente 6 caminhos pra chegar na esquina inferior direita.

Faça um programa em C que receba a ordem dá Matrix dá raiz e devolva o número de caminhos possíveis e uma cadeia de caracteres representando os movimentos de cada caminho.

Ex:

Entrada:2

Saída:DDDA

DADA

DDAD

DADD

ADAD

DADA

Ajuda por favor

 

[Anonymous Programmer]

essa liga de C que você participa coloca uns desafios complicados em....

[ExtendUrSenses]

Eu tô desde sexta feira o dia todo na faculdade estudando pra fazer isso amigo..

Pra quem só sabia If/Else e ir pra função de recursividade e árvores binárias é meio complicado..KKK

[Anonymous Programmer]

Também ;D kkkkk relaxa amanhã na aula de Cristiane a gente ver com ela.

[ExtendUrSenses]

Espero que ela seja simpática o suficiente pra ajudar a gente com isso Kkkkk

[ufrarion]

Olá,

 

Esse problema é resolvido com análise combinatória, onde a permutação eliminando as repetições será a resposta. No exemplo dado a resposta é permutação de 4 elementos divido pela repetição, sendo 2 e 2 (duas letras 'A' e duas letras 'D'), onde fica 4! / (2! * 2!) = 6.

Ex2: Com uma matriz 3x3, SEMPRE terá que descer 3 e ir 3 a direita (DDDAAA), e as possibilidades de respostas será dado por 6! / (3! * 3!) = 20.

 

OBS 1: A saída que foi postada está errada, pois DDDA sairá da matriz e DADA foi contado duas vezes sendo que é mesmo caminho, o site abaixo lista todas as possibilidades de permutação.

 

Lista correta:

A,A,D,D

D,A,A,D

A,D,A,D

D,A,D,A

A,D,D,A

D,D,A,A

 

OBS 2: o símbolo '!' significa fatorial, onde 4! = 4*3*2*1 = 24, e 5! = 5*4*3*2*1 = 120

 

Link: http://www.dcode.fr/permutations-generator