Discussion :

[RobiwanKanab1s]

Bonjour à tous !
J'ai un exercice donné à mon cours d'algorithmique basé sur la récursivité. On me demande d'inverser les chiffres d'un nombre ( 1234 devient 4321). Je vois bien comment je dois le faire de manière itérative, mais je ne parviens vraiment pas à passer à une méthode récursive, j'ai beau essayer de jouer avec les modulos 10 et les divisions entière par 10, je n'arrive pas au bon résultat :/
J'ai essayé une ébauche de code, je comprends pourquoi ca ne fonctionne pas, mais je n'arrive pas à en venir au bout :/ Je n'ai trouvé nul part sur le net une solution avec un algorithme itératif :/

Mon code actuel :

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
#include<stdio.h>
#include<conio.h>
 
int Inversion(int);
 
int main(){
    int nbr, nbri;
 
    printf("Entrez un nombre a inverser : ");
    fflush(stdin);
    scanf("%d", &nbr);
 
    nbri=Inversion(nbr);
    printf("%d\t--->\t%d",nbr, nbri);
 
    getch();
 
    return 0;
}
 
int Inversion(int nb){
    int mod, div;
 
    mod=nb%10;
    div=nb/10;
 
    if(div!=0){
        return 10*Inversion(div)+mod;
    }else{
        return mod;
    }
}

Si vous avez une solution je suis preneur !
Merci d'avance

[Matt_Houston]

Tu peux par exemple permuter les premier et dernier chiffres puis appliquer à nouveau l'algorithme sur le nombre composé des chiffres qui se trouvent entre les deux ; ainsi de suite jusqu'à ce que le nombre en entrée soit composé de moins de deux chiffres (au « centre »).

[dalfab]

Bonjour,

Tu peux aussi : Pour afficher un nombre dans l'ordre inverse :
On commence par afficher la fin du nombre.
Puis s'il reste quelque chose à afficher (condition facile à trouver) on affiche la suite (ce qui revient à appeler récursivement sur ce qui reste du nombre)

[RobiwanKanab1s]

Le problème est que je ne dois pas juste l'afficher, il doit se retrouver dans un autre entier.
Intervertir les premier et derniers nombres pourrait etre une bonne idée, mais je ne vois pas comment je pourrais aller chercher ce premier chiffre, le nombre etant de longueur quelconque :/

[edgarjacobs]

Hello,

Si tu as droit à tous les outils (pas comme dans certaines écoles), il y a une méthode très simple: tu fais un sprintf() du nombre dans une variable char[ ], tu inverses la variable char[ ], et tu récupères la solution par un atol() ( ou atoi() ). That's all, folk.

[RobiwanKanab1s]

En fait ce qui est frustrant c'est que j'ai changé d'ecole et je connaitrais plein de moyen de le faire :p
Mais dans mon contexte, on a pratiquement que les outils de bases ( operations arithmetiques, modulo), le but étant de faire un algorithme très général et de le faire en une seule fonction
Comme je n'utilise qu'une seule fonction qui prend en argument l'entier à inverser, le mettre dans un char[] me parait compliquer a cause de la recursivité ( ce qui reviendrait a chaque fois a le transformé en char[] )

J'avais deja vu pas mal d'algorithme permettant de regler ce problème en n'utilisant que des addition multiplication, division et modulo mais de manière itérative. Théoriquement il devrait y avoir moyen de faire pareil de manière récursive mais apres plusieurs heures de reflexion je n'y parvient toujours pas :/ Mais merci quand meme

[foetus]

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
#include <stdio.h>
#include <stdlib.h>
 
 
void reverse_integer01(int val, int* result, int* multiplier) {
    if (val > 9) {
        char digit = (val % 10);
 
        reverse_integer01((val / 10), result, multiplier);
        (*multiplier) *= 10;
 
        (*result) = ((digit * (*multiplier)) + (*result));
    } else {
        (*result)     = val;
        (*multiplier) = 1;
    }
}
 
 
void reverse_integer(int val, int* result) {
    if (result != NULL) {
        int multiplier;
 
        (*result) = 0;
 
        reverse_integer01(val, result, &multiplier);
    }
}
 
 
int main(int argc, char** argv)
{
    int result;
 
    for(int val = 0; val < 1001; ++val) {
        reverse_integer(val, &result);
 
        printf("%d -> %d\n", val, result);
    }
 
    return 0;
}

[Matt_Houston]

Tu ne peux effectivement pas faire l'économie de « compter les chiffres » ici. Soit via une boucle en amont, soit en ajoutant un élément de contexte à l'appel récursif comme l'a fait foetus, ou comme on le fait ci-après :

Code :

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

1
2
3
4
5
6
7
unsigned int rev_(unsigned int i, unsigned int r, unsigned int base) {
    if (i == 0)
        return r; // stop
    return rev_(i / base, r * base + i % base, base);
}
 
#define rev(i, base) rev_(i, 0, base)

C'est un exemple de cas où l'algorithme récursif est moins élégant.

[RobiwanKanab1s]

Oui je vois donc ici on serait effectivement obligé de passer par d'autres variable qu'on devra fournir en entrée
C'est peut être un peu moins élégant pour l'appel de la fonction dans le main comme on doit lui fournir ses variables, mais dans ce cas la on pourrait tout simplement passer par une fonction intermediaire qui s'en chargerait :p
Merci beaucoup de votre aide !

[Matt_Houston]

Oui dans mon exemple c'est le rôle de la macro, qu'on pourrait éventuellement remplacer par une fonction inline.

[charlonien]

Salut, je suis tombé sur le même genre d'exercice et en quelques boucle on peut tout a fait le faire.

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
/*==================[  RENVERSER ENTIER  ]====================*/
/*
	DESCRIPTION :		Renverse les digits d'uen entier donné
 
	PARAMETRES :		Un entier quelconque
 
	RETOURNE :		Un entier constitué des digits renversé.
 
	SPÉCIFICATIONS :	Les valeurs négatives sont prises en cpmpte par
				leurs valeurs absolues.
*/
int reverse_digit(int n);
/*====================================================================*/
 
 
/*====================================================================*/
/*
	STRATÉGIE:	Cas particulier de 0 (11)
			On commence par retirer les zero en derniere position (aa)
			On compte le nombre de digit(bb)
			On parcour les digits et on les agoute en puissance de 10(cc)
*/
int reverse_digit(int n) {
 
	int buffer = n;
	int reverse = 0;
	int compteur = 0;
	int zero = 0;
 
	//Selon specifications
	n = abs(n);
 
	//11
	if (n == 0) { return 0; }
 
	//aa
	while (n % 10 == 0) { n /= 10; }
 
	//bb
	while (buffer != 0) {
		++compteur;
		buffer /= 10;
	}
 
	//cc
	while (compteur != 0) {
		--compteur;
		reverse += (n % 10) * (int)pow(10, compteur);
		n /= 10;
	}
 
	return reverse;
}
/*====================================================================*/

[Sve@r]

Bonjour

et en quelques boucle on peut tout a fait le faire.

J'ai un exercice donné à mon cours d'algorithmique basé sur la récursivité. On me demande d'inverser les chiffres d'un nombre ( 1234 devient 4321). Je vois bien comment je dois le faire de manière itérative,

Donc déjà d'une part il s'agit d'un exercice de manipulation de la récursivité et d'autre part il savait déjà le faire de façon itérative.