Trouver la plus longue sous-séquence croissante dans un tableau à deux dimensions

J'ai ce problème comme devoir et je n'ai vraiment aucune idée par où commencer. J'ai implémenté la solution en utilisant un algorithme récursif (# 1), mais je n'arrive pas à comprendre comment résoudre le problème en utilisant une pile ... toute aide serait géniale.Trouver la plus longue sous-séquence croissante dans un tableau à deux dimensions

Trouvez la plus longue séquence croissante de nombres dans un tableau 15 x 15. Par exemple, si la matrice, 4x4, contient

97 47 56 36 
35 57 41 13 
89 36 98 75 
25 45 26 17

alors la plus longue séquence de nombres de plus en plus est la séquence de longueur huit consistant en 17, 26, 36, 41, 47, 56, 57, 97. On notera que il n'y a pas de doublons dans la séquence croissante.

Concevoir un algorithme récursif pour résoudre ce problème et mettre en œuvre en Java.
Concevoir un algorithme non récursif pour résoudre le même problème en utilisant une pile.

Source

2011-03-20 Recursor

Je n'arrive pas à voir comment le tableau que vous avez montré est 4x4. –

@Recursor "Je n'ai vraiment aucune idée par où commencer." Commencez ici http://home.earthlink.net/~patricia_shanahan/beginner.html –

Désolé, je dois avoir foiré le formatage. - actualisé. – Recursor

Parce que c'est des devoirs, voici une astuce: Vous pouvez convertir votre tableau de nombres à un graphe orienté acyclique. (Il est acyclique car il n'y a pas de doublons autorisés dans la séquence.) Après cela, vous pouvez utiliser un algorithme pour résoudre le plus long problème de chemin, pour trouver un chemin simple de longueur maximale dans votre graphique.

Source

2011-03-20 22:38:34 Chris

merci je pensais quelque chose à cet effet (arbre), mais ça sonne bien aussi. Diriez-vous alors que le graphe serait quelque chose comme array [x, y] -> tous les nœuds différant par array [x +/- 1], [y +/- 1] qui sont> array [x, y], etc.? Je ne suis pas sûr d'où vient ma pile, quand je récupère le résultat? – Recursor

@Recursor - traite le problème en deux parties. 1) Résolvez le problème avec un algorithme récursif. 2) Transformer l'algorithme récursif en un algorithme itératif, en utilisant un 'Stack' pour maintenir l'état qui était détenu dans les variables/paramètres locaux dans la version récursive. –

Trouver la plus longue sous-séquence croissante dans un tableau à deux dimensions

Répondre

Questions connexes