Exercice conversion nombre base 10 en base k

Version imprimable

Bonjour,

Je suis débutant en C, j'ai trouvé la fonction suivante pour convertit un nombre en base 2:
Code:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 void decomp(int nb) { if (nb > 1) decomp(nb >> 1); putchar('0' + (nb & 1)); } int main() { int nb; nb = 126; decomp(nb); return (0); }
Je veux généraliser ça, convertit un nombre en base k.

Merci d'avance.

29/11/2016, 09h53
ternel

Bonjour!
Quelques questions préliminaires:

Soit le nombre 196581342, en base 10.
Quelle est l'écriture en base 2? en base 5? en base 12? et en base 37?

La vraie question:
Comment as-tu trouvé les réponses? C'est à dire: quelle méthode as-tu employée?

La solution à ton problème de code est de répondre précisément à la question "Comment faire, de manière générale?"
Une fois la méthode trouvée, il "suffit" de l'écrire en C.

Si tu sais comment faire, tu dois pouvoir l'expliquer, à nous d'abord, puis à ton compilateur.

Citation:

Envoyé par ternel

Si tu sais comment faire, tu dois pouvoir l'expliquer, à nous d'abord, puis à ton compilateur.

Moi j'ai fait ça sur python, et j'aimerai traduire en C.

Je fais ça, pour n=21

21 = 10 * 2 + 1
j'affiche 1

10 = 2 * 5 + 0
j'affiche 0

5 = 2 * 2 + 1
j'affiche 1

2 = 2 * 1 + 0
j'affiche 0

1 = 2 * 0 + 1
j'affiche 1

Résultat = 10101

Et sur python, voici la fonction :
Code:

1 2 3 4 5 6 7 8 9 10 def base_k(n, k): q = -1 res = '' while q != 0: q = n // (k+1) #Calcule le div r = n % (k+1) # calcule le reste de la division res = `r` + res #concaténer le reste de la division n = q return res
Merci Encore.

Bonjour,

Voilà ce que je donne habituellement :

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
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
 
Calcul dans différentes bases
 
Conventions
 
Dans tout ce document, on va utiliser les notations suivantes:
 
Le symbole ^ signifie 'élever à la puissance'
par exemple 10^3 signifie 'élever 10 à la puissance 3' c'est à dire 10*10*10 = 1000
 
Un nombre suivi par
#B est écrit en base 2  (B pour binaire)
#H est écrit en base 16 (H pour Hexadécimal)
sans précision, il est écrit en base 10
 
Le symbole * signifie 'multiplier'
 
Dans les calculs, pour les divisions :
  Q signifie Quotient
  R signifie Reste
 
Rappel : Tout nombre élevé à la puissance 0 (zéro) vaut 1
(10^0 = 2^0 = 16^0 = 1)
 
 
 
Quand nous écrivons un nombre, par exemple 573, cela signifie qu'il est égal à la somme:
 
  3 * 10^0  = 3*1    =    3
+ 7 * 10^1  = 7*10   =   70
+ 5 * 10^2  = 5*100  =  500
                       -----
                        573
 
 
On peut transcrire cela dans une autre base, par exemple en base 2
 
On ne disposera alors que de 2 symboles, 0 et 1.
Les chiffres en partant de la DROITE signifieront :
0 ou 1 * 2^0
         2^1
         2^2
         2^3
         etc...
 
Soit le nombre 1000111101#B, calculons sa valeur en base 10
 
  1 * 2^0  = 1
+ 0 * 2^1  = 0
+ 1 * 2^2  = 4
+ 1 * 2^3  = 8
+ 1 * 2^4  = 16
+ 1 * 2^5  = 32
+ 0 * 2^6  = 0
+ 0 * 2^7  = 0
+ 0 * 2^8  = 0
+ 1 * 2^9  = 512
            -----
             573
 
On peut utiliser une autre base, 16.
Il nous faut alors 16 symboles pour représenter les différents 'chiffres'.
Par convention, on a choisi d'utiliser 0 à 9, puis A à F
 
A vaut donc 10 (décimal)
B = 11
C = 12
D = 13
E = 14
F = 15
 
Avec le même principe que pour la base 2, voyons le nombre 23D#H
 
  D * 16^0 =  13
+ 3 * 16^1 =  48
+ 2 * 16^2 = 512
            -----
             573
 
Le passage d'une base quelconque en base 10 est donc très simple.
 
 
 
 
Voyons maintenant comment passer de la base 10 à une autre, exemple en base 16.
 
La technique suivante permet de trouver les chiffres successifs en partant de la DROITE.
 
soit le nombre 573.
Divisons le par la base destination, soit 16
573 / 16 = 35(Q) + 13(R)
  le reste = 13 = D#H est le premier chiffre à droite de la valeur cherchée
 
répétons le calcul avec le quotient du calcul précédent (35)
35 / 16 = 2(Q) + 3(R)
  le reste = 3 = 3#H est le deuxième chiffre en partant de la droite
 
et encore une fois :
2 / 16 = 0(Q) + 2(R)
  le reste = 2 = 2#H est le troisième chiffre en partant de la droite
 
Comme le quotient = 0, on peut arrêter.
 
Le nombre 573 s'écrit donc 23D#H
 
En supprimant les commentaires, on obtient une disposition claire:
 
          (Q)   (R)   (R en base 16)
573 / 16 = 35 + 13      D
 35 / 16 =  2 +  3      3
  2 / 16 =  0 +  2      2
 
  On lit les restes de bas en haut = 23D#H
 
 
Refaisons le calcul pour écrire 573 en base 2
 
          (Q)    (R)
573 / 2 = 286   + 1
286 / 2 = 143   + 0
143 / 2 =  71   + 1
 71 / 2 =  35   + 1
 35 / 2 =  17   + 1
 17 / 2 =   8   + 1
  8 / 2 =   4   + 0
  4 / 2 =   2   + 0
  2 / 2 =   1   + 0
  1 / 2 =   0   + 1
 
  terminé puisque le quotient = 0
 
  et donc en lisant les restes de bas en haut, la valeur est 1000111101#B
 
 
Voilà, j'espère que c'est assez clair.

29/11/2016, 13h49
ternel

C'est pas mal du tout. L'explication est assez simple.

Dans les systèmes de numérations positionnels (où la position d'un chiffre dans le nombre influe sur sa valeur), il y a une quantité nommée base, qui est un facteur multiplicatif entre une position et la suivante.

Généralement, le chiffre le plus multiplié est écrit en premier.
Ainsi, en base B, on a 200 = 2 * B * B + 0 * B + 0 = 0 + B * (0 + B * (2) ).

Le chiffre à la position p est le reste de la division entière (ou euclidienne) par B à la puissance p. On peut aussi dire les restes successifs de la division entière par B.
le reste est obtenu via l'opérateur modulo, %Mais tu dois déjà le savoir, puisque tu l'utilises dans ton code python.

Concrètement, pour passer de python à C, dans ton cas, il suffit quasiment de rajouter les accolades et points-virgules.
29/11/2016, 13h55
ternel

Après réflexion, pour comprendre ton code initial, il dois juste te manquer quelques notions d'arithmétique binaire.
>> correspond à décaler les bits d'un entier vers la droite, du nombre de bits indiqué (par le second argument).
& correspond à l'opération binaire et, bit par bit

'0' + (b & 1) signifie le code numérique du caractère '0' plus la valeur de b & 1.
Cette dernière expression vaut 1 si le dernier bit de b est 1, et 0 sinon. Par construction, '0'+1 == '1'. Ainsi, l'argument de putchar est le caractère '1' si le bit de poids faible (celui des "unités") de b est 1, et le caractère '0' si c'est 0.

En fait b>>1 vaut b / 2 et b & 1 vaut b % 2, la différence étant dans les performances potentielles. Mais normalement, les compilateurs savent l'optimiser de toute façon.
29/11/2016, 13h55
hichem0550
Citation:

Envoyé par ternel

Mais tu dois déjà le savoir, puisque tu l'utilises dans ton code python.

Concrètement, pour passer de python à C, dans ton cas, il suffit quasiment de rajouter les accolades et points-virgules.

Re,

J'ai fait ça et n'as pas marché :
Code:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 char base_k(int n, int k) { int q=-1; int r; char res ; while (q != 0) { q = n / (k+1); r = n % (k+1); res = (char)r + res; n = q ; } return res; }
Merci.
29/11/2016, 13h59
ternel

C'est normal, en python, res est une chaine de caractère, et l'opérateur + concatène les différents caractères les uns après les autres.
En C, char est le type d'un entier capable de stocker un unique caractère. l'opérateur + est celui des entiers et ajoute les valeurs.

Il faut passer par une chaine de caractère, (un char* et les fonctions qui vont avec) ou mieux, dans ton cas, simplement l'afficher (par exemple via le putchar() du code initial).

Oui vous avez raison,

D'ailleurs le résultat sur python est en base 3 pour les nombres de 0 à 8:

00
01
02
10
11
12
20
21
22

En C:

0
1
2
1
2
3
2
3
4

Il fait la somme !!!!

Je vais changer où ?

Voici le 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
39
#include <iostream>
#include <stdio.h>
#include<math.h>
 
/* run this program using the console pauser or add your own getch, system("pause") or input loop */
char base_k(int n, int k)
{
	int q=-1;
	int r;
	char res ;
	while (q != 0)
    {
		q = n / (k+1);
		r = n % (k+1);
		res = (char)r + res;
		n = q ;
    }
    return res;
}
 
 
int main(int argc, char** argv) {
	int cas_general;
	int n =2;
	int k=2;
	cas_general=pow((k+1),n);
	//printf("Le resultat est  %d\n", cas_general);
 
	int i;
 
	for (i= 0 ; i < cas_general ; i++)
	{
	    char d= base_k(i, k);
		printf("Le resultat de la fonction est  %d\n", d);
	}
 
 
	return 0;
}

Merci Encore.

29/11/2016, 14h47
ternel

Ca, c'est à toi de voir.
Que font chaque ligne de ton code?

Coder, ce n'est pas écrire au hasard.
02/12/2016, 11h23
Médinoc
Citation:
Envoyé par hichem0550

Je suis débutant en C, j'ai trouvé la fonction suivante pour convertit un nombre en base 2:

Code:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 void decomp(int nb) { if (nb > 1) decomp(nb >> 1); putchar('0' + (nb & 1)); } int main() { int nb; nb = 126; decomp(nb); return (0); }

Je veux généraliser ça, convertit un nombre en base k.
Ooh, une version qui corrige l'inversion de l'ordre des chiffres par récursivité. J'aime.

Bon, on va faire simple: Remplace >> 1 par / 2 et & 1 par % 2 (Modulo 2) et tu atteindras l'illumination.