网站速度慢wordpress,福建龙岩昨天发生的新闻,怎样注册自己网站,前端区块链开发实验题1#xff1a;求1到n的连续整数和
题目描述
编写一个程序,对于给定的正整数n,求12…十n,采用逐个累加与(n1)/2(高斯法)两种解法。对于相同的n,给出这两种解法的求和结果和求解时间,并用相关数据进行测试。
运行代码
//实验题1#xff1a;求1到n的连续整数和
#includ…实验题1求1到n的连续整数和
题目描述
编写一个程序,对于给定的正整数n,求12…十n,采用逐个累加与(n1)/2(高斯法)两种解法。对于相同的n,给出这两种解法的求和结果和求解时间,并用相关数据进行测试。
运行代码
//实验题1求1到n的连续整数和
#includeiostream
#includetime.h
#includestdio.h
#includemath.h
using namespace std;
#define ll long long
ll add1(ll n) {ll sum 0;for (ll i 1; i n; i) {sum i;}return sum;
}
void AddTime1(ll n) {clock_t t;ll sum;t clock();sum add1(n);t clock() - t;cout 方法一 endl;printf( 结果1 到 %lld 之和%lld\n, n, sum);printf( 用时%lf 秒\n, ((double)t) / CLOCKS_PER_SEC);
}
ll add2(ll n) {return n * (n 1) / 2;
}
void AddTime2(ll n) {clock_t t;ll sum;t clock();sum add2(n);t clock() - t;cout 方法二 endl;printf( 结果1 到 %lld 之和%lld\n, n, sum);printf( 用时%lf 秒\n, ((double)t) / CLOCKS_PER_SEC);
}
int main() {ll n;printf(n(大于 1000000):);cin n;if (n 1000000) return 0;AddTime1(n);AddTime2(n);return 0;
}
代码思路
头文件和命名空间 包含了必要的输入输出流头文件 iostream、时间相关头文件 time.h、标准输入输出头文件 stdio.h 和数学库头文件 math.h。使用 using namespace std 引入标准命名空间。定义宏 ll 为 long long方便后续使用长整型数据类型。函数定义 add1 函数使用循环遍历从 1 到 n 的整数逐个累加求和。AddTime1 函数测量 add1 函数的执行时间并输出结果和用时。add2 函数利用数学公式 n*(n1)/2 直接计算从 1 到 n 的整数之和。AddTime2 函数测量 add2 函数的执行时间并输出结果和用时。main 函数 从用户输入获取整数 n要求 n 大于 1000000否则程序退出。分别调用 AddTime1 和 AddTime2 函数对两种方法进行测试。 方法一的原理循环遍历从 1 到 n 的每个整数逐个累加到变量 sum中最终得到从 1到 n 的整数之和。这种方法直观易懂但当 n 较大时循环执行次数较多可能会比较耗时。 方法二的原理利用数学公式 1 2 3 ... n n*(n1)/2 直接计算从 1 到 n 的整数之和。这个公式可以通过数学归纳法证明。这种方法避免了循环遍历计算效率更高尤其是对于较大的 n。
通过测量两种方法的执行时间可以看出当 n 较大时方法二通常比方法一执行速度更快因为方法二避免了大量的循环迭代操作直接利用数学公式进行计算。
实验题2:常见算法时间函数的增长趋势分析
题目描述 运行代码
//实验题2:常见算法时间函数的增长趋势分析
#include iostream
#include cmath
using namespace std;
double log2(double n) {return log10(n) / log10(2);
}
int factorial(int n) {if (n 0 || n 1)return 1;elsereturn n * factorial(n - 1);
}
int main() {cout n\tlog2(n)\t√n\tn\tn^2\tn^3\t2^n\tn! endl;for (int n 1; n 10; n) {cout n \t log2(n) \t sqrt(n) \t n \t n * n \t n * n * n \t pow(2, n) \t factorial(n) endl;}return 0;
}
代码思路
一、代码思路
函数定义 log2函数通过换底公式logₐb logₑb / logₑa这里使用以 10 为底的对数函数log10计算出以 2 为底的对数。factorial函数使用递归的方式计算给定整数n的阶乘。当n为 0 或 1 时阶乘为 1否则n的阶乘等于n乘以n - 1的阶乘。main函数 首先输出表头展示不同算法时间函数的名称。使用循环从 1 到 10 遍历整数n。在循环中分别计算并输出n、以 2 为底n的对数、n的平方根、n、n的平方、n的立方、2 的n次方、n的阶乘的值。
二、原理
log2(n)对数函数的增长非常缓慢。随着n的增大对数函数的值增长速度远远慢于线性增长。√n平方根函数的增长速度比线性增长慢但比对数函数快。n代表线性增长即随着n的增加函数值以相同的比例增加。n^2二次函数的增长速度比线性增长快得多。当n增大时二次函数的值增长迅速。n^3三次函数的增长速度比二次函数更快。2^n指数函数的增长速度非常快远远超过其他函数。n!阶乘函数的增长速度是所有这些函数中最快的。随着n的增大阶乘函数的值呈爆炸式增长。
通过输出这些不同函数在不同n值下的结果可以直观地观察到它们的增长趋势差异对于分析算法的时间复杂度非常有帮助。例如在选择算法时如果一个算法的时间复杂度是指数级的如2^n或n!那么对于较大的输入规模该算法可能会非常耗时而如果算法的时间复杂度是线性的如n或对数级的如log2(n)则通常会更加高效。
实验题3:求素数的个数
题目描述
编写一个程序,求1~n的素数个数。给出两种解法,对于相同的n,给出这两种解法的结果和求解时间,并用相关数据进行测试。
运行代码
//实验题3:求素数的个数
#include iostream
#include ctime
using namespace std;
bool isPrime1(int n) {// 方法 1传统方法判断素数时间复杂度 O(n)if (n 2) return false;for (int i 2; i n; i) {if (n % i 0) return false;}return true;
}
int prime1(int n) {int count 0;for (int i 2; i n; i) {if (isPrime1(i)) count;}return count;
}
bool isPrime2(int n) {// 方法 2改进方法判断素数时间复杂度 O(√n)if (n 2) return false;if (n 2 || n 3) return true;if (n % 2 0 || n % 3 0) return false;for (int i 5; i * i n; i 6) {if (n % i 0 || n % (i 2) 0) return false;}return true;
}
int prime2(int n) {int count 0;for (int i 2; i n; i) {if (isPrime2(i)) count;}return count;
}
void PrimeTime1(int n) {clock_t start clock();int count prime1(n);clock_t end clock();double time_taken double(end - start) / CLOCKS_PER_SEC;cout 方法 11 到 n 的素数个数为 count 用时 time_taken 秒。 endl;
}
void PrimeTime2(int n) {clock_t start clock();int count prime2(n);clock_t end clock();double time_taken double(end - start) / CLOCKS_PER_SEC;cout 方法 21 到 n 的素数个数为 count 用时 time_taken 秒。 endl;
}
int main() {int n;cout 输入 n(n100000);cin n;PrimeTime1(n);PrimeTime2(n);return 0;
}
代码思路
一、代码思路
函数定义 isPrime1函数采用传统方法判断一个整数是否为素数。从 2 开始到该数减 1 进行遍历如果存在能整除该数的数则不是素数否则是素数。时间复杂度为。prime1函数利用isPrime1函数遍历从 2 到n的所有整数统计其中素数的个数。isPrime2函数改进的方法判断素数。先处理特殊情况小于 2 的数、2 和 3。然后根据素数的性质只需要判断到该数的平方根即可并且只需要考虑 6 的倍数两侧的数即i和i 2因为所有大于等于 5 的素数一定可以表示为 6k ± 1 的形式。时间复杂度为。prime2函数与prime1类似使用isPrime2函数遍历从 2 到n的整数统计素数个数。PrimeTime1函数测量prime1函数的执行时间并输出素数个数和用时。PrimeTime2函数测量prime2函数的执行时间并输出素数个数和用时。main函数 提示用户输入一个大于 100000 的整数n。分别调用PrimeTime1和PrimeTime2函数对两种方法进行测试并输出结果。
二、原理 素数的定义素数是指一个大于 1 的自然数除了 1 和它自身外不能被其他自然数整除。 两种判断素数方法的原理 方法 1传统方法通过遍历所有小于该数的整数来判断是否有能整除它的数。这种方法虽然直观但效率较低因为需要进行大量的除法运算。方法 2改进的方法利用了素数的分布规律。首先处理特殊情况然后只需要判断到该数的平方根并且只考虑特定形式的数减少了不必要的判断提高了效率。 统计素数个数的原理通过遍历一定范围内的整数对每个整数使用判断素数的函数进行判断如果是素数则计数器加一。 测量执行时间的原理使用clock_t类型记录程序开始和结束的时间通过计算时间差并除以CLOCKS_PER_SEC得到程序的执行时间以秒为单位。
通过比较两种方法可以看出在处理较大范围的素数个数计算时改进后的方法方法 2具有更高的效率因为其时间复杂度更低。
实验题4:求连续整数阶乘的和
题目描述
编写一个程序,对于给定的正整数n,求1!2!3!…n!。给出一种时间复杂度为O(n)的解法。
运行代码
//实验题4:求连续整数阶乘的和
#include iostream
using namespace std;
long long Sum(int n) {long long sum 0;long long fact 1;for (int i 1; i n; i) {fact * i;sum fact;}return sum;
}
int main() {int n;cout 输入正整数 n(3-20);cin n;if (n 3 || n20)return 0;long long result Sum(n);cout 1! 2! 3! ... n ! 的结果为 result endl;return 0;
}
代码思路
一、代码思路
Sum函数 循环结束后返回sum即从 1 到n的连续整数阶乘之和。通过循环从 1 到n遍历整数。在每次循环中先将fact乘以当前的整数i得到当前整数的阶乘然后将这个阶乘累加到sum中。初始化变量fact为 1用于存储当前整数的阶乘。初始化变量sum为 0用于存储连续整数阶乘的和。main函数 提示用户输入一个正整数n要求在 3 到 20 之间。如果输入的n不在这个范围内程序直接返回 0 退出。调用Sum函数计算从 1 到n的连续整数阶乘之和并将结果存储在result中。输出结果显示从 1 到n的连续整数阶乘之和的具体值。
二、原理 阶乘的定义一个正整数的阶乘是所有小于及等于该数的正整数的乘积。例如5 的阶乘是 5! 5×4×3×2×1 120。 计算连续整数阶乘之和的原理 通过循环依次计算每个整数的阶乘并将其累加到总和中。首先初始化阶乘为 1因为 1 的阶乘是 1。然后从 2 开始每次将当前整数乘以当前的阶乘得到新的阶乘并将新的阶乘累加到总和中。这样通过循环可以依次得到 2!、3!、4!…… 直到n!并将它们累加到总和中最终得到从 1! 到n!的连续整数阶乘之和。
