如何确定列表中的原子数是偶数还是奇数 [英] How to determine if a list has an even or odd number of atoms

问题描述

tScheme 新手问题:

tScheme novice question:

我需要使用递归来确定列表是否包含偶数或奇数的原子.我知道最简单的方法是获取列表长度并确定它是偶数还是奇数，但我想看看它是如何使用递归完成的.

I need to determine if a list contains an even or odd amount of atoms using recursion. I know the easy way is to get list length and determine if it is even or odd, but I would like to see hows it's done using recursion.

(oddatom 
  (LIST 'x 'y 'v 'd 'r 'h 'y))

应该返回#t，而

(oddatom 
  '((n m) (f p) l (u k p)))

应该返回#f

感谢您的帮助.

推荐答案

我喜欢 Chris Jester-Young 的回答，但是我认为值得提供一个尾递归版本来维护自己的堆栈.请注意，这是将非尾递归转换为尾递归的练习，这是Scheme中某些算法的重要技术.不过，在这种情况下，它可能不是那么重要，Chris Jester-Young 的回答中的代码确实感觉更自然.因此，将此作为练习，不一定是显着的改进.

I like Chris Jester-Young's answer, but I think it's worth providing a tail-recursive version that maintains its own stack as well. Note that this is an exercise in converting non-tail recursion into tail recursion, which is an imporant technique for some algorithms in Scheme. In this case, though, it's probably not all that important, and the code in Chris Jester-Young's answer does feel much more natural. So take this as an exercise, not necessarily a significant improvement.

这里的想法是内部函数 odd? 接受一个事物列表和一个值，该值指示到目前为止是否已经看到奇数个原子(除了空列表).

The idea here is that the inner function, odd?, takes a list of things, and a value indicating whether an odd number of atoms (other than the empty list) have been seen so far.

(define (oddatom? thing)
  (let odd? ((things (list thing))
             (result #f))
    (cond
      ;; We're out of things to see.  Did we see an odd number of things?
      ((null? things)
       result)
      ;; Our list of things has the form ((x . y) …), so we recurse on 
      ;; (x y …), with the *same* value for result, since we haven't 
      ;; "seen" x or y yet, we've just "unwrapped" them.
      ((pair? (car things))
       (odd? (cons (caar things) (cons (cdar things) (cdr things))) result))
      ;; Our list of things has the form (() …), so we recurse on 
      ;; (…), with the *same* value for result, since we haven't "seen" any
      ;; additional atoms.
      ((null? (car things))
       (odd? (cdr things) result))
      ;; Our list of things has the form (<atom> …), so we recurse on (…), 
      ;; but with a flipped value for result, since we've seen one more atom.
      (else
       (odd? (cdr things) (not result))))))

最后两种情况可以结合起来，使基于 (null? (car things)) 的值的第二个递归参数为:

The last two cases could be combined, making the second recursive argument based on the value of (null? (car things)) as:

(define (oddatom? thing)
  (let odd? ((things (list thing))
             (result #f))
    (cond
      ((null? things)
       result)
      ((pair? (car things))
       (odd? (cons (caar things) (cons (cdar things) (cdr things))) result))
      (else
       (odd? (cdr things) (if (null? (car things))
                              result
                              (not result)))))))

这篇关于如何确定列表中的原子数是偶数还是奇数的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！