如何计算一个列表中模式出现在Scheme的另一列表中的次数 [英] How to compute the number of times pattern in one list appears in other list in Scheme

问题描述

我在Scheme计划中停留了大约5个小时.我正在处理的程序应将两个列表作为输入，然后计算第一个列表中的模式出现在第二个列表中的次数.

I am stuck up in a Scheme program for about 5 hours. The program that I am working on should take two lists as input and then compute the number of times the pattern within the first list appears on the second list.

例如:> (patt '(b c) '(a b c d e b c)) ==>答案= 2

For example : > (patt '(b c) '(a b c d e b c)) ==> answer = 2

(patt'(a b c)'(a b c a b c d e a b c c c))==>答案= 3

(patt '(a b c) '(a b c a b c d e a b c c c)) ==> answer = 3

(patt'(((a b)c)''(a b(a b)c d e b c))==>答案= 1

(patt '((a b) c) '(a b (a b) c d e b c)) ==> answer = 1

下面是我到现在为止的代码.

Below is the code that I have till now.

(define (patt lis1 lis2)
  (cond
    ((null? lis1) 0)
    ((null? lis2) 0)
    [(and (> (length lis1) 1) (eq? (car lis1) (car lis2))) (patt (cdr lis1) (cdr lis2))]
    ((eq? (car lis1) (car lis2)) (+ 1 (patt lis1 (cdr lis2))))
    (else (patt lis1 (cdr lis2)))
    ))

有人可以帮我解决这个问题吗?谢谢！

Can someone please help me solve this. Thanks!

推荐答案

您需要将问题分为几部分:

You need to divide the problem into parts:

(define (prefix? needle haystack)
  ...)

(prefix? '() '(a b c))        ; ==> #t
(prefix? '(a) '(a b c))       ; ==> #t
(prefix? '(a b c) '(a b c))   ; ==> #t
(prefix? '(a b c d) '(a b c)) ; ==> #f
(prefix? '(b) '(a b c))       ; ==> #t

(define (count-occurences needle haystack)
  ...)

因此，您可以想象搜索模式(count-occurences '(a a) '(a a a a)).当从第一个元素中找到它时，您需要在下一个元素上再次搜索.因此，由于匹配重叠，因此(a a a a)的结果为3.除了子列表以外的每个子列表都涉及使用prefix?

So with this you can imagine searching for the pattern (count-occurences '(a a) '(a a a a)). When it is found from the first element you need to search again on the next. Thus so that the result is 3 for the (a a a a) since the matches overlap. Every sublist except when it's the empty list involves using prefix?

祝你好运！

这篇关于如何计算一个列表中模式出现在Scheme的另一列表中的次数的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！