2

问题如下：

  1. 使用累积递归
  2. 函数消耗一个字符串并产生一个新字符串
  3. 连续出现的每个字符被替换为字母及其连续出现的次数
  4. 示例：“hellooo”=>“hel2o3”
  5. 问题是基于大学水平的

我尝试了以下方法：

(define (abbreviate str)
  (local [(define str-lst (string->list str))
          (define (count-duplicate lst char count)
            (cond
              [(empty? lst) count]
              [(equal? (first lst) char)
               (count-duplicate (rest lst)
                                (first lst)
                                (add1 count))]
              [else (count-duplicate (rest lst)
                                     (first lst)
                                     count)]))
          (define (build-string lst)
            (cond
              [(empty? lst) empty]
              [else (cons (first lst)
                          (cons (string->list (number->string 
                                         (count-duplicate (rest lst)
                                                          (first lst) 1)))
                          (build-string (rest lst))))]))]


    (build-string str-lst)))

但我得到了结果：

(list #\h (list #\4) #\e (list #\4) #\l (list #\4) #\l (list #\3) #\o (list #\3) #\o (列表#\2) #\o (列表#\1))

有什么帮助吗？

4

4 回答 4

2

首先对帮助程序进行单元测试，一些提示：

  • 如果累积递归是指尾递归，请注意：build-string不是尾递归，必须完全重写
  • count-duplicate没有按照您的预期进行 -(first lst)在递归调用中作为第二个参数传递是错误的
  • 你不是在计算连续的字符，你只是在计算字符的数量
  • 输出列表的构造不正确 - 为什么总是将一个字符与其频率粘在一起？仅当字符连续重复时才这样做
  • 预期的输出是一个字符串，而不是一个字符列表。在某些时候，您将不得不利用list->string
  • 此外，在某些时候，您必须将找到的字符数转换为字符，例如：3将变为#\3. 这是在末尾创建字符串所必需的

错误太多了，我的建议是从头开始，在将零件粘合在一起之前解决和测试子问题。但是我会帮助您完成该count-duplicate过程，请注意您只对给定字符的连续字符数感兴趣，这是正确的方法：

(define (count-duplicate lst char count)
  (cond [(or (empty? lst) (not (char=? char (first lst))))
         count]
        [else
         (count-duplicate (rest lst) char (add1 count))]))

你会这样使用它：

(count-duplicate (rest '(#\h #\e #\l #\l #\o)) #\h 1)
=> 1

(count-duplicate (rest '(#\h #\h #\h #\l #\o)) #\h 1)
=> 3

现在您必须确保对于原始字符串中的每个当前字符，您计算在列表的其余部分中找到了多少个连续字符，如果数字大于1，则以正确的方式构造输出列表。找到重复字符后不要忘记推进递归count字符，否则您将多次计算相同的字符！（提示：drop用于此）。

于 2013-06-04T02:39:05.627 回答
1

这有效，不包括将最终列表转换回字符串：

(define (abbreviate str)
  (let scanning ((list (string->list str))
                 (last #f)
                 (numb 1)
                 (rslt '()))
    (if (null? list)
        (reverse (if (= 1 numb) rslt (cons numb rslt)))  ; after reverse, make a string
        (let ((next (car list))
              (rest (cdr list)))
          (if (equal? last next)
              (scanning rest next (+ numb 1) rslt)
              (scanning rest next 1
                        (cons next (if (= 1 numb) rslt (cons numb rslt)))))))))

您可以看到它是完全尾递归的，并且在遍历字符串时会累积结果。

> (abbreviate "22")
(#\2 2)
> (abbreviate "")
()
> (abbreviate "hellllloo")
(#\h #\e #\l 5 #\o 2)
> (abbreviate "mississippi")
(#\m #\i #\s 2 #\i #\s 2 #\i #\p 2 #\i)
> (abbreviate "Noooooooooooooooooo way!")
(#\N #\o 18 #\space #\w #\a #\y #\!)
于 2013-06-04T19:36:52.160 回答
0

我假设，因为这是一个“大学水平”问题，你实际上是在为一门课学习球拍 - 我假设你正在使用高级学生语言包。

我对累积递归的理解是程序使用了某种类型的内存。这是我研究的一个解决方案。它是问题的完整解决方案，并且与高级学生语言包完全兼容；代码有点笨拙，但当然欢迎您对其进行改进。

;; abbreviate : string -> string
;; consumes a string and produces a new string, with all occurences of
;; sequences of repeating characters reduced to 1 character and the 
;; number of times the character repeats
;; Example
;; (abbreviate "oooo) should be "o4"
;; (abbreviate "thiis iss a teesstt") should be "thi2s is2 a te2s2t2"
;; (abbreviate "magic") should be "magic"
;; Definitions:
(define (abbreviate a-string)
  (local ((define memory empty)
          (define (count-dupes b)
            (cond ((empty? b) 0)
                  ((duplicate? b) (+ 1 (count-dupes (rest b))))
                  (else 0)))
          (define (skip-dupes c n)
            (cond ((= n 0) c)
                  ((empty? c) c)
                  (else (skip-dupes (rest c) (sub1 n)))))
          (define (duplicate? a)
            (equal? (first a) (first memory)))
          (define (load lst)
            (begin (set! memory (cons (first lst) memory)) (abbreviate-x (rest lst))))
          (define (abbreviate-x lst)
            (cond ((empty? lst) lst)
                  ((empty? memory) (cons (first lst) (load lst)))
                  ((duplicate? lst) (cons (+ 1 (count-dupes lst)) 
                                          (abbreviate-x 
                                            (skip-dupes lst (count-dupes lst)))))
                  (else (cons (first lst) (load lst)))))
          (define (string-adapt d)
            (cond ((empty? d) empty)
                  ((number? (first d)) (append (string->list (number->string (first d)))
                                               (string-adapt (rest d))))
                  (else (cons (first d) (string-adapt (rest d)))))))
    (list->string (string-adapt (abbreviate-x (string->list a-string))))))
;; Test
(check-expect (abbreviate "hellooo wooorldd") "hel2o3 wo3rld2"

亲切的问候

于 2013-06-05T16:26:03.157 回答
0

这是我对这个问题的看法。

第一个称为前缀的过程将告诉您在字符串的开头有多少个连续的相同字母。我正在使用string->list来处理列表而不是子字符串：

(define (prefix str)
  (let ((chars (string->list str)))
    (let loop ((chars chars) (c #\0) (l 0))
      (if (empty? chars)
          (values l c)
          (if (= l 0)
              (loop (cdr chars) (car chars) (add1 l))
              (if (char=? (car chars) c)
                  (loop (cdr chars) c (add1 l))
                  (values l c)))))))

它将返回 2 个值：出现次数和相关字符：

(prefix "")
0
#\0
(prefix "x")
1
#\x
(prefix "hello")          
1
#\h
(prefix "hhhello")     
3
#\h

第二个函数rle将使用第一个函数遍历字符串：

(define (rle str)
  (let loop ((str str) (res '()))
    (if (= (string-length str) 0)
        (string-join (reverse res) "")
        (let-values (((l c) (prefix str)))
          (loop (substring str l) 
                (cons 
                 (if (= l 1) 
                     (~a c)
                     (~a c l))
                 res))))))

如

(rle "hellooo wooorldd")
"hel2o3 wo3rld2"
于 2013-06-05T20:00:23.157 回答