用于将基数10转换为基数N的算法
我正在寻找一种方法将基数为10的数字转换为基数为N的数字，其中N可以很大。 具体来说，我正在寻找转换到base-85并再次返回。 有谁知道一个简单的算法来执行转换？ 理想情况下它会提供如下内容：
to_radix(83992, 85) -> [11, 53, 12] 任何想法都表示赞赏！
罗亚
这是一个有趣的问题，所以我有点过分了：
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地址视为base-256数字并使用映射的标识和'.'来格式化IPv4地址'.' 作为分隔符：
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
这个伪代码非常简单。 从无符号整数中得到85：
digits := ''; while (number > 0) digit := number % 85 digits := base85Digit(digit) + digits number /= 85 // integer division so the remainder is rounded off end while
以10为基础：
mult := 1 result := 0 for each digit in digits // starting from the rightmost working left result += base10(digit) * mult mult *= 85 end for
只是一般伪码算法：
- 初始化空列表
- 取当前数字mod基数，将结果存储在列表前面
- 将当前数字除以基数和下限（整数除法完美地实现）
- 如果结果仍然大于零，则在＃2处重复
83992 / 85 = 988, reminder 12 988 / 85 = 11, reminder 53 11 / 85 = 0, reminder 11
以相反的顺序写下提醒：11,53,12来获取你的base-85号码。
要取回它：
11 * 85^2 + 53 * 85^1 + 12 * 85^0 = 83992
Fixnum#to_s对你没有帮助，因为它只能达到36 。
我很惊讶你已经达到85岁了。你能解释一下基数是如何工作的吗？
我能想到的最简单的算法是（在伪代码中）：
N = base-10 number 1) N mod 85 = 1st number 2) tempVal = floor(N/85) 3) if(tempVal > 0 && tempVal < 85) then tempVal= 2nd number else 2nd number = (tempVal mod 85), then goto step (2), replacing N with N1
Base 85对二进制数据的ASCII编码特别有用，我认为它是你正在使用它的。 （但是，如果这就是为什么你应该问问自己是否真的值得额外的麻烦以及Base 64是否足够好。）
如果您将其用作编码方案，那么您的工作将是将整数（4个字节）转换为5个base85数的组。 （你如何处理不是4字节倍数的事情取决于你 – 通常最后用零填充。有关详细信息，请参阅Base 85上的Wikipedia页面。）
基本算法非常简单：当填入基数85时，将余数除以85，然后除以重复，直到完成为止。 要再次返回，请重复添加该值并乘以85，直到完成为止。 我对Ruby并不十分熟悉，所以这里的代码是C / C ++ / Javaish风格，希望你可以解释：
// To base 85 unsigned int n = // your number byte b85[5]; // What you want to fill for (int i=0 ; i<5 ; i++) { b85[4-i] = (n%85); // Fill backwards to get most significant value at front n = n/85; } // From base 85 n = 0; for (int i=0 ; i< 5 ; i++) { n = n*85 + b85[i]; }
这不用担心溢出，而不用担心添加33进入ASCII范围，而不必担心零被编码为z的约定!!!!! ， 等等。
因为我觉得递归在答案中代表性不足我给出了以下草稿
def to_radix(int, radix) int == 0 ? [] : (to_radix(int / radix, radix) + [int % radix]) end