一尘不染

一种将以10为底的数字转换为以N为底的数字的算法

algorithm

我正在寻找一种方法,可以将以10为底的数字转换为N可以很大的以N为底的数字。具体来说,我正在考虑转换为以85为基数并再次返回。有人知道执行转换的简单算法吗?理想情况下,它将提供以下内容:

to_radix(83992, 85) -> [11, 53, 12]

任何想法表示赞赏!

罗雅


阅读 337

收藏
2020-07-28

共1个答案

一尘不染

这是一个很有趣的问题,所以我有些过分了:

class Integer
  def to_base(base=10)
    return [0] if zero?
    raise ArgumentError, 'base must be greater than zero' unless base > 0
    num = abs
    return [1] * num if base == 1
    [].tap do |digits|
      while num > 0
        digits.unshift num % base
        num /= base
      end
    end
  end
end

这适用于任意基础。它仅适用于整数,尽管没有理由不能将其扩展为可使用任意数字。此外,它忽略数字的符号。再次,没有理由为什么 必须
这样做,但是主要是我不想提出在返回值中返回符号的约定。

class Integer
  old_to_s = instance_method(:to_s)
  define_method :to_s do |base=10, mapping=nil, sep=''|
    return old_to_s.bind(self).(base) unless mapping || base > 36
    mapping ||= '0123456789abcdefghijklmnopqrstuvwxyz'
    return to_base(base).map {|digit| mapping[digit].to_s }.join(sep)
  end
end

[Fixnum, Bignum].each do |klass|
  old_to_s = klass.instance_method(:to_s)
  klass.send :define_method, :to_s do |base=10, mapping=nil, sep=''|
    return old_to_s.bind(self).(base) unless mapping || base > 36
    return super(base, mapping, sep) if mapping
    return super(base)
  end
end

我还扩展了该to_s方法,使其可以使用大于36的底数。如果要使用大于36的底数,则必须传入一个将“数字”映射为字符串的映射对象。(实际上,所需要做的就是提供一个对象,该对象可以响应[]并返回响应的对象to_s。因此,字符串是完美的,但是例如整数数组也可以使用。)

它还接受一个可选的分隔符,该分隔符用于分隔数字。

例如,这允许您将IPv4地址设置为以256为基数的数字,并使用映射的标识和'.'分隔符来设置其格式:

2_078_934_278.to_s(256, Array.new(256) {|i| i }, '.') # => '123.234.5.6'

这是一个(不完整的)测试套件:

require 'test/unit'
class TestBaseConversion < Test::Unit::TestCase
  def test_that_83992_in_base_85_is_11_53_12
    assert_equal [11, 53, 12], 83992.to_base(85)
  end
  def test_that_83992_in_base_37_is_1_24_13_2
    assert_equal [1, 24, 13, 2], 83992.to_base(37)
  end
  def test_that_84026_in_base_37_is_1_24_13_36
    assert_equal [1, 24, 13, 36], 84026.to_base(37)
  end
  def test_that_0_in_any_base_is_0
    100.times do |base|
      assert_equal [0], 0.to_base(base)
      assert_equal [0], 0.to_base(1 << base)
      assert_equal [0], 0.to_base(base << base)
    end
  end
  def test_that_84026_in_base_37_prints_1od_
    assert_equal '1od_', 84026.to_s(37, '0123456789abcdefghijklmnopqrstuvwxyz_')
  end
  def test_that_ip_address_formatting_works
    addr = 2_078_934_278
    assert_equal '123.234.5.6', addr.to_s(256, (0..255).to_a, '.')
    assert_equal '123.234.5.6', addr.to_s(256, Array.new(256) {|i| i}, '.')
  end
  def test_that_old_to_s_still_works
    assert_equal '84026', 84026.to_s
    assert_equal '1su2', 84026.to_s(36)
  end
end
2020-07-28