[Algo]Changement de base

Version imprimable

Bonjour,
Je souhaiterais également contribuer à l'élargissement de cet espace.

C'est pourquoi je propose un algorithme permettant un changement de base, dont l'entrée est supposée en base décimale.

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
 
int cryptage = 0        //nombre final obtenu suite au changement de base
int entree             //nombre que l'on suppose être en base décimale
double exposant
double facteur
 
Début
	Lire(entree)
 
	while(entree >= 0)                        
 
		log(entree)/log(10) = exposant        //cast vers un entier
 
     		entree/10^exposant=facteur          //cast vers un entier
 
     		cryptage + facteur*base^exposant = cryptage
 
     		entree - facteur*10^exposant = entree
Fin

A++

03/01/2007, 15h57
PRomu@ld

Ta solution semble assez compliquée et de plus ne donne pas forcément des résultats exacts, l'utilisation du logarithme est un peu bizarre ici. Mieux vaut utiliser la division euclidienne pour ce genre de conversion, on obtient un résultat exact.

Entrée: Deux nombres entiers, le premier désignant le nombre entier en base décimale à convertir et le second la base cible.

Sortie: Affichage du résultat de la conversion

Difficulté: Niveau 1, facile
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 int tableau[3] int a <- 3 int nombre int base int y Début Lire(nombre) Lire(base) while (nombre>0) y <- cast_entier(nombre/base) tableau[a] <- nombre - y * base a <- a-1 nombre <- y Afficher(tableau) Fin
Maigre début...

Sauf que j'ai un problème, comment affecter suffisamment de place à mon tableau?
Je peux calculer sa taille à l'aide des entrées
Code:

1 2 3 Lire(nombre) Lire(base)
Citation:

base^taille_tableau=nombre
log(nombre)/log(base)=taille_tableau

Mais il m'est impossible d'attribuer un bloc mémoire en fonction d'une variable... Est-ce possible de réaliser une telle chose sans avoir recourt à une spécificité d'un langage cible?

A++

03/01/2007, 19h13
millie

C'est quoi le a-1 qui se balade tout seul ? a <- a -1 ?
03/01/2007, 19h28
reggae

Edité, merci :D
04/01/2007, 11h58
PRomu@ld
Citation:

Difficulté: Niveau 1, facile

La difficulté ne sert à rien :D

Ton code est trop proche du C pour être compris facilement. Utilises les remarques qui ont été données dans ce thread :

http://www.developpez.net/forums/sho...d.php?t=221060
Code:

1 2 int tableau[3] int a <- 3
pourquoi fixes-tu la taille de ton tableau à 3 ? Tu es en algorithmique, il faut se démarquer le plus possible de l'implémentation, pas conséquent tu peux supposer que le tableau est de taille infinie (si infini ne te plait pas, tu peux supposer que la taille est suffisante pour stoquer ton résultat).
Code:

1 2 3 Lire(nombre) Lire(base)
Ca non plus ça ne sert à rien puisque tu as supposé que c'était des entrées de ton algorithme, les nombres te sont donc donnés.

Code:

cast_entier(nombre/base)

Pourquoi un cast ? De plus algorithmiquement parlant, le cast n'a pas de sens, demande à un prof de math ce qu'est un cast, il n'est pas sur de te répondre :D Ce qu'il faut préciser, c'est que l'opérateur de division que tu utilises est l'opérateur de division euclidienne.

Code:

Afficher(tableau)

En fait, ceci est juste bon pour vérifier que le résultat est bon, ce qui importe c'est de savoir que le résultat est dans tableau, c'est la sortie de ton algorithme.

Citation:

Mais il m'est impossible d'attribuer un bloc mémoire en fonction d'une variable... Est-ce possible de réaliser une telle chose sans avoir recourt à une spécificité d'un langage cible?

En fait comme je te l'ai dis au dessus, tu supposes que la taille de ton tableau est au moins suppérieure (strictement ou pas, il faudra vérifier) à la formule que tu as donnée (log(nombre)/log(base)=taille_tableau )

Vite fait, j'ai bricolé ça en C :

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
 
void EnBase( unsigned long N , unsigned long b )
{
  if( N >= b )
    {
      EnBase( N / b , b );
      printf( " %lu" , N % b );
    }
  else
    {
      printf("%lu",N);
    }
}

Ce qui donne en algo :

Algorithme

Code:

1
2
 
Affichage en base b d'un nombre décimal.

Entrée

Code:

1
2
3
4
 
Deux nombres :
N : un entier en base 10.
B : la base dans laquelle on veut afficher N.

Sortie

Code:

1
2
 
A priori rien.

Pseudo-Code

Code:

1
2
3
4
5
6
7
8
9
10
 
EnBase( N : entier ; B : entier )
DEBUT
     SI N >= B ALORS
          EnBase( N / B , B )
          AFFICHER N modulo B
     SINON
          AFFICHER N
     FIN SI
FIN

Complexité

Code:

1
2
 
log( N )

04/01/2007, 14h37
reggae

C'est quand même beaucoup plus simple :aie: .
Ben au moins j'aurais poussé quelqu'un à écrire cet algo :mouarf: .

Merci, à vous deux.
04/01/2007, 16h18
PRomu@ld

Citation:

C'est quand même beaucoup plus simple

Les solutions récursives sont (presque) toujours plus simples à écrire que leur équivalents itératifs, c'est tout à fait normal !

Citation:

Ben au moins j'aurais poussé quelqu'un à écrire cet algo .

C'était pas bien compliqué ..., ça fera un de plus qu'il faudra que j'ajoute à la page source, c'est toujours ça de pris !

Et si B=12 ???

[QUOTE=PRomu@ld]Vite fait, j'ai bricolé ça en C :

Cela marche parfaitement pour les bases <10. Sinon il faut travailler encore un peu.

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
char chiffre ( int n)
{
    switch (n)
    {
    case 0:
        return '0';
    case 1:
        return '1';
    case 2:
        return '2';
    case 3:
        return '3';
    case 4:
        return '4';
    case 5:
        return '5';
    case 6:
        return '6';
    case 7:
        return '7';
    case 8:
        return '8';
    case 9:
        return '9';
    case 10:
        return 'A';
    case 11:
        return 'B';
    }
}
 
void EnBase (int n, int b)
{
    if (n<b)
        printf("%c",chiffre(n));
    else
    {
        EnBase (n/b,b);
        EnBase(n%b,b);
    }
}

12/01/2007, 18h25
PRomu@ld

Oui et non en fait, tu auras remarqué que j'avais rajouté un espace afin de distinguer tous les digits du nombre résultant. De plus ne voulant pas être seulement limité à une méthode d'écriture des nombres avec une base supérieure au système de numération classique, j'ai préféré utiliser une définition un peu plus mathématique : mes digits en base b sont des entiers allant de 0 à b-1, comme ça ça résout tous les problèmes.

Les lettres sont biens si tu as une base raisonnable mais si tu as une base qui dépasse les différents caractères que tu peux afficher, tu auras un problème. Encore une fois, l'algorithme est donné en l'état et a le mérite (je pense) de fonctionner sans cette limite, ensuite, libre à chacun de le personnaliser pour qu'il réponde à ses besoins.
12/01/2007, 18h25
millie

Je crois que ça ne va pas marcher si tu utilises par exemple l'appel :

EnBase(50,51);

EDIT : Excuses moi, je n'avais pas vu le "Cela marche parfaitement pour les bases <10. Sinon il faut travailler encore un peu."

Post croisé avec Promu@ld
EDIT2 : "j'ai préféré utiliser une définition un peu plus mathématique : mes digits en base b sont des entiers allant de 0 à b-1, comme ça ça résout tous les problèmes.", c'est que je pensais aussi ;)

EDIT3:
Bon, histoire que mon post serve à quelque chose. Ta méthode Zavonen aura toujours un problème, notamment car le nombre de caractère machine (genre ASCII) est limité. Donc, si tu as une base, par exemple 6500, tu auras forcement des éléments en double (style AA BC UI), voir beaucoup plus). Donc, autant se limiter à des entiers :D (à moins que tu considères une borne, du style 16, dans ce cas, ça peut aller ;) )

EDIT4: Snif, je n'essayerai pas de me rattraper cette fois :mrgreen:
12/01/2007, 18h43
PRomu@ld

Citation:

Envoyé par millie

Bon, histoire que mon post serve à quelque chose. Ta méthode Zavonen aura toujours un problème, notamment car le nombre de caractère machine (genre ASCII) est limité.

Citation:

Envoyé par PRomu@ld

Les lettres sont biens si tu as une base raisonnable mais si tu as une base qui dépasse les différents caractères que tu peux afficher, tu auras un problème.

:dehors:
13/01/2007, 00h33
Zavonen

Le b-a ba de la base

Vous avez tous raison, de constater que ma 'proposition', sauf à utiliser les alphabets grec, hébraïque, arabe, etc... se limite à la base 36 ...
(Nice try, but...)
De fait, je retiens que:
La base 12 est la base idéale. Il existe une société qui, déplorant que la nature ne nous ait donné que 10 doigts, poursuit le mythe de la révolution française de lui faire remplacer la base 'usuelle' (une des plus mauvaises mathématiquement parlant).
En pratique on ne dépasse guère la base 16, largement utilisée pour les adresses mémoire.
Mon 'bidouillage' couvre donc les cas 'usuels'.
Cela dit PRomu, grâce à son petit espace, qui avait échappé à ma perspicacité, fournit dans tous les cas, la décomposition de N suivant les puissances de B.
Je le félicite pour son sens du détail et du travail bien fait.
Mais peut on dans ce cas parler de décomposition suivant une base, dans la mesure où l'idée même de la numérotation de position est d'écrire l'ensemble potentiellement infini des entiers avec un nombre certainement fini de symboles, les 'chiffres' ?
Faut il admettre les chiffres à plusieurs chiffres ...
That is the question ?
Bonne nuit.
13/01/2007, 08h35
PRomu@ld

Citation:

Vous avez tous raison, de constater que ma 'proposition', sauf à utiliser les alphabets grec, hébraïque, arabe, etc... se limite à la base 36 ...

En fait, même en utilisant les alphabets grecs et compagnies, si tu te retrouves avec un ensemble fini de lettre, tu atteindras cette limite (limite qui devient de plus en plus théorique, pour les applications pratiques ça devrait suffire).

Citation:

La base 12 est la base idéale.

tout ceci reste encore à démontrer, la base doit être choisie en fonction des besoins et des applications. Le binaire est utilisé à l'intérieur de nos machines car elle répond à une nécessité technique. Pour avoir eu l'occasion de l'interressé à la réalisation d'une bibliothèque de nombres entiers en précision arbitraire, je me suis rendu compte qu'un moyen pratique pour la mise en place était de stocker mes nombres sous forme de puissance de 10000 (tout ceci pour faciliter les calculs et limiter l'occupation mémoire).

En fait chaque système de numérotation son application. On utilise bien le système sexagésimal pour l'heure ...

Citation:

En pratique on ne dépasse guère la base 16, largement utilisée pour les adresses mémoire.

En fait de manière interne, c'est du binaire,l'héxa est juste là pour te simplifier les écritures. Il est largement plus rapide d'écrire FFFFFFFF que son équivalent binaire.

Citation:

Cela dit PRomu, grâce à son petit espace, qui avait échappé à ma perspicacité,

C'est pas grave ;)

Citation:

Mais peut on dans ce cas parler de décomposition suivant une base, dans la mesure où l'idée même de la numérotation de position est d'écrire l'ensemble potentiellement infini des entiers avec un nombre certainement fini de symboles, les 'chiffres' ?

En fait, je préférerait parler avec le langage de la théorie des langages, ainsi au lieu de parler de chiffres, je préfère parler de lettre : la lettre 1, la lettre 24, et ainsi de suite, ça évite les confusions. C'est un problème de pur vocabulaire. En effet, les chiffres sont typiquement associés à une représentation décimale, ainsi on a du mal à se représenter un chiffre à deux symboles (ou lettres), mais en fait ça ne pose aucun problème, il s'agit d'un seul et même symbole (par exemple le symbole 36), l'idée est ensuite de pouvoir identifier simplement les symboles, j'ai utilisé un espace mais on aurait pu tout aussi bien utiliser la virgule ou le point ou tout autre symbole qui ne fait pas parti de l'alphabet utilisé pour représenter le nombre.

De plus, d'une manière plus théorique, il me semble (mais je ne pourrai le jurer) que l'écriture telle qu'on peut la faire en décimale est un raccourci d'écriture pour sa décomposition en base 10 :

123 = 1 * 100 + 2 * 10 + 3 * 1.

Avec la décomposition complète, on peut parfaitement écrire un nombre sans qu'il y ait d'ambiguité :

x(b) = an* b^n + a_n-1 * b^(n-1) + ... + a_0

C'est donc à mon avis un problème à la fois de vocabulaire et de méthode de représentation.
13/01/2007, 11h36
Zavonen

On avance, on avance

Citation:

En fait, je préférerait parler avec le langage de la théorie des langages, ainsi au lieu de parler de chiffres, je préfère parler de lettre : la lettre 1, la lettre 24, et ainsi de suite, ça évite les confusions. C'est un problème de pur vocabulaire. En effet, les chiffres sont typiquement associés à une représentation décimale, ainsi on a du mal à se représenter un chiffre à deux symboles (ou lettres), mais en fait ça ne pose aucun problème, il s'agit d'un seul et même symbole (par exemple le symbole 36), l'idée est ensuite de pouvoir identifier simplement les symboles, j'ai utilisé un espace mais on aurait pu tout aussi bien utiliser la virgule ou le point ou tout autre symbole qui ne fait pas parti de l'alphabet utilisé pour représenter le nombre.

Sur le plan 'théorique' rien à dire ! Mais le génie de l'écriture de position est de pouvoir décider de certaines propriétés arithmétiques des nombres uniquement sur leur représentation (écriture). L'exemple classique est la 'divisibilité'. Il me semble que cela disparaît dès qu'on utilise des 'symboles multichiffres' comme vous le suggérez.
Le seul intérêt véritable, à mon sens, est l'exemple que vous fournissez (utiliser la base 10000 ou plus ...). Quand la base d'écriture des nombres est une puissance de la base d'écriture des chiffres, il n'y a preque rien à faire pour passer d'une représentation à l'autre sinon couper en tranches et rajouter des 0 aux endroits opportuns. Et alors là, question efficacité, il n'y a pas photo ! A recommander donc pour les calculs avec les bignums et les calculs grande précision (infinimiment préférable aux systèmes utilisant des listes par exemple).

Citation:

En fait de manière interne, c'est du binaire,l'héxa est juste là pour te simplifier les écritures. Il est largement plus rapide d'écrire FFFFFFFF que son équivalent binaire.

Pas seulement !
Dans un système de représentation 1 chiffre= 1 symbole, les nombres ne dépassant pas une puissance de la base donnée correspondent aux nombre de longueur maximale donnée.
Ainsi dans les systèmes 16 bits où on avait le modèle de représentation des pointeurs (segment+offset), la simple écriture du modèle 'plat' en hexa, fournit immédiatement la décomposition, ce n'était pas à l'époque une simple question de rapidité d'écriture.

Citation:

De plus, d'une manière plus théorique, il me semble (mais je ne pourrai le jurer) que l'écriture telle qu'on peut la faire en décimale est un raccourci d'écriture pour sa décomposition en base 10 :
123 = 1 * 100 + 2 * 10 + 3 * 1.

Avec la décomposition complète, on peut parfaitement écrire un nombre sans qu'il y ait d'ambiguité :

x(b) = an* b^n + a_n-1 * b^(n-1) + ... + a_0

Vous pouvez le jurer !
Et dans la foulée, utiliser votre algorithme, sans modification, pour décomposer une fraction rationnelle en éléments simples. Ce qui permettrait de faire le joint avec la discusiion sur la factorisation des polynômes.

Citation:

C'est donc à mon avis un problème à la fois de vocabulaire et de méthode de représentation.

Tous les malentendus ont cette origine :)
Pour finir, si je suis limité à 36 vous l'êtes à 4294967296. Vous avez placé la barre un peu plus haut, mais il faut apprendre à vivre avec notre finitude;)
Bon week-end.
13/01/2007, 12h02
PRomu@ld

Citation:

Pour finir, si je suis limité à 36 vous l'êtes à 4294967296. Vous avez placé la barre un peu plus haut, mais il faut apprendre à vivre avec notre finitude

Absolument pas, dans la pratique, si j'ai un système 64 bits il n'en est plus de même. De plus, la méthode que je présente est une méthode algorithmique, et dans ces conditions, l'infini peut intervenir ;)

Citation:

Mais le génie de l'écriture de position est de pouvoir décider de certaines propriétés arithmétiques des nombres uniquement sur leur représentation (écriture).

Oui, mais les propriétés arithmétiques si je ne m'abuse sont définies en fonction de la base. (je ne suis pas prof de math, je n'en suis pas sur mais ça me parait logique)

Citation:

L'exemple classique est la 'divisibilité'.

La divisibilité est effectué au moyen de modulo et il existe des méthode pour trouver des critères de divisibilité dans d'autres bases. En base b on peut très rapidement calculer la divisibilité d'un nombre par un multiple de b il me semble.

Une méthode bête et méchante pour trouver si un nombre x est divisible par b est de transformer ce nombre en base b et de regarder la dernière unité du nombre, si elle vaut 0, alors le nombre est divisible par b, dans le cas inverse on a pas un diviseur.

Les méthodes que l'on apprend à l'école découlent de résultats plus généraux.

Citation:

Dans un système de représentation 1 chiffre= 1 symbole, les nombres ne dépassant pas une puissance de la base donnée correspondent aux nombre de longueur maximale donnée.
Ainsi dans les systèmes 16 bits où on avait le modèle de représentation des pointeurs (segment+offset), la simple écriture du modèle 'plat' en hexa, fournit immédiatement la décomposition, ce n'était pas à l'époque une simple question de rapidité d'écriture.

Quand j'entendais rapidité d'écriture, ça sous entendait aussi une rapidité de calcul. Dans la même veine, on pourrait citer le découpage des adresses réseau qui est bien plus facile à faire en binaire que par la représentation décimale. Mais c'est toujours un problème d'application pratique.
13/01/2007, 12h54
Zavonen

Du nombre et de l'infini

Citation:

Oui, mais les propriétés arithmétiques si je ne m'abuse sont définies en fonction de la base. (je ne suis pas prof de math, je n'en suis pas sur mais ça me parait logique)

Non ! Un nombre possède des qualités intrinsèques indépendantes de sa représentation en une base qcq. Si un nombre est somme de deux carrés cette propriété ne dépend pas de la façon dont on l'écrit.

Citation:

Une méthode bête et méchante pour trouver si un nombre x est divisible par b est de transformer ce nombre en base b et de regarder la dernière unité du nombre, si elle vaut 0, alors le nombre est divisible par b, dans le cas inverse on a pas un diviseur.

Ce n'est pas méchant, mais... Il vaut mieux simplement faire la division et regarder le reste (moins cher). Justement, toute la théorie de la divisibilité consiste à éviter de faire la division, en travaillant juste sur la représentation. Et cette fois, les 'trucs' dépendent bien de la représentation (donc de la base choisie).

Citation:

Absolument pas, dans la pratique, si j'ai un système 64 bits il n'en est plus de même. De plus, la méthode que je présente est une méthode algorithmique, et dans ces conditions, l'infini peut intervenir

La possibilité de créer un individu ayant une durée de vie plus longue que tout nombre donné à l'avance, ne vous donne pas la possibilité de créer un être immortel.
13/01/2007, 13h08
millie

Citation:

Envoyé par Zavonen

Non ! Un nombre possède des qualités intrinsèques indépendantes de sa représentation en une base qcq. Si un nombre est somme de deux carrés cette propriété ne dépend pas de la façon dont on l'écrit.

Certaines propriétés dépendent de la base. Par exemple ce qui est lié à la normalité d'un nombre. Un nombre normal en base 10 ne va pas forcement l'être en base 48.
13/01/2007, 13h09
PRomu@ld

Citation:

Non ! Un nombre possède des qualités intrinsèques indépendantes de sa représentation en une base qcq. Si un nombre est somme de deux carrés cette propriété ne dépend pas de la façon dont on l'écrit.

J'aurai du dire des propriétés. Et il doit arriver que l'on ait des démonstrations qui soient plus faciles à démontrer lorsque l'on change la base plutôt qu'en décimal.

Citation:

Ce n'est pas méchant, mais... Il vaut mieux simplement faire la division et regarder le reste (moins cher). Justement, toute la théorie de la divisibilité consiste à éviter de faire la division, en travaillant juste sur la représentation. Et cette fois, les 'trucs' dépendent bien de la représentation (donc de la base choisie).

Oui dépendent de la base mais pas du fait qu'il n'y ait qu'un seul digit ou pas (c'est sur celà que je voulais insister). Il existe (de mémoire) une méthode qui permet de trouver si un nombre écrit en base b est divisible par b+1. (ça doit être la somme alternée des termes mais j'ai un doute ...)

Citation:

La possibilité de créer un individu ayant une durée de vie plus longue que tout nombre donné à l'avance, ne vous donne pas la possibilité de créer un être immortel.

Ce n'est pas ce que j'ai dit, tu avançais un nombre qui était totalement dépendant de l'architecture de la machine (32 bits il me semble) j'ai seulement dit qu'il en serait autrement sur une machine 64 bits (tout comme 16 bits). Ensuite j'ai replacé les choses dans leurs contextes en précisant qu'en algorithmique on effectue des hypothèses et parmis elle, on y trouve la non limitation de l'espace mémoire, comme il s'agit d'une théorie on peut se le permettre.

De plus si on peut continuer sur la digression, le fait de créer un individu ayant une durée de vie plus grande que tout nombre donné à l'avance nous indique seulement qu'il n'y a pas encore de borne, ce qui laisse présager d'une possibilité de vie infinie (tout ceci ne reste que théorique on est d'accord).

Je crois que nous nous sommes très largement écarté du sujet initial tout de même ;)