首页 > 代码库 > 数据结构与算法分析C++表述第二章编程题
数据结构与算法分析C++表述第二章编程题
把昨天看的第二章巩固一下，做一做编程习题。
２．６：
第一天交２元罚金，以后每一天都是前一天的平方，第Ｎ天罚金将是多少？
这个题目和2.4.4-3介绍的幂运算基本一致。若按相同的递归思路分析，比那个问题要简单，因为从1次幂开始并且指数呈2^(n-1)分布，即1，2，3，4，16……所以没有对指数是奇数时的判定。实际上用循环来求要比用递归快。在不考虑溢出的前提下，解法如下：
#include<iostream>using namespace std;typedef unsigned long long uint64;uint64 r(int n){ if(n==1){ return 2; }else{ uint64 tmp=r(n-1); return tmp*tmp; }}uint64 w(int n){ int result=2; while(n!=1){ result*=result; n--; } return result;}int main(){ int n; cin>>n; cout<<r(n)<<" "<<w(n)<<endl;}
２．２０：
确定一个正整数是否是素数。这个问题可以简化一下，因为ｎ＊ｎ＞（ｎ－１）＊（ｎ＋１）。所以只需要求ｎ是否能被２到ｓｑｒｔ（ｎ）整除就可以了，这里需要注意的就是2是最小的素数:
for(i=2;i<sqrt(n);i++)对2不能返回正确的结果，因为1.414<2不会进入循环。所以要先行判断：
#include<iostream>#include<cmath>using namespace std;bool ispn(int n){ if((n%2)==0){ return false; }else{ int i,max=int(sqrt(n)); for(i=3;i<=max;i++){ if((n%i)==0) return false; } } return true;}int main(){ int n; cin>>n; cout<<ispn(n)<<endl;}
当然，也可以if(n==2)然后for(i=2;i<=max;i++)。需要注意的是平方根（max）的条件不是小于，是小于等于。接下来有一个厄拉多塞筛的时间复杂度问题，这里仅记录厄拉多塞筛：取从2到n，n>=2之间的全部素数只需要滤掉那些非素数。根据前面讲述的原理，去掉这些非素数的方法如下：循环去掉2-sqrt(n)之间的全部非素数：
#include<iostream>#include<cmath>#include<vector>using namespace std;typedef unsigned long long uint64;void es(vector<int> &arr){ int i,j,n=arr.size(),sqrtnum=int(sqrt(n)); for(i=2;i<=sqrtnum;i++){ //从最小的素数m(m=2)开始遍历到sqrt(arr.size()) if(arr[i]==0){ //找到后面第一个素数m（标记仍然为0的） for(j=i*2;j<=n;j+=i){ //标记m*n(1<n<=arr.size/m)为非素数。 arr[j]=1; } } }}int main(){ int i,n; cin>>n; vector<int> arr(n+1); es(arr); for(i=2;i<=n;i++){ if(arr[i]==0){ cout<<i<<endl; } }}
注意以下几点（设n为上限）：
1、代码中arr默认值为0，用以表示假定为素数，最终结果中被标志为1的都不是素数；其下标与数字一一对应，即若输入11，则数组最大下标为11，亦即数组元素为n+1个。
2、根据前面的结论，i只需要从2搜索到sqrt(n)，包含sqrt(n)。
3、在进行标志时，从当前素数的2倍开始标志。
在chinaunix上面看到一篇类似的算法，1、2都犯了，只能低效的输出n-1以内的，漏掉了n。例如输入11，得到的是2、3、5、7，例如输入2什么也没出来。
歇一歇，2017年1月1日12:45，以上。
数据结构与算法分析C++表述第二章编程题
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。