




已阅读5页,还剩6页未读, 继续免费阅读
版权说明:本文档由用户提供并上传,收益归属内容提供方,若内容存在侵权,请进行举报或认领
文档简介
习题 求100内的素数 为了比较算法效率我们扩大到求100000内素数 import datetime 1 简单算法 一个数能被从2开始到自己的平发根的正整数整数整除 就是合数 start datetime datetime now n 100000 count 0 for x in range 2 n for i in range 2 int x 0 5 1 if x i 0 break else count 1 print x delta datetime datetime now start total seconds print count 9592 print delta 0 267015 print 30 2 使用奇数 start datetime datetime now n 100000 count 1 for x in range 3 n 2 for i in range 3 int x 0 5 1 2 if x i 0 break else count 1 print x delta datetime datetime now start total seconds print count 9592 print delta 0 132007 print 30 3 存储质数 合数一定可以分解为几个质数的乘积 2是质数 质数一定不能整除1和本身之内的整数 start datetime datetime now n 100000 算法2和算法4对比 算法2的奇数应该是多于算法4的 也就是算法4应该要快一点 但是测试的记过却不是 为什 么 结果是增加了质数列表反而慢了 为什么 修改算法如下 count 1 primenumbers 2 for x in range 3 n 2 for i in primenumbers if x i 0 break else primenumbers append x count 1 delta datetime datetime now start total seconds print count 9592 print delta 4 02523 print 30 4 缩小范围 start datetime datetime now n 100000 count 1 primenumbers 2 for x in range 3 n 2 flag False 不是素数 for i in primenumbers if i int x 0 5 素数 flag True break if x i 0 合数 flag False break if flag primenumbers append x count 1 delta datetime datetime now start total seconds print count 9592 print delta 0 315018 4 缩小范围 x 0 5 在循环中只需计算一次 使用列表存储已有的质数 同时缩小范围 start datetime datetime now n 100000 这回测试 速度第一了 也就是增加了列表 记录了质数 控制了边界后 使用质数来取模比使用奇数计算更少 空间换时间 使用列表空间来换取计算时间 素数性质 大于3的素数只有6N 1和6N 1两种形式 如果6N 1和6N 1都是素数称为孪生素数 由此 得到下面算法5 count 1 primenumbers 2 for x in range 3 n 2 大于2质数只可能是奇数 flag False 不是素数 edge int x 0 5 计算一次 for i in primenumbers if i edge 素数 flag True break if x i 0 合数 flag False break if flag primenumbers append x count 1 delta datetime datetime now start total seconds print count 9592 print delta 0 106006 大于3的素数只有6N 1和6N 1两种形式 如果6N 1和6N 1都是素数称为孪生素数 注意 其实测试的都是6的倍数的前后的数字 这些数字一定是奇数 n 100 count 5 2 3 5 x 7 step 4 while x n if x 5 0 print x 打印出待测试的数 x step step 4 if step 2 else 2 5 使用素数性质 大于3的素数只有6N 1和6N 1两种形式 如果6N 1和6N 1都是素数称为孪生素数 start datetime datetime now n 100000 count 3 2 3 5 x 7 用了这个性质并没有超过算法4 原因还是在于使用列表来存储已经计算得到的素数来减少计算 请自行使用列表 完成素数的存储 计算杨辉三角前6行 第n行有n项 n是正整数 step 4 while x n if x 5 0 for i in range 3 int x 0 5 1 2 if x i 0 合数 break else count 1 x step step 4 if step 2 else 2 delta datetime datetime now start total seconds print count 9592 print delta 0 122006 第n行数字之和为2 n 1 解法1 杨辉三角的基本实现 下一行依赖上一行所有元素 是上一行所有元素的两两相加的和 再在两头各加1 预先构建前两行 从而推导出后面的所有行 变体 从第一行开始 解法2 补零 除了第一行以外 每一行每一个元素 包括两头的1 都是由上一行的元素相加得到 如何得到两头的1呢 目标 是打印指定的行 所以算出一行就打印一行 不需要用一个大空间存储所有已经算出的行 while循环实现 triangle 1 1 1 for i in range 2 6 cur 1 pre triangle i 1 for j in range len pre 1 cur append pre j pre j 1 前一行2项之和 cur append 1 triangle append cur print triangle triangle n 6 for i in range n cur 1 triangle append cur if i 0 continue pre triangle i 1 for j in range len pre 1 cur append pre j pre j 1 前一行2项之和 cur append 1 print triangle for循环实现 解法3 对称性 思路 能不能一次性开辟空间 可以使用列表解析式或者循环迭代的方式 能不能减少一半的数字计算 n 6 newline 1 第一行是特例 因为0 0不等于1 print newline for i in range 1 6 oldline newline copy 浅拷贝并补0 oldline append 0 尾部补0相当于两端补0 newline clear 使用append 所以要清除 offset 0 while offset i newline append oldline offset 1 oldline offset offset 1 print newline n 6 newline 1 第一行是特例 因为0 0不等于1 print newline for i in range 1 6 oldline newline copy 浅拷贝并补0 oldline append 0 尾部补0相当于两端补0 newline clear 使用append 所以要清除 for j in range i 1 newline append oldline j 1 oldline j print newline 1 构建行 上面创建每一行的代码过于啰嗦了 一次性创建出一行 2 中点的确定 triangle n 6 for i in range n row 1 for k in range i row append 1 if k i 1 else row append 0 triangle append row if i 0 continue print triangle triangle n 6 for i in range n row 1 i 1 triangle append row if i 0 continue print triangle 1 1 1 1 2 1 1 3 3 1 1 4 6 4 1 1 5 10 10 5 1 把整个杨辉三角看成左对齐的二维矩阵 i 2时 在第3行 中点的列索引j 1 i 3时 在第4行 无中点 i 4时 在第5行 中点的列索引j 2 得到以下规律 如果有i 2j 则有中点 triangle n 6 for i in range n row 1 i 1 一次开辟空间 triangle append row 上面的代码row j 1 val多做了一次 解法4 单行覆盖 方法2每次都要清除列表 有点浪费时间 能够用上方法3的对称性的同时 只开辟1个列表实现吗 i为0 1不进来 i为2 range 1 2 j取1 i为3 range 1 2 j取1 i为4 range 1 3 j取1 2 for j in range 1 i 2 1 val triangle i 1 j 1 triangle i 1 j row j val row j 1 val print triangle triangle n 6 for i in range n row 1 i 1 一次开辟空间 triangle append row i为0 1不进来 i为2 range 1 2 j取1 i为3 range 1 2 j取1 i为4 range 1 3 j取1 2 for j in range 1 i 2 1 val triangle i 1 j 1 triangle i 1 j row j val if i 2 j row j 1 val print triangle 首先我们明确的知道所求最大行的元素个数 例如前6行的最大行元素个数为6个 下一行等于首元素不变 覆盖 中间元素 问题出在哪里了呢 原因在于 4覆盖了3 导致3 3变成了3 4才有了7 使用一个临时变量解决 n 6 row 1 n 一次性开辟足够的空间 print row print 30 for i in range 6 offset n i for j in range 1 i 2 1 i为0 1不进入 val row j 1 row j row j val if i 2 j row j offset val print row i 1 print row n 运行结果如下 1 1 1 1 1 1 1 1 1 1 2 1 1 3 3 1 1 4 7 4 1 1 5 12 12 5 1 n 6 row 1 n 一次性开辟足够的空间 print row print 30 for i in range 6 offset n i old 1 相当于每行行首1 因为i从4开始就有覆盖了 引入这个变量 for j in range 1 i 2 1 i为0 1不进入 val old row j old row j row j val if i 2 j row j offset val print
温馨提示
- 1. 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
- 2. 本站的文档不包含任何第三方提供的附件图纸等,如果需要附件,请联系上传者。文件的所有权益归上传用户所有。
- 3. 本站RAR压缩包中若带图纸,网页内容里面会有图纸预览,若没有图纸预览就没有图纸。
- 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
- 5. 人人文库网仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对用户上传分享的文档内容本身不做任何修改或编辑,并不能对任何下载内容负责。
- 6. 下载文件中如有侵权或不适当内容,请与我们联系,我们立即纠正。
- 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。
最新文档
- 2025煤矿企业主要负责人安全生产知识和管理能力考试经典试题及答案
- 综合解析苏科版八年级物理下册《力与运动》同步测试试卷(附答案详解)
- 考点解析-人教版八年级物理上册第6章质量与密度-质量专题测试试题(含详细解析)
- 2025建筑结构构造试题及答案
- 综合解析人教版八年级物理《功和机械能》章节练习试题(含答案解析)
- 考点解析-人教版八年级物理上册第4章光现象同步训练试卷
- 达标测试人教版八年级物理上册第5章透镜及其应用-透镜综合测评试卷(附答案详解)
- 考点解析人教版八年级上册物理物态变化《汽化和液化》专项攻克练习题(含答案详解)
- 考点攻克人教版八年级上册物理物态变化《汽化和液化》章节训练试卷(含答案详解版)
- 绘画光影考试题及答案解析
- 消防管网渗漏水点排查施工方案
- 2025年福建省事业单位招聘考试教师招聘体育学科专业知识试卷(体育教学)试题
- 核电站保安考试题及答案
- 2025年绍兴鉴湖酿酒有限公司招聘7人考试模拟试题及答案解析
- 2025内蒙古国贸集团招聘11人考试参考题库及答案解析
- 民航救生衣演示知识培训课件
- 2025-2026学年第一勾股定理、第二章实数检测试卷北师大版八年级数学上册
- 2025内初班语文试卷及答案
- 2025年甘肃省酒泉市瓜州县招聘村副职干部30人考试参考试题及答案解析
- 2025年驾照三力测试试题题库及答案
- 农村厨房翻建申请书
评论
0/150
提交评论