Est-ce que quelqu'un sait (ou peut-il indiquer une source à lire) une méthode ou une algorithme pour convertir un nombre représenté dans le système de chiffres binaires dans le ternaire (mon cas particulier) ou un algorithme universel pour de telles conversions?
La solution que j'ai déjà implémentée consiste à convertir un nombre en décimal d'abord, puis de le convertir en numéraire requis. Cela fonctionne, mais il y a deux étapes. Je me demande si cela pourrait être fait dans une étape facilement sans mettre en œuvre d'abord arithmétique ternaire? Y a-t-il des trucs, les gars?
upd: Il semble que je n'ai pas réussi à décrire clairement quel moyen de conversion je cherche. Je ne demande pas un moyen de convertir la base-2 à la base-3, je sais faire cela. Vous pouvez considérer que j'ai des structures de données algébraïques pour des numéros ternaires et binaires, à Haskell, il ressemble à ceci: et il y a deux moyens évidents de convertir un à l'autre: d'abord est de le convertir en entier d'abord et d'obtenir le résultat (non intéressant), la seconde est d'implémenter la multiplication propre et l'addition de base-3 et calculer le résultat en multipliant les valeurs de chiffre à la puissance respective de deux (simples et lourds). Je me demande si une autre méthode que ces deux.
9 Réponses :
Si vous le faites avec un ordinateur, les choses sont déjà en binaires, il suffit donc de diviser à plusieurs reprises par 3 et de prendre des restes est aussi simple que les choses obtiennent.
Si vous le faites à la main, longue division en binaires d'œuvres binaires juste comme une longue division en décimal.
juste diviser par trois et prendre des restes. Si nous commençons avec 16 donc en ternaire 121
En fait, j'ai besoin d'algorithme "à la main" à mettre en œuvre dans le programme "Les données utilisées dans le calcul sont la structure de données ayant 0/1 états pour les chiffres, pas certains entier.
Après avoir pensé à cela, il y a toujours une conversion implicite en décimale. À chaque étape, la représentation décimale est toujours considérée. 100 binaire ( 4 en décimal) divisé par 11 ( 3 ). Il est toujours en cours de convertie.
@Vadim Vous êtes presque certainement mieux de convertir vos structures de données en chiffres et en utilisant l'ordinateur arithmétique.
@Jeff m: Il n'y a pas de conversion implicite en décimale. La division est la même dans n'importe quelle base - elle est définie sur des entiers eux-mêmes, pas sur leurs représentations dans une base spécifique.
Si ce sont les devoirs, pseudocode à écrire Je suis sûr que vous pouvez comprendre Comment écrire le résultat en avant à la place de l'arrière. Notez que Notez que cela ne dépend pas du tout < / em> sur la base que l'arithmétique est effectuée. L'arithmétique est définie sur des entiers, pas la représentation des entiers dans une base spécifique. Certainement, vous pourriez le faire comme vous le décrivez, mais cela ressemble à un beaucoup de travail. x dans la base b backwards: / doit être une division entière de style C (le résultat est un entier, tronqué vers zéro).
Veuillez consulter la mise à jour de la question, j'ai clarifié ce qu'il s'agit.
Je ne pense pas qu'il y ait une voie très efficace.
"La solution que j'ai déjà mise en œuvre est de convertir un nombre en décimal premier. " P> blockQuote>
Je suppose que vous êtes en train de convertir en entier intégré en premier. Je ne pense pas que l'entier intégré a quelque chose à voir avec la base 10. (Cependant, lorsque vous l'imprimez, il y aura une conversion de base 10). P>
Peut-être que vous vous attendriez qu'il y ait Quelques algorithmes qui examinent l'entrée à un chiffre à la fois et produisent la sortie. P>
Mais, disons que vous voulez convertir 3486784400 (base 10) en base 3. Vous devrez examiner chaque chiffre avant de produire une sortie, car P>
3486784401 (base 10) = 100000000000000000000 (base 3) 3486784400 (base 10) = 22222222222222222222 (base 3)
"La solution que j'ai déjà mise en œuvre est de convertir un nombre en premier." - C'était une erreur, il suffit de convertir le type algébrique mentionné (Bnumber) en entier.
Je pense qu'il pourrait y avoir des "vues" différentes du problème, même si je ne suis pas sûr que personne d'entre eux ne soit plus rapide ou mieux. Par exemple, la base de commande inférieure à 3 chiffres de n est juste n mod 3. Laissez-vous dire que vous avez déjà la représentation binaire de n. Ensuite, considérons comment les puissances de 2 fonctionnement du mod 3. 2 ^ 0 = 1 MOD 3, 2 ^ 1 = 2 MOD 3, 2 ^ 2 = 1 MOD 3, 2 ^ 3 = 2 MOD 3, ... En d'autres termes , les pouvoirs alternent entre 1 MOD 3 et être 2 mod 3. Vous avez maintenant un moyen facile d'obtenir la base à basse commande à 3 chiffres en balayant la représentation binaire de N et généralement uniquement l'addition de 1 ou 2 à chaque position de bit. où un 1 se produit.
Vous pouvez utiliser des abréviations intelligentes pour la conversion. Le code suivant est la «mauvaise» direction, c'est une conversion de ternaire en binaire en fonction du fait que 3 ^ 2 = 2 ^ 3 + 1 en utilisant uniquement un ajout binaire. Fondamentalement, je convertissons deux chiffres ternaires en trois chiffres binaires. De binaire au ternaire serait légèrement plus compliqué, comme étant ajouté ternaire (et probablement soustraction) serait nécessaire (y travaillant sur cela). Je suppose que le chiffre le moins important à la tête de la liste (qui est le seul moyen qui a du sens), vous devez donc lire les chiffres "à l'envers".
subT :: TNumber → TNumber → TNumber
subT a [] = a
subT [] b = error "negative numbers supported"
subT (a:as) (b:bs)
| b ≡ T0 = a : (subT as bs)
| a ≡ b = T0 : (subT as bs)
| a ≡ T2 ∧ b ≡ T1 = T1 : (subT as bs)
| otherwise = let td = if a ≡ T0 ∧ b ≡ T2 then T1 else T2
in td : (subT as $ addTDigit bs T1)
where addTDigit [] d = [d]
addTDigit ts T0 = ts
addTDigit (T0:ts) d = d:ts
addTDigit (T1:ts) T1 = T2:ts
addTDigit (t:ts) d = let td = if t ≡ T2 ∧ d ≡ T2 then T1 else T0
in td : (addTDigit ts T1)
Oui, c'est la solution que je viens à moi-même, mais c'est encombrant. Je pense qu'il est possible de gérer la rendant plus courte en générant les modèles de conversion, ce qui ne spécifie pas le tout dans la correspondance de modèle.
J'ai bien peur de ne pas savoir assez Haskell pour pouvoir exprimer cela en code, mais je me demande si l'utilisation de la règle de Horner pour évaluer les polynômes pourrait donner une méthode.
Par exemple, A x ^ 2 + b x + c peut être évalué comme C + x * (B + X * A).
Convertir, disons,
Le numéro ternaire A * 9 + B * 3 + C à Binary, on commence par la représentation binaire d'A, puis multiplie par 3 (c.-à-d. Maject et ajouter), puis ajoute la représentation binaire de B, multiplie le résultat de 3 et ajoute c.
Il me semble que cela devrait être faisable avec une carte (pour obtenir la représentation binaire des chiffres ternaires) et un pli (de A, B -> A + 3 * B)
Non, vous ne pouvez pas convertir un numéro de base2 en un numéro de base3 sans le charger dans un entier. La raison en est que 2 et 3 sont coprime - ils n'ont pas de facteurs communs.
Si vous travailliez avec base2 et base4, ou même base6 et base9, alors l'ensemble d'entiers jusqu'au multiple commun commun des deux bases serait représenté par deux ensembles isomorphes. Par exemple 13 (base4) = 0111 (base2), donc convertir 1313 (base4) = 01110111 (base2) - c'est une opération de recherche et de remplacement.
Au moins la solution que vous avez travaille et est relativement simple. Si vous devez améliorer les performances, convertissez la représentation complète de la base2 en un entier avant de commencer la conversion de base3; Cela signifie moins d'opérations de module. L'alternative serait traiter chaque caractère dans la base2 numéro un d'un par un, auquel cas vous diviserez par tous les pouvoirs de 3 pour chaque chiffre dans la représentation de base2.
On dirait que @woodchips a été capable de faire ce que vous avez dit ne peut être fait.
Il ne se charge pas dans des entiers mais il se charge toujours dans une représentation non binaire non ternie à des fins de traduction. C'est une solution intelligente mais c'est toujours un langage intermédiaire, donc je ne vois pas que c'est très différent. par exemple. Comment résolvez-vous 01 + 01 + 01 = 03 en binaire ou en ternaire? Vous ne pouvez pas.
Je pense que tout le monde manque quelque chose d'important. Tout d'abord, calculez une table à l'avance, pour chaque binaire binaire, nous avons besoin de la représentation en ternaire. À Matlab, je l'aurais construit comme ceci, bien que toutes les autres pas après cela se produisent purement à la main, le calcul est si facile. maintenant, considérez le nombre binaire 011000101 (qui Il se trouve être le nombre décimal 197, comme nous le saurons plus tard.) Extrayez la représentation ternaire pour chaque binaire binaire de la table. Je vais écrire les lignes correspondantes. P> base2dec('011000101',2)
ans =
197
base2dec('0021022',3)
ans =
197
Je noterai que cette approche fonctionne pour essentiellement une conversion directe entre toutes les bases de deux nombres, tant que vous calculez d'abord le tableau approprié en premier. Donc, si vous souhaitez convertir de la base 3 en Base 7, et faites-le plus d'une fois, vous pouvez le faire efficacement.
Si vous utilisez Ternaire codé binaire (une paire de bits par trit), vous pouvez convertir en utilisant une arithmétique parallèle. Voir Ce tutoriel .
Comment convaincuez-vous en décimale? Pourquoi cette même méthode ne fonctionnerait-elle pas à la conversion en ternaire?
@Stephen: Il recherche une conversion directe, aucune conversion intermédiaire en décimale.
@Jeff m: Droite. Il convertit de la base 2 en base 10 sans conversions intermédiaires. Le même algorithme lui permettra de convertir de la base 2 en base 3 sans conversions intermédiaires.
Conversion classique @Stephen: A * 2 ^ 0 + B * 2 ^ 1, etc. Donc, je vais devoir mettre en œuvre la multiplication en arithmétique ternaire. C'est ce que je voudrais éviter, juste pour le plaisir, de trouver un moyen délicat et rapide.
@Stephen: ah je vois ton point.
@Vadim Fedorov: Ah, eh bien, vous pouvez le faire sans avoir besoin d'arithmétique ternaire.