Схема сплит операции не работает - PullRequest
Новая
       23

Схема сплит операции не работает

2 голосов
/ 02 декабря 2011

Я новичок в схеме и у меня возникли проблемы с отладкой моего кода. 

; returns number of elements in a list
(define (length L)
  (cond ((null? L) 0)
        (else (+ (length (cdr L)) 1))))

; split the list in half:
; returns ((first half)(second half))
(define (split L)
  (cond 
    ((= (length L) 0) (list L L) )
    ((= (length L) 1) (list L '() ))
    (else 
      (list (sublist L 1 (/ (length L) 2) 1)
            (sublist L (+ (/ (length L) 2) 1) (length L) 1)))))

; extract elements start to end into a list
(define (sublist L start end counter)
  (cond ((null? L) L)
        ((< counter start) (sublist (cdr L) start end (+ counter 1)))
        ((> counter end) '())
        (else (cons (car L) (sublist (cdr L) start end (+ counter 1))))))

Мне кажется, что это разделит один список на два подсписка. Возможно, есть более простой способ сделать это, и поэтому я прошу прощения, если это кажется громоздким.

В любом случае, результаты: 

Expected: (split '(1 2 3 4 5)) = ('(1 2) '(3 4 5))
Actual:  (split '(1 2 3 4 5)) = ('(1 2) '(4 5))

Понятно, что length или split теряет среднее значение, но я проверял его снова и снова, и оно, похоже, теряет среднее значение. Кажется, что простым решением было бы избавиться от (+ 1) от (+ (/ (length L) 2) 1), но мне это кажется нелогичным, как: 

Assume L = '(1 2 3 4 5), (/ (length L) 2) = 2, and (+ (/ (length L) 2) 1) = 3
(sublist L 1 (2) 1) = '(1 2)
(sublist L (3) 5 1) = '(3 4 5)
** I put parens around the 2 and 3 to indicate that they were length calculations.

Очевидно, что мое предположение неверно или я упускаю из виду что-то тривиальное.

Заранее спасибо!

Ответы [ 3 ]

6 голосов
/ 02 декабря 2011

Знаете ли вы алгоритм черепахи и зайца? Черепаха ходит по списку, заяц управляет списком с двойной скоростью. Раскол происходит в положении черепахи, когда заяц достигает конца списка. Вот большая часть кода; Я позволю вам выяснить остальное: 

(define (split xs)
  (let loop ((ts xs) (hs xs) (zs (list)))
    (if (or (null? hs) (null? (cdr hs)))
        (values (reverse zs) ts)
        (loop ...))))

Здесь ts - это оставшийся список предметов, которые должны быть проверены черепахой, hs - это оставшийся список предметов, которые должны быть исследованы зайцем, а zs - это список предметов, уже проверенных черепахой, в обратном порядке.

Обратите внимание, что вам никогда не нужно считать элементы в списке ввода.

2 голосов
/ 02 декабря 2011

Я не собираюсь отлаживать ваш код для вас. Вместо этого вот более простое определение split: 

(define (split l)
  (let ((n (length l)))
    (list (take (/ n 2) l)
          (drop (+ (/ n 2) (mod n 2)) l))))

Упражнение для читателя: реализовать take и drop. Последний является просто рекурсией на n, принимая cdr из l в рекурсивном случае; первый требует немного больше усилий, чтобы получить право в базовом случае (условие остановки).

0 голосов
/ 03 декабря 2011

Вот почти ваше решение (Схема Ракетки): 

#lang racket

(define (length lst)
  (cond [(empty? lst) 0]
        [else (+ (length (rest lst)) 1)]))

(define (first-length lst)
  (quotient (length lst) 2))

(define (second-length lst)
  (- (length lst) (first-length lst)))

(define (sublist lst start end counter)
  (cond [(empty? lst) lst]
        [(< counter start) (sublist (rest lst) start end (+ counter 1))]
        [(> counter end) '()]
        [else (cons (first lst) (sublist (rest lst) start end (+ counter 1)))]))

(define (first-half-of-list lst)
  (sublist lst 1 (first-length lst) 1))

(define (second-half-of-list lst)
  (sublist lst (second-length lst) (length lst) 1))

(define (split lst)
  (cond
    [(= (length lst) 0) (list lst lst)]
    [(= (length lst) 1) (list lst '())]
    [else (list (first-half-of-list lst) 
                (second-half-of-list lst))]))

(split '(1 2 3 4 5))

=> '((1 2) (3 4 5))

Спасибо за хорошее упражнение для мозга. Ключевой момент - функция «второй длины».

...