Форум программистов, компьютерный форум, киберфорум
Наши страницы
Lisp
Войти
Регистрация
Восстановить пароль
 
 
Рейтинг 4.76/21: Рейтинг темы: голосов - 21, средняя оценка - 4.76
zara11223344
0 / 0 / 0
Регистрация: 18.10.2012
Сообщений: 57
1

Написать функцию сортировки списка методом прямого выбора

01.11.2012, 13:27. Просмотров 4230. Ответов 30
Метки нет (Все метки)

задание 1.
написать функцию сортировки списка методом прямого выбора. встроенные функции MAX и MIN не использовать.Можно использовать только средства строго функционального языка программирования(без использования функций присваивания)
задание 2. написать функцию аргуметнов , возвращающую Т если является подсписком. Элементами списков могут быть атомы и списки сюбой глубины вложенности.
0
Лучшие ответы (1)
QA
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
01.11.2012, 13:27
Ответы с готовыми решениями:

Написать функцию сортировки списка методом прямого выбора
написать функцию сортировки списка методом прямого выбора. встроенные функции MAX и MIN не...

Написать программу сортировки списка методом пузырька
С комментариями пожалуйста

Написать программу сортировки списка методом Шелла
Написать программу сортировки списка методом Шелла. Вычисление последовательности шагов сортировки...

Определить функцию THIRD выбора третьего элемента списка LST
Добрый вечер. Мне уже вчера очень помогли с решением, прошу помощи еще с одной задачей 1....

Сортировка массива методом прямого выбора и методом прямого обмена (пузырьковая)
Сортировка в Delphi массива из 6 двухзначных чисел. Методом прямого выбора и методом прямого...

30
Catstail
Модератор
24829 / 12624 / 2305
Регистрация: 12.02.2012
Сообщений: 20,542
08.11.2012, 20:50 21
Вот развернутое решение второй задачи:

Lisp
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
;; Вспомогательная функция, сравнивающая два списка на эквивалентность
 
(defun eq? (x y) 
  (cond ((and (null x) (null y)) t)
        ((Or (atom x) (atom y)) (eq x y)) 
        ((eq (car x) (car y)) (eq? (cdr x) (cdr y)))
        ((and (listp (car x)) (listp (car y))) (And (eq? (car x) (car y)) (eq? (cdr x) (cdr y))))
        (t nil)))
 
;; Решение
 
(defun sublist? (x y)
 (let ((l (length x)))   ;; запомним длину первого списка
  (cond ((null x) t)     ;; пустой список входит в любой 
        ((null y) nil)      ;; у пустого списка нет подсписков
        ((And (< l (length y)) (eq? x (subseq y 0 l))) t) ;; если x совпадает с началом y длины l - возврат t
        ((listp y)          ;; иначе, если y - список
         (cond ((eq? x (car y)) t) ;; если x совпадает с головой y - возврат t
               (t (Or (sublist? x (car y)) (sublist? x (cdr y)))))) ;; иначе или x входит в голову или в хвост
        (t nil))))          ;; иначе - nil
 
;; Проверки:
 
(sublist? '(1 2) '(1 2 3))
 
==> T
 
(sublist? '(1 2) '((1 2) 3))
 
==> T
 
(sublist? '(1 2) '((1 3)))
 
==> NIL
 
(sublist? '(1 2) '(1 3 1 2 4 5))
 
==> T
 
(sublist? '(1 2) '(1 3 (((1 2))) 4 5))
 
==> T
 
(sublist? '(1 2 (3)) '(1 3 (((1 2))) 4 5))
 
==> NIL
 
(sublist? '(1 2 (3)) '(1 3 (((1 2 3))) 4 5))
 
==> NIL
 
(sublist? '(1 2 (3)) '(1 3 (((1 2 (3)))) 4 5))
 
==> T
 
(sublist? '(1 2 (3)) '(1 3 (((1 2 (3)))) 4 5))
 
==> T
 
(sublist? 1 '(2 3 1 3))
 
==> T
 
(sublist? 1 '(2 3 3))
 
==> NIL
1
zara11223344
0 / 0 / 0
Регистрация: 18.10.2012
Сообщений: 57
08.11.2012, 21:51  [ТС] 22
у меня после проверки выводит ошибку..точнее не проверяет
CL-USER 8 : 2 > (sublist? '(1 2 (3)) '(1 3 (((1 2))) 4 5))

Error: In a call to LENGTH: 1 is not of type SEQUENCE.
1 (abort) Return to level 2.
2 Return to debug level 2.
3 Return to level 1.
4 Return to debug level 1.
5 Return to level 0.
6 Return to top loop level 0.

Type :b for backtrace, :c <option number> to proceed, or :? for other options
это что за ошибка..вроде всё так сделала

Добавлено через 57 секунд
и у вас немного другое решение ...в первом варианте было совсем по другому..чё то я совсем запуталась
0
Catstail
Модератор
24829 / 12624 / 2305
Регистрация: 12.02.2012
Сообщений: 20,542
08.11.2012, 22:04 23
Цитата Сообщение от zara11223344 Посмотреть сообщение
в первом варианте было совсем по другому
- про что речь?

А ошибка в этом коде моя (подработаю под Common Lisp)
1
zara11223344
0 / 0 / 0
Регистрация: 18.10.2012
Сообщений: 57
08.11.2012, 22:09  [ТС] 24
речь о первом варианте решения этой задачи которую вы присла самой первой"решение второй задачи"
я там всё наконец поняла....всё спасибо за них...я разобралась с вашей помощью...теперь перешла на литеры..там вот не понимаю как реализовать разделение на литеры в лиспворк....потому что explode, разбивающая имя на литеры в лиспворк не работает
0
08.11.2012, 22:09
Catstail
Модератор
24829 / 12624 / 2305
Регистрация: 12.02.2012
Сообщений: 20,542
08.11.2012, 22:12 25
Да, в LispWork explode нет. Завтра постараюсь помочь.
1
zara11223344
0 / 0 / 0
Регистрация: 18.10.2012
Сообщений: 57
08.11.2012, 22:18  [ТС] 26
СПАСИБО!!
0
foo
5 / 5 / 0
Регистрация: 31.10.2012
Сообщений: 23
08.11.2012, 22:31 27
Я не знаю как в лиспворкс... Но в Common Lisp есть во-первых функция length возвращающая длину последовательности, во-вторых, функция symbol-name, возвращающая имя символа в виде строки (которая является последовательностью). Таким образом, чтобы сравнить "длины" двух символов, можно воспользоваться примерно такой функцией:
Lisp
1
2
(defun less(a b)
    (< (length (symbol-name a)) (length (symbol-name b))))
Это я к тому, что explode вроде как и не нужен, если я правильно понял зачем он нужен (то есть, зачем он не нужен).
2
Catstail
Модератор
24829 / 12624 / 2305
Регистрация: 12.02.2012
Сообщений: 20,542
09.11.2012, 17:22 28
Уважаемый foo совершенно прав. В Common Lisp код работает после замены explode -> symbol-name (в единственном месте!):

Lisp
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
;; Построение списка пар 
 
(defun mkListL (lst) (mapcar #'(lambda (x) (cons x (length (symbol-name x)))) lst))
 
;; сортировка списка пар по полю CADR
 
(defun qsorta (x) (COND ((NULL x) NIL) 
                        (T (APPEND (qsorta (remove-if (FUNCTION (LAMBDA (z) (> (cdr z) (CDAR x)))) (CDR x)))
                                   (LIST (CAR x)) 
                                   (qsorta (remove-if (FUNCTION (LAMBDA (z) (<= (cdr z) (CDAR x)))) (CDR x)))))))
                           
;; Решение задачи
 
(defun task (lst) (mapcar 'car (qsorta (mkListL lst))))
 
;; Проверка:
 
> (task '(hgh j k k uuio iuoi o oiuiou))   
(O K K J HGH IUOI UUIO OIUIOU)             
>
Добавлено через 18 минут
Версия второй задачи (для Common Lisp):

Lisp
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
;; Сравнение на эквивалентность спис. структур
 
(defun eq? (x y) 
  (cond ((and (null x) (null y)) t)
        ((Or (atom x) (atom y)) (eq x y)) 
        ((eq (car x) (car y)) (eq? (cdr x) (cdr y)))
        ((and (listp (car x)) (listp (car y))) (And (eq? (car x) (car y)) (eq? (cdr x) (cdr y))))
        (t nil)))
 
;; обобщенная длина (для атома возвращает нуль)
 
(defun length? (x) (cond ((atom x) 0)
                         (t (length x))))
 
;; Решение
 
(defun sublist? (x y)
 (let ((l (length? x)))
  (cond ((null x) t)
        ((null y) nil)
        ((And (atom y) (eq? x y)) t)
        ((And (<= l (length? y)) (eq? x (subseq y 0 l))) t)
        ((listp y) 
         (cond ((eq? x (car y)) t)
               (t (Or (sublist? x (car y)) (sublist? x (cdr y))))))
        (t nil))))
 
(sublist? '(a b (c)) '(1 2 (a (a b (c))) 3 4))
 
==> T
2
zara11223344
0 / 0 / 0
Регистрация: 18.10.2012
Сообщений: 57
09.11.2012, 18:45  [ТС] 29
а можно спросить это всё в лиспворк будет работать????

Добавлено через 4 минуты
Цитата Сообщение от Catstail Посмотреть сообщение
Уважаемый foo совершенно прав. В Common Lisp код работает после замены explode -> symbol-name (в единственном месте!):

Lisp
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
;; Построение списка пар 
 
(defun mkListL (lst) (mapcar #'(lambda (x) (cons x (length (symbol-name x)))) lst))
 
;; сортировка списка пар по полю CADR
 
(defun qsorta (x) (COND ((NULL x) NIL) 
                        (T (APPEND (qsorta (remove-if (FUNCTION (LAMBDA (z) (> (cdr z) (CDAR x)))) (CDR x)))
                                   (LIST (CAR x)) 
                                   (qsorta (remove-if (FUNCTION (LAMBDA (z) (<= (cdr z) (CDAR x)))) (CDR x)))))))
                           
;; Решение задачи
 
(defun task (lst) (mapcar 'car (qsorta (mkListL lst))))
 
;; Проверка:
 
> (task '(hgh j k k uuio iuoi o oiuiou))   
(O K K J HGH IUOI UUIO OIUIOU)             
>
Добавлено через 18 минут
Версия второй задачи (для Common Lisp):

Lisp
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
;; Сравнение на эквивалентность спис. структур
 
(defun eq? (x y) 
  (cond ((and (null x) (null y)) t)
        ((Or (atom x) (atom y)) (eq x y)) 
        ((eq (car x) (car y)) (eq? (cdr x) (cdr y)))
        ((and (listp (car x)) (listp (car y))) (And (eq? (car x) (car y)) (eq? (cdr x) (cdr y))))
        (t nil)))
 
;; обобщенная длина (для атома возвращает нуль)
 
(defun length? (x) (cond ((atom x) 0)
                         (t (length x))))
 
;; Решение
 
(defun sublist? (x y)
 (let ((l (length? x)))
  (cond ((null x) t)
        ((null y) nil)
        ((And (atom y) (eq? x y)) t)
        ((And (<= l (length? y)) (eq? x (subseq y 0 l))) t)
        ((listp y) 
         (cond ((eq? x (car y)) t)
               (t (Or (sublist? x (car y)) (sublist? x (cdr y))))))
        (t nil))))
 
(sublist? '(a b (c)) '(1 2 (a (a b (c))) 3 4))
 
==> T
это про литеры???

Добавлено через 1 минуту
Цитата Сообщение от zara11223344 Посмотреть сообщение
а можно спросить это всё в лиспворк будет работать????

Добавлено через 4 минуты

это про литеры???
ааа простите я совсем запуталась((( это коды какой задачи???
0
Catstail
Модератор
24829 / 12624 / 2305
Регистрация: 12.02.2012
Сообщений: 20,542
09.11.2012, 19:29 30
Да, проверил. В LispWorks (и в XLisp) все работает.
1
zara11223344
0 / 0 / 0
Регистрация: 18.10.2012
Сообщений: 57
09.11.2012, 19:53  [ТС] 31
Цитата Сообщение от Catstail Посмотреть сообщение
Да, проверил. В LispWorks (и в XLisp) все работает.
да всё работает ..только я запуталась к какой задаче код?
0
09.11.2012, 19:53
Answers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
09.11.2012, 19:53

Написать программу, которая методом прямого выбора сортирует по убыванию введённый с клавиатуры массив
Здравствуйте, вот написал программу по сортировки массива по убыванию, но в нем надо чтобы значения...

Напишите процедуру сортировки линейного связного списка методом простого выбора с изменением указателей
Вот программа создающая линейный связный список. Type Ukazatel = ^S; S = Record Data : string;...

Написать процедуру сортировки массива методом простого выбора
помогите,плиз!? написать процедуру сортировки массива методом простого выбора


Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
31
Ответ Создать тему
Опции темы

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2019, vBulletin Solutions, Inc.