如何计算一个列表中模式出现在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屋!