- 浏览: 128995 次
- 性别:
- 来自: 成都
最新评论
-
yi_chao_jiang:
你好,多谢分享,问个问题,在上传数据的时候判断文件是否有上传记 ...
断点续传和下载原理分析 -
a41606709:
为什么我的tabhost显示不出来? 怎么设置在全部页面中让他 ...
TabActivity中的Tab标签详细设置 -
Zero颴:
大神篇,思路,配图都很清晰,perfect!
Android事件模型之interceptTouchEvnet ,onTouchEvent关系正解 -
QAZ503602501:
牛死人了!!!
B-树 -
mengsina:
很牛的文档。数学功底好啊
Android Matrix理论与应用详解
我的注释都写在代码里面了,就不在赘述了!如果有任何疑问欢迎留言
参考博客:
1.位操作总结:http://blog.csdn.net/morewindows/article/details/7354571
2.找素数算法总结:http://blog.csdn.net/hexiios/article/details/4400068
非常感谢上面两篇博客的仁兄,致谢!
尤其是读了位操作的那篇文章,写的非常好,希望各位都可以一次尝试哈,没准给你的程序增加一个亮点
2的总结也很好,我只是在它的基础上在详细的给了些注释,如果有不懂的地方就好理解了!
1.基础补习
什么是合数?什么是素数?百度一下你就知道
有一个重要的性质:任何一个合数一定可以表示成若干个素数之积。
如:4 = 2 * 2,6 = 2 * 3,12 = 2 * 2 * 3。也就是说,合数N一定是小于N的某个(或若干)素数的整数倍,反之,如果N不是任何比它小的素数的倍数,则N必然是素数。
这个性质就决定了下面的算法基本思想
2.检查是否是素数(这个是从基本概念出发的检测算法)
主要的改进就是检测的范围缩小从0---sqrt(n)
bool isPrime(int n){ if(n ==0 || n==1) return 0; for(int i=2; i<=sqrt(n); i++){ if(n%i == 0){ cout<<i<<endl; return 0; } } return 1; }
3.经典素数求解算法
它对每个数的检测就是利用2的方法
/** *经典素数求解算法 *prime[0]中保存素数总个数 */ int* getPrime(){ int prime[LEN] = {0};//判断是否为素数,初始都为素数 prime[0] = 0; //保存素数的总个数 for(int n=2; n<LEN; n++){ bool flag = 1; //对每个数A都按照:2到sqrt(A)依次除,看是否整除,如果能则不是素数 //这样是很低效的m*m<=n也可写成m<=sqrt(n) //注意:必须有m*m<=n 中的“=” for(int m=2; m*m<=n; m++){ //如果能整除,不是素数 if(n%m == 0){ flag = 0; break; } } if(flag){ prime[0]++; prime[prime[0]] = n; } } cout<<"\ncount:"<<prime[0]<<endl; return prime; }
4.经典算法改进版
其主要的改进的地方就是,检测的思想,前面的检测方法就是2到sqrt(A)依次除,看是否整除
改进的就不同了,它利用了合数的性质,利用已经找到的素数来除,这样大大的减少了需要整除的次数,这个改进不错!
/** *它是上面经典算法改进版 *这里prime数组中存的是素数,prime[0]中保存素数总个数 *获取0-n的所有素数 */ int* getPrime1(){ int prime[LEN] = {0};//判断是否为素数,初始都为素数 int i, n, flag; prime[0] = 0; //保存素数的总个数 for (n =2 ; n < LEN; n++) { flag = 1; //判断当前n是否被"已经找出的素数"整除(如果能,说明不是素数,根据合数性质) //使用条件prime[i] * prime[i] <= n,就是判断一个数A是否是素数的时候,不需要 //从2-A的所有数都去看是否能整除,只需要看2-sqrt(A)即可,即最终整除位置为sqrt(A),见上面isPrime(int n) //这里是用prime[i]去整除,故而只需要prime[i]*prime[i]<=n也可写成prime[i]<=sqrt(n) for (i = 1; i <= prime[0] && prime[i] * prime[i] <= n; i++) //如果不是素数,break,flag=0 if (n % prime[i] == 0) { flag = 0; break; } //flag=1,则说明是素数,存储 if (flag) { prime[0]++;//素数个数 prime[prime[0]] = n;//将确定了的素数放入数组 } } cout<<"\ncount:"<<prime[0]<<endl; return prime; }
5.厄拉多塞筛算法
所谓厄拉多塞筛算法就是:利用一个空间换时间的思想,利用一个辅助数组来存储素数的位置,然后利用的是筛选法,筛选出素数的倍数
那你就会发出一个疑问?只是筛选出素数的倍数,那是不是还有遗漏啊?这个就看看1的性质吧,即所有合数,都可以分解成若干个素数。
*首先,将所有的数组元素设为0,表示没有已知的非素数。
*然后,将已知为非素数(即为已知素数的倍数)的索引对应的数组元素设置为1。
*如果将所有较小素数的倍数都设置为1之后,a[i]仍然保持为0,则可判断它是所找的素数。
/** *厄拉多塞筛算法:prime[0]中保存素数总个数 */ int* getPrime2(){ int count = 0; int primes[LEN / 3] = {0}, pi=1; int flag[LEN] = {0};//判断是否为素数,初始都为素数 //0,1不是素数 flag[0]=1; flag[1]=1; for(int i=2; i<LEN; i++){ //倍数必然不是素数,把不是素数的都筛选出来 if(!flag[i]){ primes[pi++] = i; // 注意:这里只用素数来筛,因为合数筛时肯定被素数筛过了,所以没必要. //为什么?因为合数的性质:任何一个合数一定可以表示成若干个素数之积。如:4 = 2 * 2,6 = 2 * 3,12 = 2 * 2 * 3 //即所有合数,都可以分解成若干个素数。 for(int j=i; j<LEN; j+=i){ //为什么9624会出现在素数中? //if(j == 9624) cout<<"-----"<<i<<" "<<j<<endl; flag[j]=1; count++; } } } //从count可以看出,对于一个位置重复访问了许多次,可以优化 cout<<"访问数组总数:"<<count<<endl; primes[0] = pi - 1; cout<<"count:"<<primes[0]<<endl; return primes; }
6,厄拉多塞筛算法改进版
由于对于5来说,最大的缺憾就是利用了辅助数组,那么我们可以减少空间,反正都只是存0,1,为什么不用位来存储呢?这样就大大的减少了空间的浪费了!
首先看看一个为操作的事例:
/** *用于位测试 * */ #include <iostream> #include <cstdio> using namespace std; int main(){ //在数组中在指定的位置上写1 int b[5] = {0}; //占用连续的20个字节空间(每个int占用4字节),每个字节8位(1Byte=8bit) cout<<sizeof(b)<<" "<<sizeof(int)<<endl; int i; //在第i个位置上写1(一共有20*8=160位,现在之使用了40位) for (i = 0; i < 40; i += 3) //每int占用4字节即32位,当b[0]的32位用完,就b[1] b[i / 32] |= (1 << (i % 32)); //输出整个bitset for (i = 0; i < 40; i++) { //将数组依次右移一位,然后和1求与,判断该位是0还是1 if ((b[i / 32] >> (i % 32)) & 1) putchar('1'); else putchar('0'); } putchar('\n'); return 0; return 0; }
在下面的算法中就是利用了上面的操作,只要去看看我第一个链接,里面更详细!
/** *厄拉多塞筛算法改进版:prime[0]中保存素数总个数 */ int* getPrime3(){ int primes[LEN / 3] = {0}, pi=1; //实际素数的个数最多就是LEN / 3,故而没用LEN //用位替代int prime[LEN] = {0};//判断是否为素数,初始都为素数 int flag[LEN/32] = {0};//每个int是4字节=32bit(32位)可以存储32个0,1,故而只需要LEN/32个长度的数组即可 for(int i=2; i<LEN; i++){ //倍数必然不是素数,把不是素数的都筛选出来 if(!((flag[i/32]>>(i%32))&1)){ primes[pi++] = i; for(int j=i; j<LEN; j+=i){ //将第j位设置为1,表示不是素数 flag[j/32] |= (1<<(j%32)); } } } primes[0] = pi - 1; cout<<"count:"<<primes[0]<<endl; return primes; }
7.时间复杂度分析
10万个数:这个数来测试有些小,可以大些,这样效果比较明显
时间花费依次:62ms, 15ms, 0ms, 0ms
当然最好两个是0ms这个大些才能看出来,非常明显的效果提升
8.所有代码
/** *说明: *有一个重要的性质:任何一个合数一定可以表示成若干个素数之积。 *如:4 = 2 * 2,6 = 2 * 3,12 = 2 * 2 * 3。也就是说, *合数N一定是小于N的某个(或若干)素数的整数倍,反之,如果N不是任何比它小的素数的倍数, *则N必然是素数。 /** * Author: Blakequ@gmail.com * Data : 2012-06-02 22:20 * * */ #include <iostream> #include <cmath> #include <ctime> const int LEN = 100000; using namespace std; //检查n是不是素数 bool isPrime(int n){ if(n ==0 || n==1) return 0; for(int i=2; i<=sqrt(n); i++){ if(n%i == 0){ cout<<i<<endl; return 0; } } return 1; } /** *经典素数求解算法 *prime[0]中保存素数总个数 */ int* getPrime(){ int prime[LEN] = {0};//判断是否为素数,初始都为素数 prime[0] = 0; //保存素数的总个数 for(int n=2; n<LEN; n++){ bool flag = 1; //对每个数A都按照:2到sqrt(A)依次除,看是否整除,如果能则不是素数 //这样是很低效的m*m<=n也可写成m<=sqrt(n) //注意:必须有m*m<=n 中的“=” for(int m=2; m*m<=n; m++){ //如果能整除,不是素数 if(n%m == 0){ flag = 0; break; } } if(flag){ prime[0]++; prime[prime[0]] = n; } } cout<<"\ncount:"<<prime[0]<<endl; return prime; } /** *它是上面经典算法改进版 *这里prime数组中存的是素数,prime[0]中保存素数总个数 *获取0-n的所有素数 */ int* getPrime1(){ int prime[LEN] = {0};//判断是否为素数,初始都为素数 int i, n, flag; prime[0] = 0; //保存素数的总个数 for (n =2 ; n < LEN; n++) { flag = 1; //判断当前n是否被"已经找出的素数"整除(如果能,说明不是素数,根据合数性质) //使用条件prime[i] * prime[i] <= n,就是判断一个数A是否是素数的时候,不需要 //从2-A的所有数都去看是否能整除,只需要看2-sqrt(A)即可,即最终整除位置为sqrt(A),见上面isPrime(int n) //这里是用prime[i]去整除,故而只需要prime[i]*prime[i]<=n也可写成prime[i]<=sqrt(n) for (i = 1; i <= prime[0] && prime[i] * prime[i] <= n; i++) //如果不是素数,break,flag=0 if (n % prime[i] == 0) { flag = 0; break; } //flag=1,则说明是素数,存储 if (flag) { prime[0]++;//素数个数 prime[prime[0]] = n;//将确定了的素数放入数组 } } cout<<"\ncount:"<<prime[0]<<endl; return prime; } //------------------------------下面两个算法是典型的以空间换时间,不过空间改进即可--------------------------------------------------- /** *厄拉多塞筛算法:prime[0]中保存素数总个数 *首先,将所有的数组元素设为0,表示没有已知的非素数。 *然后将已知为非素数(即为已知素数的倍数)的索引对应的数组元素设置为1。 *如果将所有较小素数的倍数都设置为1之后,a[i]仍然保持为0, *则可判断它是所找的素数。 */ int* getPrime2(){ int count = 0; int primes[LEN / 3] = {0}, pi=1; int flag[LEN] = {0};//判断是否为素数,初始都为素数 //0,1不是素数 flag[0]=1; flag[1]=1; for(int i=2; i<LEN; i++){ //倍数必然不是素数,把不是素数的都筛选出来 if(!flag[i]){ primes[pi++] = i; // 注意:这里只用素数来筛,因为合数筛时肯定被素数筛过了,所以没必要. //为什么?因为合数的性质:任何一个合数一定可以表示成若干个素数之积。如:4 = 2 * 2,6 = 2 * 3,12 = 2 * 2 * 3 //即所有合数,都可以分解成若干个素数。 for(int j=i; j<LEN; j+=i){ //为什么9624会出现在素数中? //if(j == 9624) cout<<"-----"<<i<<" "<<j<<endl; flag[j]=1; count++; } } } //从count可以看出,对于一个位置重复访问了许多次,可以优化 cout<<"访问数组总数:"<<count<<endl; primes[0] = pi - 1; cout<<"count:"<<primes[0]<<endl; return primes; } /** *厄拉多塞筛算法改进版:prime[0]中保存素数总个数 *使用一个数组来包含最简单的元素类型,0和1两个值, *如果我们使用位的数组,而不是使用整数的数组,则可获得更高的空间有效性 */ int* getPrime3(){ int primes[LEN / 3] = {0}, pi=1; //实际素数的个数最多就是LEN / 3,故而没用LEN //用位替代int prime[LEN] = {0};//判断是否为素数,初始都为素数 int flag[LEN/32] = {0};//每个int是4字节=32bit(32位)可以存储32个0,1,故而只需要LEN/32个长度的数组即可 for(int i=2; i<LEN; i++){ //倍数必然不是素数,把不是素数的都筛选出来 if(!((flag[i/32]>>(i%32))&1)){ primes[pi++] = i; for(int j=i; j<LEN; j+=i){ //将第j位设置为1,表示不是素数 flag[j/32] |= (1<<(j%32)); } } } primes[0] = pi - 1; cout<<"count:"<<primes[0]<<endl; return primes; } int main(){ clock_t start, finish; start = clock(); int n = 0; /* cout<<"输入判断的数:"<<endl; cin>>n; if(isPrime(n)){ cout<<"是素数"<<endl; }else{ cout<<"不是素数"<<endl; } */ //-------------------------方法1(经典算法62ms)---------------------------- //getPrime(); /* int *a = getPrime(); for(int i=1; i<LEN; i++){ if(a[i]==0) break; cout<<a[i]<<" "; } */ //-------------------------方法1(经典算法改进15ms)---------------------------- //getPrime1(); /* int *a = getPrime1(); for(int i=1; i<LEN; i++){ if(a[i]==0) break; cout<<a[i]<<" "; } */ //----------------------------方法3(厄拉多塞筛算法<1ms)---------------------------- //getPrime2(); /* int *a = getPrime2(); for(int i=1; i<LEN; i++){ if(a[i]==0) break; cout<<a[i]<<" "; } */ //----------------------------方法3(厄拉多塞筛算法改进<1ms)---------------------------- //getPrime3(); int *a = getPrime3(); for(int i=1; i<LEN; i++){ if(a[i]==0) break; cout<<a[i]<<" "; } finish = clock(); cout<< "\nCost Time: " << finish - start << " ms"; return 0; }
发表评论
-
排序方法总结
2012-08-12 11:34 1140这里面包含了所有常见的排序操作 1.性能等比较分析 2 ... -
常见字符串操作大全
2012-08-12 11:34 14281.常见的字符串操作 如计算长度,求子串等都是考验基本功的, ... -
KMP算法解析
2012-08-12 11:35 2780一.理论基础 1.什么 ... -
二叉堆的实现
2012-08-12 11:35 11781.堆的概念 这里只需要注意两点: a.堆的存储方式:就是 ... -
set和map的简单实现
2012-08-10 11:35 12811.Set的简单实现 set是利用二叉查找树来实现的,而且为 ... -
红黑树的插入总结
2012-08-10 11:25 9361.红黑树 这个在july的博客中有详尽的说明,我就不在赘述 ... -
B-树实现
2012-08-10 11:03 15921.什么是B-树? 这个在我的前一篇博客中已经详细的阐释过: ... -
平衡二叉树
2012-08-10 10:39 27981.问题描述 什么是平衡 ... -
二叉排序树
2012-08-10 10:25 14241.基本概念 二叉排 ... -
B-树
2012-07-04 22:48 56241.B-树的概念 是一种多 ... -
构造哈夫曼树
2012-07-04 10:40 11941.算法说明 就是建造哈夫曼树树,从而使得构造出的树带权路径 ... -
线索二叉树
2012-07-04 09:20 12421.算法描述 就是简单的线索二叉树的建立,遍历,查找等基本操 ... -
二叉树基本操作大全
2012-07-03 18:22 25611.二叉树的基本操作 这里我有一个疑问: 在使用构造 ... -
多种队列的实现
2012-06-29 10:09 14971.算法描述 a.数据结构与算法(Mark Allen We ... -
栈的各种实现
2012-06-28 16:34 10821.算法描述 a.实现二个栈,在一个数组里面,除非没有任何空 ... -
中缀表达式转换为后缀
2012-06-28 11:10 17591.算法描述 例如a+b*c这是常见的中缀表达式,但是 ... -
后缀表达式的值
2012-06-27 16:33 12931.算法描述 计算后缀表达式的值 2.事例 如:( ... -
Josephus问题
2012-06-21 15:30 9581.算法描述 简单的游戏:有N个人坐成一圈,编号1-N、从编 ... -
关于最长递增子序列的实际应用--动态规划
2012-06-07 11:35 1793参考链接: a.http://www.programfan. ... -
线性查找二维数组
2012-06-05 17:23 10071.算法描述 有序(行有序,列有序,且每行从左至右递增 ...
相关推荐
注重算法设计的效率,对所有的算法进行了仔细、精确的运行时间分析,有利于进一步改进算法。 三、本书的用法 本书对内容进行了精心的设计和安排,尽可能考虑到所有水平的读者。即使是初学计算机算法的人,也可以在...
注重算法设计的效率,对所有的算法进行了仔细、精确的运行时间分析,有利于进一步改进算法。 三、本书的用法 本书对内容进行了精心的设计和安排,尽可能考虑到所有水平的读者。即使是初学计算机算法的人,也可以在...
附件是安装NumPy教程_详细版,文件绿色安全,请大家放心下载,仅供交流学习使用,无任何商业目的!
语音端点检测及其在Matlab中的实现.zip
使用C#完成一般文档的打印,带有页眉,页脚文档打印,表格打印,打印预览等
directx修复工具 DirectX修复工具(DirectX repair)是系统DirectX组件修复工具,DirectX修复工具主要是用于检测当前系统的DirectX状态,若发现异常情况就可以马上进行修复,非常快捷,使用效果也非常好。
人脸识别的主要算法 其核心算法是 欧式距离算法使用该算法计算两张脸的面部特征差异,一般在0.6 以下都可以被认为是同一张脸 人脸识别的主要步骤 1 获得人脸图片 2 将人脸图片转为128D的矩阵(这个也就是人脸特征的一种数字化表现) 3 保存人脸128D的特征到文件中 4 获取其他人脸转为128D特征通过欧式距离算法与我们保存的特征对比,如果差距在0.6以下就说明两张脸差距比较小
ciscn 全国大学生信息安全竞赛知识问答-CISCN 题库.zip
JAVA+SQL离散数学题库管理系统(源代码+LW+外文翻译)JAVA+SQL离散数学题库管理系统(源代码+LW+外文翻译)JAVA+SQL离散数学题库管理系统(源代码+LW+外文翻译)JAVA+SQL离散数学题库管理系统(源代码+LW+外文翻译)JAVA+SQL离散数学题库管理系统(源代码+LW+外文翻译)JAVA+SQL离散数学题库管理系统(源代码+LW+外文翻译)JAVA+SQL离散数学题库管理系统(源代码+LW+外文翻译)JAVA+SQL离散数学题库管理系统(源代码+LW+外文翻译)JAVA+SQL离散数学题库管理系统(源代码+LW+外文翻译)JAVA+SQL离散数学题库管理系统(源代码+LW+外文翻译)JAVA+SQL离散数学题库管理系统(源代码+LW+外文翻译)JAVA+SQL离散数学题库管理系统(源代码+LW+外文翻译)JAVA+SQL离散数学题库管理系统(源代码+LW+外文翻译)JAVA+SQL离散数学题库管理系统(源代码+LW+外文翻译)
strcmp函数应用.zip
蓝桥杯单片机第十一届国赛设计题试做
基于MATLAB的pca人脸识别.zip
520.html
JAVA在线考试管理系统(源代码+LW+开题报告+外文翻译+英文文献+答辩PPT)
STR710的定时器编程C语言例子,开发环境为IAR EWARM。.zip
协同过滤算法(Collaborative Filtering)是一种经典的推荐算法,其基本原理是“协同大家的反馈、评价和意见,一起对海量的信息进行过滤,从中筛选出用户可能感兴趣的信息”。它主要依赖于用户和物品之间的行为关系进行推荐。 协同过滤算法主要分为两类: 基于物品的协同过滤算法:给用户推荐与他之前喜欢的物品相似的物品。 基于用户的协同过滤算法:给用户推荐与他兴趣相似的用户喜欢的物品。 协同过滤算法的优点包括: 无需事先对商品或用户进行分类或标注,适用于各种类型的数据。 算法简单易懂,容易实现和部署。 推荐结果准确性较高,能够为用户提供个性化的推荐服务。 然而,协同过滤算法也存在一些缺点: 对数据量和数据质量要求较高,需要大量的历史数据和较高的数据质量。 容易受到“冷启动”问题的影响,即对新用户或新商品的推荐效果较差。 存在“同质化”问题,即推荐结果容易出现重复或相似的情况。 协同过滤算法在多个场景中有广泛的应用,如电商推荐系统、社交网络推荐和视频推荐系统等。在这些场景中,协同过滤算法可以根据用户的历史行为数据,推荐与用户兴趣相似的商品、用户或内容,从而提高用户的购买转化率、活跃度和社交体验。 未来,协同过滤算法的发展方向可能是结合其他推荐算法形成混合推荐系统,以充分发挥各算法的优势。
FTP(File Transfer Protocol)是文件传输协议的简称。 FTP的主要作用,就是让用户连接上一个远程计算机(这些计算机上运行着FTP服务器程序)查看远程计算机有哪些文件,然后把文件从远程计算机上拷到本地计算机,或把本地计算机的文件送到远程计算机去。 目前FTP服务器软件都为国外作品,例如Server_U、IIS,国内成熟的FTP服务器软件很少,有一些如(Crob FTP Server),但从功能上看来远不能和那些流行的服务器软件媲美。
本项目基于深度学习TensorFlow框架,针对滚动轴承故障诊断方法进行研究。项目采用了卷积神经网络(CNN)对轴承振动信号进行特征提取和分类,实现了对滚动轴承不同故障类型的自动诊断。 在技术实现上,项目利用TensorFlow搭建了一个高效的CNN模型,通过多层卷积、池化操作以及全连接层,自动学习轴承振动信号中的故障特征。同时,采用交叉熵损失函数优化模型参数,提高故障识别率。此外,项目还集成了数据预处理、模型训练、测试评估等功能模块,方便用户快速上手并进行实验研究。 经过运行测试,该项目代码运行稳定,诊断效果良好,可广泛应用于滚动轴承故障诊断领域。对于计算机相关专业的在校学生、老师或企业员工来说,该项目是一份难得的高分大作业资源,同时也是小白学习和实际项目借鉴的优秀参考资料。请放心下载使用,为您的学习和工作提供帮助!
超详细的SpringBoot框架入门教程 Spring Boot框架快速入门教程以大量示例讲解了Spring Boot在各类情境中的应用,让大家可以跟着老师的思维和代码快速理解并掌握。适用于Java 开发人员,尤其是初学Spring Boot的人员和需要从传统 Spring 转向 Spring Boot 开发的技术人员。 下边是动力节点的SpringBoot教程非常适合初学入门,讲的非常详细,而且全程无废话!
毕业设计[主机域名]ISPConfig 3.0.1.3_ispconfig3-codepub.zip