séquence des voyelles

Voir le sujet précédent Voir le sujet suivant Aller en bas

séquence des voyelles

Message par suneddine le Sam 1 Déc - 22:05

développer un programme qui permet de saisir une séquence de lettres (pas nécessairement toutes en miniscule ou en majuscule) et d'afficher la longueur de la sous-séquence des voyelles la plus longue.
avatar
suneddine
Nombre Réel
Nombre Réel

Masculin
Nombre de messages : 730
Age : 31
Localisation : tunisie
Réputation : 5
Points : 3733
Date d'inscription : 11/11/2007

Feuille de personnage
Capacité linguistique:
995/1000  (995/1000)

Revenir en haut Aller en bas

Re: séquence des voyelles

Message par informix le Sam 1 Déc - 22:32

oh! c'est assez dur. Un bon exercice pour s'entrainer et s'échauffer. Toutefois, pourquoi vous avez choisi de le mettre dans la rubrique INFO-Supérieur ? Pourquoi pas dans INFO-Lycée? confused

_________________
informix, Ecole d'ingénieurs
Les passions font vivre l'Homme; sa sagesse le fait seulement durer.
avatar
informix
Nombre Rationnel
Nombre Rationnel

Nombre de messages : 399
Réputation : 4
Points : 3937
Date d'inscription : 19/03/2007

Feuille de personnage
Capacité linguistique:
1000/1000  (1000/1000)

Revenir en haut Aller en bas

Re: séquence des voyelles

Message par manianis le Dim 2 Déc - 22:54

Je dirai que l'énoncé n'est pas assez clair.

Comment connaitre le début ou la fin d'une sous séquence ?

manianis
Nombre Réel
Nombre Réel

Masculin
Nombre de messages : 975
Localisation : Tunisie
Réputation : 4
Points : 3666
Date d'inscription : 11/10/2007

Feuille de personnage
Capacité linguistique:
999/1000  (999/1000)

http://manianis.sitesled.com/

Revenir en haut Aller en bas

Re: séquence des voyelles

Message par Napoléon le Dim 2 Déc - 23:04

Je crois que c'est clair manianis:
Une chaine qui ne concerne dans cet exercice, est toute chaine qui contient uniquement des voyelles.
On avance, caractère par caractère, là où on trouve une voyelle on annonce le début d'une éventuelle solution. Là où on détecte une "non-voyelle", on annonce la fin de la solution candidate.

_________________
Nabil - tunis
خير الناس أنفعهم للناس
avatar
Napoléon
Admin
Admin

Masculin
Nombre de messages : 2934
Localisation : Tunisie
Réputation : 122
Points : 5283
Date d'inscription : 19/03/2007

Feuille de personnage
Capacité linguistique:
999/1000  (999/1000)

http://infomath.online-talk.net

Revenir en haut Aller en bas

Re: séquence des voyelles

Message par suneddine le Dim 2 Déc - 23:15

je veux dire que j'ai pas la solution de ce problème et je l'ai proposé pour que l'on résout ensemble,

si par exemple la séquence est la suivante

bfgdKjGaeiouykjlmoisPMCX

donc aeiouy est la sous séquence des voyelles la plus longue

pour connaître son début, on teste si le caractère est a ou e ou i ou o ou u ou y.

c'est ça ou non
avatar
suneddine
Nombre Réel
Nombre Réel

Masculin
Nombre de messages : 730
Age : 31
Localisation : tunisie
Réputation : 5
Points : 3733
Date d'inscription : 11/11/2007

Feuille de personnage
Capacité linguistique:
995/1000  (995/1000)

Revenir en haut Aller en bas

Re: séquence des voyelles

Message par Napoléon le Dim 2 Déc - 23:23

oui: c'est correct l'exemple que tu as posté.
Je vais essayer de trouver une solution et l'implémenter en PASCAL. RDV après quelques minutes (inchallah)

_________________
Nabil - tunis
خير الناس أنفعهم للناس
avatar
Napoléon
Admin
Admin

Masculin
Nombre de messages : 2934
Localisation : Tunisie
Réputation : 122
Points : 5283
Date d'inscription : 19/03/2007

Feuille de personnage
Capacité linguistique:
999/1000  (999/1000)

http://infomath.online-talk.net

Revenir en haut Aller en bas

Re: séquence des voyelles

Message par Napoléon le Dim 2 Déc - 23:52

Code:
program plusLgSequenceV;
uses wincrt;

(* fontion: vérifie si une lettre est voyelle ou non *)
function isVowel(c: char):boolean;
begin
  isVowel := (Upcase(c)='A') or (Upcase(c)='E') or (Upcase(c)='I') or
              (Upcase(c)='O') or (Upcase(c)='U') or (Upcase(c)='Y');
end;

(* fonction: retourne la plus longue séquence de voyelles *)
function getLonguestSeqV(ch:string):string;
var
  curSeq : string;  (* la séquence en cours de construction *)
  lgSeq  : string;  (* la plus longue séquence trouvée *)
  i      :integer;
begin
  lgSeq  := '' ;
  curSeq := '' ;
  for i:=1 to length(ch) do
  begin
    if (isVowel(ch[i])) then
        curSeq := curSeq + ch[i]
    else
    begin
      if (length(curSeq)>length(lgSeq)) then
          lgSeq := curSeq;
      curSeq := ''; 
    end;
  end;
  if (length(curSeq)>length(lgSeq)) then
    lgSeq := curSeq;
  getLonguestSeqV := lgSeq;
end;


(* PROGRAMME PRINCIPAL *)
VAR
  chaine: string;

BEGIN
  write('Donner une séquence de lettres: ');
  readln(chaine);
  Write('Plus longue séq de VoyL: ',getLonguestSeqV(chaine));
END.

_________________
Nabil - tunis
خير الناس أنفعهم للناس
avatar
Napoléon
Admin
Admin

Masculin
Nombre de messages : 2934
Localisation : Tunisie
Réputation : 122
Points : 5283
Date d'inscription : 19/03/2007

Feuille de personnage
Capacité linguistique:
999/1000  (999/1000)

http://infomath.online-talk.net

Revenir en haut Aller en bas

Re: séquence des voyelles

Message par methodiX le Lun 3 Déc - 23:53

Excellente solution. Peut-on faire mieux??? point de vue Complexité Algorithmique!

_________________
Sami - Methodix, tunis
Le génie de Newton a consisté à dire que la lune tombe alors que tout le monde voit bien qu'elle ne tombe pas.
(Paul Valéry)
_____
Cliquer ici: Voir les nouveaux messages depuis votre dernière visite
Cliquer ici: Astuce: Utiliser l'outil "Recherche" du forum
avatar
methodiX
Admin
Admin

Masculin
Nombre de messages : 1260
Localisation : Le couloir de l'école polytechnique de Tunis
Réputation : 68
Points : 4665
Date d'inscription : 22/03/2007

Feuille de personnage
Capacité linguistique:
1000/1000  (1000/1000)

Revenir en haut Aller en bas

Re: séquence des voyelles

Message par manianis le Mar 4 Déc - 0:16

Bon programme Nabil.

manianis
Nombre Réel
Nombre Réel

Masculin
Nombre de messages : 975
Localisation : Tunisie
Réputation : 4
Points : 3666
Date d'inscription : 11/10/2007

Feuille de personnage
Capacité linguistique:
999/1000  (999/1000)

http://manianis.sitesled.com/

Revenir en haut Aller en bas

Re: séquence des voyelles

Message par suneddine le Mar 4 Déc - 9:15

Code:

 if (length(curSeq)>length(lgSeq)) then
          lgSeq := curSeq;
      curSeq := ''; 
    end;
  end;
  if (length(curSeq)>length(lgSeq)) then
    lgSeq := curSeq;
  getLonguestSeqV := lgSeq;
end;

pourquoi la même if...then se répète deux fois?
avatar
suneddine
Nombre Réel
Nombre Réel

Masculin
Nombre de messages : 730
Age : 31
Localisation : tunisie
Réputation : 5
Points : 3733
Date d'inscription : 11/11/2007

Feuille de personnage
Capacité linguistique:
995/1000  (995/1000)

Revenir en haut Aller en bas

Re: séquence des voyelles

Message par manianis le Mar 4 Déc - 10:35

La boucle for ... to pourra se terminer alors que le test s'il s'agit de la plus longue séquence n'a pas été exécuté.

Exemple :
iuytrrrrroiuyoiuyoiuy
si vous ne faites pas ce test le programme considérera iuy comme étant la séquence la plus longue.

manianis
Nombre Réel
Nombre Réel

Masculin
Nombre de messages : 975
Localisation : Tunisie
Réputation : 4
Points : 3666
Date d'inscription : 11/10/2007

Feuille de personnage
Capacité linguistique:
999/1000  (999/1000)

http://manianis.sitesled.com/

Revenir en haut Aller en bas

Re: séquence des voyelles

Message par Napoléon le Mar 4 Déc - 11:44

manianis a écrit:La boucle for ... to pourra se terminer alors que le test s'il s'agit de la plus longue séquence n'a pas été exécuté.

Exemple :
iuytrrrrroiuyoiuyoiuy
si vous ne faites pas ce test le programme considérera iuy comme étant la séquence la plus longue.

mosa:C'est exactement ça.
Essaie de l'enlever, la deuxième IF, et tu verras que si la plus longue séquence est située à la fin, elle va être ignorée.

_________________
Nabil - tunis
خير الناس أنفعهم للناس
avatar
Napoléon
Admin
Admin

Masculin
Nombre de messages : 2934
Localisation : Tunisie
Réputation : 122
Points : 5283
Date d'inscription : 19/03/2007

Feuille de personnage
Capacité linguistique:
999/1000  (999/1000)

http://infomath.online-talk.net

Revenir en haut Aller en bas

Re: séquence des voyelles

Message par informix le Sam 8 Déc - 13:52

on n'a souvent parlé de complexité dans notre forum Smile
alors, quelle est la complexité du programme proposé par NabiL ?

_________________
informix, Ecole d'ingénieurs
Les passions font vivre l'Homme; sa sagesse le fait seulement durer.
avatar
informix
Nombre Rationnel
Nombre Rationnel

Nombre de messages : 399
Réputation : 4
Points : 3937
Date d'inscription : 19/03/2007

Feuille de personnage
Capacité linguistique:
1000/1000  (1000/1000)

Revenir en haut Aller en bas

Re: séquence des voyelles

Message par manianis le Sam 8 Déc - 17:40

La complexité de votre algoithme est O(n). elle dépend uniquement du nombre de caractères dans la chaine de caractères.

manianis
Nombre Réel
Nombre Réel

Masculin
Nombre de messages : 975
Localisation : Tunisie
Réputation : 4
Points : 3666
Date d'inscription : 11/10/2007

Feuille de personnage
Capacité linguistique:
999/1000  (999/1000)

http://manianis.sitesled.com/

Revenir en haut Aller en bas

Re: séquence des voyelles

Message par Napoléon le Sam 8 Déc - 20:31

C'est à peu près comme la recherche du plus grand élément dans un tableau: il faut parcourir tout le tableau. C'est en O(n) la complexité.

NB: O(n) ne veut pas dire "n"

_________________
Nabil - tunis
خير الناس أنفعهم للناس
avatar
Napoléon
Admin
Admin

Masculin
Nombre de messages : 2934
Localisation : Tunisie
Réputation : 122
Points : 5283
Date d'inscription : 19/03/2007

Feuille de personnage
Capacité linguistique:
999/1000  (999/1000)

http://infomath.online-talk.net

Revenir en haut Aller en bas

Re: séquence des voyelles

Message par manianis le Sam 8 Déc - 22:36

Admin a écrit:C'est à peu près comme la recherche du plus grand élément dans un tableau: il faut parcourir tout le tableau. C'est en O(n) la complexité.

NB: O(n) ne veut pas dire "n"

çà veut dire que la complexité du problème est proportielle à la valeur de n.

manianis
Nombre Réel
Nombre Réel

Masculin
Nombre de messages : 975
Localisation : Tunisie
Réputation : 4
Points : 3666
Date d'inscription : 11/10/2007

Feuille de personnage
Capacité linguistique:
999/1000  (999/1000)

http://manianis.sitesled.com/

Revenir en haut Aller en bas

Re: séquence des voyelles

Message par Napoléon le Sam 8 Déc - 22:46

Pas forcément Proportonnelle à n, car sinon: O(n²) veut dire Proportionnelle à n²: ce qui est faux.
O(n^k) => Complexité polynomiale de degré k.

_________________
Nabil - tunis
خير الناس أنفعهم للناس
avatar
Napoléon
Admin
Admin

Masculin
Nombre de messages : 2934
Localisation : Tunisie
Réputation : 122
Points : 5283
Date d'inscription : 19/03/2007

Feuille de personnage
Capacité linguistique:
999/1000  (999/1000)

http://infomath.online-talk.net

Revenir en haut Aller en bas

Re: séquence des voyelles

Message par manianis le Dim 9 Déc - 0:02

Code:
Pour i=1 to n Faire
  Pour j=1 to m Faire
    traitement
  Fin Pour
Fin Pour


Quelle est la complexité de cette portion d'algorithme ?

manianis
Nombre Réel
Nombre Réel

Masculin
Nombre de messages : 975
Localisation : Tunisie
Réputation : 4
Points : 3666
Date d'inscription : 11/10/2007

Feuille de personnage
Capacité linguistique:
999/1000  (999/1000)

http://manianis.sitesled.com/

Revenir en haut Aller en bas

Re: séquence des voyelles

Message par Napoléon le Dim 9 Déc - 0:17

Elle est polynomiale. Elle vaut nxm opérations Traitements.
Soit N = max(m,n), alors, elle est en O(N²) (en réalité O(m,n)).
Le nombre d'affectation lors de l'initialisation d'une matrice A(m,n) est mxn.

_________________
Nabil - tunis
خير الناس أنفعهم للناس
avatar
Napoléon
Admin
Admin

Masculin
Nombre de messages : 2934
Localisation : Tunisie
Réputation : 122
Points : 5283
Date d'inscription : 19/03/2007

Feuille de personnage
Capacité linguistique:
999/1000  (999/1000)

http://infomath.online-talk.net

Revenir en haut Aller en bas

Re: séquence des voyelles

Message par Contenu sponsorisé


Contenu sponsorisé


Revenir en haut Aller en bas

Voir le sujet précédent Voir le sujet suivant Revenir en haut

- Sujets similaires

 
Permission de ce forum:
Vous ne pouvez pas répondre aux sujets dans ce forum