Problème de condition dans une fonction récursive

Version imprimable

Bonjour a tous,

j'ai un petit problème de test conditionnel dans une fonction récursive et je comprends pas pourquoi ... oui je débute le C++ ;)
si quelqu'un peux m'aider a voir ou je me plante dans ma logique ou dans mon code.

Code:

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
 
#include <iostream>
#include <ostream>
#include <string>
 
using namespace std;
 
void transform(string x);
int main(){
	string word = "voyage";
	transform(word);
	system ("PAUSE");
	return 0;
}
 
void transform(string x){
	string a = "a";
	string o = "o";
	string i = "i";
	string e = "e";
	string u = "u";
	string y = "y";
	string ob = "ob";
	if(x != ""){
		string element = x.substr(0,1);
		string reste = x.substr(1);
		if(element != a || element != o || element != i || element != e || element != u || element != y ){
			cout << element << " pas une voyelle " << endl;
			transform(reste);
		}
		else {
			cout << element << " est une voyelle" << endl;
			transform(reste);
		}
	}
 
 
}

Merci

13/07/2012, 16h42
Bousk

Bonjour,

le problème c'est que pour vérifier qu'une lettre ne soit pas une voyelle, elle doit être différente de chaque voyelle.
lettre != a ET != e ET ...

EDIT : Ha bah Bousk t'as maché le travail :p

Salut et bienvenu dans le monde du C++ et de la programmation ;)

Code:

if(element != a || element != o

Si la lettre courant n'est pas un a ou n'est un o ou ... alors c'est pas une voyelle.

Mais si c'est un a et pas un o, c'est vrai ! Vu que a != o. Du coup tu rentres dedans.

Je vais te laisser réfléchir à la condition, par contre ton code n'est pas bon en plusieurs points pour du C++. Je vais te le ré-écrire sans corriger la condition et mettre en rouge ce à quoi tu dois veiller :
Code:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 void transform(const string &x){ // On passe par référence car on ne veut pas copier l'objet. Et par const référence car on ne le modifie pas. string a = "a"; string o = "o"; string i = "i"; string e = "e"; string u = "u"; string y = "y"; string ob = "ob"; // Inutile et utilise de la mémoire (surtout que c'est récursif !). if(!x.empty()){ // Utiliser cette fonction rend le code plus clair car plus "textuel". string element = x.substr(0,1); // copie inutile string reste = x.substr(1); if( x[0] !='a' ||....){ cout << x[0] << " pas une voyelle " << endl; } else { cout << x[0] << " est une voyelle" << endl; } transform(x.substr(1)); // on gagne une ligne et de la clarté. En plus le fait de transformer la suite ne dépend pas du if. } }
Le gros problème du code est maintenant le x.substr(1), tu fais une copie de toute ta chaine à chaque appel, ce qui n'est pas performant du tout. Le mieux serait de passer en paramètre l'indice courant de la chaine. Donc tu commences par transform(0);. Et en défi, tu pourrais essayer avec les itérateurs ;)

Sinon je suppose que c'est un exo imposé en récursif mais c'est bien plus performant en itératif, surtout que la récursivité n'apporte même pas de simplification ici.

BOn courage; )

14/07/2012, 01h20
meancat

Merci beaucoup Trademark et Bousk

Citation:

Sinon je suppose que c'est un exo imposé en récursif mais c'est bien plus performant en itératif, surtout que la récursivité n'apporte même pas de simplification ici.

Effectivement c'est bien un exo pris dans les cours de l'université de Stanford (cours CS106B) et l'exo en question est bien , bien plus compliqué en fait.
Je pense qu'en itératif le problème est très simple, mais j’essaie de me forcer a le faire en récursif car j'ai du mal avec la récursivitée :? :calim2:

exo:

Citation:

Problem 2: Obenglobish (Chapter 3, exercise 16, page 152)
Most people—at least those in English-speaking countries—have played the Pig Latin game at some
point in their lives. There are, however, other invented “languages” in which words are created using
some simple transformation of English. One such language is called Obenglobish, in which words are
created by adding the letters ob before the vowels (a, e, i, o, and u) in an English word. For example,
under this rule, the word english gets the letters ob added before the e and the i to form obenglobish,
which is how the language gets its name.
In official Obenglobish, the ob characters are added only before vowels that are pronounced, which
means that a word like game would become gobame rather than gobamobe because the final e is silent.
While it is impossible to implement this rule perfectly, you can do a pretty good job by adopting the
rule that the ob should be added before every vowel in the English word except
• Vowels that follow other vowels
• An e that occurs at the end of the word
- 2 -
Write a function obenglobish that takes an English word and returns its Obenglobish equivalent, using
the translation rule given above. For example, if you used your function with the main program
int main() {
while (true) {
string word = getLine("Enter a word: ");
if (word == "") break;
string trans = obenglobish(word);
cout << word << " -> " << trans << endl;
}
return 0;
}
you should be able to generate the following sample run:

http://img21.imageshack.us/img21/3027/stanford.png

Salut,

C'est bien de vouloir faire l'exercice étape par étape en le décomposant, continue comme ça. Même si tu as du mal avec les fonctions récursives, ce n'est pas en essayant de tout écrire en récursif que ça ira mieux (ou alors tu apprends un langage fonctionnel). Je pense que l'idée c'est d'abord de le faire en itératif et puis après tu pourras essayer de le transformer en récursif.

Ensuite pour l'algo, ce que je ferais, c'est utiliser une entête de fonction comme celle-ci :
Code:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 template<typename IteratorIn, typename Inserter> void obenglobish(IteratorIn begin, IteratorIn end, Inserter result) { for(; begin != end; ++begin) { result = *begin; } } // L'appel dans le main #include <string> #include <iterator> std::string result; std::string chaine = "english"; obenglobish(chaine.begin(), chaine.end(), std::back_inserter(result));
Ceci peut te paraître compliquer à première vue car il y a beaucoup de chose que tu ne connais pas. Néanmoins, je pense sincèrement qu'il faut s'attacher dès le départ à écrire ce genre de code pour ne pas tomber dans un code "C with class", c'est-à-dire du C juste amélioré.

Les iterator permettent juste de parcourir une séquence, la méthode begin renvoie le début et end un élément après la fin. Par conséquent, une fois qu'un iterator est égal à "chaine.end()", il ne faut pas regarder ce qu'il contient car, c'est fini ! Il n'y a pas d'élément à cette position.

Justement, tu peux lire des éléments grâce à l'opérateur '*' en faisant "*begin".

Ensuite j'utilise un back_inserter, c'est une fonction qui construit un itérateur un peu spécial qui te permet simplement d'insérer à la fin... Tu ajoutes ensuite simplement un élément à la fin en faiant "result = *begin;".

Ensuite tu as du remarquer cette ligne là qui fait peur :

Code:

template<typename IteratorIn, typename Inserter>

Elle permet simplement de "deviner" le type des arguments passé en paramètre sans se concentrer sur un spécifique. Ceci permet entre autre que ta fonction marche avec n'importe quelle type d'itérateur par exemple. Si tu décides de ne plus bosser avec std::string ta fonction n'aura pas besoin d'être changé.

Ça fait probablement beaucoup d'un coup donc concentre toi sur la fonction et tu peux y arriver grâce à ses opérations de bases :

++begin : avancer de 1 élément (comme faire ++i)
*begin : prendre l'élément que contient l'itérateur, comme faire tableau[i]
result = *begin; (ou encore result = 'a') Insérer un élément à l'arrière de result.

Finalement, pour l'algo, par étape de construction :

Détecte les voyelles.
Quand tu détectes une voyelle, insère o et b devant.
Quand tu détectes une voyelle, vérifie qu'il n'y en a déjà pas eu une avant.
Quand tu détectes un 'e', vérifie qu'il n'est pas à la fin du mot.

Bonne chance ;)

Merci a toi encore ;)
j'ai fini par faire le prog en itératif et en récursif

Code:

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
39
40
 
#include <list>
using namespace std; 
 
template<typename IteratorIn>
string obenglobish(IteratorIn begin, IteratorIn end)
{
	int size = chaine.length();
	string temp = "";
	int countV = 0;
   for(; begin != end; ++begin){
	   if ( *begin == 'a' || *begin == 'e' || *begin == 'i' || *begin == 'o' || *begin == 'u' || *begin == 'y' ){
		   countV++;
			if ( countV == 1 && chaine[size] != 'e'){
				char tmp = *begin;
				temp.append("ob");
				temp.append(1,tmp);
			}else{
				char tmp = *begin;
				temp.append(1,tmp);
			}
		}else{
			countV = 0;
			char tmp = *begin;
			temp.append(1,tmp);
	   }
   }
   return temp ;
}
 
 
string chaine = "voyage";
 
 
 
int main(){
	std::cout << obenglobish(chaine.begin(), chaine.end()) << endl;
	system("PAUSE");
	return 0;
}

tu remarquera que je passe pas par ta fonction back_inserter() qui correspond pas a mon souci et front_inserter() qui lui m'aurai aidé, plante quand il veux insérer une string devant un char , donc j'ai contourné le problème.
ceci dit je pense que je vais être fan des templates ^^

Code:

1 2 3 4 5 6 7 8 if ( countV == 1 && chaine[size] != 'e'){ char tmp = *begin; temp.append("ob"); temp.append(1,tmp); }else{ char tmp = *begin; temp.append(1,tmp); }
Avec l'inserter :
Code:

1 2 3 if ( countV == 1 && chaine[size] != 'e') inserter = "ob"; inserter = *begin;
A part ça, ton code ne me semble pas correct, vérifie avec d'autres données. Le fait d'insérer ob seulement lorsqu'un e n'est pas à la fin devrait te donner un indice.