Вот LOOP
версия:
(defun spend-greedily (prices budget)
(loop
for spent = 0 then next-spent
for count from 0
for price in prices
for next-spent = (+ spent price)
while (< next-spent budget)
finally (return
(values count spent))))
Обратите внимание, что итерация останавливается, когда в prices
нет элемента price
или когда следующие расходы превысят бюджет. Я также возвращаю общую сумму, потраченную в дополнение к количеству.
(assert (equalp
(loop
for budget in '(3 10 20 28 29 100)
collect (list budget
(multiple-value-list
(spend-greedily '(5 10 13 20) budget))))
'((3 (0 0))
(10 (1 5))
(20 (2 15))
(28 (2 15))
(29 (3 28))
(100 (4 48)))))
Если вы сортируете последовательность, обратите внимание:
SORT
является деструктивным, и может повторно использовать исходное хранилище последовательностей любым удобным для него способом. Копировать или нет оригинальную последовательность (copy-seq
(или copy-list
)) - вопрос владение ; в случае сомнений или с буквальными данными вы должны отсортировать копию.
Но , вы не должны больше использовать исходную последовательность, вы должны использовать возвращаемое значение из sort
. Это имеет смысл, если вы рассматриваете список как цепочку понятий, которым sort
разрешено связывать другим способом. Тогда ваш первый список, который является главой оригинальной цепочки выражений, может фактически оказаться в середине отсортированного списка. Или структура цепочки может быть сохранена, но CAR
каждого списка изменяется. Фактические побочные эффекты, которые происходят с последовательностью, однако, не определены.
Подумайте об использовании STABLE-SORT
для управления тем, что происходит с парой предметов, равных w.r.t. Ваша функция сравнения: пары (x, y) , так что ни x , ни y для пользовательского <</em>. Это не важно в вашем случае, так как равные числа неразличимы, но с некоторыми объектами вы можете получить произвольный порядок для элементов, которые полагаются на детали реализации, а не на свойства объекта.