文档章节

数学和逻辑思维的魅力

专业写BUG的程序员
 专业写BUG的程序员
发布于 09/11 20:37
字数 621
阅读 61
收藏 0

 

解法1: 暴力破解, 从1到m 逐个进行判断。 得分70 

时间复杂度 O(m * n )

 

解法2: 暴力破解, 但这个暴力破解比第一个暴力破解要稍微好一点点。得分90分

假设 三个质数 3  ,5 ,7 。 必须先从小到大排序。 

7的倍数 有 m/7 个。

5的倍数 有 m/5 个 , 但是这其中有一些是7的倍数 。

3的倍数有 m/3 个 , 但是这里面有5的倍数和7的倍数 。

O( ( m/3+  m/5 + m/7   ) * n )   当 1 / a0 + 1 / a1 + ... + 1 / an < 1 时, 此算法比较占优势。

 

解法3 : 运用数学知识,容斥原理进行解决。 

 当两个质数时        M / a0 + M / a1 - M / lcm(a0,a1)  

当三个质数时   M / a0 + M / a1 + M / a2 -  M / lcm(a0,a1)   - M / lcm(a0,a2)  - M / lcm(a1,a2) +  M / lcm(a0,a1,a2)  

lcm (a0,a1,a2) = a0 * a1 * a2 可能会越界 。 所以 M / a0 / a1 / a2 .

 

从a0 ,a1 , a2 ... a(n-1)  任取m个数  ax1,ax2 ,... ,axm  . 总共有 (2^N - 1)  种取法。  (-1)^(m+1)  M / lcm(ax1,ax2 ,... ,axm) .

设 i > 0 且 i < 2^N 那么i 代表了一种取法。

将i转化为二进制 。 如果二进制第x位为1 则代表取了ax 。 不太好描述,直接上算法。 

 

 

当然这个算法有一个很大的弊端,多做了许多的除法运算。 

M / a0 / a1 ,   M / a0 / a1 / a2  做了5次除法。 实际上如果能记录下  M / a0 / a1 的值 只需要做3次除法即可 。

改进版的算法 。 这个算法之所以更快是因为sum能记录前面的运算结果。 

 

更快的算法。 

考虑到 M / a0 / a1 / a2 / a3 ... / ax  可能为0的情况,  当sum = 0时应该直接结束递归调用。 并且   17 /  3 / 5 / 7  做了三次除法才得到0, 其实做两次除法即可 17 / 7 / 5 即可得到0 .  因此将 a0,a1, a2 , ... ax 按从大到小排序将会是更好的选择。 从结果来看快了将近20% ,从82毫秒下降到56毫秒。 

 

c++ 的实现更加恐怖 4毫秒。

 

© 著作权归作者所有

专业写BUG的程序员

专业写BUG的程序员

粉丝 9
博文 123
码字总数 31504
作品 0
海淀
程序员
私信 提问
为什么具有编程思维的孩子更容易成功?孩子为什么要学编程?你想要的答案都在这儿!

为什么青少年编程突然间火了?背后有什么“阴谋”吗? 青少年编程真的有那么好吗?还是英美放的烟雾弹?又或者只是一种新的噱头? 青少年编程到底要不要跟风学? 今天,我们就来聊一聊“青少...

bodasisiter
01/08
131
0
在人工智能发展趋势下,数学教育该何去何从?

     对于“人工智能(AI)”这个名词,我想大家应该都非常熟悉,即使不是从事这一行业的工作人员,至少也听说过这个专业术语。如相关的人工智能产品已经完全走进我们的生活,如智能手机...

中国机器人
2018/05/09
0
0
浅谈学习Scratch的必要性

一、Scratch简介 Scratch是由MIT(美国麻省理工学院)针对5至16岁的儿童和青少年设计的可视化程序设计语言与开发环境,专注于用编程实现简单的动画效果。 Scratch的目的是“创作和分享你自己的...

充电实践
2018/09/16
0
0
Java编程那些事儿

Java编程那些事儿 从大学毕业到现在,马上就六年了,这六年中从事过开发,也从事培训工作,相比而言,参加培训工作的时间要长一些。由于工作的特点,遇到了各种各样的学生,在学习编程时遇到...

超人学院
2016/07/27
70
0
为什么说手写代码最能看出一个程序员的编程功底来?

记得初中第一次接触编程的时候,那时学的是FoxBase,老师带着大家用笔写,没有直接上机的,当时也没觉得什么,没想到,现在回忆下当时手写,锻炼语言是其次,真正锻炼的大脑对程序的思维逻辑...

编程需要艺术
2018/05/21
0
0

没有更多内容

加载失败,请刷新页面

加载更多

小知识:讲述Linux命令别名与资源文件的区别

别名 别名是命令的快捷方式。为那些需要经常执行,但需要很长时间输入的长命令创建快捷方式很有用。语法是: alias ppp='ping www.baidu.com' 它们并不总是用来缩短长命令。重要的是,你将它...

老孟的Linux私房菜
47分钟前
3
0
《JAVA核心知识》学习笔记(6. Spring 原理)-5

它是一个全面的、企业应用开发一站式的解决方案,贯穿表现层、业务层、持久层。但是 Spring 仍然可以和其他的框架无缝整合。 6.1.1. Spring 特点 6.1.1.1. 轻量级 6.1.1.2. 控制反转 6.1.1....

Shingfi
48分钟前
5
0
Excel导入数据库数据+Excel导入网页数据【实时追踪】

1.Excel导入数据库数据:数据选项卡------>导入数据 2.Excel导入网页数据【实时追踪】:

东方墨天
57分钟前
5
1
正则表达式如何匹配一个单词存在一次或零次并且不占捕获组位置

正则表达式如何匹配一个单词存在一次或零次并且不占捕获组位置 今天要用正则表达式实现匹配一个词出现一次或者不出现的情况,但是又不仅仅是这么简单的需求。先详细说下我这种情况吧,也许有...

Airship
今天
6
0
第八讲:asp.net C# web 读取文件

本讲主要讲解如何在asp.net页面上传文件。 首先,前台页面: 其次,后台页面: 结果: 1、前台效果: 2、后台结果:

刘日辉
今天
5
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部