欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

浙大数据结构 总结一

程序员文章站 2022-07-06 16:27:44
...

浙大数据结构与算法分析 总结一

第一个程序:

分别用递归和循环打印10,100,1000,10000,100000....

循环程序为:

#include <stdio.h>
#include <stdlib.h>
​
void p(int N);
int main()
{
    int N;
    scanf("%d",&N);
    p(N);
    return 0;
}
void p(N)
{
    int i;
    for(i=0;i<N;i++)
        printf("%d\n",i);
}
​

递归程序为:

#include <stdio.h>
#include <stdlib.h>
void p1(int N);
int main()
{
    int N;
    scanf("%d",&N);
    p1(N);
    return 0;
}
void p1(N)
{
    if(N)
    {
        p1(N-1);
        printf("%d\n",N);
    }
}

结果:输入10,100,1000,10000两者都正常工作,输入100000后

循环:

浙大数据结构 总结一

递归:

浙大数据结构 总结一

结论:循环正常运行,递归由于占用空间太大,系统无法运行

说明:解决问题方法的效率,跟空间利用效率有关

第二个程序:

写程序计算给定多项式在给定点x处的值:

一般程序:

​
double f(int n,double a[],double x)
{
    int i;
    double p=a[0];
    for(i=1;i<=n;i++)
        p+=(a[i]*pow(x,i));
    return p;
}

优化程序:将原式改写为:

double f(int n,double a[],double x)
{
    int i;
    double p=a[n];
    for(i=n;i>0;i--)
        p=a[i-1]+x*p;
    return p;
}

说明:clock():捕捉从程序开始运行到clock()被调用时所耗费的时间,这个时间单位是clock tick,即“时钟打点”

常数CLK_TCK:机器时钟每秒所走的时钟打点数

测试程序:

#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#include<time.h>
​
clock_t start,stop;
double duration;
#define MAXN 1000
double f(int n,double a[],double x);
double f1(int n,double a[],double x);
int main()
{
    int i;
    double a[MAXN];
    for(i=0;i<MAXN;i++)
        a[i]=(double)i;
    start = clock();
    for(i=0;i<MAXN;i++)
        f(MAXN-1,a,1.1);
    stop = clock();
    printf("tick1=%f\n",(double)(stop-start));
​
    start = clock();
    for(i=0;i<MAXN;i++)
        f1(MAXN-1,a,1.1);
    stop = clock();
    duration=((double)(stop-start))/CLK_TCK/MAXN;
    printf("tick2=%f\n",(double)(stop-start));
    return 0;
}
double f(int n,double a[],double x)
{
    int i;
    double p=a[0];
    for(i=1;i<=n;i++)
        p+=(a[i]*pow(x,i));
    return p;
}
double f1(int n,double a[],double x)
{
    int i;
    double p=a[n];
    for(i=n;i>0;i--)
        p=a[i-1]+x*p;
    return p;
}

结果:

浙大数据结构 总结一

结论:解决问题方法的效率,与算法的巧妙程度有关