刚巧看到一个网友研究“算法的力量”,说明好的算法有时候能大大提高速度。不过就这个网友提出的问题,其实不需要使用计算机来求解,数论方法很容易就能获取到方程的所有解。
问题是:
就是要找一个数出来,把这个数个位上的数字挪到最前面去,例如 123 变成 312,12345变成51234。但是还要求得到的“新数”要是原来数的两倍。
文章作者假定末位数为Y,10位以上为X,则需求就成了
(1) 2*(10X+Y) = Y*10 (n-1) + X
化简结果就是
(2) X = Y (10 (n-1) -2)/19
然后作者变成遍历计算10
(n-1) -2是否整除19。其实到这一步,数学的方法还可以进一步,不过需要一点的数论专业知识:
用数论的语言是求n-1使得
(3) 10 (n-1) = 2 (mod 19)
因为10和19互质(只有公约数1)、而且19是质数,所以根据费马定理
(4) 10 19-1 = 1 (mod 19)
如果等式(3)有解,n必定小于19,设定t=19-n,则
(5) 10 19-1-t = 1/10t (mod 19)
其中1/10
t代表10
tZ = 1 (mod 19)中的Z值,什么时候Z=2就是我们想要的,换言之,我们只需要知道什么时候10
t*2 = 1 (mod 19)就行,这个结果就很简单了,t的最小值为1。
所以,求解结果是:n最小值为19-t=18。有了n,Y从1-9都是可能的解。
需要说明的是:作者文章中计算10 的100次方(即n最大到100)内其实漏掉很多解。通过简单的数论知识就知道,如果n最小值为18,n=19k+18(k=0,1,2...)都是解。
所以,有时候,理论比计算来得更有挑战,只有人们没有找到求解方法的时候,才会思考各种逼近结果的算法。不过让我有点纳闷的是,小学5年级学生用的数学课外读物怎么就有这么高深的问题了?
分享到:
相关推荐
李开复:算法的力量,李开复:算法的力量,李开复:算法的力量
数字经济下的算法力量 -阿里巴巴-201902.pdf
很不错的一个介绍,适合大学生哈
阿里巴巴数字经济下的算法力量,包含了阿里内部的各类创新方法
展示算法的力量,通过举例解决实际问题展示算法。
算法的力量、算法的力量、(李开复)、程序员读
算法是计算机科学领域最重要的基石之一,但却受到了国内一些程序员的冷落。许多学生看到一些公司在招聘时要求的编程语言五花八门,就产生了一种误解,认为学计算机就是学各种编程语言,或者认为,学习最新的语言、...
在当今数字经济的浪潮中,算法已成为推动创新和效率的关键力量。2019年,阿里巴巴集团汇编了其算法实践的精髓,发布了《数字经济下的算法力量——阿里算法年度精选集》,这是一份对大数据解决方案进行深入剖析的文档...
算法是计算机科学领域最重要的基石之一,编程语言虽然该学,但是学习计算机算法和理论更重要,因为计算机语言和开发平台日新月异,但万变不离其宗的是那些算法和理论
阿里巴巴-数字经济下的算法力量 -2019.2-329页.pdf
算法是计算机科学领域最重要的基石之一,但却受到了国内一些程序员的冷落。许多学生看到一些公司在招聘时要求的编程语言五花八门就产生了一种误解,认为学计算机就是学各种编程语言,或者认为,学习最新的语言、技术...
模型算法大全(20+种常用算法模型+代码实现)模型算法大全(20+种常用算法模型+代码实现)模型算法大全(20+种常用算法模型+代码实现)模型算法大全(20+种常用算法模型+代码实现)模型算法大全(20+种常用算法模型+...
浅析Dijkstra最短路径算法在消防力量调集中的应用
LFU算法LFU算法LFU算法LFU算法LFU算法
分配算法 首次适应算法 最佳适应算法 循环首次适应算法 有流程图 源代码
详细介绍了神经网络算法、粒子群算法、遗传算法、模糊逻辑控制、免疫算法、蚁群算法、小波分析算法及其MATLAB的实现方式等内容; 第二部分详细介绍了智能算法的工程中的应用问题,包括模糊神经网络在工程中的应用、...
1. 通过实验,进一步理解直线段扫描转换的DDA算法、中点bresenham算法及bresenham算法的基本原理; 2. 掌握以上算法生成直线段的基本过程; 3. 通过编程,会在C/C++环境下完成用DDA算法、中点bresenham算法及...
用matlab实现了标准粒子群算法,遗传算法,以及粒子群遗传算法的结合算法。可直接运行
2019 数字经济下的算法力量阿里算法年度精选集(327p)
我搜集的电梯调度算法,论文。包括:强化学习算法,LOOK调度算法,最短寻道算法,遗传算法,滚动优化算法,模糊控制,预约电梯群控算法,基于现场总线的算法。希望免除大家搜索之苦。