[Dúvida] exercicio em c

[alves077]

Boa tarde,

Estou a tentar implementar um mini-jogo, que consiste: tendo uma matriz de números terei que percorrer a matriz começando no topo até ao fundo da matriz procurando nas posições adjacentes da actual números iguais, se conseguir percorrer números ganho senão perco. Isto resolver com ciclos tenho comparações que nunca mais acabam, queria resolver recursivamente mas não tenho grande experiência em algoritmo recursivos, se me pudessem dar uma luz.

ex:

1 2 3 4

4 2 7 8

9 1 2 3

4 2 5 4

Têm uma solução com o algarismo 2 conseguimos chegar ao fim. a ideia era pegar no 1º numero e tentava chegar verificava os adjacentes, se existe igual, guardava as posições e seguia para os adjacentes desse ponto, senão havia andava uma coluna para a direita e começava o mesmo raciocínio isto no pior caso faria para todos da primeira linha, caso não haja nenhum o jogo termina, porque têm ir do topo para o fundo (incluindo todas as linhas). Alguém consegue dar uma ajuda como implementar esta ideia recursivamente.

Obrigado pela atenção,

alves077

[pmg]

Consegues resolver o problema para uma linha?

E para duas linhas?

Consegues transformar o problema de duas linhas num problema equivalente mas com apenas uma linha?

Se sim as perguntas todas acima, vai 'removendo' linhas ao problema (recursivamente) ate teres a resposta.

[alves077]

Estás a dizer para analisar linha a linha?

Isto é, analiso uma linha vejo os números, guardo a informação chamo recursivamente a função tratará da seguinte, faz as combinações possíveis e assim adiante?

Percebo a ideia, implementá-la é que está difícil Resolver para uma linha é verificar os números que lá existem, se for a primeira linha, guardo a informação, se for da primeira para a frente tenho que procurar algum tipo de combinação adjacente com a linha anterior. Isto é, tenho que ir analisando duas a duas linhas.

Obrigado pela atenção,

alves077

[HappyHippyHippo]

o problema é um pouco mais complicado do que isso

imagina esta matriz:

8 1 8 8 8 8 8 8 8

8 1 8 8 1 1 1 1 8

8 1 8 8 1 8 8 1 8

8 1 1 1 1 8 8 1 8

8 8 8 8 8 8 8 1 8

estás a ver o problema ?

poderias ir linha a linha, mas necessitarias de trabalhar a linha onde estás, a anterior a e seguinte

ou ainda pior : imagina o seguinte:

8 1 8 8 8 8 8 8 8

8 1 8 1 1 1 1 1 1

8 1 8 8 1 8 8 1 8

8 1 1 1 1 1 8 1 8

8 1 8 8 8 1 8 1 8

8 1 1 1 8 8 8 1 8

8 8 8 8 8 8 8 1 8

estás a ver o problema agora ? e se chegas a um "beco sem saída" ?

o que podes fazer é aplicar a regra da mão direita (ou esquerda 😄 )

- viras para a direita

- enquanto não puderes andar

- virar 90 graus para a esquerda

- andas um passo

este algoritmo faz com que saias de um labirinto com 100% de garantias

[pmg]

O basico para resolver problemas recursivamente é transformar o problema de tamanho N num problema equivalente de tamanho mais pequeno (normalmente N - 1 ou N/2)

Como podes transformar o problema de encontrar um caminho num 'quadro' com N linhas num problema para um quadro de N - 1 linhas?

Depois de saberes responder esta pergunta, o programa pode ser escrito facilmente:

int solve(int *valores, int colunas, int linhas) {
 if (linhas == 1) {
   /* solucao basica para 1 linha */
   return solucao;
 } else {
   /* alterar valores de acordo com resposta a pergunta acima */
   return solve(valores, colunas, linhas - 1); /* chamada recursiva */
 }
}

[alves077]

@HappyHippyHippo: é suposto só existir uma solução para o jogo, isto é, só um número vai do top ao fundo.

8 1 8 8 8 8 8 8 8

8 1 8 8 1 1 1 1 8

8 1 8 8 1 8 8 1 8

8 1 1 1 1 8 8 1 8

8 8 8 8 8 8 8 1 8

Este caso não é permitido, mas caso ele existisse o que algoritmo deve fazer é por exemplo correr os 8 todos da 1ª coluna e está encontrada uma solução. Mas é suposto só haver uma solução possível.

por exemplo:

8 1 1 1

2 8 2 2

3 8 3 3

4 4 8 4

@pmg; O jogo para 1 linha não há mais nada a fazer do que guardar os valores dessa mesma linha, para N-1 tenho que comparar com a linha seguinte e ver se posso "andar", uma das minhas dificuldades está ai, como coordenar as verificações e quando saber onde guardar.

Obrigado pela atenção,

alves077

[HappyHippyHippo]

era uma exemplo .. troca os 8's por X de maneira que os 8' nunca sejam solução

Edited February 16, 2013 at 08:11 PM by HappyHippyHippo

[pmg]

Imagina as seguintes linhas

1 3 8 6 5
3 4 5 6 7
. . . . .

Podes transformar este problema de N linhas noutro equivalente de N-1 linhas? (X indica que nao ha caminho (podes usar 0 ou -1 no programa a serio))

3 X X 6 X
. . . . .

Edited February 16, 2013 at 08:22 PM by pmg

[alves077]

hm.. estava a pensar fazer algo do género:

int solve(int *valores, int colunas, int linhas) {
 if (linhas == 1) {
/* solucao basica para 1 linha */
return solucao;
 } else {
/*verifico numero actual guardando num variavel temporaria*/
  int temp=valores[linhas][colunas];
/*faltando as condicoes das fronteiras da matriz*/
 if(valores[linhas+1][colunas] != temp)
  valores[linhas+1][colunas]=-1;
else if( valores[linhas+1][colunas+1] != temp )
 valores[linhas+1][colunas+1]=-1;
else if( valores[linhas][colunas+1] != temp )
  valores[linhas+1][colunas+1]=-1;

return solve(valores, colunas, linhas - 1); /* chamada recursiva */
 }
}

Só que isto têm vários problemas, como por exemplo modifico a matriz, quando chego a ultima linha verifico que afinal não tenho caminho, matriz esta modificada, quando voltar ao inicio já posso ter alterado a base da matriz. Outros dos meus problemas é que queria ir guardando as coordenadas do caminho, tinha um array para guardar, só que a probabilidade de haver inconsistência de dados é grande, por volta a base, mesmo problema. Imaginando que onde chamo esta função de recursão vou incrementando o número de colunas, para ele ir andando pelas colunas também.

Obrigado pela atenção,

alves077

Edited February 16, 2013 at 10:19 PM by alves077

[HappyHippyHippo]

pelos visto estás a ignorar o que disse ...

ok, resolve esta matriz:

5 0 6 7 8 5 6 7 8

6 0 5 8 0 0 0 0 5

7 0 7 6 0 6 8 0 6

8 0 0 0 0 5 6 0 7

5 6 7 5 6 7 8 0 5

e mesma matriz mas agora está como tu queres ...

Edited February 16, 2013 at 10:19 PM by HappyHippyHippo

[pmg]

Estas a tentar resolver varios problemas diferentes: nomeadamente

a) e possivel percorrer a matriz com o primeiro numero da primeira linha?

b) e possivel percorrer a matriz com o segundo numero da primeira linha?

...

N) e possivel percorrer a matriz com o ultimo numero da primeira linha?

Podes facilitar e resolver os problemas todos de uma vez

1) Comecando na primeira linha que numeros chegam a ultima linha?

Repara que para um numero ir da primeira linha para a ultima, tem que passar pela segunda linha, pela terceira linha, ..., ...

[alves077]

@HappyHippyHippo Sim tens razão, não olhei bem para o teu post, quanto a questão do beco sem saída, pelo que sei tenho duas oportunidades de escolha de caminho, verifico uma, senão der volto até ao ponto que posso escolher e escolho a outra. Como puseste neste exemplo:

8 1 8 8 8 8 8 8 8

8 1 8 1 1 1 1 1 1

8 1 8 8 1 8 8 1 8

8 1 1 1 1 1 8 1 8

8 1 8 8 8 1 8 1 8

8 1 1 1 8 8 8 1 8

8 8 8 8 8 8 8 1 8

Na 4ª linha 2ª coluna iria para baixo por exemplo chegava a conclusão que não dava voltava ao mesmo ponto e seguia pelo outro caminho. A dificuldade e implementar, sabendo que dava jeito ir guardando as coordenadas do caminho até a vitoria.

O algoritmo que explicas-te:

- viras para a direita

- enquanto não puderes andar

- virar 90 graus para a esquerda

- andas um passo

Vou caminhando por linhas, por exemplo, se não conseguir andar mais, viro para a direita, e vou andando 90 graus até conseguir sair, no máximo volto para cima?

@pmg

Mas a ideia não é estando eu num ponto verificar os adjacentes, se puder andar ando, chamando recursivamente a função para a proxima linha, se não puder andar procuro alternativas nas adjacentes, se não existir nenhum possivel tenho que voltar a linha 0, numa coluna a frente, e testar com um novo número?

Obrigado pela atenção,

alves077

[pmg]

Hmmm ... eu estava a basear-me num sistema linear (e nao labirintico) em que diminuis sempre uma linha a medida que avancas.

Com o problema labirintico, ja as minhas sugestoes nao se aplicam.

[HappyHippyHippo]

Vou caminhando por linhas, por exemplo, se não conseguir andar mais, viro para a direita, e vou andando 90 graus até conseguir sair, no máximo volto para cima?

a indentação que dei na descrição do algoritmo é importante

[alves077]

Sim, eu reparei:

- viras para a direita

- enquanto não puderes andar

- virar 90 graus para a esquerda

- andas um passo

Vou virando enquanto não puder andar, quando puder andar ando. Um dos meus problemas é se quiser guardar o caminho no caso de vitória, quando o guardar..

é que basicamente, como fiz aqui escrevi no codigo todos os casos possiveis,

int solve(int *valores, int colunas, int linhas,int rows,int columns) {
 if (x == row) {
	/* verificar se há solução*/

 } else {
	/*verifico numero actual guardando num variavel temporaria*/
  int temp=valores[linhas][colunas];
/*faltando as condicoes das fronteiras da matriz*/
 if(valores[linhas+1][colunas] == temp)
        /*chamar recursivamente */
        solve(valores, colunas,linhas+1,rows,columns);
else if( valores[linhas+1][colunas+1] == temp )
	solve(valores, colunas+1,linhas+1,rows,columns);
else if( valores[linhas][colunas+1] == temp )
	  solve(valores, colunas+1,linhas,rows,columns);
  /*...*/
 }
}

A minha ideia era se não estiver no fim da tabela, pega no valor da posição (linha,coluna), compara com os adjacentes, se for igual chama recursivamente a função, como se fosse para andar para frente, só não sei faço o uso correcto da recursividade, e ainda não consegui maneira de ir guardando os valores, posso guardar só que posso chegar a ultima linha e verificar que não há final, logo tenho que voltar todo ao inicio.

E falta a questão dos "becos sem saída", isto é quando têm opções para andar, maneira como estava a pensar e seguir pela 1ª que aparecer, mas terei que ter a opção de ele voltar para traz até a altura da decisão.

Obrigado pela atenção,

alves077

[HappyHippyHippo]

Um dos meus problemas é se quiser guardar o caminho no caso de vitória, quando o guardar..

a maneira mais simples:

- definires uma matriz de tamanho igual ao labirinto

- definires os seguintes valores DIR: 0 = nada, 1 = norte, 2 = oeste, 3 = sul, 4 = este

- sempre que começares um processo de pesquisa (posição inicial), limpar a matriz a zeros

- sempre que estiveres na posição (x,y) e deres um passo na direcção DIR, guardares esse valor na matriz criada

- se chegares ao fim, terás a solução colocando-te na posição inicial e seguires as direcções guardadas

[alves077]

Acho que percebi a ideia do algoritmo, vou dando as coordenadas e ele percorre o caminho. Mas estou aqui com alguns problemas, um deles é na parte se ele chegar a um ponto de não ter para onde ir. Isto é, vou andando até chega a um ponto que não consigo mais, terei que conseguir ir até ao ponto de escolha, ou voltar para a primeira linha,certo? Imaginando o caso

1 2 3 4

2 7 2 5

2 9 2 9

2 9 9 9

Segundo o que estou a desenvolver ele segui por um caminho, mas depois não sei como voltar para trás caso não chegue ao final.

int solve(int *valores,int *temp_v,int colunas, int linhas,int rows,int columns) {
 if (x == row-1) {
               /*chegou a um final*/
               temp_v[linhas][colunas]=NORTE;
 } else {
			/*verifico numero actual guardando num variavel temporaria*/
  int temp=valores[linhas][colunas];
/*faltando as condicoes das fronteiras da matriz*/
 if(valores[linhas+1][colunas] == temp){
        temp_v[linhas][colunas]=S;
	 solve(valores, colunas,linhas+1,rows,columns); }
else if( valores[linhas+1][colunas+1] == temp ){
         temp_v[linhas][colunas]=SE;    
         solve(valores, colunas+1,linhas+1,rows,columns); }
else if( valores[linhas][colunas+1] == temp ){
         temp_v[linhas][colunas]=L;
        solve(valores, colunas+1,linhas,rows,columns);}
  /*...*/
else{
         temp_v[linhas][colunas]=NADA;
         solve(0,y+1,colunas,linhas,matrix,matriz_aux);
}
 }
}

Isto seria uma pequena ideia do que queria implementar, mas como disse há casos que não sei bem como implementar, como este caso de escolha de caminhos, e como voltar atrás, posso ter uma variável saber de onde venho e ir voltando para trás, mas acho que é capaz de não bater certo.

Obrigado pela atenção,

alves077

[HappyHippyHippo]

já te disse, se seguires o algoritmo que te disse, se o caminho não tem solução, imperativamente voltas ao início

ps : o teu código alem de não ser legível, está muito à quem do algoritmo que te disse

[alves077]

A minha ideia era percorrer recursivamente, guardo no temp o valor, vejo os pontos adjacentes ao ponto actual, verifico se posso andar, se puder guarda na tal matriz auxiliar, e chamo recursivamente a função no novo ponto, assim a adiante quando o x == linhas-1 quer dizer que chegou a ultima linha, ai tem que verificar se pode concluir e guarda o fim. Muito provavelmente existe uma maneira mais pratica e legível para resolver, mas não estou a ver..

Edit:

Imaginemos o caso:

12345

63838

83838

88838

Chegava ao ponto (3,2) e analisava que não conseguia andar mais passo nenhum, movendo 90º graus para a esquerda até conseguir andar, acabando por voltar para cima, mas depois no ponto (2,2) não pode acontecer de voltar oura vez para baixo e andar num ciclo sem conseguir sair?

Obrigado pela atenção,

alves077

Edited February 18, 2013 at 11:12 AM by alves077