chemins récursion de coordonner coordinate

Question

Je travaille sur une mission java pour une classe et je ne suis pas sûr comment résoudre ce problème. Je ne veux pas terminé pour moi, mais m'a commencé dans la bonne direction. Je suis la plupart du temps incertain de la partie récursive du programme. Je ne suis pas très bon à la programmation.

  problème

:

     

    

chemins de NorthEast sont obtenus à partir d'un     grille à deux dimensions en déplaçant vers le haut et     droite. Par exemple, dans la figure     ci-dessous, il y a deux chemins de 1,0 à     0,1. La première est (1,0), (0,0), (0,1),     le second est (1,0), (1,1), (0,1).     Notez qu'il n'y a pas de chemins de NorthEast     de (0,1) à un autre point quelconque. Aussi     noter qu'il ya un chemin de NorthEast     de (1,1) à (0,1). Vous devez écrire     un programme qui prend un certain nombre (taille de     grille - pas plus grand que 10) et un     lieu de départ et une fin     emplacement et calcule récursive tous     des chemins "NorthEast".

  

0,0 0,1

1,0 1,1

Je lis dans le fichier prog2.dat

qui se lit dans la taille de la grille d'abord et ensuite les coordonnées de départ et ensuite les coordonnées de finition. par exemple:

5

3 0

1 3

Il doit être un des fichiers, donc je vais utiliser des méthodes. Si quelqu'un pouvait me aider à démarrer ou me diriger à une question similaire déjà affichée, je vous serais reconnaissant.

Answer 1

Une solution impliquant récursivité consiste à trouver le point suivant sur le chemin que vous obtiendrez le plus proche de votre destination. Une fois que vous avez ce point, vous utilisez la même méthode pour déterminer le prochain point le plus proche et ainsi de suite. Ce processus (ou la récursion) se termine lorsque vous êtes arrivé à votre destination.

Vous pouvez essayer de faire quelque chose comme ceci:

void getNextPoint(Point start, Point end, Path currentPath) {
    //if start == end, then you're done with the recursion
    //and you have a valid path

    //if you can move east from start to get closer to end
    //Point next = east of start
    //append next to the currentPath
    //then call getNextPoint(next, end, currentPath)

    //if you can move north from start to get closer to end
    //Point next = north of start
    //append next to currentPath
    //then call getNextPoint(next, end, currentPath)
}

J'ai omis beaucoup de détails afin que vous pouvez trouver plus pour vous-même, mais c'est une approche à l'aide de la récursivité. Essentiellement, vous construisez un chemin. Vous devez savoir comment gérer vos chemins, mais les chances sont que vous devez être en mesure de pousser et de points de pop hors d'eux.

Answer 2

Cela peut aider:

http://en.wikipedia.org/wiki/Binomial_theorem

Answer 3

Commencez par lire sur le Triangle de Pascal.

Pour un emplacement de départ donné (x0, y0), et un emplacement de fin donné (x1, y1) et vous limiter à déplacer du Nord ou de l'Est sur une grille, un chemin de longueur minimale consistera précisément (x1-x0 ) étapes de l'Est et (y1-y0) étapes vers le Nord, dans un certain ordre.