Enigme : les chemins tortueux

[invite06fcc10b]

X***
****
****
***Y

Question simple :
Combien y a t-il de chemins possibles pour aller de X à Y en se déplaçant uniquement horizontalement ou verticalement de 1 case à la fois et sans jamais repasser par la même case ?
Moins de 100 ?
Plus de 100 ?
Le nombre exact ?

ps : mouvement en diagonal interdit et pas de tableau circulaire !
-----

[yat]

A première vue, je dirais 184.

[invite06fcc10b]

A première vue, je dirais 184.

Moi, je dirais plus ... quoique, comment t"as fait ?

[invite06fcc10b]

Moi, je dirais plus ... quoique, comment t"as fait ?

Dis-donc Yat, je viens de vérifier par ordi, tu m'impressionnes là !

[A voir en vidéo sur Futura]

[invite06fcc10b]

Dis-donc Yat, je viens de vérifier par ordi, tu m'impressionnes là !

Rien que pour Yat, j'ai une nouvelle énigme plus difficile :
Même question avec n colonnes et n lignes, le départ en haut à gauche, l'arrivée en bas à droite, avec n variant entre 4 et 10 !

[yat]

Moi, je dirais plus ... quoique, comment t"as fait ?

Comme ça :

#include <stdio.h>

char tab[4][4];
int nbsol;

void recurs(int i, int j) {
  tab[i][j]=1;

  if(i==3&&j==3) nbsol++;
  else {
    if(i>0&&tab[i-1][j]==0) recurs(i-1,j);
    if(j>0&&tab[i][j-1]==0) recurs(i,j-1);
    if(i<3&&tab[i+1][j]==0) recurs(i+1,j);
    if(j<3&&tab[i][j+1]==0) recurs(i,j+1);
  } //if
  tab[i][j]=0;
} //recurs

void main(void) {
  int i,j;

  for(i=0;i<4;i++) for(j=0;j<4;j++) tab[i][j]=0;
  nbsol=0;
  recurs(0,0);
  printf("%d\n",nbsol);
} //main

Un peu moins impressionné, maintenant, non ?

[invite06fcc10b]

Bien vu ! Tout en récursif, c'est effectivement rapide et efficace. Alors que moi j'ai utilisé un programme de je ne sais plus combien de lignes, qui peut tout faire ou presque mais qui n'est pas présentable ...

[yat]

Rien que pour Yat, j'ai une nouvelle énigme plus difficile :
Même question avec n colonnes et n lignes, le départ en haut à gauche, l'arrivée en bas à droite, avec n variant entre 4 et 10 !

Alors pour n=5 : 8 512
Pour n=6 : 126 2816

Au delà, euh... j'ai peur que ça commence à être un peu compliqué...

[invite06fcc10b]

Alors pour n=5 : 8 512
Pour n=6 : 126 2816

Au delà, euh... j'ai peur que ça commence à être un peu compliqué...

Voilà ce qui arrive quand on fait du récursif, on aboutit à un stackoverflow ...
Bon, je dis ça, mais mon programme n'a pas donné de réponse non plus, en tout cas pas encore ...

[yat]

Voilà ce qui arrive quand on fait du récursif, on aboutit à un stackoverflow ...

Pas encore, non... mais je peux pas trop laisser tourner des applis des heures sur ma machine, là...
Il ne devrait pas y avoir de stack overflow, puisqu'il n'y aura que n² empilements de deux entiers... avec n=100 devrait pas y avoir de problème de ce coté là.