Discussion :

[Inf0phile]

Bonsoir,

Je possède un tableau de caractères qui représente une séquence d'ADN, par exemple u=GTAGCTAACA. On dira que v est une sous séquence de u si par exemple v=GTAC car u=GTAGCTAACA. Autrement dit on retrouve la séquence v dans u en conservant l'ordre des lettres.

On veut alors écrire une Fonction EstSousSeq qui teste si la séquence v de longueur m est sous-séquence de u de longueur n.

Voilà mon code :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
Program genome;
 
uses dos,crt;
 
Type Seq=array[1..20] of char;
 
Procedure EstSousSeq(n,m:integer; var u,v : Seq)
 
var i,j:integer;
 
begin
 
for i:=1 to m do
 
    begin
    j:=i;
    while v[i]<>u[j] do j:=j+1;
    if j<>n then write(u[j]) else write('v n est pas une sous séquence de u');
    end;
 
end;
 
begin
 
end.

En compilant j'obtiens une erreur "Expected but VAR found" à la ligne "var i,j:integer;". Par ailleurs j'aimerai savoir si la structure de mon algorithme est bonne car je n'ai pas su utiliser une fonction (qui renverrait je suppose un booleen).

Merci beaucoup !

[droggo]

Fio,

Il manque un ; (point-virgule) sur la ligne définissant l'en-tête de la procédure

Procedure EstSousSeq(n,m:integer; var u,v : Seq);

[Inf0phile]

Bonsoir

Effectivement l'erreur venait de là merci ! Cela dit mon programme n'est pas opérationnel... une idée ?

[Inf0phile]

S'iouplait

[droggo]

Dio,

Bonsoir

Effectivement l'erreur venait de là merci ! Cela dit mon programme n'est pas opérationnel... une idée ?

Ben, si le code est celui posté plus haut + correction, il ne va pas faire grand chose, puisque tu ne lui donne rien à faire.

[Inf0phile]

Bonsoir,

J'ai deux problèmes : le premier c'est que je ne sais même pas si ma procédure permet effectivement de vérifier si v est une sous-séquence de u ; et le deuxième c'est que je ne sais pas générer une liste de caractère aléatoirement, ou même demander à l'utilisateur de les rentrer lui-même pour pouvoir lui appliquer la procédure.

Excusez moi je débute en Pascal

Merci pour vos réponses !

[droggo]

Fio,

Bonsoir,

J'ai deux problèmes : le premier c'est que je ne sais même pas si ma procédure permet effectivement de vérifier si v est une sous-séquence de u ; et le deuxième c'est que je ne sais pas générer une liste de caractère aléatoirement, ou même demander à l'utilisateur de les rentrer lui-même pour pouvoir lui appliquer la procédure.

Excusez moi je débute en Pascal

Merci pour vos réponses !

Alors, il faut apprendre les bases.

[Inf0phile]

Vous ne pouvez pas m'aider ?

[Alcatîz]

Bonjour !

L'algorithme est assez simple, une boucle dans laquelle l'indice dans la séquence de référence est incrémenté à chaque itération et l'indice dans la sous-séquence n'est incrémenté que lorsque une base est trouvée dans la séquence de référence. Si l'indice dans la sous-séquence a atteint la fin de celle-ci, c'est que toutes les lettres se trouvent (dans l'ordre) dans la séquence de référence.

Voici ce que pourrait donner l'algo :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
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;

Deux petites remarques en passant :

• Tu devrais choisir des noms de variables plus parlants
• Tu pourrais travailler avec des chaînes de type String[20], c'est plus pratique pour leur affecter une valeur.

[droggo]

Gie,

Bonsoir,

Je possède un tableau de caractères qui représente une séquence d'ADN, par exemple u=GTAGCTAACA. On dira que v est une sous séquence de u si par exemple v=GTAC car u=GTAGCTAACA. Autrement dit on retrouve la séquence v dans u en conservant l'ordre des lettres.

Dans ton message, je vois que tu sembles accepter qu'on peut rechercher la séquence même s'il y a un nucléotide qui s'y insère.

Est-ce volontaire ou une erreur ?

Si c'est volontaire, quelles sont les limites des insertions acceptées (une insertion de 1 ou plusieurs nucléotides, plusieurs insertions de 1 ou plusieurs nucléotides) ?

L'algorithme va évidemment dépendre de ces valeurs.

[Loceka]

Pour faire de l'aléatoire, il faut utiliser la fonction random, que l'on initialise avec randomize (voir la FAQ).

Le résultat te donnant un entier (si tu affectes le résultat d'un random à un entier), il faut que tu fasses toi-même le lien avec les caractères. Tu peux par exemple utiliser un tableau de 4 cases contenant tes caractères et l'entier que tu tires correspondra à un index du tableau.

Pour les interactions avec l'utilisateur, le plus simple est d'utiliser la fonction readln. Exemple :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
program interaction;
uses crt;
 
var
  s : string;
begin
  writeln("tapez quelque chose au clavier.");
  readln(s);
  write("vous avez ecrit : ",s);
end.

Après tu peux faire des boucles sur les entrées/sorties pour répéter un traitement.

[Inf0phile]

Bonjour à tous, et merci pour vos réponses !

droggo > Oui on peut insérer des bases entre, on dit que v est une sous séquence de u si on retrouve les bases qui composent v dans u avec le même ordre.

Du coup il me semble que la fonction d'Alcatiz ne colle pas à cette définition non ? J'ai l'impression en le lisant qu'on aurait une sous séquence uniquement si on retrouve v dans u tel quel. En tout cas je le remercie pour l'effort et je vais tâcher de tenir compte de ses conseils !

Et merci aussi à Loceka je vais me renseigner sur cette fonction random.

[droggo]

Voi,

droggo > Oui on peut insérer des bases entre, on dit que v est une sous séquence de u si on retrouve les bases qui composent v dans u avec le même ordre.

Mais il doit bien y avoir une limite sur les insertions admises, sinon, si la séquence est assez longue, on a de bonnes chances de retrouver une sous-séquence de longueur notablement inférieure.

[Inf0phile]

Je ne comprends pas bien, un exemple sera peut-être plus parlant :

u = GACTGATTCGT et v = GGACT

On a bien v qui est une sous-séquence de u car on retrouve ces lettres dans le même ordre à l'intérieur de u :

u = GACTGATTCGT

Et on n'a pas obligatoirement unicité de la sous-séquence dans u.

Et en lisant la fonction d'Alcatiz j'ai l'impression qu'elle tente de retrouver le "bloc" GGACT dans u, c'est le cas ?

Merci beaucoup !

[droggo]

Gio,

Donc, on accepte n'importe quelles insertions, du moment qu'on retrouve la sous-séquence, même découpée à l'extrême, avec des insertions de longueur quelconque.

Mais je reprends un de mes messages précédents : te lancer là-dedans sans connaître les bases ne te mènera pas loin (savoir demander une donnée à l'utilisateur est basique parmi les bases, utiliser un array[1..20] of char au lieu de string[20] l'est tout autant [il n'est bien entendu pas interdit d'utiliser array[1..20] of char, mais il faut savoir pourquoi on le fait, car en se passant des string, on se prive de tout le fonctionnement basique des chaînes]), et je n'insisterai pas sur la génération de nombres pseudo-aléatoires, donc sur l'existence des fonctions Random et Randomize.
Donc, apprends les bases avant de vouloir aller plus loin.

[Inf0phile]

Donc, on accepte n'importe quelles insertions, du moment qu'on retrouve la sous-séquence, même découpée à l'extrême, avec des insertions de longueur quelconque.

Tout à fait !

Pour le reste excusez moi mais je suis le cheminement donné par mon prof, l'utilisation de array est demandé dans mon exercice...

Ce n'est pas de la mauvaise volonté de ma part, j'ai répondu à plein d'autres questions, celle-ci en est une sur laquelle je bloque. Je suis un habitué d'un site de maths, et souvent on peut voir des intervenants qui se contentent de dire "c'est trivial, apprend ton cours", et je ne pense pas que ça soit très constructif. Pour ma part j'ai besoin de "faire" pour assimiler, je demande juste que l'on m'aiguille un petit peu.

Pour en revenir au problème, je voudrais savoir si le raisonnement logique de mon code (premier post) est juste : Je prends la première lettre de v et je balaye u jusqu'à ce que je trouve la même, puis je prend la deuxième lettre de v et je balaye de nouveau en repartant de la lettre trouvée où je me suis arrêté au premier balayage, et ainsi de suite. Si à chaque itération je trouve une lettre correspondante dans u alors v sera sous-séquence.

Est-ce que ça vous paraît correct ?

Merci beaucoup !

[droggo]

Fio,

Et ton prof ne t'a pas appris à utiliser ReadLn pour lire une donnée entrée par l'utilisateur ? ...

Si c'est le cas, en voilà un de plus qu'il faut fusiller immédiatement.

Pour ton algorithme, c'est ok selon ta description ci-dessus, mais ce n'est pas ce que fait ta procédure, ou du moins, elle le fait mal :

- par exemple, pas de vérification des limites utiles/maxi des tableaux, problème qui se posera si on ne trouve pas la sous-séquence
(ici, tant qu'à faire, le type utilisé pourrait plutôt être

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
 
const
  seqLongMaxi = 20;
 
type
  seqTable = array [1..seqLongMaxi];
 
  seq = record
    longueur : integer; { longueur effective des données dans la table }
    table : seqTable;
  end;

ça évite de trimbaler des variables séparées pour la table et sa longueur effectivement utile (ce regroupement est le but premier des enregistrements (record))

- La boucle For sur la longueur de la sous-séquence est inadaptée, car elle ira jusqu'au bout, même si on a déjà déterminé que la sous-séquence ne pourra pas être trouvée.

Et je reprends un message d'Alcatîz : utilise des noms significatifs pour les variables, ça simplifie la lecture, aussi bien pour toi que pour les autres (u,v,... ne sont pas directement reliés à ce qu'ils représentent).
C'est là une des règles à suivre systématiquement, ça facilite la lecture/maintenance du code, par toi ou par quelqu'un d'autre.

[Inf0phile]

Merci de votre aide, j'apprécie

Je me suis renseigné pour "record", si j'ai bien compris à une variable on associe une "sous-variable" qu'on appelle champs. En particulier ici à chaque séquence on associe sa longueur.

Et effectivement la boucle For c'est pas terrible si par exemple pour IndiceExtrait=1 on ne trouve pas de lettre correspondante dans Séquence (je reprends les notations d'Alcatiz c'est plus clair c'est vrai). Peut-être peut-on utiliser un "break" pour stopper la boucle si on ne trouve pas de lettre dans la Séquence ?

Enfin je n'ai jamais manipulé de boolean pour les fonctions, donc ici si je ne me trompe pas la fonction retourne "vrai" si IndiceExtrait = LgExtrait c'est-à-dire si la boucle n'a pas été stoppée ?

[Alcatîz]

Bonjour,

Je ne comprends pas bien, un exemple sera peut-être plus parlant :

u = GACTGATTCGT et v = GGACT

On a bien v qui est une sous-séquence de u car on retrouve ces lettres dans le même ordre à l'intérieur de u :

u = GACTGATTCGT

Et on n'a pas obligatoirement unicité de la sous-séquence dans u.

Et en lisant la fonction d'Alcatiz j'ai l'impression qu'elle tente de retrouver le "bloc" GGACT dans u, c'est le cas ?

Merci beaucoup !

Il suffit de tester. Et il me semble qu'elle accomplit bien ce qui est demandé. C'est parce que l'algo est simple qu'il est louche (je plaisante) ?

S'il fallait tester la présence d'un bloc tout entier, le problème se résoudrait en une seule ligne avec la fonction Pos (vu que j'ai raisonné sur des strings).

[Inf0phile]

C'est parce que l'algo est simple qu'il est louche (je plaisante) ?

Je vais essayer de tester alors, désolé d'avoir douté ! J'essaierai ensuite de bien comprendre l'algorithme.

A dans quelques minutes