2

  1. (CountDigits n)接受一个正整数n，并返回它包含的位数。例如，

    (CountDigits 1) → 1
(CountDigits 10) → 2
(CountDigits 100) → 3
(CountDigits 1000) → 4
(CountDigits 65536) → 5

我想我应该使用剩余的数字和其他东西，但除此之外，我真的迷路了。我首先尝试将数字除以 10，然后查看数字是否小于 1。如果是，则它有 1 个数字。如果它不除以 100，依此类推。但我不确定如何将其扩展到任何数字，所以我放弃了这个想法

(define (num-digits number digit) (if (= number digit 0) 1

4

3 回答 3

3

偶然发现了这一点，不得不提供基于日志的答案：

(define (length n)
    (+ 1 (floor (/ (log n) (log 10))))
)

为清楚起见进行编辑：这是一个不使用递归的 O(1) 解决方案。例如，给定

(define (fact n)
  (cond
    [(= n 1) 1]
    [else (* n (fact (- n 1)))]
  )
)

(define (length n)
  (+ 1 (floor (/ (log n) (log 10))))
)

运行（时间（长度（事实 10000）））产生

cpu time: 78 real time: 79 gc time: 47
35660.0

表示10000！产生一个由 35660 位数字组成的答案。

于 2017-10-26T22:39:43.187 回答
2

在评论中的一些讨论之后，我们想出了如何用x位取一个数字n并得到一个x-1位的数字：除以 10（使用整数除法，即我们忽略余数）。我们可以通过检查一个数字是否小于 10 来检查一个数字是否只有一位。现在我们只需要一种将数字的总位数表示为（递归）函数的方法。有两种情况：

  1. （基本情况）小于 10的数字n有 1 个数字。所以 CountDigits( n ) = 1。
  2. （递归情况）大于 10的数n具有 CountDigits( n ) = 1+CountDigits( n/10 )。

现在只需编写代码即可。这听起来像家庭作业，所以我不想放弃一切。您仍然需要弄清楚如何在 Scheme 中编写条件“ n < 10”以及“ n /10”（只是商部分），但一般结构是：

(define (CountDigits n)                       ; 1
  (if [n is less than 10]                     ; 2
      1                                       ; 3
      (+ 1 (CountDigits [n divided by 10])))) ; 4

对这些行的解释，一次一个：

  1. (define (CountDigits n)开始定义一个CountDigits名为 like的函数(CountDigits n)。
  2. 在 Racket 中，if用于评估一个表达式，称为测试或条件，然后评估并返回其余两个表达式之一的值。 (if test X Y)评估test，如果test产生true，则X评估并返回结果，否则Y评估并返回结果。
  3. 1是当n小于 10时要返回的值（上面的基本情况）。
  4. 1+CountDigits(n/10) 是您要以其他方式返回的值，在 Racket（和 Scheme，以及一般的 Lisp）中，它写为(+ 1 (CountDigits [n divided by 10])).

熟悉 Racket 文档的风格是一个好主意，所以我会为您指出相应的章节：3.2.2 Generic Numerics。您需要的功能应该在那里，并且文档应该提供足够的示例让您弄清楚如何编写缺失的位。

于 2013-10-22T23:48:39.130 回答
2

我知道这是旧的，但为了将来参考个人发现这个的任何人，我会这样写：

(define (count-digits n acc)
  (if (< n 10)
    (+ acc 1)
    (count-digits (/ n 10) (+ acc 1))))

不同之处在于这个是尾递归的，本质上等同于迭代函数（在内部，Racket 的迭代形式实际上利用了这个事实。）

使用 trace 说明了差异：

(count-digits-taylor 5000000)
>(count-digits-taylor 5000000)
> (count-digits-taylor 500000) 
> >(count-digits-taylor 50000)
> > (count-digits-taylor 5000)
> > >(count-digits-taylor 500)
> > > (count-digits-taylor 50)
> > > >(count-digits-taylor 5)
< < < <1
< < < 2
< < <3
< < 4
< <5
< 6
<7
7

(count-digits 5000000 0)
>(count-digits 5000000 0)
>(count-digits 500000 1)
>(count-digits 50000 2)
>(count-digits 5000 3)
>(count-digits 500 4)
>(count-digits 50 5)
>(count-digits 5 6)
<7
7

对于这个练习，这并不重要，但它是一种很好的学习方式。当然，由于原始帖子要求使用一个名为 CountDigits 的函数，它只接受一个参数 (n)，您只需添加：

(define (CountDigits n) 
  (count-digits n 0))
于 2016-07-04T21:23:47.273 回答