- 浏览: 177969 次
- 性别:
- 来自: 武汉
文章分类
最新评论
-
beiizl:
用了博主的方法和代码,不同证书居然可以正常通讯?
Java SSLSocket的使用 -
SHANGLIJAVA:
sorry,运行时没看清。博主的代码确实没问题。。。
Java SSLSocket的使用 -
SHANGLIJAVA:
YoungeeOne 写道最后一个为什么初始化一个空的证书,也 ...
Java SSLSocket的使用 -
q979713444:
那这个的心跳怎么弄呢
Java SSLSocket的使用 -
43350860:
busybox不是每台机器有安装的, 有没有比较裸的办法获取p ...
android中查看端口占用
算法小练习--歌德巴赫猜想
- 博客分类:
- 数据结构与算法
晚上没事,尝试解决一个小的算法问题。 我的算法比较弱,也没查什么参考资料,自己想的思路。肯定有更好的解法。
1. 歌德巴赫猜想
所有大于等于6的偶数都可以表示成两个(奇)素数之和。给定1-10000;要求找出每一个可以表示为两素数之和的数,如果有多对,则只需要输出其中之一即可。
输出:
N = a + b;
N=1-10000;对于不能表示的就不用输出。
a,b为两个素数。
要求:复杂度较低,代码可运行。
2. 思路:
1. 找到1-10000范围内的素数, 得到一个有序数组A (时间复杂度为O(nlogn))
2. 对1-10000范围内的数进行遍历. 对每个数 i, 使用二分查找确定它在有序数组A中的"位置" pos (若存在,则为数组下标;若不存在,则为这个数插入该数组后仍能保证数组的大致位置) (时间复杂度为O(nlogn))
3. 从有序数组A的pos位置开始,令num = A[pos],二分查找确定 i - num是否也在这个数组A中。 若在, 则表示i可以用两个素数之和表示。否则, pos递减继续查找 (时间复杂度 O(n * n * logn) ??? )
第1步生成素数列表应该有更好的方法。 第3步感觉比较低效, 但实际运行时发现pos需要递减的情况比较少。也就是说,一个很大的偶数,基本上都会被分解成一个很大的素数和一个非常小的素数。下面是运行结果。
3. 代码
# encoding: utf-8 import math from timeit import Timer from functools import partial # 生成素数列表 # 版本一. 比较低效 def sushu(n): num = 2 alist = [2] for i in range(3, n + 1): istrue = True #for j in range(2, int(math.sqrt(i))): for j in range(2, i / 2 + 1): if i % j == 0: istrue = False break if istrue: alist.append(i) return alist # 生成素数列表 # 版本二 def sushu2(n): num = 2 alist = [2] for i in range(3, n + 1): istrue = True for j in range(2, int(math.sqrt(i)) + 1): #for j in range(2, i / 2): if i % j == 0: istrue = False break if istrue: alist.append(i) return alist # 生成素数列表 # 版本三 def sushu3(n): #num = 2 alist = [] for i in range(3, n + 1, 2): istrue = True for j in range(3, int(math.sqrt(i)) + 1): #for j in range(2, i / 2): if i % j == 0: istrue = False break if istrue: alist.append(i) return alist # 通过二分查找找到alist中最接近 n的数的位置 def bin_search(alist, n): low = 0 high = len(alist) while low < high: mid = low + (high - low) / 2 if n == alist[mid]: return mid elif n < alist[mid]: high = mid - 1 else: low = mid + 1 return low # 所有大于等于6的偶数都可以表示成两个(奇)素数之和。 def split(n): # 素数列表 alist = sushu3(n) alist_len = len(alist) for i in range(8, n + 1, 2): pos = bin_search(alist, i) #print pos # 修正pos if pos >= alist_len: pos = alist_len - 1 isok = 0 while pos > 0: isok = 1 #print pos >= alist_len j = i - alist[pos] # TODO in 是否低效 if j in alist: isok = 2 break pos -= 1 ''' if isok == 2: print '%d = %d + %d' %(i, alist[pos], i - alist[pos]) elif isok == 1: print '%d = 不能表示' % (i) else: print '%d = 运行异常' % (i) ''' # 所有大于等于6的偶数都可以表示成两个(奇)素数之和。 def split2(n): # 素数列表 alist = sushu3(n) alist_len = len(alist) for i in range(8, n + 1, 2): pos = bin_search(alist, i) #print pos # 修正pos if pos >= alist_len: pos = alist_len - 1 isok = 0 while pos > 0: isok = 1 #print pos >= alist_len j = i - alist[pos] if j == alist[bin_search(alist, j)]: isok = 2 break pos -= 1 ''' if isok == 2: print '%d = %d + %d' %(i, alist[pos], i - alist[pos]) elif isok == 1: print '%d = 不能表示' % (i) else: print '%d = 运行异常' % (i) ''' if __name__ == '__main__': #print sushu(100) if False: t = Timer(partial(sushu, 10000)) print t.timeit(10) t2 = Timer(partial(sushu2, 10000)) print t2.timeit(10) t3 = Timer(partial(sushu3, 10000)) print t3.timeit(10) if False: print sushu(100) print sushu2(100) print sushu3(100) if False: alist = sushu3(100) print alist for x in [96, 100, 110]: pos = bin_search(alist, x) print 'pos = ', pos #print alist[pos - 1], alist[pos], alist[pos + 1] if True: t = Timer(partial(split, 10000)) print t.timeit(10) t2 = Timer(partial(split2, 10000)) print t2.timeit(10)
发表评论
-
算法小练习-根据上排数求下排数
2013-01-16 10:24 2233参考 http://blog.csdn.net ... -
算法小练习-二分查找树转换成排序的双向链表
2013-01-10 23:46 0题目:输入一棵二元查找树,将该二元查找树转换成一个排序的双向链 ... -
Trie树
2012-12-30 12:15 0数据结构之Trie树 http://dongxiche ... -
一些小算法题2
2012-12-29 21:31 0求N个字符串中的最大公子串 http://www.it ... -
一些小算法题
2012-12-20 19:38 0android面试题 http://blog.c ... -
(正式)Java学习之Collection
2012-11-30 23:15 0Collection类详解 -
(正式)数据结构之排序算法
2012-11-29 08:57 01. 归并算法 python版 # --coding ... -
Java学习之BlockingQueue及其实现
2012-11-15 14:34 0static class MyBlockingQ ... -
Bit-Map算法
2012-11-07 10:08 0http://baike.baidu.com/view/ ... -
控制cpu的占用率
2012-09-21 17:09 0test -
Fibonacci级数求解
2012-08-10 19:16 0一点点空间,换取了无数倍的时间。效率的差别真是恐怖。 ... -
地图寻点问题和100万电话号查重
2012-07-11 11:42 0分治法求最近两点距离(理论) 给一个点集,求其中 ... -
堆排序
2012-07-10 10:50 0import java.util.Arrays; ... -
归并排序
2012-07-09 17:38 0# --coding: utf-8 -- # 归并 ... -
快速排序(2)
2012-07-06 14:02 0一个Quicksort究竟可以写到多么短 http: ... -
快速排序(1)
2012-07-06 13:18 0public class QuickSort { ... -
栈与队列(1)
2012-06-28 20:33 0import java.util.Arrays; ... -
简单排序(3)插入排序
2012-06-28 20:01 0思想: 1) 假定第0个数据有序,第1个数据开始无序,in标 ... -
简单排序(2)选择排序
2012-06-27 21:23 0思想 有n条数据,使用i标记最左边未排序的数据,且暂时标记第 ... -
简单排序(1)冒泡排序
2012-06-27 20:40 0思想 从第0个数开始,依次比较第0和第1个数据,如果 ...
相关推荐
2--[哥德巴赫猜想].zip源码scratch2.0 3.0编程项目源文件源码案例素材源代码2--[哥德巴赫猜想].zip源码scratch2.0 3.0编程项目源文件源码案例素材源代码2--[哥德巴赫猜想].zip源码scratch2.0 3.0编程项目源文件源码...
从关于偶数的哥德巴赫猜想,可推出:任一大于7的奇数都可写成三个质数之和的猜想。后者称为“弱哥德巴赫猜想”或“关于奇数的哥德巴赫猜想”。若关于偶数的哥德巴赫猜想是对的,则关于奇数的哥德巴赫猜想也会是对的...
python验证哥德巴赫猜想 import checkPrime as aa def canSplit(n): for m in range(1,n//2): if aa.isPrime(m) and aa.isPrime(n-m): return True return False flag = True for n in range(8,10000,2): if ...
哥德巴赫猜想 数据结构(C语言实现) 用C语言实现哥德巴赫猜想的数据结构!cpp文件。
验证哥德巴赫猜想c 验证哥德巴赫猜想c 验证哥德巴赫猜想c 验证哥德巴赫猜想c 验证哥德巴赫猜想c 验证哥德巴赫猜想c 验证哥德巴赫猜想c 验证哥德巴赫猜想c 验证哥德巴赫猜想c 验证哥德巴赫猜想c 验证哥德巴赫猜想c ...
4-验证哥德巴赫猜想.cpp
1157:哥德巴赫猜想 时间限制: 1000 ms 内存限制: 65536 KB 提交数: 14300 通过数: 8298 【题目描述】 哥德巴赫猜想的命题之一是:大于6 的偶数等于两个素数之和。编程将6~100所有偶数表示成两个素数之和。 【输入...
哥德巴赫猜想的算法,一般是可以用很多种语言来实现,这是用c语言写的,希望对大家有用
最古老的哥德巴赫猜想(“每个甚至严格大于4的正整数都是两个质数之和”)自1742年以来一直没有得到证明。最近的证明[1]将哥德巴赫猜想与每个正复合整数n严格大于3的事实联系在一起。 ,位于两个质数之间的距离的...
数学领域著名的“哥德巴赫猜想”的大致意思是:任何一个大于2的偶数总能表示为两个素数之和。比如:24=5+19,其中5和19都是素数。本实验的任务是设计一个程序,验证20亿以内的偶数都可以分解成两个素数之和。 输入...
哥德巴赫猜想\哥德巴赫猜想 C++验证源码
这是一个基于C语言的哥德巴赫猜想,主要的思想是循环。
在本文中,我们使用集合,函数,筛和数论来研究素数和合成数,证明由欧拉函数导出的素数个数的下限公式,并... 我们通过数学归纳证明了哥德巴赫猜想是正确的。 最后,我们通过数学分析和计算机数据证明了证明的可靠性。
【PYTHON练习题】验证哥德巴赫猜想 【PYTHON练习题】验证哥德巴赫猜想 编制判断素数的Sub函数或者Function函数,验证哥德巴赫猜想:⼀个不⼩于6的偶数可以表⽰为两个素数之和。例 如,6=3+3,8=5+3,10=3+7. x=int...
用java验证哥德巴赫猜想,输出满足哥德巴赫猜想的所以值
哥德巴赫猜想偶数公式的计算机验证,庄严,庄宏飞,本文选用各种不同性质的偶数,对哥德巴赫猜想证明的最后结论,哥德巴赫猜想偶数公式进行了大范围验证对比,理论计算结果与客观实
自己写的 关于哥德巴赫猜想验证,只要输入一个 数字 ,就能验证输入数及所有小于输入数的数是否符合哥德巴赫猜想,有较好算法,以100W为例,运行时间只需40几秒(程序包含运行时间的计算)
哥德巴赫猜想.cpp
C语言源码哥德巴赫猜想,界面不错,验证哥德巴赫猜想,大一新生必备
哥德巴赫猜想的简单代码证明,当然只是一个框架,不是真正的证明。