数据结构作业.docx

1.(1) 问题的描述: 设计一个程序 exp1-, 输出所有小于等于 n(n 为一个大于二的正整数) 的素数。要求:( 1 )每行输出 10 个素数;(2) 尽可能采用较优的算法。(2) 解决思想: 判断一个整数 n 是否为素数, 只需要用 2~ n -1 之间的每一个整数去除, 如果都不能被整除,那么 m 就是一个素数。其实可以简化, n 不被被 2~ n -1 之间的每一个整数去除,只需被 2~ 根号 n 之间的每个数去除就可以了。因为如果 n 能被 2~ n -1 之间任意整数整除,如果这个数大于根号 m ,那这个数必定对应的还有一个比根号 m 小的因子(3) 源代码: exp1- #include <iostream> #include <> using namespace std; int main() { int n,flag; int count=0; cout<<" 请输入一个大于二的正整数"<<"n="; cin>>n; if(n<=2) cout<<" 输入错误"; else for(int i=2;i<=n;i++) { flag=0; for(int j=2;j<= (int) sqrt(i);j++) { if(i%j==0) { flag=1; break; }} if(flag==0) { cout<<i<<" "; count++; if(count%10==0) cout<<endl; }} cout<<endl; return 0; } (4) 运行结果截图(5) 心得体会: 按照素数定义来判断素数时, 可以进行一个较为明显的优化, 即只需从 2 枚举到根 n 即可。 2.(1) 问题的描述:编写一个程序 exp1-, 计算任一输入的正整数的各位数字之和,并分析算法的时间复杂度。(2) 解决思想: 采用递归的算法,对输入的正整数进行不断的取模运算和取商运算,即可得到该正整数的各位数字之和。时间复杂度为 O(1) (3) 源代码 exp1- #include <iostream> using namespace std; int fun(int n) { if(n <= 0) { return 0; } else return n%10 + fun(n/10); } int main() { int n; cout<<" 请输入一个正整数:"; cin>>n; cout<<" 各位数字之和是:"<<fun(n)<<endl; } (4) 运行结果截图(5) 心得体会:当遇到一个复杂问题时,可以从最简单的地方着手,刚开始不知道 n 是几位数, 感觉这个问题有点棘手, 心想如果是二位数就好办了, 因此脑海中浮现了“递归”的思想,把一个复杂问题转变成简单问题。即把一个正整数 n 边分解边累加,直到分解完毕。 3.(1) 问题的描述:编写一个程序 exp1-, 判断一个字符串是否为“回文”( 顺读和倒读都一样的字符串称为“回文”) ,并