algorithme récursive Fermé

Question

Bonjour,
j'ai un petit un probleme en algo, quelqu'un peut m'aider a faire une fonction récursive qui permet d'enlever la premiere occurence d'une chaine de caractere?

salhi · Answer

bonjour,
enlever la première occurence de la chaine dans quoi? pouvez vous donner un exemple explicatif

cil · Answer

merci pour la réponse rapide  par exemple en un une chaine de caractere  X et un caractere c donc enlever la premiere occurence de c dans la chaine et si il existe pas et ba en renvoie la chaine X

par exemple chaine  de caractere("2 3 3 4 5"  3) la fonction ne donne "2 3 4 5"
un autre exemple ( "A B G C A"  'A')  nous donne ("B G C A")

cil · Answer

en faite j'ai pensé a faire
 si x[1]= c ALORS je renvoie la chaine X- X[1] 
SINO JE renvoyer fonction au deuxieme element de la chaine X  et en garde le premier element tester de la chaine
mais je ne suis pas sure

salhi · Answer

votre proposition sera correcte en utilisant une fonction récursive mais en ajoutant juste une condition d'arret:
appel: f(x,1)
corps:
f(x:chaine,i:entier):chaine
Si(i>long(x))alors
retourner(x)
sinon
  si x[i]=c alors retourner (x-x[i])
  sinon retourner f(x,i+1)
  Finsi
Finsi

et voici un programme solution en pascal si c'est le langage désiré:
program test;
uses wincrt;
var
ch:string;
c:char;
function supp_occ(ch:string; c:char;i:byte):string;
begin
 if (i>length(ch))then
   supp_occ := ch
 else
 begin
   if (ch[i]=c)then
   begin
      delete(ch,i,1);
      supp_occ := ch
   end
   else
      supp_occ:= supp_occ(ch,c,i+1);
 end;
end;

BEGIN
writeln('saisir la chaine:');
readln(ch);
writeln('saisir le caractère:');
readln(c);
Writeln('Le résultat est:',supp_occ(ch,c,1));
end.

j'éspère que votre problème est maintenant résolu?

cil · Answer

merci bcp
 c'est ça

maymo · Answer

bonsoit, qui peut m'aider a resoudre cet exercice:
Analyser une fonction récursive booléenne qui détermine si une chaîne de caractères CH comporte plus de caractères C1 que de caractères C2. (Cette fonction retourne VRAI si le nombre de C1 est supérieur à celui de C2 dans la chaîne).merci d'avance.

salhi · Answer

bonsoir,

fonction tester(ch:chaine; c1,c2:caractere;  nc1,nc2,i:entier):booleen
Si(i>long(ch)) alors
  retourner(nc1>nc2)
Sinon
 si (ch[i]=c1) alors   retourner tester(ch,c1,c2,nc1+1,nc2,i+1)   finsi
 si (ch[i]=c2) alors   retourner tester(ch,c1,c2,nc1,nc2+1,i+1)   finsi
 
Finsi
Fin tester


l'appel dans le programme pincipale doit être: b<-- tester(ch,c1,c2,0,0,1)

salhi · Answer

pardon, la fonction une condition:

...
sinon
 si(ch[i]=c1) alors retourner .....
 sinon si (ch(i]=c2) alors retourner ......
          sinon retourner tester (ch,c1,c2,nc1,nc2,i+1)
 finsi

maymo · Answer

merci bien  pour la correction.j'ai un autre exercice qui me semble difficile, c'est le suivant:
soit la procedure iteratif suivante:
procedure compter;
var i:integer;
begin
s:=0;
for i:=1 to n do
s:=s+sqr(i);
end;
transformer cette procedure en une procedure recursive qui admet  un parametre?

salhi · Answer

procedure compter(i:integer);
begin
if(i>n)
s:=0
else
s:=sqr(i)+compter(i+1)
end;

l'initialisation s:=0; doit être faite en dehors de la procédure

maymo · Answer

bonsoir, je crois que votre solution n'est pas correcte car on peut pas ecrire sqr(i)+compter(i+1)( compter n'est pas une fonction!!!)

salhi · Answer

bonsoir,
oui, vous avez raison, j'ai pas fais attention.
donc:
procedure compter(i:integer); 
begin 
if(i>n) 
s:=0 
else 
begin
compter(i+1) ;
s:=sqr(i)+s;
end;
end; 

c'est ça, non?

salhi · Answer

plus tôt: s:=sqr(i)+s; puis compter(i+1);

maymo · Answer

bonsoir,la solution n'est pas correcte dans les deux cas ou vous appelez la procedure avec  1 ou n parceque dans le cas d'une procedure la valeur de la variable locale ne passe pas  a l'appel precedent , si vous testez le programme ca marche pas,

salhi · Answer

bonsoir mon ami,
je ne sais pas de quelle variable locale vous parlez, il n'y a acune variable locale utilisée car lorsque il s'agit de récursivité on déclare pas des variables à l'interieur. sauf la condition if i>n then s:=0 ici est faite lorsque j'ai envoyé la première solution dont j'ai pris compter comme fonction et non pas procédure.
testez le programme suivant et vous allez être sûr que j'ai raison:
-----------------------

program exemple;
uses wincrt; 
var
s:integer;
n:integer;


procedure compter(i:integer);
begin 
if(i<n)then
begin
  s:=sqr(i)+s;
  compter(i+1);
end; 
end;

begin
s:=0;
write('n=');
readln(n);
compter(1);
writeln('le resultat est:',s);
writeln('alors, c'est correct maintenant ?');
end.

maymo · Answer

merci bien , la solution est correcte ,seulement il fau changer if i<=n .mais avec votre solution, ca devient floue dans ma tête a propos de la récursivité, j'ai crus que compter(3) ne peut pas utiliser la valeur de s trouver dans compter (2) qui ne peut pas utiliser s trouver  dans compter(1) , est ce que vous avez compris?????? si vous pouvez m'expliquer le principe,merci d'avance.

salhi · Answer

bonsoir,
la variable s dans le programme est une variable globale, c.a.d qu'elle est connue à tout endroit du programme donc à chaque appel de la procedure compter on va utiliser la valeur courante de s. Plus précisement, on a un seul objet nommé s pour tout le programme, après appel par exemple de compter(2) le cotenu de la variable s est modifié, donc qu'elle est la valeur de s qui va être utilisée dans compter(3)???
c'est certainement la dernière valeur trouvée.
cela est équivalent au cas où s est passée en paramètre mais un passage par variable: compter(i:integer; var s:integer);
j'espère que vous arrivez à me comprendre.
question: êtes vous en bac info?
bonne chance......

maymo · Answer

merci pour l'explication, je suis bien en bac info et vous , je vous souhaite bonne annee pleine de succes.

Algorithme récursive

18 réponses

Discussions similaires