> 1 <

Автор Сообщение

vikssik

Members


Статус

9 сообщений

Где: Russia
Род занятий:
Возраст:

#1796   2010-04-04 14:15 GMT+3 часа(ов)      
Здравствуйте, необходимо реализовать сортировку слиянием. Единственный важный момент: обойтись без использования специфических ф-ии. т.е. допускается использование таких команд как: cons cond cdr car и т.п. но не сложнее!))


И еще...надо сделать задачу которая бы выводила список с количеством встречаемых элементов.
пример: дан список: (a b c b a c b m) вывести надо (a 2 b 3 c 2 m 1)

заранее спасибо! буду очень благодарна!!!

Михаил

Members


Статус

120 сообщений

Где: ---
Род занятий:
Возраст:

#1799   2010-04-04 23:47 GMT+3 часа(ов)      
(define (split L)
(letrec ((f (lambda (L A B)
(if (or (null? L) (null? (cdr L)))
(cons A B)
(f (cddr L) (cdr A) (cons (car A) B))))))
(f L L '())))
(define (merge pred A B)
(cond ((null? A) B)
((null? B) A)
((pred (car A) (car B))
(cons (car A) (merge pred (cdr A) B)))
(else
(cons (car B) (merge pred A (cdr B))))))
(define (merge-sort pred L)
(if (or (null? L) (null? (cdr L)))
L
(let ((s (split L)))
(merge pred
(merge-sort pred (car s))
(merge-sort pred (cdr s))))))

> (merge-sort <= '(44 2 3 8 12 19 6))
(2 3 6 8 12 19 44)

(reverse A) можно убрать, т.е. заменить на A.

Михаил

Members


Статус

120 сообщений

Где: ---
Род занятий:
Возраст:

#1800   2010-04-04 23:55 GMT+3 часа(ов)      
(define (pred x y)
(string<=? (symbol->string x)
(symbol->string y)))
(define (count-copy l c)
(if (or (null? l) (not (equal? (car l) c)))
0
(+ 1 (count-copy (cdr l) c))))
(define (f2 l)
(if (null? l)
'()
(let ((n (count-copy l (car l))))
(cons (car l)
(if (> n 0)
(cons n (f2 (list-tail l n)))
(f2 (cdr l)))))))
(define (f pred L)
(f2 (merge-sort pred L)))

> (f pred '(a b c b a c b m))
(a 2 b 3 c 2 m 1)

vikssik

Members


Статус

9 сообщений

Где: Russia
Род занятий:
Возраст:

#1809   2010-04-05 02:40 GMT+3 часа(ов)      
Михаил! Огромное спасибо!
> 1 <


Онлайн :

0 пользователь(ей), 60 гость(ей) :