Inscription / Connexion Nouveau Sujet
Algorithme sous-séquence en Pascal
Bonsoir 
Soit
J'ai essayé mais ça n'a pas l'air de fonctionner (alors que le compilateur ne signale pas d'erreurs) :
Program tri;
uses dos,crt;
Const n=10;
Type vecteur=array[0..n] of integer;
var u:vecteur;
Procedure Permute(var v:vecteur; taille:integer);
var i,j,k:integer;
w:vecteur;
begin
j:=0;
for i:=0 to taille do
begin
if v[i] mod 2 = 0 then
begin
w[j]:=v[i];
j:=j+1;
end;
end;
for i:=0 to taille do
begin
if v[i] mod 2 <> 0 then
begin
w[j]:=v[i];
j:=j+1;
end;
end;
for k:=0 to taille do v[k]:=w[k];
end;
begin
initialisation(u,n); (*C'est une procédure qui génère aléatoirement un vecteur*)
writeln;
Permute(u,n);
writeln;
readln;
end.
Merci à ceux qui pourront m'aider
Bonjour Eric
Ca ne me tri rien du tout, à l'exécution on voit le vecteur initial s'afficher mais pas le vecteur trié 
bon. Je n'ai jamais codé en Pascal.
Ton raisonnement a l'air bon.
Mais je ne sais pas trop comment fonctionne le passage des parametres dans les procédures.
La procédure retourne t-elle quelquechose?
Lorsque tu appelles Permute sur le vecteur u, est-ce que u est modifié, ou seulement une copie?
Je pense que le probleme est de cet ordre.
As tu essayer d'afficher le vecteur à l'intérieur de la procédure?
Merci de t'intéresser à mon problème
Les procédures ne retournent rien (à l'inverse des fonctions).
Lorsque j'appelle Permute sur u, oui u est modifié (normalement, là c'est pas le cas 
)
Et oui j'ai essayé d'afficher le vecteur mais le compilateur râle, apparemment avec ce type on ne peut pas écrire write(u);
Salut Kévin et Eric
Que signifient les instructions writeln et readln ?
Je n'ai jamais non plus programmé en Pascal, donc c'est pas dit que je puisse t'aider 
Sinon ta procédure de génération d'un vecteur aléatoire fonctionne correctement?
Fractal 
A mon avis ca écrit et va à la ligne (comme en java), mais ca écrit quoi? bonne question. le vecteur courant u?
Voui c'est pour ça, je trouve bizarre une fonction qui écrit mais qui ne prend aucun paramètre, comment elle peut savoir que c'est u qu'on veut écrire?
Et puis si cette fonction marche, pourquoi ne pas l'utiliser dans la procédure pour essayer de trouver ce qui plante.
Fractal
Salut guillaume
Ca y est ça marche ! Le message de 22:27 d'eric était la solution, c'était pas grand chose finalement !
Merci à vous deux
J'aurai peut-être besoin de vos lumières, je continue à travailler sur le problème
PS : Ca a l'air de te plaire l'info guillaume
Voui, j'adore l'info ^^
J'avais déjà programmé avant, mais ça faisait longtemps que j'avais pas fait grand chose et là je suis entrain de redécouvrir la programmation (même si j'aurais préféré un autre langage que Caml...)
Fractal
lol
moi cette année j'aurai fait C ,Java, PHP,SQL,UML,XML,shell...
mais jamais fait de pascal ni Caml
Bonsoir,
je ne connais pas le pascal, en revanche le Caml fait partie de notre vie de taupin ... Tu pourrais faire l'analogie :je nomme prog le programme
Let prog v =
let n= vect_length v
ans v'=make_vect 0 n
(*je crée vecteur qui contient 0 et de même longueur que v*)
and j=ref 0 (*j contiendra l'indice des impairs*)
ans i=ref 0 in (*i contiendra l'indice des pairs*) in
for k =0 to n-1 do
if v.(k) mod 2
zut erreur de frappe je reprend :
Let prog v =
let n= vect_length v
and v'=make_vect 0 n
(*je crée vecteur qui contient 0 et de même longueur que v*)
and j=ref n-1 (*j contiendra l'indice des impairs*)
ans i=ref 0 in (*i contiendra l'indice des pairs*) in
for k =0 to n-1 do
if v.(k) mod 2 = 0 then
v'.(i)<-v.(k);
i:=!i +1
else v'.(j)<- v.(k);
j:=!j-1;
done;
!v;;
hatimy -> Il ne peut pas y avoir plusieurs instructions dans un if, il faut que tu mettes des begin end. De plus t'as oublié quelques points d'exclamation
En prépa tout le monde n'apprend pas le Caml, dans le lycée de Kévin ils ont choisi le Pascal à la place.
Fractal
Begin
En effet, j'ai oublié l'exclamation avant le v', mais bon à 3h du mat on manque de vigilance ...
Par contre pour le coup du begin end, on m'a jamais appris ça, on m'a plutôt dit qu'on l'utilisait qu'on voulait définir une même variable dans un même programme ... grossomodo elles jouent le rôle de parenthèse ...
Et puis j'ai toujours cru qu'on n'enseignait que le Caml, vu le faible effectif des élèves qui composent avec le Pascal d'après ce qui est signalé dans les concours. Dans tous les cas j'aurais préféré le Pascal.
End
Si tu rentres le programme suivant, il ne passe même pas le compilateur :
let test b =
if b then
print_endline "Vrai";
print_endline "Vrai bis"
else
print_endline "Faux";
print_endline "Faux bis";;
Pour que le if prenne en compte le fait qu'il y ait plusieurs instructions, il faut soit les encadrer de begin end :
let test b =
if b then
begin
print_endline "Vrai";
print_endline "Vrai bis"
end
else
begin
print_endline "Faux";
print_endline "Faux bis"
end;;
soit les encadrer de parenthèses :
let test b =
if b then
(print_endline "Vrai";
print_endline "Vrai bis")
else
(print_endline "Faux";
print_endline "Faux bis");;
D'autre part, moi aussi j'étais persuadé que tout le monde apprenait le Caml, mais visiblement non
Fractal
Bonsoir
Je suis sur un autre problème, intéressant mais mon programme ne fournit rien (et encore une fois aucune erreur n'est signalée).
But du problème : On possède deux séquences d'ADN formée des bases G,T,A,C. Soit Séquence celle dont la longueur est la plus grande et Extrait l'autre. On cherche à écrire un algorithme qui teste si Extrait est une sous-séquence de Séquence.
Pour fixer les idées, on dit que v est une sous-séquence de u si on retrouve les bases de v dans u et ceci dans le même ordre.
Exemple : u = GTACGTTA et v = GCTA alors on a bien v sous-séquence car u = GTACGTTA
Voilà mon code :
Program genome;
uses dos,crt;
Type Seq=array[1..20] of char;
var i,j,LgSequence, LgExtrait : integer;
Sequence, Extrait : Seq;
baseseq, baseext : char;
Function EstSousSeq (LgSequence, LgExtrait : Integer; Sequence, Extrait : Seq) : Boolean;
Var IndiceSequence, IndiceExtrait : Integer;
Begin
IndiceSequence := 1;
IndiceExtrait := 1;
while (IndiceExtrait <= LgExtrait) and (IndiceSequence <= LgSequence) do
begin
if Extrait[IndiceExtrait] = Sequence[IndiceSequence]
then
Inc(IndiceExtrait);
Inc(IndiceSequence);
end;
EstSousSeq := (IndiceExtrait > LgExtrait);
End;
begin
writeln('Entrez la longueur de la sequence');
readln(LgSequence);
writeln('Entrez la longueur de l extrait');
readln(LgExtrait);
for i:=1 to LgSequence do
begin
writeln('Entrez dans la sequence le terme ',i);
readln(baseseq);
Sequence[i]:=baseseq;
end;
for j:=1 to LgExtrait do
begin
writeln('Entrez dans l extrait le terme ',j);
readln(baseext);
Extrait[j]:=baseext;
end;
for i:=1 to Lgsequence do write(Sequence[i],' ');
writeln;
for j:=1 to LgExtrait do write(Extrait[j], ' ');
writeln;
EstSousSeq(LgSequence,LgExtrait,Sequence,Extrait);
writeln;
readln;
end.
Merci à la personne qui aura le courage d'y jeter un oeil
Salut Kévin
Je ne pourrai pas te corriger sur la syntaxe, mais l'algorithme me semble correct.
Ensuite il y a toujours quelque chose que je ne comprends pas, c'est comment tu es censé récupérer le résultat à la fin? Tu exécutes ta fonction mais il n'y a pas d'instruction d'affichage ou autre, si?
D'autre part, as-tu moyen de faire des fonctions récursives en Pascal? Bien que ton algorithme me semble parfaitement correct, il m'aurait semblé plus naturel de le faire en récursif.
Fractal
Salut Guillaume
Je pensais que puisque c'était une fonction le résultat s'afficherait sans rien demander non ?
Et oui on peut faire du récursif en Pascal mais c'est quelque chose que je ne maitrise pas vraiment.
Je pensais que puisque c'était une fonction le résultat s'afficherait sans rien demander non ?
Là, aucune idée, en Caml il n'y a pas de distinction entre procédures et fonctions, donc je ne peux pas t'en dire plus. Il me semble juste qu'une fonction renvoie un résultat, mais qu'il faut quand même faire un print si tu veux l'afficher. Moi je mettrais un truc du genre :
if EstSousSeq(LgSequence,LgExtrait,Sequence,Extrait);
then
writeln('C'est une sous-séquence, youpi !!');
else
writeln('Ah bah non, c'est pas une sous-séquence, tant pis...');
Si tu ne maîtrise pas le récursif, pas de problème, ton algorithme itératif est très bien
Fractal
Et tsé quoi, en Caml les noms des variables peuvent aller jusqu'à 16 millions de caractères 
Promis, c'est tiré du manuel officiel de Caml ^^
Fractal
Roh t'es génial Guillaume ça marche 
Pour la peine je rend mon devoir avec :
if EstSousSeq(LgSequence,LgExtrait,Sequence,Extrait);
then
writeln('C'est une sous-séquence, youpi !!');
else
writeln('Ah bah non, c'est pas une sous-séquence, tant pis...');
Merci t'assure, toujours là pour filer un coup de main
J'ai été voir
Sache qu'en général ce n'est pas autorisé d'aller sur d'autres topics pour demander de l'aide
Voué ^^ J'essaye
On arrive à se parler entre deux ordis de la maison, c'est déjà ça, mais c'est que par le réseau local pour l'instant, je sais pas si ça marche pour deux ordinateurs connectés uniquement par internet, doit y avoir tous les pare-feux qui vont se réveiller pour empêcher les informations de passer
Fractal
Et c'est balèse à coder ?
Ca me rappelle en MPI en seconde, on avait trouvé un truc pour se parler d'un ordi à l'autre sous ms dos ^^
Non, la partie gestion du réseau est facile, suffit de trouver les quelques commandes nécessaires, mais ça se fait facilement. Après faudra que je voie comment faire pour que chacun puisse parler n'importe quand, parce que la commande qui permet de récupérer ce que l'autre a écrit est bloquante, c'est à dire qu'il est impossible de faire autre chose pendant ce temps, c'est pas pratique.
Fractal
Re infophile,
Pour ton programme, moi je voudrais te proposer quelque chose un poil plus compliqué :
si on a deux séquences u et v représentées par des vecteurs, comment verifier
si v est dans u dans le sens où les bases qui constituent v doivent se succéder dans u.
exemple : u = GTACGTTA et v = ACGT alors v est incluse dans u.(le mot "inclus" je l'ai inventé ).
Tu comprend ce que je cherche ?
Ton programme me paraît long. Est ce dû au langage Pascal lui même ?
je propose ce qui suit :
Let sous-sequence u v =
(*on vérifiera si v est sous-séquence de u*)
let i =ref 0 (*indique l'indice d'un élément de v*)
ans n= vect_length v
and m = vect_length u
and b = ref True in
While !b do
for j =0 to n-1 do
i:=0
while v.(!i)<>v.(j) do
if !i < m then i:=!i+1 (*Fractal j'espère que c'est bon cette fois-ci *)
else b:=False
done
done
done;
!b;;
Bonjour ^^
Ca me rappelle en MPI en seconde, on avait trouvé un truc pour se parler d'un ordi à l'autre sous ms dos ^^
netsend hein ?
Je me rappelle qu'en TD de phsique en première, on avait trouvé la commande
pour envoyer un message ... à tout le réseau
(ie les 500 ordis du bahut )
Et sinon > Guigui, bravo
moi j'aimerais resté dans les données de ton vecteur et résoudre ce problème.
C'est quoi cette fonction Pos ?
Regarde ici : 
Cela dit ça doit pas être bien compliqué à programmer, on prend la première lettre de l'extrait on regarde si elle est dans la séquence et une fois trouvée on regarde si les lettres suivantes coincident avec le reste de l'extrait. Et on fait une boucle pour traiter les occurences.
Oui, là le coût du programme doit être grossomodo de l'ordre de np avec n la longueur de ta liste et p la longueur de ton mot (je trouve qu'il vaut dans le pire des cas p.(n-(p+1)/2) )
Je sais pas s'il peut y avoir une astuce pour avoir un coût moindre...
Re-bonjour
J'ai de nouveau un tout petit problème :
Une séquence w est sous-séquence commune maximale de u et v si w est sous-séquence de u et v, et de longueur maximale. On note L(i,j) la longueur d'une sous-séquence commune maximale aux mots u(i) = a1...ai et v(j) = b1...bj.
J'ai montré que
On veut une fonction qui donne la longueur maximale de cette sous-séquence commune. Alors voici l'algo que j'ai testé, il marche (presque) bien, il donne la longueur maximale - 1 et je ne vois pas d'où sort ce -1
Function LongSSC(n,m:integer;u,v:Seq):integer;
Var i,j,k,l:integer;w:array[0..Nmax,0..Nmax] of integer;
Begin
for k:=0 to n do
begin
for l:=0 to n do w[k,l]:=0;
end;
for i:=1 to n do
begin
for j:=1 to m do
begin
if (u[i-1]=v[j-1]) then
w[i,j]:=1+w[i-1,j-1]
else
begin
if (w[i,j-1]<w[i-1,j]) then
w[i,j]:=w[i-1,j]
else
w[i,j]:=w[i,j-1];
end;
end;
end;
LongSSC:=w[n,m];
End;
Merci à celui qui verra le soucis
est ce que tu l'a fait récursivement ton programme ? Comment est ce qu'on déclare la récursivité en Pascal ?
Non je n'ai pas fait de récursif, en plus ça ne fonctionne pas chez moi, par exemple j'ai essayé de trouver le bit p d'un nombre a en récursif et j'ai une erreur à la compilation :
Function bit2(a,p : integer) : LongInt;
begin
if p>0 then bit2(a,p):=bit2(a div 2, p-1) else bit2(a,p):=a mod 2
end;
Et ça marque : Argument can't be assigned to
Annuler
connectez vous