关于 Recursive...

Nickeolosophy

Write an iterative and a recursive version of theFibonacci series algorithm. You need to ensure the correctness of the bothalgorithms. Both algorithms should produce similar output if given a similarinput.

a.
Measure the performance of the two algorithms bymeasuring the time for both algorithms to listing out 10, 20, 30, 40, 50, 60,70 and 80 of Fibonacci numbers. The listing procedure could be done with aloop. For each test, repeat 3 times and get the average value.



看了几次，不是很明白问题在讲什么？

(我知道 recursive 不是 looping...)
请各位高手帮帮忙，谢咯。。。

yiquan1981

我忘记这个数列了，给个例子很容易的

Nickeolosophy

原帖由 yiquan1981 于 1-7-2009 04:58 PM 发表
我忘记这个数列了，给个例子很容易的

lecturer 也很够力下。。。
什么都不讲清楚，然后就丢给我们做了。。。
所以我也给不到 example...

Nickeolosophy

原帖由 yiquan1981 于 1-7-2009 04:58 PM 发表
我忘记这个数列了，给个例子很容易的

lecturer 也很够力下。。。
什么都不讲清楚，然后就丢给我们做了。。。
所以我也给不到 example...

onlylonly

题目很明白了喔。。。
有那一点是不清楚的？

ibonacci series， google 一下就有了

f(n) = f(n-1) + f(n-2)

一个用loop来些， 一个 recursive approach，两个不同的fibonacci 分别各跑
10, 20, 30, 40, 50, 60,70  80 个 fibonacci number，

记录时间， 重复3此， 拿平均时间。

Nickeolosophy

原帖由 yiquan1981 于 1-7-2009 04:58 PM 发表
我忘记这个数列了，给个例子很容易的

lecturer 也很够力下。。。
什么都不讲清楚，然后就丢给我们做了。。。
所以我也给不到 example...

yeenfei

原帖由 Nickeolosophy 于 1-7-2009 07:15 PM 发表


lecturer 也很够力下。。。
什么都不讲清楚，然后就丢给我们做了。。。
所以我也给不到 example...

我不懂是你的理解能力有限，还是英文不及格。。题目讲得很清楚了。。。

Write an iterative and a recursive version of the Fibonacci series algorithm.
Fibonacci 是一个序列演算法，每个数值为之前两个的总合, 如下：
0, 1, 1, 2, 3, 5, 8, 13

题目要求写出两个程序来运算出 N 个fibonacci value, 一个用普通的while/for condition looping, 另一个以recursive手法计算，也就是function会重复call自己直到满足特定条件

You need to ensure the correctness of the both algorithms. Both algorithms should produce similar output if given a similar input.
这个是废话，fibonacci series只有一个，如果你的程序算出来的答案不一样，肯定是你的问题

Measure the performance of the two algorithms by measuring the time forboth algorithms to listing out 10, 20, 30, 40, 50, 60,70 and 80 ofFibonacci numbers.
比较两种程序运算出 N 个fibonacci value的效率，怎么比较？看哪个用比较短的时间完成咯。。

The listing procedure could be done with a loop.
可以用loop来显示运算出来的fibonacci value, 也就是说程序运算时将答案放进准备好的array/variable, 过后才一次过显示出来。

For each test, repeat 3 times and get the average value.
以上试验各重复三次来得到平均值

Nickeolosophy

原帖由 onlylonly 于 1-7-2009 09:02 PM 发表
题目很明白了喔。。。
有那一点是不清楚的？

ibonacci series， google 一下就有了

f(n) = f(n-1) + f(n-2)

一个用loop来些， 一个 recursive approach，两个不同的fibonacci 分别各跑
10, 20, 30, 40, 5 ...

就是说，一个用 looping 做 ，一个用 recursive 做 ?

yiquan1981

0, 1, 1, 2, 3, 5, 8, 13
对就是这个数列， 你要我给答案吗？

onlylonly

对， 过后你会发现 fibonacci series recursive approach 很慢。 你的老师就是要你们明白何时不应该用 recursive， 还有为什么不应该用

yeenfei

原帖由 yiquan1981 于 1-7-2009 10:10 PM 发表
0, 1, 1, 2, 3, 5, 8, 13
对就是这个数列， 你要我给答案吗？

他们需要的不是答案,而是一个肯花心思学习的脑袋.
你给了这一次,下一个呢?

yiquan1981

再给我当复习，多好虽然我已经不用了

Nickeolosophy

原帖由 yiquan1981 于 1-7-2009 10:10 PM 发表
0, 1, 1, 2, 3, 5, 8, 13
对就是这个数列， 你要我给答案吗？

答案迟点给吧，我要试试做先。
pm me msn : yip_han88@hotmail.com

数据库专区

先試試寫簡單的 recursive 程式

譬如 要列印 1,2,3,4,5

我們會這樣寫

for i = 1 to 5
   print i
next

要列印 5,4,3,2,1
for i = 5 to 1 step -1
   print i
next

那麼不需要靠 loop 可否做得到呢
用 recursive 囉

call asc(1,5)
sub asc( i as integer, max as integer )
   if i <= max then
       print i
       asc(i+1,max)
   end if
end sub

call desc(1,5)
sub desc( i as integer, max as integer )
   if i <= max then
       desc(i+1,max)
       print i
   end if
end sub

asc 及 desc 的邏輯很相似 只是 desc  的 print i 的陳述移到 end if 之前了
使用 recursive 一定要設下中止條件 (terminate condition)
不然會永無止境的遞增至 stack memory 爆炸

當我們不知一個問題在什麼情況下有解答時
就可以用 recursive 來寫演算法 (algorithms)
像老鼠走迷宮
有一個入口及一個出口時
若迷宮地圖出口路徑是任意由電腦生成


或問題像 fibonacci, quicksort, tree graph, 要用 用各個擊破 (divide and conquer)  來解決
優先考慮使用 recursive 吧
它可以簡化問題的解決過程

這裡有詳細的 fibonacci 的解釋及 recursive 解答
http://en.wikipedia.org/wiki/Recursion_%28computer_science%29
http://en.wikipedia.org/wiki/Fibonacci_number

有空訪問一下這裡
http://en.wikipedia.org/wiki/Divide_and_conquer_algorithm

[ 本帖最后由 数据库专区 于 5-7-2009 10:21 AM 编辑 ]