从十进制转换为非十进制并打印(无字符串、数组和递归)

Question

需要帮助了解如何将十进制数转换为非十进制形式(任意，由用户输入给出)并打印它。限制是不允许使用数组和字符串，虽然我为此编写了一个递归函数，但我正在考虑针对同一件事的非递归方法。

更多的是个人挑战/锻炼，而不是任何重要/严肃的事情，所以请随时告诉我该把自己推到哪里。

注意:我在本练习中使用 C 语言。

Answer 1

回想一下，基数 B 中的数字 x 表示如下:x = a_nBⁿ + ... + a₂B² + a₁B + a₀ ，其中0≤a_i 。请注意，将 x 除以 B 得到 a_nB^n-1 + ... + a ₂B + a₁ 余数 a₀/B 。换句话说， x mod B = a₀( mod是缩写 模，即除法后的余数)。

作为算法实现:

var x    = POSITIVE_INTEGER
var base = POSITIVE_INTEGER2
while x > 0
    print(x mod base)
    x = x div base    // Where "div" is integer division, equivalent to math.floor(x/base)
                      // This way we are discarding a_0.
                      // Next iteration we will get a_1, then a_2, etc.

这将以相反的顺序打印数字。

解决方法:我们不是调制以获得最低有效数字，而是调制以获得最高有效数字。我们通过注意到 x - (x mod Bⁿ) = a_n，其中 n 是最高有效数字。

var x    = POSITIVE_INTEGER
var base = POSITIVE_INTEGER2
var bn   // This is base**n, where `n` is the most significant digit.
while x > 0
    print(x - x mod bn) // Print out a_n
    x = x mod bn        // Discard a_n
    bn = bn / base      // Next iteration get a_(n-1), then a_(n-2), etc.

bn 可以计算为 base ** math.floor(math.log(x)/math.log(base)) 或通过执行

var bn = 1
while bn * base < x
    bn = bn * base