Kennt irgendjemand eine Methode oder einen Algorithmus, um eine Zahl, die im System mit binären Zahlen dargestellt wird, in den ternären (meinen speziellen Fall) oder universellen Algorithmus für solche Umwandlungen umzuwandeln (oder auf eine Quelle zu zeigen)?
Die Lösung, die ich bereits implementiert habe, besteht darin, eine Zahl zuerst in Dezimalzahlen umzuwandeln und sie dann in das erforderliche Zahlensystem umzuwandeln. Das funktioniert, aber es gibt zwei Schritte. Ich frage mich, ob es in einem Schritt leicht gemacht werden könnte, ohne zuerst die ternäre Arithmetik zu implementieren? Gibt es einen Trick, Leute?
UPD: Es scheint, dass ich es nicht geschafft habe, klar zu beschreiben, nach welcher Art von Conversion ich suche. Ich frage nicht nach einige Möglichkeit, Base-2 zu Base-3 zu konvertieren, ich weiß, wie das geht. Sie können in Betracht ziehen, dass ich algebraische Datenstrukturen für ternäre und binäre Zahlen habe, in Haskell sieht es so aus:
%Vor%Und es gibt zwei offensichtliche Möglichkeiten, um eins zu einem anderen zu konvertieren: zuerst ist es in Integer zuerst zu konvertieren und das Ergebnis (nicht interessante Weise) zu erhalten, zweitens ist es, eigene Multiplikation und Addition in Base-3 zu implementieren und das Ergebnis zu multiplizieren Ziffernwerte zur jeweiligen Zweierpotenz (einfach und schwer).
Ich frage mich also, ob es eine andere Methode als diese beiden gibt.
Sie können einige kluge Abkürzungen zum Konvertieren verwenden. Der folgende Code ist die "falsche" Richtung, es ist eine Umwandlung von ternär zu binär basierend auf der Tatsache, dass 3 ^ 2 = 2 ^ 3 + 1 nur binäre Addition verwendet. Im Grunde konvertiere ich zwei Ternärziffern in drei Binärziffern. Von binär zu ternär wäre etwas komplizierter, da eine ternäre Addition (und wahrscheinlich eine Subtraktion) erforderlich wäre (daran zu arbeiten). Ich nehme die niedrigste Stelle im Kopf der Liste an (was nur sinnvoll ist), also müssen Sie die Zahlen "rückwärts" lesen.
%Vor%[Edit] Hier ist die binäre in ternäre Richtung, wie erwartet ein wenig länger:
%Vor%[Edit2] Eine etwas verbesserte Version von subT, die addT nicht benötigt
%Vor%Wenn du es mit einem Computer machst, sind die Dinge bereits in Binärform, also ist es einfach so, wie es nur geht, einfach dreimal durch 3 zu teilen und Reste zu nehmen.
Wenn Sie es mit der Hand machen, funktioniert die lange Division im Binärformat genauso wie die lange Division im Dezimalsystem. Teilen Sie einfach durch drei und nehmen Sie Reste. wenn wir mit 16 beginnen
%Vor%so in ternäre 121
Ich denke, dass jedem etwas Wichtiges fehlt. Berechnen Sie zuerst eine Tabelle im Voraus, für jedes binäre Bit benötigen wir die Darstellung in ternär. In MATLAB habe ich es so aufgebaut, obwohl jeder zweite Schritt danach von Hand gemacht wird, ist die Berechnung so einfach.
%Vor%Betrachten Sie nun die Binärzahl 011000101 (die zufällig die Dezimalzahl 197 ist, wie wir später herausfinden werden.) Extrahieren Sie die ternäre Darstellung für jedes Binärbit aus der Tabelle. Ich schreibe die entsprechenden Zeilen aus.
%Vor%Jetzt nur summieren. Wir bekommen diese Darstellung in ungetragener ternärer Form.
%Vor%Ja, das sind keine ternären Zahlen, aber sie sind fast in einer gültigen Basis-3-Darstellung. Jetzt müssen Sie nur noch die Überträge machen. Beginnen Sie mit der Einerstelle.
5 ist größer als 2, also subtrahieren Sie die Anzahl der Vielfachen von 3 und erhöhen Sie die zweite Ziffer des Ergebnisses entsprechend.
%Vor%Die zweite Ziffer ist jetzt eine 2, eine legale ternäre Ziffer, also weiter zur dritten Ziffer. Trage das auch,
%Vor%Schließlich ergibt sich die nun vollständig gültige Ternärzahl ...
%Vor%Waren meine Berechnungen korrekt? Ich lasse MATLAB das endgültige Urteil für uns fällen:
%Vor%Habe ich darauf hingewiesen, wie trivial diese Operation war, dass ich die Konvertierung komplett von Hand machen konnte, im Wesentlichen direkt von binär zu ternär, mindestens einmal hatte ich diese Initialtabelle aufgeschrieben und gespeichert?
Ich fürchte, ich weiß nicht genug Haskell, um das im Code ausdrücken zu können, aber ich frage mich, ob die Verwendung der Hornerschen Regel zur Auswertung von Polynomen eine Methode ergeben könnte.
Zum Beispiel kann ein x ^ 2 + b x + c als c + x * (b + x * a) ausgewertet werden.
Um zu konvertieren, sagen wir, die ternäre Zahl a * 9 + b * 3 + c zu binär, beginnt man mit der binären Darstellung von a, multipliziert diese mit 3 (dh shift und add), addiert dann die binäre Darstellung von b, multipliziert das Ergebnis mit 3 und fügt c.
hinzuEs scheint mir, dass dies mit einer Map (um die Binärdarstellung der ternären Ziffern zu erhalten) und einer Faltung (von a, b - & gt; a + 3 * b)
machbar ist Falls es sich um eine Hausaufgabe handelt, Pseudocode, um x in Basis b rückwärts zu schreiben:
Ich bin mir sicher, dass Sie herausfinden können, wie Sie das Ergebnis vorwärts anstatt rückwärts schreiben können. Beachten Sie, dass / eine C-artige Ganzzahl-Division sein muss (das Ergebnis ist eine Ganzzahl, die gegen Null abgeschnitten ist).
Beachten Sie, dass dies nicht überhaupt von der Basis abhängt, in der die Arithmetik ausgeführt wird. Arithmetik wird für ganze Zahlen definiert, nicht für die Darstellung von Ganzzahlen in einer bestimmten Basis.
Bearbeiten: Basierend auf Ihrer aktualisierten Frage würde ich die Zifferndarstellung in eine Ganzzahl (über ors und shifts) zerlegen und den oben beschriebenen Algorithmus mit Ganzzahlarithmetik verwenden.
Sicherlich könntest du es so machen, wie du es beschreibst, aber es scheint eine Menge Arbeit zu sein.
Ich glaube nicht, dass es einen super-effizienten Weg gibt.
"Die Lösung, die ich bereits implementiert habe ist eine Zahl in Dezimalzahlen umzuwandeln zuerst. "
Ich nehme an, dass Sie zuerst in einen eingebauten Integer-Typ konvertieren. Ich glaube nicht, dass Built-In Integer etwas mit Base 10 zu tun hat. (Wenn Sie es drucken, wird es jedoch eine Basis-10-Konvertierung geben.)
Vielleicht würden Sie erwarten, dass es einen Algorithmus gibt, der die Eingabe eine Ziffer nach der anderen betrachtet und die Ausgabe erzeugt.
Aber sagen Sie, dass Sie 3486784400 (Basis 10) in Basis 3 konvertieren möchten. Sie müssen jede Ziffer überprüfen, bevor Sie die Ausgabe erzeugen, weil
%Vor%.. auch
"Berechne die multiplizierende Zahl des Ergebnisses Werte zur jeweiligen Potenz von zwei "
das explizite Berechnen einer Potenz ist nicht erforderlich, siehe von Basis 60 in konvertieren Basis 10
Ich denke, es könnte verschiedene unterschiedliche "Ansichten" des Problems geben, obwohl ich mir nicht sicher bin, ob sie schneller oder besser sind. Zum Beispiel ist die untere Ordnung der 3-stelligen Zahl von n gerade n mod 3. Nehmen wir an, Sie haben bereits die binäre Repräsentation von n. Dann bedenke, wie die Potenzen von 2 mod 3 ausbilden. 2 ^ 0 = 1 mod 3, 2 ^ 1 = 2 mod 3, 2 ^ 2 = 1 mod 3, 2 ^ 3 = 2 mod 3, ... Mit anderen Worten , die Kräfte wechseln zwischen 1 mod 3 und 2 mod 3. Sie haben jetzt einen einfachen Weg, um die niedrigste Basis 3-stellig durch Scannen der Binärdarstellung von n und in der Regel nur Addition von entweder 1 oder 2 an jeder Bitposition zu bekommen wo eine 1 auftritt.
Nein, Sie können eine base2-Nummer nicht in eine base3-Zahl konvertieren, ohne sie in eine ganze Zahl zu laden. Der Grund ist, dass 2 und 3 Koprime sind - sie haben keine gemeinsamen Faktoren.
Wenn Sie mit base2 und base4 oder sogar base6 und base9 arbeiten würden, würde die Menge der ganzen Zahlen bis zum kleinsten gemeinsamen Vielfachen der zwei Basen durch zwei isomorphe Mengen repräsentiert. Zum Beispiel 13 (base4) = 0111 (base2), also 1313 (base4) = 01110111 (base2) umwandeln - es ist eine Operation zum Suchen und Ersetzen.
Zumindest die Lösung, die Sie haben und ist relativ einfach. Wenn Sie die Leistung verbessern müssen, konvertieren Sie die gesamte base2-Repräsentation in eine ganze Zahl, bevor Sie die base3-Konvertierung starten. es bedeutet weniger Moduloperationen. Die Alternative wäre, jedes Zeichen in der base2-Nummer eins nach dem anderen zu verarbeiten. In diesem Fall werden Sie durch alle Potenzen von 3 für jede Ziffer in der base2-Darstellung dividieren.
Tags und Links algorithm math theory numbers ternary-representation