从计划列表中获取最长子列表的大小
我想从列表中获取最长子列表的大小。从计划列表中获取最长子列表的大小
例如
(getlongest((A)B(demn)(AD(cmgcyumld)一)))
返回9自(cmgcyumld)具有尺寸9.
我写这功能
(define getlongest
(lambda (ls)
(cond
((null? ls)0)
(else
(cond
((atom? (car ls))
(+ 1 (getlongest (cdr ls))))
(else
(max (getlongest(car ls)) (getlongest(cdr ls)))))))))
但是如果我写
(getlongest ((a) (a (d d d e) m)))
我得到5.任何人都可以帮我解决这个问题吗?
感谢
所以你的代码的问题是,你计算1个长度您已经计数的列表的一部分,即使你去发现,该列表的子列表实际上是最长的。例如,您的代码也会返回5:(getlongest '(a (b (c (d (e))))))
。
您的方法很难轻易修复。我认为,你在递归时需要传递更多的数据。如果每次打电话给getlongest
知道当前长度,那么你应该能够得到正确的最大值。
如果这不是功课,这里就是我会本能地写相同的功能(不是尽可能有效,但简单的:)
(define (get-longest x)
(cond ((null? x) 0)
((atom? x) 1)
; else take either the length of this list, or of the longest sub-list
(else (apply max (length x) (map get-longest x)))))
“家庭作业”是如何暗示“不要求使用高阶函数”?我想认为FP上的_good_课程将尽可能多地鼓励HOF。 –
另外,你可以简化'apply'调用:'(apply max(length x)(map get-longest x))''。我发现额外的'cons'使得代码难以阅读。 –
我认为这个简单的问题是家庭作业可能意味着它适合于“如何递归思考简单问题”部分,在这种情况下,练习的要点是弄清楚如何构建递归解决方案,但是我取出了我的免责声明无论如何。感谢您的建议,我暂时忘了“apply”这样做。 – mquander
如果您跟踪通过与笔的节目的原因是很明显的和纸张。我建议你这样做,然后用你的发现来更新这个问题。提示:1.考虑如何在封面下形成列表。 2.(+ 1(getlongest(cdr ls)))'不符合你的期望,因为定义了'getlongest'的方式。 –
我知道有很多人发布作业,以便其他人可以为他们解决它。就我而言,我是这个初学者,花了我几个小时才想出这个错误的解决方案。如果我发布这个问题是因为我非常渴望找到解决方案。我已经通过几次纸质追踪迭代,我知道有什么不对,但我不知道如何解决。我正在努力提高我的技能,但我没有太多选择。我将通过一轮纸质追踪,看看我是否找到新的东西。 – locorecto
在这种情况下,用mquander的答案作为起点。 :-)如果你喜欢,追踪他们的版本,看看它与你的不同;尽管如此,姆坎德尔的回答已经详细解释了区别。 –