Konversi Basis Sewenang-wenang [ditutup]

10

Buat rutin yang mengambil array blok dalam satu sistem basis numerik, dan mengonversinya menjadi array blok dalam sistem basis numerik lain. Baik dari dan ke sistem bersifat arbitrer dan harus diterima sebagai parameter. Array input dapat berupa panjang arbitrer (Jika menggunakan bahasa di mana panjang array tidak disimpan dengan array, seperti C, parameter panjang harus diteruskan ke fungsi).

Begini cara kerjanya:

fromArray = [1, 1]
fromBase = 256
toBase = 16
result = convertBase(fromArray, fromBase, toBase);

Yang harus kembali [0, 1, 0, 1]atau mungkin [1, 0, 1]( 0s adalah opsional karena mereka tidak mengubah nilai jawabannya).

Berikut ini beberapa vektor uji:

  1. Vektor Tes Identitas

    fromArray = [1, 2, 3, 4]
fromBase = 16
toBase = 16
result = [1, 2, 3, 4]

  2. Vektor Uji Sepele

    fromArray = [1, 0]
fromBase = 10
toBase = 100
result = [10]

  3. Vektor Uji Besar

    fromArray = [41, 15, 156, 123, 254, 156, 141, 2, 24]
fromBase = 256
toBase = 16
result = [2, 9, 0, 15, 9, 12, 7, 11, 15, 14, 9, 12, 8, 13, 0, 2, 1, 8]

  4. Vektor Uji Sangat Besar

    fromArray = [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1]
fromBase = 2
toBase = 10
result = [1, 2, 3, 7, 9, 4, 0, 0, 3, 9, 2, 8, 5, 3, 8, 0, 2, 7, 4, 8, 9, 9, 1, 2, 4, 2, 2, 3]

  5. Vektor Dasar Tanpa Titik

    fromArray = [41, 42, 43]
fromBase = 256
toBase = 36
result = [1, 21, 29, 22, 3]

Kriteria / aturan lain:

  1. Semua variabel integer harus masuk dalam standar integer bertanda 32 bit untuk semua rentang input yang masuk akal.

  2. Anda dapat mengonversi ke representasi perantara, selama perantara tersebut tidak lebih dari sebuah array bilangan bulat bertanda 32 bit.

  3. Berharap untuk menangani basis dari 2 hingga 256. Tidak perlu mendukung basis yang lebih tinggi dari itu (tetapi jika Anda ingin, dengan segala cara).

  4. Berharap untuk menangani ukuran input dan output setidaknya hingga 1000 elemen. Solusi yang menskala elemen 2 ^ 32-1 akan lebih baik, tetapi 1000 tidak masalah.

  5. Ini tidak selalu tentang memiliki kode terpendek yang akan memenuhi aturan ini. Ini tentang memiliki kode terbersih dan paling elegan.

Sekarang, ini tidak sepele untuk dilakukan, jadi jawaban yang hampir berhasil mungkin diterima!

code-challenge number ircmaxell
sumber
Apakah # 1 berarti kita tidak bisa menggunakan tipe bigint?
Keith Randall
@Keith: Benar. Hanya bilangan bulat 32 bit.
ircmaxell
Anda mengatakan "integer yang ditandatangani" tetapi contohnya hanya untuk bilangan bulat positif, jadi: apakah kita harus menangani yang negatif?
Eelvex
@Eelvex: Saya tidak melihat perlunya menangani hal negatif. Jika negatif ditangani, itu akan berada di luar konverter.
ircmaxell
Apakah mereka selalu basis integer?
Peter Olson

Jawaban:

8

Python

# divides longnum src (in base src_base) by divisor
# returns a pair of (longnum dividend, remainder)
def divmod_long(src, src_base, divisor):
  dividend=[]
  remainder=0
  for d in src:
    (e, remainder) = divmod(d + remainder * src_base, divisor)
    if dividend or e: dividend += [e]
  return (dividend, remainder)

def convert(src, src_base, dst_base):
  result = []
  while src:
    (src, remainder) = divmod_long(src, src_base, dst_base)
    result = [remainder] + result
  return result
Keith Randall
sumber
Terima kasih. Saya mencari rutinitas seperti ini. Butuh beberapa saat untuk mengubahnya menjadi Javascript. Saya mungkin akan sedikit golf dan posting di sini untuk bersenang-senang.
Stephen Perelson
5

Inilah solusi Haskell

import Data.List
import Control.Monad

type Numeral = (Int, [Int])

swap              ::  (a,b) -> (b,a)
swap (x,y)        =   (y,x)

unfoldl           ::  (b -> Maybe (b,a)) -> b -> [a]
unfoldl f         =   reverse . unfoldr (fmap swap . f)

normalize         ::  Numeral -> Numeral
normalize (r,ds)  =   (r, dropWhile (==0) ds)

divModLongInt            ::  Numeral -> Int -> (Numeral,Int)
divModLongInt (r,dd) dv  =   let  divDigit c d = swap ((c*r+d) `divMod` dv)
                                  (remainder, quotient) = mapAccumR divDigit 0 (reverse dd)
                             in   (normalize (r,reverse quotient), remainder)

changeRadixLongInt       ::  Numeral -> Int -> Numeral
changeRadixLongInt n r'  =   (r', unfoldl produceDigit n)
  where  produceDigit  (_,[])   =  Nothing
         produceDigit  x        =  Just (divModLongInt x r')

changeRadix :: [Int] -> Int -> Int -> [Int]
changeRadix digits origBase newBase = snd $ changeRadixLongInt (origBase,digits) newBase

doLine line = let [(digits,rest0)] = reads line
                  [(origBase,rest1)] = reads rest0
                  [(newBase,rest2)] = reads rest1
              in show $ changeRadix digits origBase newBase

main = interact (unlines . map doLine . lines)

Dan menjalankan tes dari pertanyaan:

$ ./a.out 
[1,2,3,4] 16 16
[1,2,3,4]
[1,0] 10 100
[10]
[41, 15, 156, 123, 254, 156, 141, 2, 24] 256 16
[2,9,0,15,9,12,7,11,15,14,9,12,8,13,0,2,1,8]
[1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] 2 10
[1,2,3,7,9,4,0,0,3,9,2,8,5,3,8,0,2,7,4,8,9,9,1,2,4,2,2,3]
[41, 42, 43] 256 36
[1,21,29,22,3]
Geoff Reedy
sumber
Oh wow. Itu luar biasa! Sekarang, andai saja saya bisa memahaminya: -) ... (tapi itu tugas saya sekarang) ...
ircmaxell
5

R

Menangani ribuan elemen * dalam waktu kurang dari satu menit.

addb <- function(v1,v2,b) {
    ml <- max(length(v1),length(v2))
    v1 <- c(rep(0, ml-length(v1)),v1)
    v2 <- c(rep(0, ml-length(v2)),v2)
    v1 = v1 + v2
    resm = v1%%b
    resd = c(floor(v1/b),0)
    while (any(resd != 0)) {
        v1 = c(0,resm) + resd
        resm = v1%%b
        resd = c(floor(v1/b),0)
    }
    while (v1[1] == 0) v1 = v1[-1]
    return(v1)
}

redb <- function(v,b) {
    return (addb(v,0,b))
}

mm = rbind(1)

mulmat <- function(fromb, tob, n) {
    if (dim(mm)[2] >= n) return(mm)
    if (n == 1) return(1)
    newr = addb(mulmat(fromb,tob,n-1) %*% rep(fromb-1,n-1), 1, tob)
    newm = mulmat(fromb,tob,n-1)
    while (is.null(dim(newm)) || dim(newm)[1] < length(newr)) newm = rbind(0,newm)
    mm <<-  cbind(newr, newm)
    return(mm)
}

dothelocomotion <- function(fromBase, toBase, v) {
    mm  <<- rbind(1)
    return(redb(mulmat(fromBase, toBase, length(v)) %*% v, toBase))
}

* untuk> 500 elemen Anda harus menaikkan level rekursi default atau tidak me-reset mmmatriksdothelocomotion()

Contoh:

v1 = c(41, 15, 156, 123, 254, 156, 141, 2, 24)
dothelocomotion(256,16,v1)
2  9  0 15  9 12  7 11 15 14  9 12  8 13  0  2  1  8

dothelocomotion(256,36,c(41,42,43))
1 21 29 22  3

dothelocomotion(2,10, rep(1,90))
1 2 3 7 9 4 0 0 3 9 2 8 5 3 8 0 2 7 4 8 9 9 1 2 4 2 2 3
Eelvex
sumber
3

Versi JavaScript yang kurang jelas dan lebih cepat:

function convert (number, src_base, dst_base)
{
    var res = [];
    var quotient;
    var remainder;

    while (number.length)
    {
        // divide successive powers of dst_base
        quotient = [];
        remainder = 0;
        var len = number.length;
        for (var i = 0 ; i != len ; i++)
        {
            var accumulator = number[i] + remainder * src_base;
            var digit = accumulator / dst_base | 0; // rounding faster than Math.floor
            remainder = accumulator % dst_base;
            if (quotient.length || digit) quotient.push(digit);
        }

        // the remainder of current division is the next rightmost digit
        res.unshift(remainder);

        // rinse and repeat with next power of dst_base
        number = quotient;
    }

    return res;
}

Waktu komputasi bertambah sebagai o (jumlah digit 2 ).
Tidak terlalu efisien untuk jumlah besar.
Pengkodean baris base64 versi khusus memanfaatkan rasio dasar untuk mempercepat perhitungan.


sumber
melakukan pekerjaan putra dewa
bryc
2

Javascript

Terima kasih Keith Randall atas jawaban Python Anda. Saya berjuang dengan hal-hal kecil dari solusi saya dan akhirnya menyalin logika Anda. Jika ada yang memberikan suara untuk solusi ini karena berfungsi maka silakan juga memberikan suara untuk solusi Keith.

function convert(src,fb,tb){
  var res=[]
  while(src.length > 0){
    var a=(function(src){
      var d=[];var rem=0
      for each (var i in src){
        var c=i+rem*fb
        var e=Math.floor(c/tb)
        rem=c%tb
        d.length||e?d.push(e):0
      }
      return[d,rem]
    }).call(this,src)
    src=a[0]
    var rem=a[1]
    res.unshift(rem)
  }
  return res
}

Tes

console.log(convert([1, 2, 3, 4], 16, 16))
console.log(convert([1, 0], 10, 100))
console.log(convert([41, 15, 156, 123, 254, 156, 141, 2, 24], 256, 16))
console.log(convert([1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1], 2, 10))
console.log(convert([41, 42, 43], 256, 36))

/*
Produces:
[1, 2, 3, 4]
[10]
[2, 9, 0, 15, 9, 12, 7, 11, 15, 14, 9, 12, 8, 13, 0, 2, 1, 8]
[1, 2, 3, 7, 9, 4, 0, 0, 3, 9, 2, 8, 5, 3, 8, 0, 2, 7, 4, 8, 9, 9, 1, 2, 4, 2, 2, 3]
[1, 21, 29, 22, 3]
*/

Ini mungkin bisa menyusut banyak, tetapi saya sebenarnya ingin menggunakannya untuk proyek sampingan kecil. Jadi saya membuatnya tetap dapat dibaca (agak) dan mencoba untuk menjaga variabel tetap di periksa.

Stephen Perelson
sumber
bagaimana itu javascript? untuk setiap?
Hernán Eche
Tidak ada nama variabel di atas 3 karakter, for eachpernyataan yang sudah ketinggalan zaman, dan konstruk yang menarik seperti d.length||e?d.push(e):0... Apakah ini tantangan kode yang dikaburkan atau semacamnya? Anda dapat menulis hal yang sama dengan sintaks yang dapat dimengerti dan kinerja yang lebih baik.
@kuroineko Ini adalah kode golf. Apa yang kamu harapkan? Bersih, kode yang dapat dibaca menggunakan standar terkini? Saya tidak pernah mengklaim jawaban saya sempurna dan saya pasti tidak akan menggunakannya seperti dalam proyek produksi.
Stephen Perelson
Yah saya benar-benar membutuhkan algoritma ini dalam JavaScript untuk beberapa alasan, dan saya harus menulis ulang dari awal, mengambil solusi python sebagai basis. Saya menghargai kontribusi Anda, tetapi untuk tujuan praktis itu hampir tidak bisa digunakan sama sekali IMHO.
2

Mathematica

Tidak ada variabel yang ditentukan, input apa pun yang diterima asalkan sesuai dengan memori.

f[i_, sb_, db_] := IntegerDigits[FromDigits[i, sb], db];

Uji jalan: 

f[{1,2,3,4},16,16]
f[{1,0},10,100]
f[{41,15,156,123,254,156,141,2,24},256,16]
f[{1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,
   1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,
   1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1},2,10]
f[{41,42,43},256,36]

Di luar

{1,2,3,4}
{10}
{2,9,0,15,9,12,7,11,15,14,9,12,8,13,0,2,1,8}
{1,2,3 7,9,4,0,0,3,9,2,8,5,3,8,0,2,7,4,8,9,9,1,2,4,2,2,3}
{1,21,29,22,3}
Belisarius
sumber
1

Scala:

def toDecimal (li: List[Int], base: Int) : BigInt = li match {                       
  case Nil => BigInt (0)                                                             
  case x :: xs => BigInt (x % base) + (BigInt (base) * toDecimal (xs, base)) }  

def fromDecimal (dec: BigInt, base: Int) : List[Int] =
  if (dec==0L) Nil else (dec % base).toInt :: fromDecimal (dec/base, base)

def x2y (value: List[Int], from: Int, to: Int) =
  fromDecimal (toDecimal (value.reverse, from), to).reverse

Kode uji dengan tes:

def test (li: List[Int], from: Int, to: Int, s: String) = {
 val erg= "" + x2y (li, from, to)
 if (! erg.equals (s))
   println ("2dec: " + toDecimal (li, from) + "\n\terg: " + erg + "\n\texp: " + s)
}   

 test (List (1, 2, 3, 4), 16, 16, "List(1, 2, 3, 4)")
 test (List (1, 0), 10, 100, "List(10)")
 test (List (41, 15, 156, 123, 254, 156, 141, 2, 24), 256, 16, "List(2, 9, 0, 15, 9, 12, 7, 11, 15, 14, 9, 12, 8, 13, 0, 2, 1, 8)") 
 test (List (1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1), 
   2, 10, "List(1, 2, 3, 7, 9, 4, 0, 0, 3, 9, 2, 8, 5, 3, 8, 0, 2, 7, 4, 8, 9, 9, 1, 2, 4, 2, 2, 3)") 
 test (List (41, 42, 43), 256, 36, "List(1, 21, 29, 22, 3)")

Lulus semua tes.

Pengguna tidak diketahui
sumber
1

J, 109 105

Menangani ribuan digit tanpa keringat. Tidak ada bilangan bulat yang dirusak!

e=:<.@%,.|~
t=:]`}.@.(0={.)@((e{:)~h=:+//.@)^:_
s=:[t[:+/;.0]*|.@>@(4 :'x((];~[t((*/e/)~>@{.)h)^:(<:#y))1')

Contohnya

256 16 s 41 15 156 123 254 156 141 2 24
2 9 0 15 9 12 7 11 15 14 9 12 8 13 0 2 1 8

256 36 s 41 42 43
1 21 29 22 3

16 16 s 1 2 3 4
1 2 3 4

256 46 s ?.1000$45
14 0 4 23 42 7 11 30 37 10 28 44 ...

time'256 46 s ?.3000$45'  NB. Timing conversion of 3000-vector.
1.96s

Semakin pendek.

Eelvex
sumber
0

Smalltalk, 128

o:=[:n :b|n>b ifTrue:[(o value:n//b value:b),{n\\b}]ifFalse:[{n}]].
f:=[:a :f :t|o value:(a inject:0into:[:s :d|s*f+d])value:t].

tes:

f value:#[41 15 156 123 254 156 141 2 24]
  value:256
  value:16. 
    -> #(2 9 0 15 9 12 7 11 15 14 9 12 8 13 0 2 1 8)

f value:#[1 2 3 4]
  value:16
  value:16.
    -> #(1 2 3 4)

f value:#[1 0]
  value:10
  value:100.
    -> #(10)

f value:#[1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1]
  value:2
  value:10.
    -> #(1 2 3 7 9 4 0 0 3 9 2 8 5 3 8 0 2 7 4 8 9 9 1 2 4 2 2 3)

f value:#[41 42 43]
  value:256
  value:36.
    -> #(1 21 29 22 3)

dan untuk hiburan khusus Anda ( tantangan: mencari tahu, apa yang istimewa dari nilai input ):

f value:#[3 193 88 29 73 27 40 245 35 194 58 189 243 91 104 156 144 128 0 0 0 0]
  value:256
  value:1000.
    -> #(1 405 6 117 752 879 898 543 142 606 244 511 569 936 384 0 0 0)
blabla999
sumber