帮帮我~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

原帖由 ~Zero 于 2009-7-12 07:19 PM 发表
这个 fibonaci number recursive 的话有一个很大的进步空间,

f(n) = f(n-1) + f(n-2)
f(n-2) 整个其实在 f(n-1) 里面都做过了, 可是还是要再做多一次, 重复动作.
试试想办法解决, 可以加快很多.

哈.... 這樣的 recursive 感覺像是 iterative 混合在當中

~Zero

这个 fibonaci number recursive 的话有一个很大的进步空间,

f(n) = f(n-1) + f(n-2)
f(n-2) 整个其实在 f(n-1) 里面都做过了, 可是还是要再做多一次, 重复动作.
试试想办法解决, 可以加快很多.

Super-Tomato

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

在旧电脑单单执行 f(40) 用 6 秒左右是差不多，而你的 coding 是从 1~40 当然时间上就不一样了啊，况且你要看好题目要求的执行范围

原帖由 凯茹 于 2009-7-11 11:54 PM 发表
做到了。。。
可以教我做try/catch吗？
that mean不可以key in alphabet,only integer~

如果只是 C 是没 try and catch， 但 C++ 就有，你可以让使用者输入文字，之后用 atoi 把文字转换成数字来判断使用者是否是输入数字
如

if(atoi(inputText))
{
      printf("This is numeric data type");
}
else
{
      printf("Invalid numeric type");
}

凯茹

做到了。。。
可以教我做try/catch吗？
that mean不可以key in alphabet,only integer~

凯茹

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

Super-Tomato

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

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

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

凯茹

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

~Zero

把 double 换去 int 试试

凯茹

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