2

因此，我们班被分配了一项将十进制数转换为八进制表示的作业。我设法只是修补它直到它起作用，但我在理解它为什么起作用时遇到了一些问题。有没有可能以更简单的方式解释递归？谢谢。

(define octify
 (lambda (n)
  (cond
   ((zero? n) 0)
   ((zero? (quotient n 8)) n)
   (else  (+ (* 10 (octify (quotient n 8))) (remainder n 8))))))
4

3 回答 3

3

首先，“数字”不是十进制或八进制。“数字”是一个数学概念，它以某种格式与一堆位存储在计算机中。十进制和八进制指的是数字的不同字符串表示形式。也就是说，“十进制”和“八进制”等仅在谈论字符串时才有意义，并且可以将特定数字转换为十进制或八进制或其他形式的字符串。

生成整数的八进制（或其他基数）字符串表示是编程中常见的基本任务。您基本上已经弄清楚的算法：将数字的余数乘以基数得到最后一位数字，然后对数字的商进行递归以得到数字的其余部分（除最后一位外）。

您正在做的事情的奇怪之处在于您没有像通常为该任务所做的那样生成字符串。相反，您试图将其打包回一个数字中，以使生成的数字的十进制表示看起来像原始数字的八进制表示的样子。（这恰好是可能的，因为任何八进制表示也是某个数字的有效十进制表示。例如，使用十六进制是不可能的。）换句话说，您正在将数字转换为其八进制字符串表示，然后解析将该字符串转换为一个数字，就好像它是十进制表示一样。以数字 42 为例，其十进制表示为字符串“42”，八进制表示为字符串“52”。

您可能会感到困惑，因为您将其输入到解释器中，并且当您计算或打印一个数字时，它会输出十进制表示。但重要的是要了解数字与字符串完全不同。（如果您在解释器中计算了一个字符串，也许它会用引号或其他东西包围它。）如果您的程序输出八进制表示的字符串，而不是打印时看起来像它的数字，那将是最有意义的。

于 2012-01-30T02:17:47.970 回答
1

风靡全球的数字的主流表示法是位置记法。它是一种与商和余数运算的概念密切相关的表示，您从递归函数定义中可以看出这一点。这是为什么？

让我们先暂时搁置一下：位置符号并不是数字的唯一可行表示。经常出现的一种方法是计数方法，其中一个数字要么为零，要么比数字多一。我们可以用棍子。由于我们在谈论程序，所以让我们使用数据类型。

Number :== Zero
         | Successor(n) where n is a number

将其读作“一个数字要么是零，要么是另一个数字的后继”。或者，要在支持结构化表示（如 Racket）的 Scheme 中对其进行编码，我们可以这样写：

(define-struct Zero ())
(define-struct Successor (n))

例如，用这种符号表示三将是(Successor (Successor (Successor (Zero)))。（如果我没记错的话，这个表示叫做 Peano。）

处理这种结构化数据类型的函数通常具有与数据类型本身相同的形状。也就是说，在 Peano 中作用于表示的函数看起来像这样：

 ;; a peano-eating-function-template: peano-number -> ???
(define (a-peano-eating-function-template a-num)
   (cond [(Zero? a-num)
          ...]
         [(Successor? a-num)
          ...
          (a-peano-eating-function-template (Successor-n a-num)) 
          ...]

这...将是特定于您试图解决 Peano 数字的特定问题的东西。这是一个遵循他们正在处理的数据结构的函数的问题。作为 Peano-eating 函数的一个具体示例，下面是一个将钢琴变成一堆星星的函数：

;; peano->stars: peano-number -> string
;; Turn a peano in a string of stars.  We are all made of stars.
(define (peano->stars a-num)
  (cond [(Zero? a-num)
         ""]
        [(Successor? a-num)
         (string-append "*"
                        (peano->stars (Successor-n a-num)))]))

无论如何，因此数据类型自然会导致具有特定形状的函数。这导致我们回到位置符号。我们可以将位置符号捕获为数据类型吗？

事实证明我们可以！位置记法（例如十进制记法）的描述方式类似于皮亚诺数描述的工作方式。让我们将此表示称为 Base10，它看起来像这样：

Base10 :== Zero
         | NonZero(q, r) where q is a Base10, and r is a digit.

Digit :== ZeroD | OneD | TwoD | ... | NineD

如果我们想用一种结构语言具体化编程，

(define-struct Zero ())
(define-struct NonZero(q r))

(define-struct ZeroD ())
(define-struct OneD ())
(define-struct TwoD ())
(define-struct ThreeD ())
(define-struct FourD ())
;; ...

例如，数字42在 Base10 中可以表示为：

(NonZero (NonZero (Zero) (FourD)) (TwoD))

哎呀。这看起来有点……疯了。但是，让我们多依靠这一点。和以前一样，处理 Base10 的函数通常具有与 Base10 的结构相匹配的形状：

;; a-number-eating-function-template: Base10 -> ??? 
(define (a-number-eating-function-template a-num)
  (cond
    [(Zero? a-num)
     ...]
    [(NonZero? a-num)
     ... (a-number-eating-function-template (NonZero-q a-num))
     ... (NonZero-r a-num)]))

也就是说，我们几乎可以免费获得在 Base10 上工作的递归函数的形状，只需遵循 Base10 本身的结构即可。

...但这是处理数字的一种疯狂方式，对吧？嗯......记住四十二的古怪表示：

(NonZero (NonZero (Zero) (FourD)) (TwoD))

这是表示相同数字的另一种方式。

((0 * 10 + 4) * 10 + 2)

几乎一样的想法。在这里，让我们去掉更多的括号。我们可以用以下符号表示四十二：

42

我们的编程语言经过硬编码，知道如何处理这种数字表示法。

我们检查零的等价物是什么？我们知道那个。

(= n 0)   ;; or (zero? n)

我们检查非零的等价物是什么？简单的！

(> n 0)

NonZero-q 和 NonZero-r 的等价物是什么？

(quotient n 10)
(remainder n 10)

然后，我们几乎可以即插即用来获得递归函数的形状，这些函数在位置上处理它们的数字输入。

(define (a-decimal-eating-function-template n)
  (cond [(= n 0)
         ...]
        [(> n 0)
         ... (a-decimal-eating-function-template (quotient n 10))
         ... (remainder n 10)]))

看起来熟悉？:)

有关更多信息，请参阅如何设计程序之类的教科书。

于 2012-01-31T02:54:37.223 回答
0

显然，(octify 0)应该是 0 并且(octify n)对于 n 使得 0 < n < 8 是 n。下一个条件是复杂的。第一个问题是“(octify (quotient n 8))返回什么？”。对于基数为 10 的数字，除以 10 会删除最右边的数字 - 145/10=14（假设整数除法）。对于以 8 为基数的数字，除以 8 的工作方式类似。因此，如果定义正确（我们必须假设） ，则(octify (quotient n 8))返回一个除 n 的最后一位以外的所有数字。octify现在，我们需要把这个数字“推”到左边一个数字。将其乘以 10 即可，因为打印机将以 base-10 进行打印。 (remainder n 8)得到 n 的最后一位。现在我们有了第一个但很多的数字（最后一个数字是零）和最后一个数字，所以我们可以通过添加它们来组合它们。至此，函数完成，返回正确的值。

于 2012-02-02T04:54:38.747 回答