数据结构第五版——第一章课后实验题

新学期新知识

只不过数据结构这东西还是挺让人头疼的

归根结底还是自己大一的时候C的指针和C++的链表没有好好听

最后还是得自己慢慢研究慢慢写

第一章的内容其实不多,所以实验题也都是一些经典的入门算法题

用来帮助提高我已经非常惨淡的算法技能再合适不过了


实验题1:求1~n的连续整数和

对于给定的正整数n,求1+2+….+n

采用逐个累加和高斯法两种解法

对于相同的n,给出这两种解法的求和结果和求解时间

这里的话其实算法不是难点,主要是计算求解时间是个问题

一开始我理解的求解时间是程序return0后控制台给的那个时间

然而并不是

这里需要用到ctime头文件里的clock函数记录某一语句执行完的时间点

(C的话就是time.h)

然后通过时间点的相减去计算起点和终点内语句的运行时间

有的人会奇怪为啥这里用了long long整型

原因是如果数字不够大的话时间变化是看不大出来的(会都是0因为太小了)

所以为了能尽量用较大的数字用了long long

#include<iostream>
#include<ctime>
using namespace std;

long long Plus(long long n){
    clock_t Start,End;
    long long sum=0;
    Start = clock();
    for(int i=1;i<=n;i++){
        sum = sum +i;
    }
    End = clock();
    cout << (double)(End - Start) / CLOCKS_PER_SEC << endl;
    return sum;
}//累加法 

long long Gaussian(long long n){
    clock_t Start,End;
    long long sum=0;
    Start = clock();
    sum = (n*(n+1))/2;
    End = clock();
    cout<<(double)(End - Start) / CLOCKS_PER_SEC << endl;
    return sum;
}//高斯法 

int main(){
    int n=0;
    cin>>n;
    cout<<Plus(n)<<endl;
    cout<<Gaussian(n)<<endl;
}
//注释掉任一一个都可以

实验题2:常见算法时间函数的增长趋势分析

编写一个程序,对于1~n的每个整数n

输出log2n,sqrt(n),n,nlog2n,n^2,n^3,2^n,n!的值

这个也没什么难度

就是要记住特殊的函数像对数和根号

log2n就是log(n)/log(2)

别忘了cmath头文件(C的math.h)

#include<iostream>
#include<cmath>
using namespace std;

double Log2N(int n){
    return log(n)/log(2);
} 

double Sqrt(int n){
    return sqrt(n);
}

int Keep(int n){
    return n;
}

double Power(int n){
    return pow(2,n);
}

int N(int n){
    int sum=1;
    for(int i=2;i<=n;i++){
        sum=sum*i;
    }
    return sum;
}

void Out(int n){
    cout<<"以下是第"<<n<<"个数字的内容"<<endl; 
    cout<<"log2n="<<Log2N(n)<<endl;
    cout<<"根号n="<<Sqrt(n)<<endl;
    cout<<"n = " <<Keep(n)<<endl;
    cout<<"nlog2n = "<<Keep(n)*Log2N(n)<<endl;
    cout<<"n^2 = "<<Keep(n)*Keep(n)<<endl;
    cout<<"n^3 = "<<Keep(n)*Keep(n)*Keep(n)<<endl;
    cout<<"2^n = "<<Power(n)<<endl;
    cout<<"n! = "<<N(n)<<endl;
    cout<<endl;
} 

int main(){
    int n=0;
    cin>>n;
    cout<<endl;
    for(int i=1;i<=n;i++){
        Out(i);
    }
    return 0;
}

实验题3:求素数的个数

求1~n的素数个数,给出两种解法

对于相同的n,给出这两种解法的结果和求解时间

并用相关的数据进行测试

我自己想了第一种方法也是最常用的方法

除了1和2这两个特殊的数

剩下的数里只有奇数可能是素数(因为素数除了2一定是奇数)

那只要验证奇数只能被自己和1整除就可以推出这个数是素数了

第二种方法则是很经典的方法

叫做筛法求素数

下面我就直接搬百度的说明了

原文链接

用筛法求素数的基本思想是:把从2到N的一组正整数从小到大按顺序排列。从中依次删除2的倍数、3的倍数、5的倍数,直到根号N的倍数为止,剩余的即为2~N之间的所有素数。如有:
2 3 4 5 6 7 8 9 10
11 12 13 14 15 16 17 18 19 20
21 22 23 24 25 26 27 28 29 30
去掉2的倍数(不包括2),余下的数是:
3 5 7 9 11 13 15 17 19 21 23 25 27 29
剩下的数中3最小,去掉3的倍数,如此下去直到所有的数都被筛完,求出的素数为:
2 3 5 7 11 13 17 19 23 29
按照上面这个思路就可以很快的算出素数的个数
要记住这个题目并不是求素数是啥,所以肯定有很快的算法
#include<iostream>
#include<cmath>
#include<ctime>
using namespace std;

void First(int n){
    int number = 0;//统计素数的个数 
    int isprime = 0;//如果数字为2那就是只能被1和它本身整除 
    clock_t Start,End;
    Start = clock();
    for(int i=3;i<=n;i++){
        if(i%2!=0){
            //先判断是不是奇数,因为除了2,2之后所有的素数都一定是奇数 
            for(int j=1;j<=i;j=j+2){
                if(i%j==0){
                    isprime++;//让这个奇数去除奇数,因为它不可能被偶数整除 
                }
            }
            if(isprime == 2){
                number++;//符合素数的条件所以素数的个数+1 
                isprime = 0;//记得数值要初始化 
            }else{
                isprime = 0;
            }
        }
    }
    End = clock();
    cout<<(double)(End - Start) / CLOCKS_PER_SEC << endl;
    cout<<number+1<<endl;//最后统计的数值应该加上2这个特殊的素数 
}

void Second(int n){
    bool isprime[n];
    int number=0;
    clock_t Start,End;
    Start = clock();
    for(int i=0;i<n;i++){
        isprime[i]=true;
    } //假设一开始都是素数 
    isprime[0]=isprime[1]=false;//先筛去特殊的1和2 
    for(int i=2;i<=n;i++){
        if(isprime[i]){
            for(int j=2*i;j<=n;j+=i){
                isprime[j]=false;
            }
        }//从3开始进行判断,筛去3的奇数倍数,并且筛去素数的乘积 
    } 
    for(int i=0;i<n;i++){
        if(isprime[i]){
            number++;
        }
    }//统计素数的个数
    End = clock();
    cout<<(double)(End - Start) / CLOCKS_PER_SEC << endl; 
    cout<<number<<endl;
}

int main(){
    int n;
    cin>>n;
    First(n);
    Second(n);
    
    return 0;
}

实验题4:求连续整数阶乘的和

对于给定的正整数n,求1!+2!+3!+…+n!

给出一种时间复杂度为0(n)的解法

只用一个for循环就要做到累加和累乘

一开始我也觉得不可能

但是事实上这是一题找规律的题目

我们假设每一项子项分别为a1、a2、a3…an

我们会发现an = n*a(n-1)

注:这里是n-1是下标,意思就是上一项

通过这个我们就可以整一个很奇妙的算法出来

#include<iostream>
using namespace std;

int main(){
    int i=0;
    int n=0;
    int s=1;//计每一项的阶乘
    int sum=0;//计阶乘的和
    
    cin>>n;
    for(i=1;i<=n;i++){
        s=s*i;
        sum=sum+s;
    } 
    cout<<sum<<endl;
    return 0;
}

 

 

发表评论

您的电子邮箱地址不会被公开。