Forum INFOMATH
Vous souhaitez réagir à ce message ? Créez un compte en quelques clics ou connectez-vous pour continuer.
Le Deal du moment :
Google Pixel 7 5G – Smartphone 6,3″ OLED ...
Voir le deal
316 €

séquence des voyelles

5 participants

Aller en bas

séquence des voyelles Empty séquence des voyelles

Message par suneddine 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.
suneddine
suneddine
Nombre Réel
Nombre Réel

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

Feuille de personnage
Capacité linguistique:
séquence des voyelles Left_bar_bleue995/1000séquence des voyelles Empty_bar_bleue  (995/1000)

Revenir en haut Aller en bas

séquence des voyelles Empty Re: séquence des voyelles

Message par informix 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
informix
Nombre Rationnel
Nombre Rationnel

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

Feuille de personnage
Capacité linguistique:
séquence des voyelles Left_bar_bleue1000/1000séquence des voyelles Empty_bar_bleue  (1000/1000)

Revenir en haut Aller en bas

séquence des voyelles Empty Re: séquence des voyelles

Message par manianis 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 : 6015
Date d'inscription : 11/10/2007

Feuille de personnage
Capacité linguistique:
séquence des voyelles Left_bar_bleue999/1000séquence des voyelles Empty_bar_bleue  (999/1000)

http://manianis.sitesled.com/

Revenir en haut Aller en bas

séquence des voyelles Empty Re: séquence des voyelles

Message par Napoléon 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.
Napoléon
Napoléon
Admin
Admin

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

Feuille de personnage
Capacité linguistique:
séquence des voyelles Left_bar_bleue999/1000séquence des voyelles Empty_bar_bleue  (999/1000)

https://infomath.1fr1.net

Revenir en haut Aller en bas

séquence des voyelles Empty Re: séquence des voyelles

Message par suneddine 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
suneddine
suneddine
Nombre Réel
Nombre Réel

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

Feuille de personnage
Capacité linguistique:
séquence des voyelles Left_bar_bleue995/1000séquence des voyelles Empty_bar_bleue  (995/1000)

Revenir en haut Aller en bas

séquence des voyelles Empty Re: séquence des voyelles

Message par Napoléon 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)
Napoléon
Napoléon
Admin
Admin

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

Feuille de personnage
Capacité linguistique:
séquence des voyelles Left_bar_bleue999/1000séquence des voyelles Empty_bar_bleue  (999/1000)

https://infomath.1fr1.net

Revenir en haut Aller en bas

séquence des voyelles Empty Re: séquence des voyelles

Message par Napoléon 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.
Napoléon
Napoléon
Admin
Admin

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

Feuille de personnage
Capacité linguistique:
séquence des voyelles Left_bar_bleue999/1000séquence des voyelles Empty_bar_bleue  (999/1000)

https://infomath.1fr1.net

Revenir en haut Aller en bas

séquence des voyelles Empty Re: séquence des voyelles

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

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

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

Feuille de personnage
Capacité linguistique:
séquence des voyelles Left_bar_bleue1000/1000séquence des voyelles Empty_bar_bleue  (1000/1000)

Revenir en haut Aller en bas

séquence des voyelles Empty Re: séquence des voyelles

Message par manianis 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 : 6015
Date d'inscription : 11/10/2007

Feuille de personnage
Capacité linguistique:
séquence des voyelles Left_bar_bleue999/1000séquence des voyelles Empty_bar_bleue  (999/1000)

http://manianis.sitesled.com/

Revenir en haut Aller en bas

séquence des voyelles Empty Re: séquence des voyelles

Message par suneddine 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?
suneddine
suneddine
Nombre Réel
Nombre Réel

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

Feuille de personnage
Capacité linguistique:
séquence des voyelles Left_bar_bleue995/1000séquence des voyelles Empty_bar_bleue  (995/1000)

Revenir en haut Aller en bas

séquence des voyelles Empty Re: séquence des voyelles

Message par manianis 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 : 6015
Date d'inscription : 11/10/2007

Feuille de personnage
Capacité linguistique:
séquence des voyelles Left_bar_bleue999/1000séquence des voyelles Empty_bar_bleue  (999/1000)

http://manianis.sitesled.com/

Revenir en haut Aller en bas

séquence des voyelles Empty Re: séquence des voyelles

Message par Napoléon 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.
Napoléon
Napoléon
Admin
Admin

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

Feuille de personnage
Capacité linguistique:
séquence des voyelles Left_bar_bleue999/1000séquence des voyelles Empty_bar_bleue  (999/1000)

https://infomath.1fr1.net

Revenir en haut Aller en bas

séquence des voyelles Empty Re: séquence des voyelles

Message par informix 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
informix
Nombre Rationnel
Nombre Rationnel

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

Feuille de personnage
Capacité linguistique:
séquence des voyelles Left_bar_bleue1000/1000séquence des voyelles Empty_bar_bleue  (1000/1000)

Revenir en haut Aller en bas

séquence des voyelles Empty Re: séquence des voyelles

Message par manianis 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 : 6015
Date d'inscription : 11/10/2007

Feuille de personnage
Capacité linguistique:
séquence des voyelles Left_bar_bleue999/1000séquence des voyelles Empty_bar_bleue  (999/1000)

http://manianis.sitesled.com/

Revenir en haut Aller en bas

séquence des voyelles Empty Re: séquence des voyelles

Message par Napoléon 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"
Napoléon
Napoléon
Admin
Admin

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

Feuille de personnage
Capacité linguistique:
séquence des voyelles Left_bar_bleue999/1000séquence des voyelles Empty_bar_bleue  (999/1000)

https://infomath.1fr1.net

Revenir en haut Aller en bas

séquence des voyelles Empty Re: séquence des voyelles

Message par manianis 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 : 6015
Date d'inscription : 11/10/2007

Feuille de personnage
Capacité linguistique:
séquence des voyelles Left_bar_bleue999/1000séquence des voyelles Empty_bar_bleue  (999/1000)

http://manianis.sitesled.com/

Revenir en haut Aller en bas

séquence des voyelles Empty Re: séquence des voyelles

Message par Napoléon 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.
Napoléon
Napoléon
Admin
Admin

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

Feuille de personnage
Capacité linguistique:
séquence des voyelles Left_bar_bleue999/1000séquence des voyelles Empty_bar_bleue  (999/1000)

https://infomath.1fr1.net

Revenir en haut Aller en bas

séquence des voyelles Empty Re: séquence des voyelles

Message par manianis 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 : 6015
Date d'inscription : 11/10/2007

Feuille de personnage
Capacité linguistique:
séquence des voyelles Left_bar_bleue999/1000séquence des voyelles Empty_bar_bleue  (999/1000)

http://manianis.sitesled.com/

Revenir en haut Aller en bas

séquence des voyelles Empty Re: séquence des voyelles

Message par Napoléon 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.
Napoléon
Napoléon
Admin
Admin

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

Feuille de personnage
Capacité linguistique:
séquence des voyelles Left_bar_bleue999/1000séquence des voyelles Empty_bar_bleue  (999/1000)

https://infomath.1fr1.net

Revenir en haut Aller en bas

séquence des voyelles Empty Re: séquence des voyelles

Message par Contenu sponsorisé


Contenu sponsorisé


Revenir en haut Aller en bas

Revenir en haut

- Sujets similaires

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