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

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

01.11.2012, 13:27. Просмотров 4218. Ответов 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
Модератор
24741 / 12544 / 2289
Регистрация: 12.02.2012
Сообщений: 20,403
01.11.2012, 13:49 2
Лучший ответ Сообщение было отмечено как решение

Решение

Вот функциональное решение первой задачи (сортировка выбором):

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
;; вспомогательная функция min2
 
(defun min2 (x y) (if (< x y) x y))
 
==> min2
 
(min2 5 6)
 
==> 5
 
(min2 5 -6)
 
==> -6
 
;; распространение min2 на произвольное к-во чисел
 
(defun min! (x) (cond ((= (length x) 1) (car x))
                      ((= (length x) 2) (min2 (car x) (cadr x)))
                      (t (min2 (car x) (min! (cdr x))))))
 
==> min!
 
;; Удаление из списка первого вхождения атома 
 
(defun remove (x a) (cond ((null x) nil)
                          ((EQ a (car x)) (cdr x))
                          (t (cons (car x) (remove (cdr x) a))))) 
 
==> remove
 
(remove '(11 22 33 11 22 33) 33)
 
==> (11 22 11 22 33)
 
;; Сортировка выбором
 
(defun sort (x) (cond ((null x) nil)
                      (t (cons (min! x) (sort (remove x (min! x) ))))))
 
(sort '(1 2 -3 33 12))
 
==> (-3 1 2 12 33)
Добавлено через 14 минут
Вторая задача:

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
;; Вспомогательная функция сравнения структур
 
(defun equal (x y) (COND ((ATOM x) (EQ x y)) 
                                   ((ATOM y) NIL) 
                                   ((equal (CAR x) (CAR y)) (equal (CDR x) (CDR y))) (T NIL)))
 
==> equal
 
(equal '(1 2 3) '(1 2 3))
 
==> T
 
(defun isSublist(lst s) 
    (cond ((null lst) nil)
          ((atom (car lst)) (OR (equal (car lst) s) (isSublist (cdr lst) s))) 
          (t (OR (equal (car lst) s) (isSublist (car lst) s) (isSublist (cdr lst) s))))) 
 
==> isSublist
 
(isSublist '(1 2 3) 2)
 
==> T
 
(isSublist '(1 2 3) 7)
 
==> NIL
 
(isSublist '(1 2 (((7))) 3) 7)
 
==> T
 
(isSublist '(1 2 (((7))) 3) '(7))
 
==> T
1
zara11223344
0 / 0 / 0
Регистрация: 18.10.2012
Сообщений: 57
01.11.2012, 14:04  [ТС] 3
о боже вообще не понимаю(( с рекурсией вроде немного понятно но здесь(( блин куда я пошла учиться(
0
Catstail
Модератор
24741 / 12544 / 2289
Регистрация: 12.02.2012
Сообщений: 20,403
01.11.2012, 14:11 4
Цитата Сообщение от zara11223344 Посмотреть сообщение
о боже вообще не понимаю(( с рекурсией вроде немного понятно но здесь(( блин куда я пошла учиться(
- не паникуй! Позже я разъясню, как это работает.
1
01.11.2012, 14:11
zara11223344
0 / 0 / 0
Регистрация: 18.10.2012
Сообщений: 57
01.11.2012, 14:29  [ТС] 5
а вот ещё такие задания:
1.описать систему функций для задачи:написать функцию, сортирующую список символьных атомов по количеству литер в атомах.сортировка - любая, кроме прямого выбора.

Добавлено через 1 минуту
Цитата Сообщение от Catstail Посмотреть сообщение
- не паникуй! Позже я разъясню, как это работает.
эээм как вы мне это разъясните??
0
Catstail
Модератор
24741 / 12544 / 2289
Регистрация: 12.02.2012
Сообщений: 20,403
01.11.2012, 15:18 6
Цитата Сообщение от zara11223344 Посмотреть сообщение
эээм как вы мне это разъясните??
- ну... я предполагал расписать, что "делает" каждая строка. Но если не требуется - я не навязываю.
0
zara11223344
0 / 0 / 0
Регистрация: 18.10.2012
Сообщений: 57
02.11.2012, 00:25  [ТС] 7
Цитата Сообщение от Catstail Посмотреть сообщение
- ну... я предполагал расписать, что "делает" каждая строка. Но если не требуется - я не навязываю.
нет нет требуется ещё как)))) я просто чё то не додумалась как)) мне бы это очень помогло)
0
Catstail
Модератор
24741 / 12544 / 2289
Регистрация: 12.02.2012
Сообщений: 20,403
02.11.2012, 18:45 8
Сортировка по числу литер. Привожу решение для HomeLisp. В HomeLisp есть функция explode, разбивающая имя на литеры:

Lisp
1
2
3
(explode 'fgh)
 
==> (f g h)
Теперь напишем функцию, которая берет список символов, а возвращает список пар (Символ . К-во литер):

Lisp
1
2
3
4
5
6
7
(defun mkListL (lst) (mapcar #'(lambda (x) (cons x (length (explode x)))) lst))
 
==> mkListL
 
(mkListL '(asd h dd w eeq sa sss dd d))
 
==> ((asd . 3) (h . 1) (dd . 2) (w . 1) (eeq . 3) (sa . 2) (sss . 3) (dd . 2) (d . 1))
Теперь полученный список нужно отсортировать по полю длины (по вторым элементам пар). Воспользуемся версией быстрой сортировки:

Lisp
1
2
3
4
5
6
7
8
9
10
11
12
13
14
(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)))))))
==> qsorta
 
;; Проверим работу:
 
(qsorta (mkListL '(asd h dd w eeq sa sss dd d)))
 
==> ((d . 1) (w . 1) (h . 1) (dd . 2) (sa . 2) (dd . 2) (sss . 3) (eeq . 3) (asd . 3))
 
;; Сортирует верно...
Теперь из полученного списка нужно убрать вторые элементы пар (оставив только символы). Для этого - стандартный mapcar:

Lisp
1
2
3
(mapcar 'car '((d . 1) (w . 1) (h . 1) (dd . 2) (sa . 2) (dd . 2) (sss . 3) (eeq . 3) (asd . 3)))
 
==> (d w h dd sa dd sss eeq asd)
А теперь соберем все вместе:

Lisp
1
2
3
4
5
6
7
(defun task (lst) (mapcar 'car (qsorta (mkListL lst))))
 
==> task
 
(task '(qwe d f wwwwwww x cccccc))
 
==> (x f d qwe cccccc wwwwwww)
Все работает...
1
Catstail
Модератор
24741 / 12544 / 2289
Регистрация: 12.02.2012
Сообщений: 20,403
03.11.2012, 19:24 9
Выполняю обещание:

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
;; вспомогательная функция min2
 
(defun min2 (x y) (if (< x y) x y)) ;; если x < y вернет x, иначе y (минимум из двух чисел)
 
;; распространение min2 на произвольное к-во чисел
 
(defun min! (x) 
     (cond ((= (length x) 1) (car x))                 ;; если список сост. из одного числа, то мининум ему и равен
           ((= (length x) 2) (min2 (car x) (cadr x))) ;; если из двух - то вызываем min2
           (t (min2 (car x) (min! (cdr x))))))        ;; а иначе рекурсия - вызываем min2, примененный к 
                                                      ;; первому элементу и вызову min! на хвосте списка. 
 
;; Удаление из списка первого вхождения атома 
 
(defun remove (x a) 
     (cond ((null x) nil)                          ;; если список пуст - удалять нечего
           ((EQ a (car x)) (cdr x))                ;; если голова списка есть удаляемый атом - оставляем хвост
           (t (cons (car x) (remove (cdr x) a))))) ;; а иначе голову присоединяем к хвосту,
                                                   ;; из которого удален атом a 
  
;; Сортировка выбором
 
(defun sort (x) 
   (cond ((null x) nil)                                    ;; список пуст - сортировать нечего
         (t (cons (min! x) (sort (remove x (min! x) )))))) ;; иначе берем минмимум списка и 
                                                           ;; присоединяем его первым элементом к новому списку,
                                                           ;; который получается из сортировки исходного списка без первого минимума
 
(sort '(1 2 -3 33 12))
 
==> (-3 1 2 12 33)
Легче не стало?
1
zara11223344
0 / 0 / 0
Регистрация: 18.10.2012
Сообщений: 57
08.11.2012, 12:40  [ТС] 10
спасибо легче стало на многоэто все поняла.
0
Catstail
Модератор
24741 / 12544 / 2289
Регистрация: 12.02.2012
Сообщений: 20,403
08.11.2012, 13:11 11
Вот и славно...
1
zara11223344
0 / 0 / 0
Регистрация: 18.10.2012
Сообщений: 57
08.11.2012, 14:24  [ТС] 12
да это хорошо но тут у меня еще есть такие задания которые даже сюда не могу записать.вообще темный лес . . может расскажете принцип как можно уже наконец самой делать. я на основе вашей помощи пыталась решить другое задание но у меня не выходит.либо я совсем тупая либо не знаю.теоретически я понимаю как там нужно но на языке не могу реализовать, слишком много всяких функции и всех их не запомню. вы наверное долго изучаете лисп раз так все просто делаете? вам не составляет это труда?!?
0
Catstail
Модератор
24741 / 12544 / 2289
Регистрация: 12.02.2012
Сообщений: 20,403
08.11.2012, 14:46 13
Пишите, попробую помочь. Только по правилам нужно новый вопрос задавать в новой теме
0
zara11223344
0 / 0 / 0
Регистрация: 18.10.2012
Сообщений: 57
08.11.2012, 18:08  [ТС] 14
да я уже поняла...щас разберусь с тем что есть ещё раз и создам новую тему)

Добавлено через 1 час 57 минут
ТУТ Я ЗАБЫЛА ПРИПИСАТЬ..ТЕПЕРЬ И КОД ЗНАЧИТ ДРУГОЙ??
задание 2. написать функцию аргуметнов l1 И l2 , возвращающую Т , если l2 является подсписком l1
. Элементами списков могут быть атомы и списки сюбой глубины вложенности.
ЭТО НЕ ДРУГОЕ ЗАДАНИЕ!!! ПРОСТО НЕМНОГО НЕПРАВИЛЬНОЕ(ДЛЯ АДМИНА)))
0
_sg
4130 / 3877 / 294
Регистрация: 12.05.2012
Сообщений: 2,730
08.11.2012, 18:18 15
1.
Lisp
1
2
3
4
5
6
7
8
9
10
11
12
13
(defun selection-sort (w)
  (when w (cons (mini w) (selection-sort (remove (mini w) w)))))
 
(defun mini (w)
  (mi (cdr w) (car w)))
 
(defun mi (w m)
  (cond ((null w) m)
    ((< (car w) m) (mi (cdr w) (car w)))
        ((mi (cdr w) m))))
 
> (selection-sort '(5 4 7 1 3))
(1 3 4 5 7)
1
zara11223344
0 / 0 / 0
Регистрация: 18.10.2012
Сообщений: 57
08.11.2012, 18:18  [ТС] 16
у меня функция remove не работает(показывает ошибку
0
Catstail
Модератор
24741 / 12544 / 2289
Регистрация: 12.02.2012
Сообщений: 20,403
08.11.2012, 19:42 17
В каком Лиспе работаешь? И что за ошибка?

Вот реализация remove:

Lisp
1
2
3
4
(DEFUN remove (x L)
  (COND ((NULL L) NIL) 
        ((equal x (CAR L)) (remove x (CDR L)))
        (T (CONS (CAR L) (remove x (CDR L))))))
0
zara11223344
0 / 0 / 0
Регистрация: 18.10.2012
Сообщений: 57
08.11.2012, 20:19  [ТС] 18
Цитата Сообщение от Catstail Посмотреть сообщение
В каком Лиспе работаешь? И что за ошибка?

Вот реализация remove:

Lisp
1
2
3
4
(DEFUN remove (x L)
  (COND ((NULL L) NIL) 
        ((equal x (CAR L)) (remove x (CDR L)))
        (T (CONS (CAR L) (remove x (CDR L))))))
нет всё спасибо...решила))

Добавлено через 1 минуту
а какой код в таком вроде несложном но непонятном задании: реализовать сортировку списка методом шелла.
и код с литерами немного не понимаю..там всё так запутано((
0
Catstail
Модератор
24741 / 12544 / 2289
Регистрация: 12.02.2012
Сообщений: 20,403
08.11.2012, 20:41 19
Шелловская сортировка непроста... Это надо на Лиспе сделать?
0
zara11223344
0 / 0 / 0
Регистрация: 18.10.2012
Сообщений: 57
08.11.2012, 20:47  [ТС] 20
да(
и ещё вопрос: где код про литеры и там функция explode она реализуется в обычном лиспе а не хоумлисп??

Добавлено через 27 секунд
я работаю в лиспворкс
0
08.11.2012, 20:47
Answers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
08.11.2012, 20:47

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

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

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


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

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

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