帮帮我~C Programing~

凯茹

这是我的功课 : -
1.Write an iterative and a recursive version of the Fibonacci series algorithm. You need to ensure the correctness of the both algorithms. Both algorithms should produce similar output if given a similar input.

a. Measure the performance of the two algorithms by measuring 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 a loop. For each test, repeat 3 times and get the average value.

Your report should include the following items:-

i.Problem statements
ii.The codes of your both algorithms
iii.Your machines specification, e.g. CPU type and amount of RAM.
iv.A table of your experiment results, before and after the average.
v.A graph of your experiment results using the average.
vi.A short discussion from the results obtained


这是我的coding for iterative
#include<stdio.h>
#include<stdlib.h>
#include<time.h>

int main(void){

                     double num[80];
        int n;

        srand(time(NULL));
        clock_t start;
        clock_t stop;
       
        printf("lease enter the size of Fibonacci series : ");
        scanf("%d",&n);

                    start = clock();

                for(int i = 0 ;i < n ; i++){
                        if(i == 0 || i == 1)
                                num = i;
                        else
                                num = num[i-1] + num[i-2];
                                printf("\n%d",i+1);
                                printf("\t%.f\n",num);
                }

        stop = clock();
        printf("The time to stop this prosses is %.3f\n",(float)(stop-start)/CLOCKS_PER_SEC);
        system("AUSE");
        return 0;
}

这是我的coding for iterative
#include<stdio.h>
#include<stdlib.h>
#include<time.h>

double fib(int num);

int main(void){
        int n;
        srand(time(NULL));
    clock_t start;
        clock_t stop;

        printf("lease the size of Fibonacci series : ");
        scanf("%d",&n);
        start = clock();
        for(int i = 0 ; i < n ; i++){
                printf("\n%d",i+1);
                printf("\t%.f\n",fib(i));}

        stop = clock();
    printf("The time to stop this prosses is %.3f\n",(float)(stop-start)/CLOCKS_PER_SEC);

        system("AUSE");
        return 0;
}

double fib(int num){
        if(num == 0 || num == 1)
                return num;
        else
                return fib(num - 1) + fib(num - 2);
        }

For recursive,我loop 40的话需要2X秒~
我的朋友他们只用X秒啊！
原以为是电脑spec的问题，但他的spec比我还差。。。
My PC spec-C2DT6400 4GB DDR2 800
Friend PC spec - M Processor 740 1.73Ghz 512MB RAM

高手指点指点~em0017
谢谢~em0008

[ 本帖最后由 凯茹 于 2009-7-11 11:44 PM 编辑 ]

Super-Tomato

原帖由 凯茹 于 2009-7-9 06:10 PM 发表
这是我的功课 : -
1.Write an iterative and a recursive version of the Fibonacci series algorithm. You need to ensure the correctness of the both algorithms. Both algorithms should produce similar ...

妳的題目主要是要你可以使用循環列出三次 10, 20... 80 這幾個 fibonanci, 並且取得平均值
recursive 也就是要你使用 function 做循環計算

凯茹

我的iteration loop是对的吗？
那我做了function loop 在放上来~
另外，老师说可以做extra feature to impress him的话会加分~
有什么idea呢？？
请指点迷津em0014

Super-Tomato

原帖由 凯茹 于 2009-7-9 10:17 PM 发表
我的iteration loop是对的吗？
那我做了function loop 在放上来~
另外，老师说可以做extra feature to impress him的话会加分~
有什么idea呢？？
请指点迷津em0014

妳的 iterative 做法沒錯, 但我想用 recursive 的做法應該執行不到 80 吧, 執行到 f(40) 之後應該就會很久了
至於 idea 就自己想吧, 大致上就如讓使用者輸入 f(x) 然後輸出答案, 或從 f(x) 開始讓使用者選擇要輸出多少個 result 等

~Zero

这样的题目, recursion 比 iteration 容易多很多.

fibonaci: 1, 1, 2, 3, 5, 8, 13......

if n=1 =>  f(n) = 1
if n=2 => f(n) = 1
else => f(n) = f(n-1) + f(n-2)

凯茹

我的recursion放上来了~
请各位type40看一下一共loop几秒~
我需要二十多秒太久了吧。。。
必要的application我全关了。。。
为什么呢？？？

~Zero

把 double 换去 int 试试

凯茹

不可能。。。
int的range一定不能接受那么大的数字。

Super-Tomato

原帖由 凯茹 于 2009-7-11 02:59 PM 发表
我的recursion放上来了~
请各位type40看一下一共loop几秒~
我需要二十多秒太久了吧。。。
必要的application我全关了。。。
为什么呢？？？

我已经说过这是必然的，iterative 的循环次数就只是 f(x) 的 x 次数，而 recursive 是需要loop x 的几何次数，当然就会花时间

最简单的检查方式可以定义一个 int a 然后在你的 recursive 函数中 a++ 等到执行完毕的时候列印出 a 就可以理解了

凯茹

我知道等是必然的。。。
但我朋友pc spec很差，他才跑六秒而已（其他朋友也是around这几秒）~
另外，我已经改了iteration的code,+scanf了。
但我type40，它只跑1-38,怎样让它run到我所type的number?