4

我对 lisp 相当陌生，这是练习问题之一。

首先，这个问题很简单scheme。我不知道如何回答这个问题。
这个问题的目的是编写一个函数，count-odd它以一个句子作为输入，并计算其中包含多少个奇数，如下所示：

（奇数'（234 556 4 10 97））6

或者

（奇数'（24680 42 88））0

如果可能的话，你怎么能做到这一点，使用高阶函数，或递归或两者兼而有之——无论什么都能完成。

4

5 回答 5

4

我会给你一些指示，而不是一个完整的解决方案：

首先，我看到了两种不同的方法，递归或高阶函数+递归。对于这种情况，我认为直接递归更容易理解。

所以我们需要一个函数，它接受一个列表并做一些事情，所以

(define count-odd
  (lambda (ls) SOMETHING))

所以这是递归的，所以我们想要拆分列表

(define count-odd
  (lambda (ls)
    (let ((head (car ls)) (rest (cdr ls)))
      SOMETHING)))

现在这有一个问题，它是一个空列表的错误（例如(count-odd '())），但我会让你弄清楚如何解决这个问题。提示，查看 scheme 的 case 表达式，方便查看和处理空列表

现在有些东西是我们的递归，所以对于类似的东西：

(+ (if (is-odd head) 1 0) (Figure out how many odds are in rest))

那应该给你一些开始。如果您稍后有任何具体问题，请随时发布更多问题。

于 2012-12-19T04:57:53.780 回答
1

请首先考虑其他答案指南，以便您尝试自己完成。以下是解决它的另一种方法。这是一个经过测试的完整解决方案：

(define (count-odd num_list)
    (if (null? num_list)
        0
        (+ (num_odds (car num_list)) (count-odd (cdr num_list)))))

(define (num_odds number)
    (if (zero? number)
        0
        (+ (if (odd? number) 1 0) (num_odds (quotient number 10)))))

这两个过程都是递归的。

  • count-odd不断获取列表的第一个元素并将其传递给，num_odds直到列表中没有元素为止（即基本情况，空列表）。

  • num_odds获取一个数字的奇数位数。为此，始终询问数字是否为奇数，在这种情况下它将加 1，否则加 0。然后将数字除以 10 以删除最低有效位（确定数字是奇数还是偶数）并传递为新调用的参数。该过程重复，直到数字为零（基本情况）。

于 2012-12-19T13:49:06.217 回答
0

如果其他一些解决方案看起来很奇怪，请不要感到困惑。firstSimply Scheme 对和使用非标准定义butfirst。这是一个解决方案，我希望遵循简单方案友好。

这是解决问题的一种策略：

  • 把数字变成数字列表
  • 转换为零和一的列表（零=偶数，一=奇数）
  • 添加列表中的数字

示例：123 -> '(1 2 3) -> '(1 0 1) -> 2

(define (digit? x)
  (<= 0 x 9))

(define (number->digits x)
  (if (digit? x)
      (list x)
      (cons (remainder x 10)
            (number->digits (quotient x 10)))))

(define (digit->zero/one d)
  (if (even? d) 0 1))

(define (digits->zero/ones ds)
  (map digit->zero/one ds))

(define (add-numbers xs)
  (if (null? xs)
      0
      (+ (first xs)
         (add-numbers (butfirst xs)))))

(define (count-odds x)
  (add-numbers 
     (digits->zero/ones 
        (number->digits x))))

以上内容未经测试，因此您可能需要修复一些拼写错误。

于 2012-12-19T23:27:13.663 回答
0

我认为这也是一个好方法。

(define (count-odd sequence)
  (length (filter odd? sequence)))

(define (odd? num)
  (= (remainder num 2) 1))

(count-odd '(234 556 4 10 97))

希望这会有所帮助~

(length 序列) 将返回序列的长度，
(filter proc 序列) 将返回一个包含所有满足 proc 的元素的序列。
您可以定义一个名为 (odd? num) 的函数

于 2012-12-20T09:08:30.637 回答
0

在跳转到更高阶的解决方案之前，尝试仅使用递归手动解决问题；为此，我建议看看其他答案。完成此操作后，使用您可以使用的工具寻求一个实用的解决方案 - 我会将问题分为两部分。

首先，如何在其数字列表中拆分正整数；这是对输入数字的递归过程。有几种方法可以做到这一点 - 首先将数字转换为字符串，或使用算术运算来提取数字，仅举几例。我将使用后者，并使用尾递归实现：

(define (split-digits n)
  (let loop ((n n)
             (acc '()))
    (if (< n 10)
        (cons n acc)
        (loop (quotient n 10)
              (cons (remainder n 10) acc)))))

有了这个，我们可以用高阶函数来解决问题，解决方案的结构反映了用于手动解决问题的心理过程：

  1. 首先，我们遍历输入列表中的所有数字（使用map）
  2. 拆分组成它的数字中的每个数字（使用split-digits）
  3. 计算这些数字中有多少是奇数，这给出了一个数字的部分解决方案（使用count）
  4. map在（使用apply）返回的列表中添加所有部分解决方案

这是它的外观：

(define (count-odd lst)
  (apply +
         (map (lambda (x)
                (count odd? (split-digits x)))
              lst)))
于 2012-12-19T13:58:35.173 回答