【编程解决智力题之三】大数计算——Lua的短板
lua吧
全部回复
仅看楼主
level 13
沙城雨人 楼主
【题目】:有一个数字,把这个数字最后一位挪到第一位,新的数字是原来数字的两倍,找出一个这样的数。
【分析】:假设这个数是一个N+1位数(N>=1),前N位为a,最后一位为b,则此数可记为10a+b。
根据题意:
2*(10*a + b) = b*10^N + a
==> 19*a = b*(10^N - 2)
我们需要找到一个10^N - 2的数,它能被19整除,或者说找一个10^N,它整除19的余数为2。
lua求余数的函数为:math.mod,看起来直接写个简单的程序就能算出结果:
local n = 0
local k = 1
while true do
n = n + 1
k = k*10
if math(k,19) == 2 then
break
end
end
print(n,k-2/19)
-----------------------------------
结果:
171e+017
这里算出了n=17,也就是说这个数是一个18位数(n+1位数),但是我们试图输出a值,却发现是个科学计算法的精确度很低的数。
大数计算是lua的短板,因为lua中没有整数的概念,所有的数都是双精度型,在这个数比较大的时候,一律采用科学计数法,得到的结果不是精确值。所以我们在编程的时候,一定要设法避免大数计算。
如果只求n值,有个数论的技巧:从1开始,一路乘10取mod 19,直到结果等于2为止,取模运算将结果限制在0-18之间,就不会因为精度影响算法结果。程序如下:
local n = 0
local k = 1
while true do
n = n + 1
k = math.mod(k*10,19)
if k == 2 then
break
end
end
print(n)
-----------------------------------
结果:
17
同样的问题,如果用c,c++或者python,都可以算出精确结果。
附python程序(python必须缩排,自己处理一下):
n=1
k=10
while True:
n=n+1
k=k*10
if k%19==2:
a=(k-2)/19
break
print(n,a)
-----------------------------------
结果:
17 5263
15789473684
21
这个题目是多解,事实上,当b=1时的第一个解 05263
15789473684
2实际只有17位,是不合格的,当b=2-9时算出来的都是合法解:
105263
15789473684
2
157894736842105263
2105263
15789473684

263157 894736 842105
315789 473684 210526
2014年04月11日 08点04分 1
level 13
沙城雨人 楼主
漏了2个:
421052631578947368
473684210526315789
事实上,这一串数字和1/19的循环节有密切关系。这里面涉及的数论知识有兴趣的朋友自己研究。
2014年04月11日 08点04分 3
坐等大神教我用Lua算奥数
2014年10月22日 09点10分
level 13
沙城雨人 楼主
还漏了个3
15789473684
210526,贴吧不能修改只有打补丁了。
2014年04月11日 08点04分 4
level 10
大数计算其实并不考虑lua
因为没有integer
但是既然会要求大数计算
也就一般要求高效率了
一般就用C++的数组去模拟了
   --新鲜萝莉交流与深入:3.1.4.1.8.6.0.8.2
2014年10月25日 09点10分 6
level 8
。。。。 挖下坟,
用lua table 模拟大数可求精确的数值。
2015年02月17日 02点02分 7
level 1
执子之手,与子偕老。愿得一人心,白首不分离
2015年05月02日 15点05分 8
level 2
挖下坟。
楼主的lua程序有问题,print(n,k-2/19)应该是print(n,(k-2)/19),不是lua的问题。
楼主说的问题不存在。
2019年12月11日 02点12分 9
1