séquence des voyelles
5 participants
Forum INFOMATH :: Enseignement de l'informatique :: INFO - Supérieur (Etudiants et Professionnels) :: C/C++
Page 1 sur 1
séquence des voyelles
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- Nombre Réel
-
Nombre de messages : 730
Age : 38
Localisation : tunisie
Réputation : 5
Points : 6082
Date d'inscription : 11/11/2007
Feuille de personnage
Capacité linguistique:
(995/1000)
Re: séquence des voyelles
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?
informix- Nombre Rationnel
- Nombre de messages : 399
Réputation : 4
Points : 6286
Date d'inscription : 19/03/2007
Feuille de personnage
Capacité linguistique:
(1000/1000)
Re: séquence des voyelles
Je dirai que l'énoncé n'est pas assez clair.
Comment connaitre le début ou la fin d'une sous séquence ?
Comment connaitre le début ou la fin d'une sous séquence ?
manianis- Nombre Réel
-
Nombre de messages : 975
Localisation : Tunisie
Réputation : 4
Points : 6015
Date d'inscription : 11/10/2007
Feuille de personnage
Capacité linguistique:
(999/1000)
Re: séquence des voyelles
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.
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- Admin
-
Nombre de messages : 2934
Localisation : Tunisie
Réputation : 122
Points : 7632
Date d'inscription : 19/03/2007
Feuille de personnage
Capacité linguistique:
(999/1000)
Re: séquence des voyelles
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
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- Nombre Réel
-
Nombre de messages : 730
Age : 38
Localisation : tunisie
Réputation : 5
Points : 6082
Date d'inscription : 11/11/2007
Feuille de personnage
Capacité linguistique:
(995/1000)
Re: séquence des voyelles
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)
Je vais essayer de trouver une solution et l'implémenter en PASCAL. RDV après quelques minutes (inchallah)
Napoléon- Admin
-
Nombre de messages : 2934
Localisation : Tunisie
Réputation : 122
Points : 7632
Date d'inscription : 19/03/2007
Feuille de personnage
Capacité linguistique:
(999/1000)
Re: séquence des voyelles
- 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- Admin
-
Nombre de messages : 2934
Localisation : Tunisie
Réputation : 122
Points : 7632
Date d'inscription : 19/03/2007
Feuille de personnage
Capacité linguistique:
(999/1000)
Re: séquence des voyelles
Excellente solution. Peut-on faire mieux??? point de vue Complexité Algorithmique!
methodiX- Admin
-
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:
(1000/1000)
Re: séquence des voyelles
Bon programme Nabil.
manianis- Nombre Réel
-
Nombre de messages : 975
Localisation : Tunisie
Réputation : 4
Points : 6015
Date d'inscription : 11/10/2007
Feuille de personnage
Capacité linguistique:
(999/1000)
Re: séquence des voyelles
- 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- Nombre Réel
-
Nombre de messages : 730
Age : 38
Localisation : tunisie
Réputation : 5
Points : 6082
Date d'inscription : 11/11/2007
Feuille de personnage
Capacité linguistique:
(995/1000)
Re: séquence des voyelles
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.
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 de messages : 975
Localisation : Tunisie
Réputation : 4
Points : 6015
Date d'inscription : 11/10/2007
Feuille de personnage
Capacité linguistique:
(999/1000)
Re: séquence des voyelles
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- Admin
-
Nombre de messages : 2934
Localisation : Tunisie
Réputation : 122
Points : 7632
Date d'inscription : 19/03/2007
Feuille de personnage
Capacité linguistique:
(999/1000)
Re: séquence des voyelles
on n'a souvent parlé de complexité dans notre forum
alors, quelle est la complexité du programme proposé par NabiL ?
alors, quelle est la complexité du programme proposé par NabiL ?
informix- Nombre Rationnel
- Nombre de messages : 399
Réputation : 4
Points : 6286
Date d'inscription : 19/03/2007
Feuille de personnage
Capacité linguistique:
(1000/1000)
Re: séquence des voyelles
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 de messages : 975
Localisation : Tunisie
Réputation : 4
Points : 6015
Date d'inscription : 11/10/2007
Feuille de personnage
Capacité linguistique:
(999/1000)
Re: séquence des voyelles
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"
NB: O(n) ne veut pas dire "n"
Napoléon- Admin
-
Nombre de messages : 2934
Localisation : Tunisie
Réputation : 122
Points : 7632
Date d'inscription : 19/03/2007
Feuille de personnage
Capacité linguistique:
(999/1000)
Re: séquence des voyelles
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 de messages : 975
Localisation : Tunisie
Réputation : 4
Points : 6015
Date d'inscription : 11/10/2007
Feuille de personnage
Capacité linguistique:
(999/1000)
Re: séquence des voyelles
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.
O(n^k) => Complexité polynomiale de degré k.
Napoléon- Admin
-
Nombre de messages : 2934
Localisation : Tunisie
Réputation : 122
Points : 7632
Date d'inscription : 19/03/2007
Feuille de personnage
Capacité linguistique:
(999/1000)
Re: séquence des voyelles
- 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 de messages : 975
Localisation : Tunisie
Réputation : 4
Points : 6015
Date d'inscription : 11/10/2007
Feuille de personnage
Capacité linguistique:
(999/1000)
Re: séquence des voyelles
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.
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- Admin
-
Nombre de messages : 2934
Localisation : Tunisie
Réputation : 122
Points : 7632
Date d'inscription : 19/03/2007
Feuille de personnage
Capacité linguistique:
(999/1000)
Forum INFOMATH :: Enseignement de l'informatique :: INFO - Supérieur (Etudiants et Professionnels) :: C/C++
Page 1 sur 1
Permission de ce forum:
Vous ne pouvez pas répondre aux sujets dans ce forum
|
|