我正试图将一个用Python编写的递归问题(第四个问题请参阅其repo页面了解详细信息(转换为(Common(Lisp
以下是我为了可读性而稍微编辑过的Python代码：
def coin(target,coins,res):
# Default output to target
min_coins = target
# Base Case
if target in coins:
res[target] = 1
return 1
# Return a known result if it happens to be greater than 1
elif res[target] > 0:
return res[target]
else:
# for every coin value that is <= than target
for i in [c for c in coins if c <= target]:
num_coins = 1 + coin(target-i,coins,res)
# Reset Minimum if we have a new minimum
if num_coins < min_coins:
min_coins = num_coins
res[target] = min_coins
return min_coins
target = 14
coins = [1,3,5]
res = [0]*(target+1)
print(coin(target,coins,res))
# => returns 4 ( 1 x 1, 1 x 3, 2 x 5)
这是我写的Lisp代码：
(defun coin (target coins res)
(let ((min_coins target))
(if (some (lambda (x) (= target x)) coins)
(progn
(setf (aref res target) 1)
1)
(if (> (aref res target) 0)
(aref res target)
(dolist (i (remove-if-not (lambda (x) (<= x target)) coins))
(let ((num_coins (1+ (coin (- target i) coins res))))
(when (< num_coins min_coins)
(setf min_coins num_coins)
(setf (aref res target) min_coins))
min_coins))))))
(coin 14 '(1 3 5) (make-array 15 :initial-element 0) )
当它被执行时，它会停止并出现以下错误：
The value
NIL
is not of type
NUMBER
如何安排它以使其正确运行？
更新：
(trace coin)之后是输出：
CL-USER> (coin 14 '(1 3 5) (make-array 15 :initial-element 0) )
0: (COIN 14 (1 3 5) #(0 0 0 0 0 0 0 0 0 0 0 0 0 0 0))
1: (COIN 13 (1 3 5) #(0 0 0 0 0 0 0 0 0 0 0 0 0 0 0))
2: (COIN 12 (1 3 5) #(0 0 0 0 0 0 0 0 0 0 0 0 0 0 0))
3: (COIN 11 (1 3 5) #(0 0 0 0 0 0 0 0 0 0 0 0 0 0 0))
4: (COIN 10 (1 3 5) #(0 0 0 0 0 0 0 0 0 0 0 0 0 0 0))
5: (COIN 9 (1 3 5) #(0 0 0 0 0 0 0 0 0 0 0 0 0 0 0))
6: (COIN 8 (1 3 5) #(0 0 0 0 0 0 0 0 0 0 0 0 0 0 0))
7: (COIN 7 (1 3 5) #(0 0 0 0 0 0 0 0 0 0 0 0 0 0 0))
8: (COIN 6 (1 3 5) #(0 0 0 0 0 0 0 0 0 0 0 0 0 0 0))
9: (COIN 5 (1 3 5) #(0 0 0 0 0 0 0 0 0 0 0 0 0 0 0))
9: COIN returned 1
9: (COIN 3 (1 3 5) #(0 0 0 0 0 1 2 0 0 0 0 0 0 0 0))
9: COIN returned 1
9: (COIN 1 (1 3 5) #(0 0 0 1 0 1 2 0 0 0 0 0 0 0 0))
9: COIN returned 1
8: COIN returned NIL
; Evaluation aborted on #<TYPE-ERROR expected-type: NUMBER datum: NIL>.
正确性
您的代码失败，因为您的dolist返回nil。
您需要更换
(dolist (i (remove-if-not (lambda (x) (<= x target)) coins)) ...)
带有
(dolist (i (remove-if-not (lambda (x) (<= x target)) coins) min_coins) ...)
效率
您在Python中通过在for循环中使用[]来创建免费列表，在Lisp中通过在dolist中使用remove-if-not来创建免费名单。谚语中的"；足够智能的编译器"；应该能够消除它，但Python3不够聪明，SBCL也不够聪明。
样式
代码可读性很重要。我建议修改你的代码：
def coin(target,coins,res):
# Default output to target
# Base Case
if target in coins:
res[target] = 1
return 1
# Return a known result if it happens to be greater than 1
if res[target] > 0:
return res[target]
# for every coin value that is <= than target
min_coins = target
for i in target:
if i <= target:
num_coins = 1 + coin(target-i,coins,res)
# Reset Minimum if we have a new minimum
if num_coins < min_coins:
min_coins = num_coins
res[target] = min_coins
return min_coins
和
(defun coin (target coins res)
(cond ((find target coins)
(setf (aref res target) 1))
((plusp (aref res target))
(aref res target))
(t
(let ((min-coins target))
(dolist (i coins min-coins)
(when (<= i target)
(let ((num-coins (1+ (coin (- target i) coins res))))
(when (< num-coins min-coins)
(setf min-coins num-coins)
(setf (aref res target) min-coins)))))))))
Common Lisp中一个相对相似的版本是：
(defun coin (target coins res)
(let ((min-coins target))
(cond ((member target coins)
(setf (elt res target) 1)
(return-from coin 1))
((plusp (elt res target))
(return-from coin (elt res target)))
(t (loop for i in (loop for c in coins when (<= c target) collect c)
for num-coins = (1+ (coin (- target i) coins res))
if (< num-coins min-coins)
do (setf min-coins num-coins)
else
do (setf (elt res target) min-coins))))
(return-from coin min-coins)))
(let* ((target 14)
(coins '(1 3 5))
(res (make-list (1+ target) :initial-element 0)))
(print (coin target coins res)))
Lisp和Python之间有一些基本的区别。其中四个是：
在Lisp中，所有表达式都返回值(零、一个或多个(。因此，像Python中那样调用
return或return-from通常不是Lisp风格。为了适应Lisp风格，可以将代码转换为不返回的版本。但如果不小心的话，这可能会带来错误。return-from需要块的名称才能从中返回。在Lisp中，基本数据结构是一个单链表。在Python中，它是数组之王。因此，可能需要不同的操作员，并且性能不同。在Lisp中，遍历列表、追加到末尾、随机访问等操作成本高昂。对于某些用途来说，这可能无关紧要，但通常更倾向于使用更符合目的的数据结构。所以这里我使用了Lisp列表，用向量(一维数组(代替它们可能会很有用。还有一种类型序列的想法，它为列表和向量提供通用操作。操作是
elt、remove、remove-if、concatenate、map和一堆其他操作。局部变量不能被引入到某些表达式序列的中间。需要像
let这样的特殊构造。Lisp中的迭代可以用LOOP 完成
是的，我用了不同的方法，但得出了类似的结论。添加了depth参数来计算它在递归过程中所做的操作。然后使用它来遵循Lisp脚本中的逻辑。使用此备忘单作为参考https://jtra.cz/stuff/lisp/sclr/index.html
#! /usr/bin/env python3
def coin( target, coins, result, depth ):
min_coins = target ## Default output to target
print( depth, result )
if target in coins: ## Base Case
result[ target ] = 1
return 1
# Return a known result if it happens to be greater than 1
elif result[ target ] > 0:
return result[ target ]
else:
# for every coin value that is <= than target
for i in [ c for c in coins if c <= target ]:
num_coins = 1 +coin( target -i, coins, result, depth +1 )
# reset Minimum if we have a new minimum
if num_coins < min_coins:
min_coins = num_coins
result[ target ] = min_coins
return min_coins
target = 14
coins = [ 1, 3, 5 ]
result = [0] *( target +1 )
print( coin( target, coins, result, 0 ) )
# => returns 4 ( 1 x 1, 1 x 3, 2 x 5)
#! /usr/bin/sbcl --script
(defun coin (target coins result depth)
"recursive coin count"
(let ((min_coins target)) ;; min_coins = target
(cond ((member target coins) ;; if target in coins:
(progn
(setf (aref result target) 1) ;; result[ target ] = 1
1)) ;; return 1
((> (aref result target) 0) ;; elif result[ target ] > 0:
(aref result target)) ;; return result[ target ]
((progn ;; for every coin value that is <= target
(dolist (i (remove-if-not (lambda (x) (<= x target)) coins))
;; num_coins = 1 +coin( target -i, coins, result, depth +1 )
(let ((num_coins (1+ (coin (- target i) coins result (+ depth 1)))))
(when (< num_coins min_coins) ;; if num_coins < min_coins:
(setf min_coins num_coins) ;; min_coins = num_coins
(setf (aref result target) min_coins)))) ;; result[ target ] = min_coins
min_coins)) ;; return min_coins
)
)
)
(defvar c 14)
(print (coin c '(1 3 5) (make-array (+ c 1) :initial-element 0) 0 ) )