Discussion :

[blackbird1]

bonjour,
j'ai un pb avec ce code, qui calcule le nombre d'occurence d'un caractère dans une chaîne de manière récursive.

pb n1 :
quand je donne la chaine "azza" et le caractère "a" il affiche 1 par contre quand je donne "z" il affiche2.

pb n2 :
quand je donne une longue chaine il génère un 202 runtime error

merci d'avance

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
26
27
28
29
30
31
32
33
34
35
36
37
38
 
uses wincrt;
var Phrase : string;
    Car : char;
    NbreOcc : byte;
 
procedure Occurence(Ph:string;C:char;var Nbre:byte) ;
var 
    SPh : string;
begin
if (length(Ph) = 0) then
     Nbre:=0;
 
SPh:=copy(Ph,1,1);
delete(Ph,1,1);
 
 
if(length(Ph) >0) then
   begin
   if (C = SPh[1]) then
       Nbre := Nbre + 1;
   Occurence(Ph,C,Nbre);
   end;
 
end;
 
 
 
 
begin
NbreOcc:=0;
writeln('Saisir une phrase :');
readln(Phrase);
writeln('Saisir un caractère :');
readln(Car);
Occurence(Phrase,Car,NbreOcc);
writeln('l''occurence de la lettre <<',Car,'>> = ',NbreOcc);
end.

[diden138]

et ça ?

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
26
27
28
29
30
31
32
33
34
 
uses wincrt;
var Phrase : string[256];
    Car : char;
    NbreOcc : byte;
 
procedure Occurence(Ph:string[256];C:char;var Nbre:byte) ;
var 
    SPh : string[256];
begin
if (length(Ph) = 0) then
     Nbre:=0;
 
SPh:=copy(Ph,1,1);
delete(Ph,1,1);
if(length(Ph) >0) then
   begin
   if (SPh[1]=C) then
       Nbre := Nbre + 1;
   Occurence(Ph,C,Nbre);
   end
else
 if (SPh[1]=C) then Nbre:=1;
 
end;
begin
NbreOcc:=0;
writeln('Saisir une phrase :');
readln(Phrase);
writeln('Saisir un caractère :');
readln(Car);
Occurence(Phrase,Car,NbreOcc);
writeln('l''occurence de la lettre <<',Car,'>> = ',NbreOcc);
end.

Dans ton exemple je tiens à signaler que le nombre d'occurence de a est de 2.
cordialement @+

[krachik]

et ça ?

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
26
27
28
29
30
31
32
33
34
 
uses wincrt;
var Phrase : string[256];
    Car : char;
    NbreOcc : byte;
 
procedure Occurence(Ph:string[256];C:char;var Nbre:byte) ;
var 
    SPh : string[256];
begin
if (length(Ph) = 0) then
     Nbre:=0;
 
SPh:=copy(Ph,1,1);
delete(Ph,1,1);
if(length(Ph) >0) then
   begin
   if (SPh[1]=C) then
       Nbre := Nbre + 1;
   Occurence(Ph,C,Nbre);
   end
else
 if (SPh[1]=C) then Nbre:=1;
 
end;
begin
NbreOcc:=0;
writeln('Saisir une phrase :');
readln(Phrase);
writeln('Saisir un caractère :');
readln(Car);
Occurence(Phrase,Car,NbreOcc);
writeln('l''occurence de la lettre <<',Car,'>> = ',NbreOcc);
end.

Dans ton exemple je tiens à signaler que le nombre d'occurence de a est de 2.
cordialement @+

Et bah pas mieux ,je dirai pire .

Code :

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

Phrase :string[256]

pourquoi 256? une chaine de caractere String a une longueur compris entre 1 et 255,en tout cas un compilateur Pascal Standart refusera cette declaration ;encore "String[255]" ça ira.Mais dans ce cas je te demanderai la difference entre un String et un String[255] .
@blackbird1
1)Il faut tout simplement revoir l'algorithme que tu utilises si ça marche des fois et d'autres fois non
2)C'est un debordement de la pile d'execution,ce qui arrive dans des cas d'utilisation de fonctions recursives mal gerées.Dans ton cas tu peux fixer la taille de ta chaine à 10 ou 15 par exemple .(String[10])

Et concernant ton code pour optimiser tout cas tu peux aussi traiter le cas ou la chaine entrée sera vide , En plus ça tu peux le faire de maniere tres simple au lieu d'utiliser une variable local passer ta chaine par reference :
Tester le premier caractere si c'est egale au caractere donné (si oui nboccurence++)
Supprimer le premier caractere, et apres faire de façon recursive ,
Je te laisse revoir ton algo (juste de petite modifications à faire) et apres on passera à Pascal
@+
[edit]Au passage l'indentation n'est pas encore ça [/edit]

[droggo]

Voe,

Je vais finir par établir un catalogue de tous les programmes du forum Pascal où l'utilisation de la récursivité est absurde.

[krachik]

Voe,

Je vais finir par établir un catalogue de tous les programmes du forum Pascal où l'utilisation de la récursivité est absurde.

Il y a en quand meme un tas
1)Saisir un entier
2)Somme de deux entiers
3)Inversion d'un tableau
4)Toutes les algo de tri y sont passés(shell,fusion,selection,etc)
5)Afficher des données
6)Creer un Fichier
7)Arrangement,Permutation
8)Somme des éléments d'une matrice
9)Traiment dans un tableau :Nombre d'occurences d'un element
10)Inversion d'une chaine
11)Element ième d'un tableau
12)..............

En tout cas je n'ai pas encore vu celui de la resolution d'un équation du second degré.Les boucles vont disparaitre (pauvre for )

En meme temps utilisation absurde pas tout à fait mais utilisation non adapté oui.
Bon soyons serieux
@+

[droggo]

Fie,

En meme temps utilisation absurde pas tout à fait mais utilisation non adapté oui.

Je maintiens le terme "absurde".

Il est absurde de vouloir utiliser la récursivité pour résoudre un problème dont l'algorithme immédiat, c'est à dire le premier auquel tout le monde pense, ou qui résulte directement de la définition, est itératif.

Dans le cas présent, il faut parcourir une chaîne pour faire des tests sur son contenu : la première idée venant à l'esprit est de faire une boucle sur les caractères de la chaîne.

Ceux que tu cites sont de la même espèce, sauf pour certains algorithmes de tri, pour lesquels la récursivité fait en quelque sorte partie de la définition (même si on peut toujours en faire une version itérative, plus ou moins facilement selon les cas).

[darrylsite]

Fie,

Je maintiens le terme "absurde".

Il est absurde de vouloir utiliser la récursivité pour résoudre un problème dont l'algorithme immédiat, c'est à dire le premier auquel tout le monde pense, ou qui résulte directement de la définition, est itératif.

Dans le cas présent, il faut parcourir une chaîne pour faire des tests sur son contenu : la première idée venant à l'esprit est de faire une boucle sur les caractères de la chaîne.

Ceux que tu cites sont de la même espèce, sauf pour certains algorithmes de tri, pour lesquels la récursivité fait en quelque sorte partie de la définition (même si on peut toujours en faire une version itérative, plus ou moins facilement selon les cas).

Je ne vois pas pourquoi vous en fait un probleme. C' est peut etre absurde comme tu le dis mais il faut savoir que les profs donnent ces genres d' exercices juste pour voir si l' eleve peut mettre en oeuvre la reccursivité. Vous serez bien d'accord avec moi que c' est pas du tout evident de passer du coup de la forme iterative (la seule que l' eleve connaisait) à la forme reccursive. Je comprend que les profs ne se demandent pas si la forme reccursive est utile mais si l' eleve à la capacité de le faire (histoire de s' habituer avec). mais c' est vraiment pour la comprehension de cette forme <barbare> (pour un debutant).

[darrylsite]

bonjour,
j'ai un pb avec ce code, qui calcule le nombre d'occurence d'un caractère dans une chaîne de manière récursive.

pb n1 :
quand je donne la chaine "azza" et le caractère "a" il affiche 1 par contre quand je donne "z" il affiche2.

pb n2 :
quand je donne une longue chaine il génère un 202 runtime error

merci d'avance

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
26
27
28
29
30
31
32
33
34
35
36
37
38
 
uses wincrt;
var Phrase : string;
    Car : char;
    NbreOcc : byte;
 
procedure Occurence(Ph:string;C:char;var Nbre:byte) ;
var 
    SPh : string;
begin
if (length(Ph) = 0) then
     Nbre:=0;
 
SPh:=copy(Ph,1,1);
delete(Ph,1,1);
 
 
if(length(Ph) >0) then
   begin
   if (C = SPh[1]) then
       Nbre := Nbre + 1;
   Occurence(Ph,C,Nbre);
   end;
 
end;
 
 
 
 
begin
NbreOcc:=0;
writeln('Saisir une phrase :');
readln(Phrase);
writeln('Saisir un caractère :');
readln(Car);
Occurence(Phrase,Car,NbreOcc);
writeln('l''occurence de la lettre <<',Car,'>> = ',NbreOcc);
end.

Le premier probleme vient de la condition :

if(length(Ph) >0) then
begin
if (C = SPh[1]) then
Nbre := Nbre + 1;
Occurence(Ph,C,Nbre);
end;

En effet pour la chaine azza, on a :
azza->1 (length(ph)=3 et ph="zza")
zza->0 (length(ph)=2 et ph="za")
za->0 (length(ph)=1 et ph="a"
a->0 (length(ph)=0 et ph="")

tu dois modifier la condition comme suit :

Code :

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

1
2
3
4
5
6
7
8
9
10
 
if(length(Ph) >=0) then
   begin
   if (C = SPh[1]) then
       Nbre := Nbre + 1;
 
 {modification ici}
   if (length(ph)<>0) then
      Occurence(Ph,C,Nbre);
   end;

[droggo]

Dio,

Je ne vois pas pourquoi vous en fait un probleme. C' est peut etre absurde comme tu le dis mais il faut savoir que les profs donnent ces genres d' exercices juste pour voir si l' eleve peut mettre en oeuvre la reccursivité. Vous serez bien d'accord avec moi que c' est pas du tout evident de passer du coup de la forme iterative (la seule que l' eleve connaisait) à la forme reccursive. Je comprend que les profs ne se demandent pas si la forme reccursive est utile mais si l' eleve à la capacité de le faire (histoire de s' habituer avec). mais c' est vraiment pour la comprehension de cette forme <barbare> (pour un debutant).

J'en fais un problème parce que ça donne de mauvaises habitudes aux élèves : ils ont tendance à vouloir mettre de la récursivité partout, y compris quand il n'y en a absolument pas besoin.

La récursivité est une belle chose conceptuelle, mais on n'a pas trouvé mieux pour consommer les ressources d'un ordinateur (puissance de calcul et mémoire).
Exemple parfait dans le cas présent, où très vite se produit un débordement de pile, même si on peut améliorer un peu.

Et pour expliquer ce qu'est la récursivité et la mettre en pratique, les exemples où elle est effectivement utile ne manquent pas. Alors pourquoi ne pas les utiliser ?

[Tuxico]

droggo:


Je suis d'accord avec ton point de vue mais pour bien maitriser les concepts de la récursivité,il faut commencer par les appliquer sur des exemples où l'itératif est plus efficace, les élèves maitrisent en général mieux ce type d'algo, commencer la récursivité en apprenant les arbres directement, par exemple, n'est pas très pédagogique.
D'un autre côté, il faut ensuite rajouter un cours de calcul sur O (performance d'algos) pour bien différencier quand la récursivité à sa place et quand elle ne l'a pas du tout Sinon en effet, ils appliqueraient la récursivité pour tout et n'importe quoi!

[diden138]

bonjour,
tous d'abord désolé pour le 256
bon je commence déjà par

pourquoi 256? une chaine de caractere String a une longueur compris entre 1 et 255

non de 0 à 255 ce qui fais 256 caractères (d'où mon 256 absurde).

difference entre un String et un String[255]

ben rien si on spécifie pas la taille ,la chaine prendra automatiquement la taille max(255) mais je me souviens que j'avais eu un problème (il y a longtemps) les caractères s'affichait bizarrement quand j'ai définit la taille le problème c'est résolu c'est tout.
aussi une chaine si elle dépasse 255 caractères elle est automatiquement tronquée.

J'en fait un problème parce que ça donne de mauvaises habitudes aux élèves : ils ont tendance à vouloir mettre de la récursivité partout, y compris quand il n'y en a absolument pas besoin.

si t'avais fais un peu de prolog tu serais le rôle de ce genre d'exercices
quand à ce post ce n'est pas un post pour "êtes vous ou non pour la récursivité"
quand à ton problème krachik je ne vois aucune solution si t'a chaine dépasse les 20 caractères ça plante en pascal.
les appels récursive sont très couteux car ça implique la sauvegarde de tous l'environnement de travail (pile(@de retour,cs,cd...)+le display(qui indique à chaque foie ou débute le programme d'exécution) ) donc une chaine de 20 caractères implique 20 appel récursives les 16ko de la pile(en pascal) ne suffisent plus.
voila sinon le code modifié que j'ai donné marche (en modifiant le 256 bien sur par 255)
sinon une autre solution est d'utiliser le readkey et de faire la récursivité sur .
cordialement @+

[krachik]

voila sinon le code modifié que j'ai donné marche (en modifiant le 256 bien sur par 255)

Alors vu que comme tu l'as dit qu'il y a aucune difference entre "String" et "String[255]" je ne vois pas pourquoi garder une telle declaration dans le code si ce n'est pas l'alourdir .
Aussi si tu penses qu'une chaine de 20caracteres vont faire un "Stack Over Flow" alors tu crois que c'est 255 caracteres ne vont pas le faire ?

quand à ce post ce n'est pas un post pour "êtes vous ou non pour la récursivité"

Qui a dit le contraire ?
Jusqu'a preuve du contraire ton code ne fonctionnera pas.

Code :

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

1
2
3
4
5
6
7
8
9
 
if(length(Ph) >0) then
   begin
   if (SPh[1]=C) then
       Nbre := Nbre + 1;
   Occurence(Ph,C,Nbre);
   end
else
 if (SPh[1]=C) then Nbre:=1;

Le "else" c'est a dire si "if(length(Ph) <0)" tu fais un test sur "SPh"?
Et l'autre solution que tu proposes avec le Readkey consisterait a lire le caractere à chercher avant de lire la chaine elle meme si j'ai compris.
@+

[droggo]

Fio,

si t'avais fais un peu de prolog tu serais le rôle de ce genre d'exercices

Il se trouve que j'en ai fait assez souvent, mais cela n'a rien à voir ici : nous parlons de Pascal (et des langages du même type, par extension).

[katrena99]

Dio,

J'en fais un problème parce que ça donne de mauvaises habitudes aux élèves : ils ont tendance à vouloir mettre de la récursivité partout, y compris quand il n'y en a absolument pas besoin.

En effet, tu te rappelles peut-être de la fois où je l'ai utilisée pour calculer la factorielle

[Tuxico]

bêtement pour revenir au sujet :

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
Program OccString;
 
Var
       Chaine : string;
       car : char;
       Occ,Ch : integer;
 
Begin
       Chaine := 'alala quelle histoire';
       car := 'a';
       Occ := 0;
       Ch := 1;
       while(Ch<=length(Chaine)) do 
       begin
              if(Chaine[Ch] = Car) then
                              occ := occ + 1;
              Ch := Ch + 1;
       end;
       write(Occ);
End.

[krachik]

Ok Tuxico
Tout le monde à compris que c'est rapide avec uen boucle seulement ce n'est pas ce qui à été demandé ,on pourrait aussi utiliser uen boucle "For" avec seulement quelque ligne de code
Aussi je ne vois aucun signe de l'auteur du post pour voir la ou il en est lui
@+

[Tuxico]

Niveau efficacité, la boucle for ne change rien vis-à-vis du while maintenant s'il préfère un "for", c'est pas bien compliqué à changer.

S'il veux un algo récursif, il faut qu'il cherche aussi un peu lui-même une récursion bien-fondée (qui elle non-plus n'est pas bien compliquée à trouver)

je donnais juste la version la plus logique

@+

[krachik]

D'accord avec toi mais il ne se manifeste pas .
Une avec une boucle "for" on lui laisse le soin de corriger son algo avant de lui donner ;même si darrylsite lui a dejà donné

Code :

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

1
2
3
4
5
6
7
8
9
10
11
 
   function nbOccurrences(String ch;Char car):byte;
   var nbOccur:byte; 
         tCh,i:byte;
   begin
        tCh:=length(ch);
        nbOccur:=0;
        for i:=1 to tch do
             if(ch[i]=car)  then inc(nbOccur);
        nbOccurrences:=nbOccur;
   end;

@+

[diden138]

krachik nous avons voulu te laisser réfléchir bien au problème mais bon
ce que je te propose c'est de faire la récursivité sur l'indice avec lequel tu parcoure ta chaine et non pas la chaine toute entière (ce qui est absurde) donc voila en gros ma solution

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
26
27
28
29
 
program incroyable;
var
    chaine     :string;
    car         :char;
    indice,
    nbr         :byte;
 
procedure occurence(chaine:string;car:char;var i:byte;var nbr:byte);
begin
  if (length(chaine)=0) then nbr:=0;
  while i<=length(chaine) do
     begin
       if (chaine[i]=car) then  nbr:=nbr+1;
       i:=i+1;{// on avance dans la chaine //}
       occurence(chaine,car,i,nbr);
     end;
end;
begin
 nbr    :=0;
 indice :=1;  
 writeln('entrez votre chaine');
 readln(chaine); 
 writeln('entrez votre caractère');
 readln(car);
 occurence(chaine,car,indice,nbr); 
 writeln(nbr);
 readln;
end.

sinon pour l'autre solution que je t'ai proposé c'est d'utiliser un readkey et de lire à chaque foie le caractère entré et tu vérifie à chaque foie si c'est le caractère recherché tu incrément et tu défini un caractère comme étant la fin de ta chaine (exemple '#' ) en gros ça donnerait ça

Code :

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

1
2
3
4
5
6
7
8
9
10
11
12
13
 
procedure occurence(car:char;var nbr:byte);
var
   c:char;
begin
        c:=readkey;
        write(c);{// c'est juste pour afficher les caractères entré par l'utilisateur pour qu'il voit ce qui tape//}
        if (c<>'#')   then
                          begin
                            if (c=car) then nbr:=nbr+1;
                            occurence(car,nbr);       
                          end;
end;

l'avantage de cette solution c'est que tu n'est pas limité à 255 caractères.
en espérant avoir mis fin à tes souffrance
cordialement @+

[krachik]

Merci c'est gentil de ta part de mettre fin à mes soufrances
Seulement ce Post n'est pas de moi et je crois que j'aurai trouvé une solution depuis si j'avais un genre d'exercice comme ça a faire .
Ah que vois-je?un nouveau code ,je parlais de ton premier code que tu as posté (je ne parle ps des "String[256]")
Est ce que ton premier code fait bien ce que dit l'exercice?
Merci pour le code mais ce qu'on essaie de faire comprend a l'auteur du post pourquoi son code ne marche pour qu'il le corrige lui meme
@+