0

我在想一种方法来创建一个不使用反向来检测回文的函数……我想我会很聪明，做一个条件，即子串 0 到中间等于子串端到中间。我发现它只适用于带有 3 个字母“wow”的单词，因为“w”=“w”。但如果字母像“wooow”，wo 不等于 ow。什么是不使用反向函数检测回文的方法？

提示或解决方案可能会很有帮助

(define (palindrome? str)
(cond
((equal? (substring str 0 (- (/ (string-length str) 2) 0.5))
         (substring str (+ (/ (string-length str) 2) 0.5) (string-length str))) str)
 (else false)))

哦，我正在使用初学者语言，所以我不能使用地图或过滤器之类的东西

是的，我知道这是一个非常没用的功能哈哈

4

3 回答 3

1

可以通过弄乱给定索引中的字符串字符来解决这个问题。诀窍是string-ref明智地使用。在这里，让我给您一些提示，指出适用于初学者语言的解决方案：

; this is the main procedure
(define (palindrome? s)
  ; it uses `loop` as a helper
  (loop <???> <???> <???>))

; loop receives as parameters:
; `s` : the string
; `i` : the current index, starting at 0
; `n` : the string's length
(define (loop s i n)
  (cond (<???>  ; if `i` equals `n`
         <???>) ; then `s` is a palindrome
        (<???>  ; if the char at the current index != its opposite (*)
         <???>) ; then `s` is NOT a palindrome
        (else   ; otherwise
         (loop <???> <???> <???>)))) ; advance the recursion over `i`

当然，有趣的部分是标有 的部分(*)。0想想看，如果索引处的字符等于索引处的字符n-1（n即字符串的长度）并且1索引处的字符等于索引处的字符，则字符串是回文n-2，依此类推。一般来说，如果索引处的字符确实i等于索引处的字符n-i-1（它的“相反”）对于 all i，那么我们可以得出结论该字符串是回文 - 但如果一对相反的字符不等于彼此，那么这不是回文。

作为进一步的优化，请注意您不需要遍历整个字符串，只需测试字符串长度的一半（这在 Chris 的回答中对此进行了解释）就足够了 - 直观地，您可以看到，如果char ati等于 char at n-i-1，那么 char atn-i-1等于 char at i，所以不需要两次执行相同的测试。

尝试自己编写程序，不要忘记测试它们：

(palindrome? "")
=> #t
(palindrome? "x")
=> #t
(palindrome? "axa")
=> #t
(palindrome? "axxa")
=> #t

(palindrome? "axc")
=> #f
(palindrome? "axca")
=> #f
(palindrome? "acxa")
=> #f
(palindrome? "axcta")
=> #f
于 2013-04-02T23:07:52.210 回答
1

这是一个创造性的答案

(define (palindrome list)
  (let halving ((last list) (fast list) (half '()))
    (cond ((null? fast)       (equal? half last))
          ((null? (cdr fast)) (equal? half (cdr last)))
          (else (halving (cdr last) (cddr fast)
                         (cons (car last) half))))))

它在列表的中间行进（fast用于查找结尾），建立第一个列表，half然后简单地使用列表equal?的half其余部分。

于 2013-04-03T03:42:45.477 回答
0

简单的。

  1. 对于每一个i，从 0 到floor(length / 2)，比较 indexi和 index 处的字符length - i - 1。
  2. 如果不匹配，则返回 false。
  3. 否则，如果循环用完，则返回 true。

骨架代码：

(define (palindrome? str)
  (define len (string-length str))
  (define halfway <???>)
  (let loop ((i 0))
    (cond ((>= i halfway) #t)
          ((char=? <???> <???>)
           (loop (+ i 1)))
          (else #f))))
于 2013-04-02T23:04:29.673 回答