Forum Clubic

Besoin d'aide projet JAVA

Bonjour tout le monde, alors voilà je suis en deuxième année de licence MASS et je dois rendre un projet d’info. Sauf que je suis vraiment mauvais en cette matière et donc j’ai besoin de votre aide. Je vous transmets l’énoncé :

On se propose de programmer deux algorithmes de calcul d’une plus longue sous-suite croissante dans une
permutation des entiers de 1 à n:
On se donne une permutation des entiers entre 1 et n sous la forme d’une suite T indexée entre 1 et n;
où T désigne le ième élément de la suite (chaque entier de 1 à n apparaît exactement une fois dans le
tableau). Une sous-suite S de (1; …; n) est dite croissante dans T (et par abus, croissante tout court) si
(i;j) appartiennent à S et i < j impliquent T < T[j]:
A titre d’exemple, considérons:
T = (9; 1; 8; 6; 4; 3; 5; 2; 7)
alors la sous-suite de positions S = (2; 5; 7; 9) forme une sous-suite croissante de T (les valeurs associées
sont 1; 4; 5; 7), alors que la sous-suite de positions (1; 2; 3) ne forme pas une sous-suite croissante de T
(les valeurs associées sont 9; 1; 8).
1 2 3 4 5 6 7 8 9
T : 9 1 8 6 4 3 5 2 7
S : 2 5 7 9

Nous nous intéressons ici au problème de l’extraction d’une sous-suite croissante de longueur maximale à partir d’une permutation des entiers de 1 à n.
Dans la suite, nous noterons lis(i) la longueur maximale d’une sous-suite croissante dont l’indice maximal
(la position la plus à droite) est égal à i. Dans l’exemple précédent lis(0) = 0; lis(1) = 1; lis(2) = 1;
lis(3) = lis(4) = lis(5) = lis(6) = 2, lis(7) = 3; lis(8) = 2; et lis(9) = 4
Algorithme I
1.
Analyse
a) A quelle condition sur T, une sous-suite croissante maximale se terminant à la position i
peut-elle être le début d’une sous-suite croissante maximale se terminant à la position j, avec j > i
? En déduire une relation simple entre la valeur de lis(i + 1) et les valeurs de lis(j) pour j<=i:

b) Déduire de la question a un algorithme prenant en entrée les valeurs lis,. . . ,lis[k]
(sous la forme d’un tableau lis de longueur k) correspond à une permutation T de longueur n, avec
k<=n-1 et qui retourne un tableau lis complété avec la valeur lis[k + 1].

c) Reprendre l’algorithme de la question précédente pour obtenir un algorithme simple
qui prend en argument une permutation des entiers de 1 à n et qui calcule la longueur maximale
d’une sous-suite croissante dans cette permutation.

d) Modi?er l’algorithme précédent pour qu’il retourne un exemple de plus longue sous-suite
croissante. Prouvez la terminaison et la correction de cet algorithme.

Programmation.

Programmer cet algorithme en java.

Voila. Donc j’ai fait quelques trucs mais je suis quasi sur que c’est faux, je voudrais que vous m’aidiez ce serait exceptionnel. Pour des pros du java cela ne doit pas être très difficile! :slight_smile: Merci infiniment d’avance.

Salut,

Je ne pense pas que tu recevras une réponse… tout simplement car tu dois chercher pas toi-même (on m’a déjà fait le coup).
Je te conseille de poser ta question sur le forum du siteduzero. Par contre, montre que tu as travaillé. Même si c’est faux, les personnes seront plus enclin à t’aider.

Me concernant, je pourrai te répondre dans 5 ans (lorsque j’aurais terminé ma licence :wink:

Désolé ne pas avoir su t’aider…

Ah mais non, ce n’est pas vrai, même si il n’a rien fait, je suis prêt à faire le boulot à sa place, aucun problème. Facturer une journée de consultant pour faire ça, moi ça ne me pose pas de soucis :ane:

Pareil. 600€.