Wie man die Umwandlung von Dezimal in Binär implementiert

Question

Ich habe eine Funktion zur Umwandlung von Binär in Dezimal in Haskell implementiert und arbeite derzeit an einer Funktion, die eine Dezimalzahl in einen Binärwert umwandeln würde. (Mir ist bewusst, dass diese Funktionalitäten irgendwo verfügbar sind, obwohl sie nicht Teil von Prelude.hs sind)

Ich habe den folgenden Code für eine C-ähnliche prozedurale Sprache erstellt, habe jedoch Schwierigkeiten, ihn in das funktionale Paradigma zu überführen.

while (n > 0)
{
    if (n % 2 == 1)
        str = str + "1";
    else
        str = str + "0";
    n = n / 2;
}

Ich habe mich erst kürzlich in die funktionale Programmierung in Haskell gewagt, also bin ich ziemlich neu in der funktionalen Denkweise. Ich habe versucht, das oben Genannte sowohl mit Rekursion als auch mit Listenverständnis umzusetzen, bin mir aber nicht sicher, wie ich die Wachen und die Logik richtig platzieren soll, da dies mehrere Bedingungen beinhaltet. Ich benutze eine Int Liste, um die einzelnen Binärziffern zu speichern.

--Decimal to binary
toBin:: Int -> [Int]
toBin 0 = [0]
toBin n | (n % 2 == 1) =
        |(n % 2 == 0) = 

Ich habe verstanden, dass das obige Muster es dem Programm ermöglichen würde, entweder die Wache zu wählen und die Auswertung der Funktion zu beenden. Liege ich hier falsch?

Im Folgenden ist das, was ich mit primitiver Rekursion entwickelt habe, um eine beliebige Basis (kleiner als 10, anstelle der 2) in Dezimal umzuwandeln.

toDecimal :: [Int] -> Int
toDecimal [] = 0
toDecimal (x:xs) = (x * 2 ^(length xs)) + bin xs

Answer 1

Es gibt keinen % Operator; wahrscheinlich suchen Sie stattdessen nach `mod`:

toBin 0 = [0]
toBin n | n `mod` 2 == 1 = ...
        | n `mod` 2 == 0 = ...

Wachen ermöglichen es Ihnen, zwischen mehreren Zweigen einer Funktion zu wählen. In diesem Fall wird jedes ... das Ergebnis von toBin n sein, wenn die entsprechende Bedingung wahr ist. Um zwei Listen zusammenzufügen, können Sie den ++ Operator verwenden, und `div` entspricht der ganzzahligen Division:

toBin 0 = [0]
toBin n | n `mod` 2 == 1 = toBin (n `div` 2) ++ [1]
        | n `mod` 2 == 0 = toBin (n `div` 2) ++ [0]

Allerdings hat dies einige Probleme. Zum einen beginnt es das Ergebnis immer mit 0, was überflüssig ist; außerdem ist es langsam, ++ [1] zu verwenden, da es die gesamte Liste durchlaufen muss, um ein Element am Ende hinzuzufügen; es wäre besser, jedes Element während des Durchlaufs voranzustellen und am Ende das Ergebnis umzukehren.

Um diese Dinge zu beheben, werden wir toBin in eine Hauptfunktion und eine Hilfsfunktion aufteilen:

toBin 0 = [0]
toBin n = reverse (helper n)

helper 0 = []
helper n | n `mod` 2 == 1 = 1 : helper (n `div` 2)
         | n `mod` 2 == 0 = 0 : helper (n `div` 2)

In dieser Version verwenden wir den : Operator, der einen Wert und eine Liste nimmt und die Liste mit dem Wert an den Anfang voranbringt. Für 0 geben wir auch ein leeres Ergebnis in unserer Hilfsfunktion zurück und behandeln den Fall 0 stattdessen in toBin, damit im Ergebnis nicht mehr 0s als nötig enthalten sind.

Wir können den Code von helper vereinfachen, indem wir die Wachen komplett überspringen, da wir das Ergebnis von n `mod` 2 einfach erneut auf der rechten Seite schreiben:

helper 0 = []
helper n = (n `mod` 2) : helper (n `div` 2)

Zuletzt gibt es eine Funktion, die einen div und ein mod in einem Schritt ausführt, was effizienter sein kann:

helper 0 = []
helper n = let (q,r) = n `divMod` 2 in r : helper q

Als zusätzliche Anmerkung: Dies konvertiert eigentlich nicht von dezimal zu binär, sondern wandelt eine Ganzzahl in binär um; Haskell-Implementierungen speichern Ganzzahlen wahrscheinlich nicht im dezimalen Format, obwohl sie in diesem Format geschrieben und gedruckt werden. Um eine vollständige Umwandlung von dezimal zu binär durchzuführen, wäre eine Funktion erforderlich, die einen Dezimalstring in eine Ganzzahl umwandelt.

Answer 2

toBinary :: Int -> [ Int ]

toBinary 0 = [ 0 ]

toBinary n = toBinary ( n `quot` 2 ) ++ [ n `rem` 2 ]

Answer 3

Also ich habe in letzter Zeit darüber nachgedacht und ich bin auf eine großartige Lösung gekommen, der Code ist in Haskell und einfach, aber sehr effektiv, funktioniert aber nur auf positiven Zahlen, da ich noch nicht fortgeschritten genug bin, um zum Beispiel das Zweierkomplement zu berechnen oder andere Dinge, die mit dem Binärcode verbunden sind.

binarz :: Int -> [Int]
binarz 0 = []
binarz n = binarz (div n 2) ++ [(mod n 2)]

Answer 4

toBin :: Int -> [Int]
toBin 0 = [0]
toBin 1 = [1]
toBin n
    | n `mod` 2 == 0 = toBin (n `div` 2) ++ [0]
    | otherwise = toBin (n `div` 2) ++ [1]

0 und 1 sind triviale Fälle. Wenn n gerade ist, sollten Sie null am Ende anhängen, sonst hängen Sie eins an. Es ist eine gute Praxis, alles in Ihrem letzten Wächterausdruck zu erfassen (deshalb habe ich ansonsten verwendet, was dasselbe wie True ist)

Answer 5

Sie können die unfoldr-Funktion aus dem Modul Data.List und intToDigit aus dem Modul Data.Char verwenden:

dez2bin :: Int -> [Char]
dez2bin = reverse . map intToDigit . unfoldr (\x -> if x==0 then Nothing else Just(rem x 2, div x 2))

Hier führt die unfoldr-Funktion die Eingabe mit der bereitgestellten anonymen Funktion solange aus, bis sie Nothing zurückgibt, während sie den ersten Wert aus Just in einer Liste aggregiert. Diese Liste enthält Ints, die in Chars umgewandelt werden müssen, indem intToDigit verwendet wird. Anschließend werden sie umgekehrt, da sie in umgekehrter Reihenfolge gesammelt wurden. Eine Liste von Chars ist ein String in Haskell, also sind Sie fertig.