Следующая страница > 1 < [2]

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

artemt

Members


Статус

25 сообщений

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

#3131   2010-10-14 02:16 GMT+3 часа(ов)      
Задание : Напишите функцию swap-two-ellement, которая переставляет в списке-аргументе два указанных своими порядковыми номерами элемента в этом списке.

Решил : ( defun f1 ( a b lst1 ) ( let (( a1 ( nth a lst1))) ( progn ( setf ( nth a lst1 ) ( nth b lst1 )) ( setf ( nth b lst1 ) ( nth a1 lst1 )))))

Выполнение:
( setf lst1 '( 1 2 3 4 5 ))
( f1 0 4 lst1 ) => (5 2 3 4 2)

Вопрос: Где ошибка? Почему он прибавил единицу к первому элементу?

LinkFly

Members


Статус

152 сообщений

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

#3134   2010-10-14 03:43 GMT+3 часа(ов)      
Я хотел тебе помочь, но записанный тобой код не форматируется в slime из-за того, что после скобок в формах поставлены дурацкие пробелы, в итоге возится с этим лень. Так что, если больше никто не напишет - не удивляйся.

VH

Members


Статус

289 сообщений

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

#3136   2010-10-14 12:50 GMT+3 часа(ов)      
При условии, что порядковые номера задаются в правильной последовательности (сначала меньший, затем больший) и не выходят за границы (нижняя: 0, верхняя: длина_списка - 1)
(defun SWAP-TWO-ELEMENT (L N1 N2)
(cond
((> N1 0)
(cons (car L) (SWAP-TWO-ELEMENT (cdr L) (1- N1) (1- N2))))
((> N2 1)
((lambda (result)
(cons (car result) (cons (cadr L) (cdr result))))
(SWAP-TWO-ELEMENT (cons (car L) (cddr L)) (1- N1) (1- N2))))
(T
(cons (cadr L) (cons (car L) (cddr L))))))

ander-skirnir

Members


Статус

227 сообщений
http://lisper.ru
Где: Ukraine
Род занятий: `'`,`',`',
Возраст: 30

#3139   2010-10-14 20:01 GMT+3 часа(ов)      
Можно еще так:
(defun swap-nth (list n1 n2 &aux place temp)
(sortf < n1 n2)
(prog1 list
(dotimes (i (1+ n2))
(cond ((= i n1)
(setf place list
temp (car list)))
((= i n2)
(setf (car place) (car list)
(car list) temp)))
(setf list (cdr list)))))


С sortf'ом советую разобраться - пару раз в неделю бывает полезен.
http://www.bookshelf.jp/texi/onlisp/onlisp_13.html#SEC93

Только следует обратить внимание, что get-setf-method
с тех пор переименовали в get-setf-expansion.

artemt

Members


Статус

25 сообщений

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

#3144   2010-10-15 00:20 GMT+3 часа(ов)      
Спасибо!
С этими рекурсиями голову свернёшь.
Пишу следующий код:
( setf '( 1 2 3 ))
( append ( cdr l ) ( car l )) -> ( 2 3 . 1 )
Не могу понять как избавиться от этой точки.
Если использовать cons, то точки нету! Но мне cons yt не подходит потому что делает вложенные списки.

ander-skirnir

Members


Статус

227 сообщений
http://lisper.ru
Где: Ukraine
Род занятий: `'`,`',`',
Возраст: 30

#3145   2010-10-15 00:32 GMT+3 часа(ов)      
> ( setf '( 1 2 3 ))
l убежала.

> Не могу понять как избавиться от этой точки.
Разберись с точечными парами. С тем, как работает cons, list, как вообще представляются списки.
(append (cdr l) (list (car l)))

artemt

Members


Статус

25 сообщений

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

#3146   2010-10-15 00:56 GMT+3 часа(ов)      
ander-skirnir
Спасибо!
Я начал понимать! Car возвращает атом ( без скобок, т.е. без списка ). Cdr возвращает хвост в виде списка.
А append не может нормально соединить атом со списком, ему нужно подать 2 списка.

ander-skirnir

Members


Статус

227 сообщений
http://lisper.ru
Где: Ukraine
Род занятий: `'`,`',`',
Возраст: 30

#3149   2010-10-15 01:36 GMT+3 часа(ов)      
Вообще-то нет.
Лучше всего представить себе списочные ячейки в виде пар квадратиков, где первый - car, второй - cdr.
Вот набросал рисуночек - слишком уж часто это вызывает непонимание у начинающих (мне-то повезло, я изучение практически с этого и начинал):

artemt

Members


Статус

25 сообщений

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

#3150   2010-10-15 01:51 GMT+3 часа(ов)      
ander-skirnir
Я на первых лабах чертил эти квадратики.

artemt

Members


Статус

25 сообщений

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

#3152   2010-10-15 01:53 GMT+3 часа(ов)      
Во! Ты мне хороший пример показал. Теперь я наконец-то понял чем точечная пара отличается от списка.

ander-skirnir

Members


Статус

227 сообщений
http://lisper.ru
Где: Ukraine
Род занятий: `'`,`',`',
Возраст: 30

#3153   2010-10-15 01:55 GMT+3 часа(ов)      
> Я на первых лабах чертил эти квадратики.
Наверное, и хорошо, что в моём универе Лисп не изучают - есть вероятность,
что я не так внимательно усваивал бы материал, как в случае самостоятельного изучения :)

LinkFly

Members


Статус

152 сообщений

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

#3158   2010-10-15 02:27 GMT+3 часа(ов)      
> ander-skirnir

Может быть, если бы не изучали математика в старших классах и в институте, было бы полно математиков? ;)

ander-skirnir

Members


Статус

227 сообщений
http://lisper.ru
Где: Ukraine
Род занятий: `'`,`',`',
Возраст: 30

#3159   2010-10-15 02:37 GMT+3 часа(ов)      
Не поверишь, думаю - было бы больше, чем есть. У многих преподов есть такой талант, как умение плохо преподнести даже интересный материал, что исчезает всякое желание вообще заниматься предметом. Кроме того, в учебных заведениях преподносят стандартный материал, а предметы - гораздо шире. Вполне вероятна ситуация, что у студента, которого тошнит от матана, теория групп и кристаллография - в крови. Самостоятельно, он нашел бы себя в математике, а так - и не посмотрит по сторонам.

artemt

Members


Статус

25 сообщений

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

#3160   2010-10-15 02:53 GMT+3 часа(ов)      
ander-skirnir
В любом случае нацию надо обучать. Без университетов никуда.

LinkFly

Members


Статус

152 сообщений

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

#3161   2010-10-15 02:55 GMT+3 часа(ов)      
Откуда, такие извращены берутся? Из институтов чтоли?
(setq ls '(1 2 3 4 5 6))
(rotatef (nth 0 ls) (nth 2 ls))

ander-skirnir

Members


Статус

227 сообщений
http://lisper.ru
Где: Ukraine
Род занятий: `'`,`',`',
Возраст: 30

#3163   2010-10-15 02:59 GMT+3 часа(ов)      
Ну зачем же так грубо?
Такой вариант, конечно, очевиден, но делает слишком много лишней работы.
Его сложность = O(n1+n2), в то время, как сложность двух вышеприведённых = O(max(n1,n2)).

ander-skirnir

Members


Статус

227 сообщений
http://lisper.ru
Где: Ukraine
Род занятий: `'`,`',`',
Возраст: 30

#3164   2010-10-15 03:20 GMT+3 часа(ов)      
(declaim (inline swap-nth))
(defun swap-nth (list n1 n2)
(sortf < n1 n2)
(prog1 list
(let (place temp)
(dotimes (i (1+ n2))
(cond ((= i n1)
(setf place list
temp (car list)))
((= i n2)
(setf (car place) (car list)
(car list) temp)))
(setf list (cdr list))))))
 
(declaim (inline swap-nth-2))
(defun swap-nth-2 (list n1 n2)
(rotatef (nth n1 list)
(nth n2 list)))
 
(defparameter *list* (make-list 1000))
 
(time
(dotimes (_ 1000000)
(swap-nth *list* 998 999)))
 
Evaluation took:
4.405 seconds of real time
4.352428 seconds of total run time (4.352428 user, 0.000000 system)
98.80% CPU
9,371,772,552 processor cycles
0 bytes consed
 
(time
(dotimes (_ 1000000)
(swap-nth-2 *list* 998 999)))
 
Evaluation took:
7.843 seconds of real time
7.831250 seconds of total run time (7.831250 user, 0.000000 system)
99.85% CPU
16,690,304,380 processor cycles
0 bytes consed


inline здесь нужен, чтобы абстрагироваться от оверхеда на сами вызовы функций, и сравнивать только время их фактической работы.

LinkFly

Members


Статус

152 сообщений

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

#3165   2010-10-15 03:30 GMT+3 часа(ов)      
"Задание : Напишите функцию swap-two-ellement, которая переставляет в списке-аргументе два указанных своими порядковыми номерами элемента в этом списке."

Что-то я тут ничего не вижу про сложность алгоритма.
Впрочем, как и про сложность кода ;)

ander-skirnir

Members


Статус

227 сообщений
http://lisper.ru
Где: Ukraine
Род занятий: `'`,`',`',
Возраст: 30

#3166   2010-10-15 03:36 GMT+3 часа(ов)      
Да ладно тебе отмазываться
Вообще хорошо, что ты привёл такой вариант, для разовых операций на небольших списках он вполне годится.
Теперь этот тред полностью решает задачу в зависимости от разных приоритетов.

artemt

Members


Статус

25 сообщений

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

#3170   2010-10-16 00:55 GMT+3 часа(ов)      
Цитата
VH :
При условии, что порядковые номера задаются в правильной последовательности (сначала меньший, затем больший) и не выходят за границы (нижняя: 0, верхняя: длина_списка - 1)
(defun SWAP-TWO-ELEMENT (L N1 N2)
(cond
((> N1 0)
(cons (car L) (SWAP-TWO-ELEMENT (cdr L) (1- N1) (1- N2))))
((> N2 1)
((lambda (result)
(cons (car result) (cons (cadr L) (cdr result))))
(SWAP-TWO-ELEMENT (cons (car L) (cddr L)) (1- N1) (1- N2))))
(T
(cons (cadr L) (cons (car L) (cddr L))))))




С этими рекурсиями можно голову поломать.
Я так и не могу до конца понять как это работает.
А мне ещё 2 лабораторных надо сделать ( в каждой по 10 заданий по мере возрастания ).

VH

Members


Статус

289 сообщений

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

#3172   2010-10-16 12:06 GMT+3 часа(ов)      
Да, "рекурсивное" мышление совсем другое в сравнении с "итеративным".
Зачастую полезен ход мысли "в обратном направлении" - с учетом результата, возвращаемого со следующего уровня рекурсии.
Однако Вам понравится, когда Вы освоите.
Но прежде всего исключите <для себя> «переменные» и связывание символа со значением (все эти set setq setf), как будто их нет вообще (так как они и не нужны), и используйте формальные параметры вызова функции (в том числе безымянной) - будет легче.
Тексты заданий предоставьте.

Fallen_s4e

Members


Статус

114 сообщений
http://lisper.ru
Где: Zimbabwe lisper.ru
Род занятий: fallen_s4e
Возраст: 8

#3175   2010-10-16 18:41 GMT+3 часа(ов)      
Цитата
Его сложность = O(n1+n2), в то время, как сложность двух вышеприведённых = O(max(n1,n2)).

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

ander-skirnir

Members


Статус

227 сообщений
http://lisper.ru
Где: Ukraine
Род занятий: `'`,`',`',
Возраст: 30

#3176   2010-10-16 18:50 GMT+3 часа(ов)      
Ок, в следующий раз напишу "количество итераций".

artemt

Members


Статус

25 сообщений

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

#3177   2010-10-16 19:09 GMT+3 часа(ов)      
Уютненький форум у вас. Не ожидал таких отзывчивых людей. Спасибо большое за помощь!
VH
Зачастую полезен ход мысли "в обратном направлении" - с учетом результата, возвращаемого со следующего уровня рекурсии.

Постараюсь щас пойти таким методом.
VH
Тексты заданий предоставьте.



Лабораторная работа № 6.
1. Что будет результатом (mapcar 'вектор '(570-40-) ?
2. Напишите функцию, которая уменьшает на 10 все числа из списка -aргумента этой функции.
3. Написать функцию, которая возвращает первый аргумент списка -аргумента, который сам является непустым списком.
4. Написать функцию, которая выбирает из заданного списка только те числа, которые больше 1 и меньше 10.
(Вариант: между двумя заданными границами.)
5. Написать функцию, вычисляющую декартово произведение двух
своих списков-аргументов. ( Напомним, что A x B это множество всевозможных пар (a b), где a принадлежит A , b принадлежит B.)

6. Почему так реализовано reduce, в чем причина?
(reduce #'+ ()) -> 0
(reduce #'+ ()) -> 0
7. Пусть list-of-list список, состоящий из списков. Написать функцию, которая вычисляет сумму длин всех элементов list-of-list, т.е. например для аргумента ((1 2) (3 4)) -> 4.
8. Написать рекурсивную версию (с именем rec-add) вычисления суммы чисел заданного списка.
Например: (rec-add (2 4 6)) -> 12
9. Написать рекурсивную версию с именем rec-nth функции nth.
10. Написать рекурсивную функцию alloddr, которая возвращает t , когда все элементы списка нечетные.
11. Написать рекурсивную функцию, относящуюся к хвостовой рекурсии с одним тестом завершения, которая возвращает последний элемент списка-аргумента.
12. Написать рекурсивную функцию, относящуюся к дополняемой рекурсии с одним тестом завершения, которая вычисляет сумму всех чисел от 0 до
n-ого аргумента функции.
Вариант: 1) от n-аргумента функции до последнего >= 0,
2) от n-аргумента функции до m-аргумента c шагом d.
13. Написать рекурсивную функцию, которая возвращает последнее нечетное число из числового списка, возможно создавая некоторые
вспомогательные функции.
14. Используя cons-дополняемую рекурсию с одним тестом завершения, написать функцию которая получает как аргумент список чисел,
а возвращает список квадратов этих чисел в том же порядке.
15. Написать функцию с именем select-odd, которая из заданного
списка выбирает все нечетные числа.
(Вариант1: select-even,
вариант 2: вычисляет сумму всех нечетных чисел(sum-all-odd) или сумму всех четных чисел (sum-all-even) из заданного списка.)

Лабораторная работа № 7.
Common Lisp
1. Написать итеративный вариант функции memberp, которая возвращает t или nil в зависимости от того, принадлежит ли первый аргумент второму, как элемент.
2. Написать итеративный вариант функции assoc c именем it-assoc.
3. Написать итеративный вариант функции length c именем it-length.
4. Написать итеративный вариант функции nth c именем it-nth.
5. Написать итеративный вариант функции reverse c именем it-reverse.
6. Написать итеративные варианты функций, вычисляющих объединение, разность и симметрическую разность двух множеств .
7. Используя в одном варианте dolist, а в другом do или do*, написать функцию, возвращающую наибольший элемент из списка чисел.
8. Используя в одном варианте dolist, а в другом do или do*, написать функцию, возвращающую первый нечисловой элемент заданного списка. Написать рекурсивный вариант этой же функции.
9. Написать итеративную и рекурсивную версии функции, которая
сортирует по возрастанию полученный набор чисел.

Fallen_s4e

Members


Статус

114 сообщений
http://lisper.ru
Где: Zimbabwe lisper.ru
Род занятий: fallen_s4e
Возраст: 8

#3178   2010-10-16 19:45 GMT+3 часа(ов)      
Я не совсем об этом.
В одну строчку решение, а медленнее менее чем в 2 раза. Но не суть.)

VH

Members


Статус

289 сообщений

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

#3179   2010-10-16 20:08 GMT+3 часа(ов)      
Warning: Используется LISP такой, что ортодоксальней некуда.
6.1.
Уточните текст задания.
6.2.
(defun F (L)
(if L
((lambda (elem result)
(cons
(if (numberp elem)
(- elem 10)
elem)
result))
(car L)
(F (cdr L)))))

Если список-аргумент состоит только из чисел, то можно проще:
(defun F (L)
(if L
(cons
(- (car L) 10)
(F (cdr L)))))

6.3.
(defun F (L)
(cond
((null L) nil)
((atom (car L)) (F (cdr L)))
(T (car L))))

6.4.
(defun F (L Inf Sup)
(if L
((lambda (elem result)
(if (numberp elem)
(if (< Inf elem Sup)
(cons elem result)
result)))
(car L)
(F (cdr L) Inf Sup))))

Если список-аргумент состоит только из чисел, то можно проще:
(defun F (L Inf Sup)
(cond
((null L) nil)
((< Inf (car L) Sup)
(cons
(car L)
(F (cdr L) Inf Sup)))
(T (F (cdr L) Inf Sup))))

отредактировал(а) VH: 2010-10-16 22:28 GMT+3 часа(ов)

artemt

Members


Статус

25 сообщений

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

#3180   2010-10-16 20:33 GMT+3 часа(ов)      
VHСпасибо большое. Но такие простые задания я сам могу решить! Смотри сложные задания с рекурсиями.
Есть краткая теория по Лиспу на русском? Кроме учебника, автора Тородняя, я ничего не нашел.

VH

Members


Статус

289 сообщений

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

#3181   2010-10-16 20:53 GMT+3 часа(ов)      
6.5.
По мотивам Хювёнен-Сеппянен "Мир Лиспа" т.1 стр.255:
(defun CARTESIAN_PRODUCT (A B) ; в оригинале ДЕКАРТОВО
(apply 'append
(mapcar
'(lambda (A)
(mapcar
'(lambda (B)
(list A B))
B))
A)))

отредактировал(а) VH: 2010-10-16 22:28 GMT+3 часа(ов)

VH

Members


Статус

289 сообщений

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

#3182   2010-10-16 21:03 GMT+3 часа(ов)      
6.7.
(defun F (L)
(cond
((null L) 0)
((null (car L)) (F (cdr L)))
(T (1+ (F (cons (cdar L) (cdr L)))))))

отредактировал(а) VH: 2010-10-16 22:28 GMT+3 часа(ов)

VH

Members


Статус

289 сообщений

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

#3183   2010-10-16 21:19 GMT+3 часа(ов)      
6.8.
(defun F (L)
(if L
(+
(if (numberp (car L)) (car L) 0)
(F (cdr L)))
0))

Если список-аргумент состоит только из чисел, то можно проще:
(defun F (L)
(if L
(+ (car L) (F (cdr L)))
0))

отредактировал(а) VH: 2010-10-16 22:29 GMT+3 часа(ов)


Онлайн :

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