JBTALKS.CC

标题: 帮帮我~C Programing~ [打印本页]
作者: 凯茹    时间: 2009-7-9 06:10 PM
标题: 帮帮我~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 09:06 PM
原帖由 凯茹 于 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 做循環計算
作者: 凯茹    时间: 2009-7-9 10:17 PM
我的iteration loop是对的吗？
那我做了function loop 在放上来~
另外，老师说可以做extra feature to impress him的话会加分~
有什么idea呢？？
请指点迷津em0014
作者: Super-Tomato    时间: 2009-7-9 11:14 PM
原帖由 凯茹 于 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    时间: 2009-7-10 08:18 PM
这样的题目, 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)
作者: 凯茹    时间: 2009-7-11 02:59 PM
我的recursion放上来了~
请各位type40看一下一共loop几秒~
我需要二十多秒太久了吧。。。
必要的application我全关了。。。
为什么呢？？？
作者: ~Zero    时间: 2009-7-11 03:05 PM
把 double 换去 int 试试
作者: 凯茹    时间: 2009-7-11 04:42 PM
不可能。。。
int的range一定不能接受那么大的数字。
作者: Super-Tomato    时间: 2009-7-11 10:35 PM
原帖由 凯茹 于 2009-7-11 02:59 PM 发表
我的recursion放上来了~
请各位type40看一下一共loop几秒~
我需要二十多秒太久了吧。。。
必要的application我全关了。。。
为什么呢？？？



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

最简单的检查方式可以定义一个 int a 然后在你的 recursive 函数中 a++ 等到执行完毕的时候列印出 a 就可以理解了
作者: 凯茹    时间: 2009-7-11 11:07 PM
标题: 回复 #9 Super-Tomato 的帖子
我知道等是必然的。。。
但我朋友pc spec很差，他才跑六秒而已（其他朋友也是around这几秒）~
另外，我已经改了iteration的code,+scanf了。
但我type40，它只跑1-38,怎样让它run到我所type的number?
作者: 凯茹    时间: 2009-7-11 11:54 PM
做到了。。。
可以教我做try/catch吗？
that mean不可以key in alphabet,only integer~
作者: Super-Tomato    时间: 2009-7-12 03:14 AM
原帖由 凯茹 于 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");
}
作者: ~Zero    时间: 2009-7-12 07:19 PM
这个 fibonaci number recursive 的话有一个很大的进步空间,

f(n) = f(n-1) + f(n-2)
f(n-2) 整个其实在 f(n-1) 里面都做过了, 可是还是要再做多一次, 重复动作.
试试想办法解决, 可以加快很多.
作者: Super-Tomato    时间: 2009-7-12 09:44 PM
原帖由 ~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 混合在當中



欢迎光临 JBTALKS.CC (https://jbtalks.my/) Powered by Discuz! X2.5