Discussion :

[einsteina]

Bonjour,

je dois ecrire une fonction qui inverse un nombre par exemple 12345 doit devenir 54321

j'ai fais un code mais là, je bloque. Le soucis se trouve avec le j, il devrait representer le plus grand i mais là, ... je sais pas
ca marche pour un nombre de 3 mais pas plus

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
#include <iostream>
using namespace std;
#include <stdlib.h>
#include <math.h>
int f(int a);
int s,y, a,j, i,n ;
int   x;
 
int f(int a)
 
{cin>>a;s=0;
while(a>=10){
 
 x= a/10;
 i=1;
while (x >=10)
 
{
 x=x/10;
 i++;
 j=i;
 } 
  cout<<"i ="<<i<<endl;
 
  cout<<"j ="<<j<<endl;
 
y= x*int(pow(10,j-i));
a= (a- double (x* pow(10,i)));  
cout<<"nouveau a "<<a<<endl;
 cout<<"x "<<x<<endl;
cout<<"y ="<<y<<endl;
 s=s+y ;
 cout<<"s "<<s<<endl;
}x=a;
 
 cout<<"a"<<a<<endl;
cout<<"x "<<x<<endl;
cout<<"j ="<<j<<endl;
double p=double (pow(10,j)); cout<<"p"<<p<<endl;
double e=( x*p);cout<<"e"<<e<<endl;
s=s+e;
 
return s;
}  
 
 
 
int main (void)
{
 
cout<<"sol  =   "<<f(a)<<endl;
 
system("pause");
return 0;
}

[francois987]

bonjour,

un algorithme qui fonctionnerait serait de passer par une chaine de caractères:
- nombre1, nombre2 des entiers
- chaine1, chaine2 des chaines de caractères de meme longueur
- convertir(nombre1, chaine1)
- pour i de 0 à longueur(chaine1)
chaine2(i) = chaine1(longueur(chaine1)-i)
fin pour
- convertir(chaine2, nombre2)

[koala01]

Salut,

Le fait est qu'il faut créer un algorithme cohérent, car il n'existe - à ma connaissance - rien de pareil.

Ce que je te conseillerais, c'est de te baser sur trois propriétés propriétés intéressantes en ce qui concerne les entiers:

1. Il est possible de récupérer le reste d'une division entre deux entiers en utilisant %
2. Si le résultat de la division entre deux entiers est inférieur à 1, on obtient 0.
3. si tu prend le reste de la division par 10 d'un entier, tu obtiens... les unités

L'idée devient alors relativement simple:

• tu déclare une variable de retour, de type entier, que tu initialise à 0
• Tant que la valeur d'origine est plus grande que zéro, il va falloir "mouiller la chemise"
• tu additionne le reste de la division de la valeur d'origine par 10 à la variable de retour
• Comme il faut tout décaler "d'un cran vers la gauche" si la valeur d'origine est supérieure à dix, tu multiplie la valeur de retour par dix si c'est le cas
• tu n'a plus qu'à diviser la valeur d'origine par dix pour recommencer le travail.
• Une fois que la valeur d'origine vaut 0, tu peux renvoyer la valeur de retour

Cela pourrait se traduire par un code proche de ceci:

Code :

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

1
2
3
4
5
6
7
8
9
10
11
12
int inverse(int origine)
{
    int result = 0;
    while(origine>0)
    {
        result+=(origine%10);
        if(origine>10)
            result*=10;
        origine/=10;
    }
    return result;
}

qui pourrait très bien être utilisé dans un cadre proche de

Code :

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

1
2
3
4
5
6
7
8
9
int main()
{
    int orig;
    int result;
    cin >>orig;
    result=inverse(orig);
    cout<<result<<endl;
    return 0;
}

[HanLee]

bonjour,

un algorithme qui fonctionnerait serait de passer par une chaine de caractères:
- nombre1, nombre2 des entiers
- chaine1, chaine2 des chaines de caractères de meme longueur
- convertir(nombre1, chaine1)
- pour i de 0 à longueur(chaine1)
chaine2(i) = chaine1(longueur(chaine1)-i)
fin pour
- convertir(chaine2, nombre2)

Oui le plus élégant est de passer par une chaîne de caractère (ou un vecteur de chiffres).
L'idée est là mais ça marche pas.
Il suffit d'échanger les caractères 2 à 2 par rapport à "l'axe de symétrie" de la chaîne de caractères.

[loufoque]

Le plus élégant serait sûrement de faire un itérateur qui soit capable d'extraire les digits un à un, d'inverser la séquence avec un autre d'adapteur, puis de regénérer l'entier à partir de cette séquence.

[koala01]

Oui le plus élégant est de passer par une chaîne de caractère (ou un vecteur de chiffres).
L'idée est là mais ça marche pas.
Il suffit d'échanger les caractères 2 à 2 par rapport à "l'axe de symétrie" de la chaîne de caractères.

A vrai dire, il faut voir quel est l'usage de cette valeur inversée...

Mais j'ai du mal à comprendre "pourquoi ce serait plus élégant" de passer par une chaine de caractères

Quand on y pense, le fait de convertir un entier ne chaine de caractère ne demandera pas beaucoup moins de travail (du point de vue du processeur) que la petite fonction que j'ai présentée...

De plus, sur les (très) gros nombres, tu te trouvera face à l'utilisation de N caractères là où... un int aurait très bien pu suffire...

Cela n'a peut être l'air de rien, mais, ce qui est pris n'est plus à prendre

[HanLee]

A vrai dire, il faut voir quel est l'usage de cette valeur inversée...

Mais j'ai du mal à comprendre "pourquoi ce serait plus élégant" de passer par une chaine de caractères

Quand on y pense, le fait de convertir un entier ne chaine de caractère ne demandera pas beaucoup moins de travail (du point de vue du processeur) que la petite fonction que j'ai présentée...

De plus, sur les (très) gros nombres, tu te trouvera face à l'utilisation de N caractères là où... un int aurait très bien pu suffire...

Cela n'a peut être l'air de rien, mais, ce qui est pris n'est plus à prendre

Elégant = simple, concis et évident, ce qui n'implique pas qu'il soit efficace.

Chaîne de caractère, c'est une façon de parler, dans le sens où l'algorithme est essentiellement un traitement sur la représentation d'un nombre dans une base donnée, et non pas sa valeur!

C'est un traitement purement visuel (palindrome, tout ça).
Ce que loufoque propose est une autre implémentation.

----

Pour des int, ta solution est probablement la plus efficace ceci-dit, mais pour un très grand nombre style BigInt, je ne vois pas pourquoi tu dis que ta solution ne demanderait qu'un int ?

OK, en terme de complexité mémoire, ma solution naïve demanderait une occupation en O(log(N)/log(base)) caractères.

Mais toi, il faudra faire le modulo, la multiplication, l'addition, ce qui est potentiellement lourd aussi!

[einsteina]

je vous remercie par vos reponses ,je n ai pu utiliser les chaine de caracteres car je ne suis pas sensée trvailler avec les vecteurs, (consignes du prof)
Merci koala pour ta reponse ,elle m'a ete d une grande aide

[koala01]

Mais toi, il faudra faire le modulo, la multiplication, l'addition, ce qui est potentiellement lourd aussi!

L'addition et la multiplication sont des opérations de base, qui ne demande finalement que très peu de temps d'exécution et de resources...

Il n'est pas impossible que le modulo prenne effectivement un peu plus de temps, mais, à mon sens, tout cela prend de toutes manière beaucoup moins de temps et de ressources que de passer par une conversion vers les caractères correspondant à chaque type... (même si la conversion naïve en caractères représentant le nombre se baserait aussi sur ces opérations mathématiques, une fois la conversion effectuée, tu dois encore... inverser le tout )

[HanLee]

L'addition et la multiplication sont des opérations de base, qui ne demande finalement que très peu de temps d'exécution et de resources...

Il n'est pas impossible que le modulo prenne effectivement un peu plus de temps, mais, à mon sens, tout cela prend de toutes manière beaucoup moins de temps et de ressources que de passer par une conversion vers les caractères correspondant à chaque type... (même si la conversion naïve en caractères représentant le nombre se baserait aussi sur ces opérations mathématiques, une fois la conversion effectuée, tu dois encore... inverser le tout )

Arf, tu lis trop vite! Je parlais de ça dans le cas d'un type BigInt que tu semblais évoquer!

Evidemment que sinon c'est plus lent. Une allocation mémoire, c'est de l'ordre de 2 ordres de grandeur de plus qu'une simple addition et tout!

[koala01]

Arf, tu lis trop vite! Je parlais de ça dans le cas d'un type BigInt que tu semblais évoquer!

(HS: il n'existe pas un type bigint... )

Mais, quel que soit le type d'entier que tu utilise, entre le nombre de bits utilisés pour représenter la valeur et le nombre de caractères nécessaires pour représenter les plus grandes des valeurs que le type autorise, tu auras toujours besoin de plus de caractères que ceux qui sont utilisés par le type entier que tu envisage...

Quand tu regarde un entier de type int (sur mon architecture), il faut 10 chiffres pour représenter la valeur maximale, alors que la valeur tient en... l'équivalent de 4 caractères.

Si tu passe à un long ou à un long long, le type utilise peut être effectivement un nombre de caractères plus important pour représenter ses valeur, mais, chez moi, le long long utilise 8 caractères, mais il en faut...20 pour représenter la valeur maximale

[HanLee]

(HS: il n'existe pas un type bigint... )

Mais, quel que soit le type d'entier que tu utilise, entre le nombre de bits utilisés pour représenter la valeur et le nombre de caractères nécessaires pour représenter les plus grandes des valeurs que le type autorise, tu auras toujours besoin de plus de caractères que ceux qui sont utilisés par le type entier que tu envisage...

Quand tu regarde un entier de type int (sur mon architecture), il faut 10 chiffres pour représenter la valeur maximale, alors que la valeur tient en... l'équivalent de 4 caractères.

Si tu passe à un long ou à un long long, le type utilise peut être effectivement un nombre de caractères plus important pour représenter ses valeur, mais, chez moi, le long long utilise 8 caractères, mais il en faut...20 pour représenter la valeur maximale

Tant qu'on reste sur des petits chiffres, je ne dis pas le contraire, mais en fait je ne sais pas ce que tu cherches à me montrer.

A la base, tu me disais qu'un algorithme textuel utilise trop de mémoire pour rien, ce à quoi je suis tout à fait d'accord ; puis tu rajoutes qu'il n'était surtout pas scalable pour des entiers arbitrairement grands, donc pour moi tu penses à BigInt, les nombres de GMP, un truc du style.

On aurait pu s'arrêter là, mais j'ai rebondi sur le dernier point.
A ce sujet, j'ai juste pointé du doigt le fait que :
- bien que ma solution textuelle naïve soit bien moins efficace, la consommation mémoire est la même à une constante près
- le fait d'appliquer l'algorithme à un type entier arbitrairement long (style BigInt, les nombres de GMP, ou comme ça) t'obligerait également à en utiliser un avec l'algorithme que tu as montré (pour result)
- en termes de complexité temporelle, je ne suis pas sûr qu'asymptotiquement, tous les modulos, divisions, multiplications continueront à donner un avantage, parce qu'on ne manipule plus des primitives de base.

Ceci dit c'est hors sujet, parce qu'on ne parle que d'int/long/long long.

[screetch]

et tu passes comment un nombre en chaine de caracteres sans utiliser modulo et div??

[HanLee]

et tu passes comment un nombre en chaine de caracteres sans utiliser modulo et div??

Pas bête !

On divague, mais effectivement, potentiellement ya du modulo et div.
En théorie ça dépend de la base interne utilisée pour la représentation de notre entier, mais à tous les coups, ce sera un truc en base 2^32 ou 2^16.

J'ai pas besoin de multiplier "result", ni de comparer avec 10, mais après il faut convertir de string en BigInt... On perd encore oui là.

[Médinoc]

Pour inverser la représentation d'un nombre dans une quelconque base, j'utiliserais une fonction proche de celle de Koala01 :

Code C :

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
int inverse(int source, int base)
{
	int result = 0;
	while(source > 0)
	{
		//"pop" source
		int digit = source % base;
		source /= base;
 
		//"push" result
		result *= base;
		result += digit;
	}
	return result;
}

[Obsidian]

Ça me permet d'introduire dans la discussion une petite subtilité dont j'avais traité ici : http://www.abcelectronique.com/forum...ad.php?t=23722

Bien que le calcul d'une division implique obligatoirement celui de son reste, il n'est pas possible d'obtenir simultanément l'un et l'autre en C ou C++ dans la même opération, et c'est bien dommage car cela plombe directement tous les algorithmes de cet acabit ...

[Médinoc]

Et c'est bien bête, car sur des proc comme le Motorola 68000, la même opération assembleur donnait le quotient et le reste. C'est dans ces circonstances qu'on peut faire une fonction contenant un bloc __asm (non-standard!) pour faire le boulot...

[nicroman]

Ça me permet d'introduire dans la discussion une petite subtilité dont j'avais traité ici : http://www.abcelectronique.com/forum...ad.php?t=23722

Bien que le calcul d'une division implique obligatoirement celui de son reste, il n'est pas possible d'obtenir simultanément l'un et l'autre en C ou C++ dans la même opération, et c'est bien dommage car cela plombe directement tous les algorithmes de cet acabit ...

Et c'est faux... je t'enjoins à regarder le code assembleur générer par l'algo de koala....
Il va utiliser "div"... puis le registre EAX (qui contient le dividende) et EDX (qui contient le reste)...

Faites un peu plus confiances aux optimiseurs....