Discussion :

[narcis60floyjo]

Bonjour,
je suis tout nouveau sur le forum et aussi en programmation en C++.
Alors voilà, je vous expose mon probleme (peut-etre tout bete pour certains).
Il faut que j'écrive un programme permettant d'afficher la suite de syracuse, à partir d'un nombre entré, de maniere récursive et itérative.

Suite de syracuse :

si n est pair -> U(n+1) = Un/2
si n est impair -> U(n+1) = 3*Un + 1

J'ai commencé à faire le programme de maniere recursive avec dev-cpp. Le voilà !

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
 
#include <iostream>
using namespace std;
 
 
int syrac (int n, int r)
{
      if (n%2==0)
      {
	r=n/2;
      }
	else
            {             
		r=3*n+1;
            }
 
    return r;
}
 
int main ()
{
    int n;
    int r;
 
 
    cout << "Entrez un entier positif : " << endl;
    cin >> n;
 
    r = syrac (n,r);
    cout << "vol " << n << " -> " << n << " " << r << " " << endl;
 
 
    system("PAUSE");
    return 0;
}

J'aimerais savoir ce qu'il manque pour que ca affiche toute la suite car là je n'obtiens que le premier résultat.
Merci de m'aider.

[Kujara]

J'aimerais savoir ce qu'il manque

Une boucle ?

[narcis60floyjo]

Récursivité = PAS DE BOUCLE
Je ne me trompe pas ?

Donc merci de corriger mon programme.

[Alp]

Pour obtenir de la récursivité, il faut une fonction récursive.
Une fonction récursive est une fonction qui s'appelle elle-même.
Là tu vas dire : oui mais ça s'arrête quand ?
La réponse est : justement, tu dois décider de quand l'arrêter. Par exemple :
si le rang est p, on ne calcule plus les termes suvants.

[narcis60floyjo]

Je suis d'accord avec ça. Mais je ne vois pas comment faire sans boucle en fait.

[Alp]

Je ne vais pas t'écrire le code, mais ça donne quelque chose comme :

Code :

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

1
2
3
4
5
6
7
8
9
10
int syracuse(int n,/* autre chose ? */ int dernier_rang)
{
if(n==dernier_rang)
{
// ici c'est fini
}
else {
// on affiche le valeur de la suite au rang n, puis on invoque syracuse(n+1, /* autre chose ? */ dernier_rang)
}
}

[darrylsite]

Code :

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

1
2
3
4
5
6
7
8
9
10
int syriac(int n)
 {
   if (n=0) 
    return 0; //valeur de u(0)
     else
       if (n%2==0) 
         return syriac(n-1)/2;
          else 
           return 3*syriac(n-1)+1;
 }

[millie]

Juste pour indiquer. On ne sait pas encore prouvé que cet algorithme termine... Ce qui fait qu'il est fort possible que ta pile d'appel explose, donc il vaut mieux utiliser une version non récursive

[coyotte507]

Juste pour indiquer. On ne sait pas encore prouvé que cet algorithme termine...

Quand tu dis "on ne sait pas encore prouver qu'il se termine", tu sous-entends qu'il se termine quand même?

Dans ce cas on peut utiliser la version récursive

[millie]

Pour être plus clair. On a pas démontré que cette fonction étant mathématiquement définie.

Je dis juste qu'il y a certaine valeur (avec un paramètre inférieur à 20.000 par exemple) qui font énormement monter le nombre d'appel.

De toute façon, le paramètre est un int (ce qui est loin d'être les entiers naturels), la fonction fonctionne correctement pour un ensemble restreint d'int (ceux qui ne font pas d'overflow)

Mathématiquement parlant (sans considération sur les overflow), l'algorithme termine si n appartient à [1, 2^64]

[aoyou]

Même si on tourne autour du sujet, je crois que personne n'a encore répondu à la question initiale

Il faut que j'écrive un programme permettant d'afficher la suite de syracuse, à partir d'un nombre entré, de maniere récursive et itérative.

Suite de syracuse :
si n est pair -> U(n+1) = Un/2
si n est impair -> U(n+1) = 3*Un + 1

Il faut afficher le n-ième élément de la suite, donc la taille de la pile est maîtrisée puisqu'on ne fera qu'au maximum n appels.
On ne parle pas de la conjecture de Syracuse dont le nombre d'appels récursifs est effectivement inconnu, dont l'algorithme termine mais on ne l'a toujours pas prouvé.

On parle ici de la suite de Syracuse et on veut avoir son n-ième élément. Cette suite a pour particularité d'être de période 3 à partir d'un certain rang (séquence 4, 2, 1).

narcis60floyjo, pour ce qui est du récursif, tu dois donc coder une fonction de la forme

Code :

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

1
2
3
4
5
6
7
8
9
10
 
// Renvoie le n-ième élément de la suite de Syracuse initialisée avec u
int syracuse (int u, int n) {
 if (...) { // condition de fin de la récursion
    ... // renvoie le n-ième élément de la suite
 } else if (u % 2 == 0) {
    ... // ce qui va bien
 } else {
    ...
 }

Tu initialises cette fonction avec un u0 que tu auras demandé à l'utilisateur.

Au passage, la condition est si un est pair (et non n est pair).
Cette suite ne donne pas grand chose.

[koala01]

Salut,

Le problème des fonctions récursives, c'est qu'il faut trouver ce que l'on appelle le "cas de base".

Il s'agit en fait du cas qui forcera la fonction à renvoyer une valeur (ou à arreter l'exécution).

Ce "cas de base" est la première chose qu'il faille tester, et il faut "engager" la récursivité s'il n'est pas vérifié.

En plus, ce que millie a expliqué est tout à fait vrai: avec un nombre donné d'appel, on risque fort d'obtenir un "stack overflow": un dépassement de capacité de la pile d'appels.

Dans le cas qui t'intéresse, le "cas de base" est, tout simplement, 1... car si tu cherche la suite de cyracuse de 1, tu n'obtiendra que cette valeur

Le code pour l'implémenter sera donc, tout simplement

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
 
/* Fonction récursive affichant la liste de cyracuse
 * @in: nombre entier non signé (je crais que cela ne fonctionne pas avec
 *      les entiers signés)
 * @out: rien
 */
void cyracuse (size_t ind)
{   /* on affiche ind, car ce doit toujours etre fait
     */
 
    cout<<ind<<" ";
    /* comme il n'y a plus rien à faire si le cas de base est vérifié,
     * contentons-nous de vérifier s'il ne l'est pas :D
     */
    if(ind!=1)
    {
        /* si le cas de base n'est pas vérifié, il faut :
         * -Appeler la fonction avec la moitié de la valeur si ind est pair
         * -multiplier ind par trois et ajouter 1 avant d'appeler la fonction
         * si ind est impaire
         */
        if(ind%2==0)
        {
             ind/=2;
        }
        else
        {
            ind=ind*3+1;
        }
        cyracuse(ind);
    }
}

@millie: Le risque principal ne repose pas sur le dépassement de pile, mais bien sur le dépassement de valeur pour un entier non signé...

Ainsi, sur mon antique Athlon 170XP, ou UINT_MAX est déclaré à 0xFFFFFFFF entre 1 et 300 000 (désolé, je n'ai pas eu le courage de tester au delà de 300 000 ), il y a quelques valeurs qui doivent être évitées pour éviter de dépasser cette valeur, et donc fausser les résultats:

• 159 487
• 212 649
• 239 231
• 270 271
• 288 615

et la probabilité de tomber sur une valeur qui menera à dépasser UINT_MAX augmente bien évidemment avec l'augmentation de la valeur à tester

Quoi qu'il en soit, le dépassement de valeur joue justement en notre faveur pour éviter le "stack overflow"
En simple boucle iterative, cela prendrait sans doute la forme de

Code :

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

1
2
3
4
5
6
7
8
9
10
11
void cyracuseiter(size_t ind)
{
    do
    {
        cout<<ind<<" ";
        if(ind%2==0)
            ind/=2;
        else
            ind=ind*3+1;
    }while(ind!=1);
}

Cela évitera surement le risque de dépassement de pile, mais ne résoudra de toutes façons pas le problème que certaines valeurs vont vouloir dépasser UINT_MAX lors de la multiplication par 3

[millie]

@millie: Le risque principal ne repose pas sur le dépassement de pile, mais bien sur le dépassement de valeur pour un entier non signé...

Oui, j'avais effectivement précisé :

De toute façon, le paramètre est un int (ce qui est loin d'être les entiers naturels), la fonction fonctionne correctement pour un ensemble restreint d'int (ceux qui ne font pas d'overflow)

Mais c'est vrai que c'était un peu caché par le brouillard de mes réponses

[koala01]

En fait, j'avais très mal interprété ton intervention

Je l'avais comprise comme une mise en garde sur le risque de "stack overflow" sur les appels récursifs.

Bien que le danger soit effectivement présent, si l'on prend cette remarque trop au sérieux, on en viendrait presque à éviter un code du genre de

Code :

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Node
{
    public:
        Node(/*...*/){}
        virtual ~Node();
        /*...*/
    private:
        std::vector<Node*> tab;
}
Node::~Node()
{
    for(size_t i=0;i<tab.size();i++)
        delete tab[i];
}

car l'instruction delete tab[i] n'est jamais qu'un appel récursif qui ne se montre pas, alors que l'on ne peut malheureusement pas faire autrement

[JolyLoic]

J'ai eu des cas où ce genre d'appel faisait sauter la pile, et où il a fallu le réécrire autrement (généralement avec un pile dynamique gérée par un std::stack).

[Jean-Marc.Bourguet]

J'ai eu des cas où ce genre d'appel faisait sauter la pile, et où il a fallu le réécrire autrement (généralement avec un pile dynamique gérée par un std::stack).

Le problème ici est tel qu'une version itérative est possible. Pour ceux que ça intéresse, afficher en binaire est quelque chose à faire.

[koala01]

Le problème ici est tel qu'une version itérative est possible. (snip)

As tu remarqué que j'ai aussi fournis un code de fonction itérative au passage

Mais sinon, de fait, il est important de rappeler que, s'il est possible de créer une fonction sous forme de boucle, il est souvent bien préférable de préférer cette version à une version récursive

[narcis60floyjo]

Je trouve que vous vous égarez parfois du problème initial.
Quoiqu'il en soit, j'ai fini par abandonner la manière récursive pour l'instant (je la ferai plus tard).
J'ai tenté la manière itérative pour la suite de Syracuse. Voilà mon code. Il marche.

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
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
#include <iostream>
using namespace std;
 
int p (int n, int j)
{
	j=n/2;
	return j;
}
 
int i (int n, int j)
{
	j=3*n+1;
	return j;
}
 
bool r (int n, int j)
{
	j=n%2;
	if (j==0)
	{
		return true;
	}
	else 
	{
		return false;
	}
}
 
 
void syrac (int n, int j) 
{
	bool k;
 
 
	while (n!=1)
	{
 
	k=r(n,j);
	cout << n << " ";
		if (k==true)
			n=p(n,j);
		else
			n=i(n,j);
 
	}
 
 
}
 
int main ()
{
	int n;
	int j;
 
 
	cout << "Entrez un entier positif : " << endl;
	cin >> n;
	cout << "Vol" << n << " -> ";
	syrac(n,j);
	cout << "1" << endl;
 
	system("PAUSE");
	return 0;
}

Donc avec ce code, j'affiche les termes de la suite en fonction du nombre entré.
La question suivante que je veux résoudre est :
"Quel code dois-je mettre pour que le programme me calcule la durée de la suite, c'est-à-dire le nombre de fois qu'on a dû calculer les termes suivants ?"

Je ne sais pas si vous comprenez ma questin. En gros, on aimerait connaitre le nombre de termes de la suite sans compter le nombre entré.

Merci de m'aider.

[aoyou]

Je ne comprends pas ton "sans compter le nombre entré" mais tu veux le temps de vol ?
Eh ben, tu rajoutes un compteur dans ta fonction syrac. A chaque passage dans la boucle while, tu incrémentes ce compteur. Quand n sera égal à 1, ton compteur (si tu l'as bien initialisé), te donnera le temps de vol. Ensuite tu peux même t'arranger pour que ta fonction renvoie cette valeur. Ca ne parait pas très compliqué...

Je trouve tes fonctions i, p et r plutôt inutiles mais c'est toi qui voit. Tu pourrais condenser ton code sans nuire à sa lisibilité.

[narcis60floyjo]

Oui ça je le sais déjà. Mais le compteur, comment l'initialise-t-on ?

(cpt = 0 ; cpt<n ; cpt++)

Comme ça ?