We have bunnies standing in a line, numbered 1, 2, ... The odd bunnies (1, 3, ..) have the normal 2 ears. The even bunnies (2, 4, ..) we'll say have 3 ears, because they each have a raised foot. Recursively return the number of "ears" in the bunny line 1, 2, ... n (without loops or multiplication).
我的尝试: public int bunnyEars2(int bunnies) { if (bunnies==0){ return 0; } else { return bunnies+bunnies%2+bunnyEars2(bunnies-1); } }
【 在 midpasse (事人) 的大作中提到: 】 : 我没有受过CS科班训练,碰到recursion的题都是没法找到好的思路下手。都是靠不断 : 去碰试,看看能不能碰出来一个正确的算法。 : 比如这么简单一道 : We have bunnies standing in a line, numbered 1, 2, ... The odd bunnies (1, 3 : , ..) have the normal 2 ears. The even bunnies (2, 4, ..) we'll say have 3 : ears, because they each have a raised foot. Recursively return the number of : "ears" in the bunny line 1, 2, ... n (without loops or multiplication). : 我的尝试: : public int bunnyEars2(int bunnies) { : if (bunnies==0){ : ...................
tree遍历的概念 先搞清楚 然后就容易了 【 在 midpasse (事人) 的大作中提到: 】 : 我没有受过CS科班训练,碰到recursion的题都是没法找到好的思路下手。都是靠不断 : 去碰试,看看能不能碰出来一个正确的算法。 : 比如这么简单一道 : We have bunnies standing in a line, numbered 1, 2, ... The odd bunnies (1, 3 : , ..) have the normal 2 ears. The even bunnies (2, 4, ..) we'll say have 3 : ears, because they each have a raised foot. Recursively return the number of : "ears" in the bunny line 1, 2, ... n (without loops or multiplication). : 我的尝试: : public int bunnyEars2(int bunnies) { : if (bunnies==0){ : ...................
【 在 midpasse (事人) 的大作中提到: 】 : 我没有受过CS科班训练,碰到recursion的题都是没法找到好的思路下手。都是靠不断 : 去碰试,看看能不能碰出来一个正确的算法。 : 比如这么简单一道 : We have bunnies standing in a line, numbered 1, 2, ... The odd bunnies (1, 3 : , ..) have the normal 2 ears. The even bunnies (2, 4, ..) we'll say have 3 : ears, because they each have a raised foot. Recursively return the number of : "ears" in the bunny line 1, 2, ... n (without loops or multiplication). : 我的尝试: : public int bunnyEars2(int bunnies) { : if (bunnies==0){ : ...................
【 在 midpasse (事人) 的大作中提到: 】 : 我没有受过CS科班训练,碰到recursion的题都是没法找到好的思路下手。都是靠不断 : 去碰试,看看能不能碰出来一个正确的算法。 : 比如这么简单一道 : We have bunnies standing in a line, numbered 1, 2, ... The odd bunnies (1, 3 : , ..) have the normal 2 ears. The even bunnies (2, 4, ..) we'll say have 3 : ears, because they each have a raised foot. Recursively return the number of : "ears" in the bunny line 1, 2, ... n (without loops or multiplication). : 我的尝试: : public int bunnyEars2(int bunnies) { : if (bunnies==0){ : ...................
【 在 midpasse (事人) 的大作中提到: 】 : 我没有受过CS科班训练,碰到recursion的题都是没法找到好的思路下手。都是靠不断 : 去碰试,看看能不能碰出来一个正确的算法。 : 比如这么简单一道 : We have bunnies standing in a line, numbered 1, 2, ... The odd bunnies (1, 3 : , ..) have the normal 2 ears. The even bunnies (2, 4, ..) we'll say have 3 : ears, because they each have a raised foot. Recursively return the number of : "ears" in the bunny line 1, 2, ... n (without loops or multiplication). : 我的尝试: : public int bunnyEars2(int bunnies) { : if (bunnies==0){ : ...................
我没有受过CS科班训练,碰到recursion的题都是没法找到好的思路下手。都是靠不断
去碰试,看看能不能碰出来一个正确的算法。
比如这么简单一道
We have bunnies standing in a line, numbered 1, 2, ... The odd bunnies (1, 3, ..) have the normal 2 ears. The even bunnies (2, 4, ..) we'll say have 3
ears, because they each have a raised foot. Recursively return the number of "ears" in the bunny line 1, 2, ... n (without loops or multiplication).
我的尝试:
public int bunnyEars2(int bunnies) {
if (bunnies==0){
return 0;
}
else {
return bunnies+bunnies%2+bunnyEars2(bunnies-1);
}
}
我试了好几个表达式,都得不到以下这个结果
bunnyEars2(0) → 0
bunnyEars2(1) → 2
bunnyEars2(2) → 5
bunnyEars2(3) → 7
bunnyEars2(4) → 10
bunnyEars2(5) → 12
bunnyEars2(6) → 15
bunnyEars2(10) → 25
请教如何解recursion的题,谢谢!
recursion没那么复杂,就是function可以call on itself, 但设置了先决条件不会死
循环。
比如计算fibonacci sequence, O(logn), 你这个例子就是这种。
解这玩意儿就看recursion发生在哪里。
recursive function弄不好会很慢,为了避免重复计算,下一步优化是加上hashtable
记录和调用已知计算结果。
【 在 midpasse (事人) 的大作中提到: 】
: 我没有受过CS科班训练,碰到recursion的题都是没法找到好的思路下手。都是靠不断
: 去碰试,看看能不能碰出来一个正确的算法。
: 比如这么简单一道
: We have bunnies standing in a line, numbered 1, 2, ... The odd bunnies (1, 3
: , ..) have the normal 2 ears. The even bunnies (2, 4, ..) we'll say have 3
: ears, because they each have a raised foot. Recursively return the number of
: "ears" in the bunny line 1, 2, ... n (without loops or multiplication).
: 我的尝试:
: public int bunnyEars2(int bunnies) {
: if (bunnies==0){
: ...................
tree遍历的概念 先搞清楚 然后就容易了
【 在 midpasse (事人) 的大作中提到: 】
: 我没有受过CS科班训练,碰到recursion的题都是没法找到好的思路下手。都是靠不断
: 去碰试,看看能不能碰出来一个正确的算法。
: 比如这么简单一道
: We have bunnies standing in a line, numbered 1, 2, ... The odd bunnies (1, 3
: , ..) have the normal 2 ears. The even bunnies (2, 4, ..) we'll say have 3
: ears, because they each have a raised foot. Recursively return the number of
: "ears" in the bunny line 1, 2, ... n (without loops or multiplication).
: 我的尝试:
: public int bunnyEars2(int bunnies) {
: if (bunnies==0){
: ...................
就是想多了。别想,如果有了小一号的答案,怎么扩展成下一步答案。
recursion和DP在思考上是一回事,实现的时候解空间的构造和维护不同而已。其实都
十分简单,搞不清就是想多了。
【 在 midpasse (事人) 的大作中提到: 】
: 我没有受过CS科班训练,碰到recursion的题都是没法找到好的思路下手。都是靠不断
: 去碰试,看看能不能碰出来一个正确的算法。
: 比如这么简单一道
: We have bunnies standing in a line, numbered 1, 2, ... The odd bunnies (1, 3
: , ..) have the normal 2 ears. The even bunnies (2, 4, ..) we'll say have 3
: ears, because they each have a raised foot. Recursively return the number of
: "ears" in the bunny line 1, 2, ... n (without loops or multiplication).
: 我的尝试:
: public int bunnyEars2(int bunnies) {
: if (bunnies==0){
: ...................
比如写个函数,f(n)
if n = 1 return 2
else {
if n is even, return f(n-1) +3
else return f(n-1) +2 }
意思一下。 我老不写代码谋生。 不明白这东西明明没用, 为啥还琢磨它,有这时间
,学点别的不好么?
这题要递归干啥?
if (n%2 == 0) {
return 5 * (n/2)
} else {
return 5 * (n/2) + 2
}
你要真想写递归,就是楼上那个写法
这一行有bug:
return bunnies+bunnies%2+bunnyEars2(bunnies-1);
应改成:
return 2+bunnies%2+bunnyEars2(bunnies-1);
【 在 midpasse (事人) 的大作中提到: 】
: 我没有受过CS科班训练,碰到recursion的题都是没法找到好的思路下手。都是靠不断
: 去碰试,看看能不能碰出来一个正确的算法。
: 比如这么简单一道
: We have bunnies standing in a line, numbered 1, 2, ... The odd bunnies (1, 3
: , ..) have the normal 2 ears. The even bunnies (2, 4, ..) we'll say have 3
: ears, because they each have a raised foot. Recursively return the number of
: "ears" in the bunny line 1, 2, ... n (without loops or multiplication).
: 我的尝试:
: public int bunnyEars2(int bunnies) {
: if (bunnies==0){
: ...................
Devide and conquer
【 在 midpasse (事人) 的大作中提到: 】
: 我没有受过CS科班训练,碰到recursion的题都是没法找到好的思路下手。都是靠不断
: 去碰试,看看能不能碰出来一个正确的算法。
: 比如这么简单一道
: We have bunnies standing in a line, numbered 1, 2, ... The odd bunnies (1, 3
: , ..) have the normal 2 ears. The even bunnies (2, 4, ..) we'll say have 3
: ears, because they each have a raised foot. Recursively return the number of
: "ears" in the bunny line 1, 2, ... n (without loops or multiplication).
: 我的尝试:
: public int bunnyEars2(int bunnies) {
: if (bunnies==0){
: ...................
(defn bunnies [num]
(loop [c 0 n num]
(cond
(zero? n) c
(odd? n) (recur (+ c 2) (dec n))
:else (recur (+ c 3) (dec n)))))
递归不需要动脑子
(time (bunnies 10))
"Elapsed time: 0.0359 msecs"
=> 25
【 在 mjmjmjmjmjmj (mjmjmjmjmjmj) 的大作中提到: 】
: 这题要递归干啥?
: if (n%2 == 0) {
: return 5 * (n/2)
: } else {
: return 5 * (n/2) + 2
: }
: 你要真想写递归,就是楼上那个写法
递归是简便方法,对程序栈有压力。考试时,有些题会说不许递归。
写递归注意几个点:
选择合适的递归入口
有解套代码,就是在这个点不是继续递归而是通过其他方式返回
递归深度不能太大
俺们中国人不是从初中就学了数学归纳法?一回事