如何计算一个列表中模式出现在Scheme的另一列表中的次数

本文介绍了如何计算一个列表中模式出现在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?

祝你好运！