Aar*_*ock 7 python math integer-arithmetic
编写一个Python程序来查找一个4位数的整数,当它与自身相乘时,得到一个8位整数,其最后4位数等于原始数.
我会发布我的答案,但我对更优雅的解决方案感兴趣,简洁但易读的解决方案!(有人会对python有什么新的理解吗？)
Aus*_*tin 14
这是一个没有任何模块的单线解决方案:
>>> next((x for x in range(1000, 10000) if str(x*x)[-4:] == str(x)), None)
9376
如果您认为数字1000到3162,他们的广场给你一个7数字.因此,迭代3163将更加优化,因为正方形应该是8数字.感谢@adrin这么好的观点.
>>> next((x for x in range(3163, 10000) if str(x*x)[-4:] == str(x)), None)
9376
如果您对使用第三方库感到满意,可以使用numpy.此版本与numba优化相结合.
import numpy as np
from numba import jit
@jit(nopython=True)
def find_result():
for x in range(1e7**0.5, 1e9**0.5):
i = x**2
if i % 1e4 == x:
return (x, i)
print(find_result())
# (9376, 87909376)
[差不多] 1班轮:
from math import sqrt, ceil, floor
print(next(x for x in range(ceil(sqrt(10 ** 7)), floor(sqrt(10 ** 8 - 1))) if x == (x * x) % 10000))
打印:
9376
定时:
%timeit next(x for x in range(ceil(sqrt(10 ** 7)), floor(sqrt(10 ** 8 - 1))) if x == (x * x) % 10000)
546 µs ± 32.5 µs per loop (mean ± std. dev. of 7 runs, 1000 loops each)
@theausome的答案(最短(以字符为单位)):
%timeit next((x for x in range(3163, 10000) if str(x*x)[-4:] == str(x)), None)
3.09 ms ± 119 µs per loop (mean ± std. dev. of 7 runs, 100 loops each)
@jpp的答案(最快):
import numpy as np
from numba import jit
@jit(nopython=True)
def find_result():
for x in range(1e7**0.5, 1e9**0.5):
i = x**2
if i % 1e4 == x:
return (x, i)
%timeit find_result()
61.8 µs ± 1.46 µs per loop (mean ± std. dev. of 7 runs, 10000 loops each)
以下解决方案不像其他答案那样可读.但它缺乏可读性,效率提高.
蛮力方法检查给定范围内的每个数字,使其为O(10 ^ n),其中n是所需数字的数量(如果我们考虑乘法和转换,则最差).
相反,我们可以从右到左构建所需的数字,只要生成的数字形成其方形的尾随数字,就可以添加数字.这提供了一个O(n³)算法(参见底部的时间复杂度部分).
def get_all_numbers(n, _digits=None):
# We are provided digits that form a number with desired properties
digits = [] if _digits is None else _digits
# Base case: if we attained the number of digits, return those digits
if len(digits) >= n:
return [int(''.join(digits))]
solutions = []
# Add digits from 0 to 9 and check if the new number satisfies our property
for x in range(10):
next_digits = [str(x)] + digits if x else ['0'] + digits
next_number = int(''.join(next_digits))
# If it does try adding yet another digit
if int(str(next_number ** 2)[-len(next_digits):]) == next_number:
solutions.extend(get_all_numbers(n, next_digits))
# Filter out solutions with too few digits
# Necessary as we could have prepended only zeros to an existing solution
return [sol for sol in solutions if sol >= 10 ** (n - 1)]
def get_numbers(n, sqr_length=None):
if sqr_length:
return [x for x in get_all_numbers(n) if len(str(x ** 2)) == sqr_length]
else:
return get_all_numbers(n)
get_numbers(4, 8) # [9376]
这对于少量数字来说不是必需的,但是允许解决更大输入的问题,其中蛮力解决方案需要永远.
get_numbers(100) # Outputs in a few milliseconds
对于给定数量的数字n,除了0和1之外,最多只能存在两个解决方案.并且任何解决方案都是根据较少数字的解决方案构建的.
由此我们得出结论,尽管递归,但算法需要O(n)步才能找到解决方案.
现在,每个步骤都必须执行一些乘法和转换.整数转换为O(n²),Python中的乘法使用Karatsuba算法,该算法小于转换.
总的来说,这会产生O(n³)时间复杂度.
这可以通过使用线性整数转换算法来改进,然后提供O(n ^(1 + log(3)))复杂度.
这是一行实施,不包括97.24%的候选人:
import itertools
step = itertools.cycle((24, 1, 24, 51))
[x for x in range(3176, 10000, next(step)) if str(x*x)[-4:] == str(x) ]
拨打电话abcd.你可以通过限制最后两位来优化,cd只有4种合法的可能性,不包括96%的cd候选者.同样,我们只需要测试31 <= ab <100,不包括31%的候选人ab.因此我们排除了97.24%
cd_cands = set((n**2) % 100 for n in range(0,99+1) if ((n**2 % 100) == n))
cd_cands = sorted(cd_cands)
[0, 1, 25, 76]
for ab in range(31,99+1):
for cd in cd_cands:
n = ab*100 + cd
if n**2 % 10**4 == n :
print("Solution: {}".format(n))
#break if you only want the lowest/unique solution
...
Solution: 9376
(当然你可以把它压成一行列表理解,但它会很难看)
现在我们可以用以下观察来分离多个for循环:严格来说我们只需要在3162以上的第一个合法候选人开始测试,即3176.然后,我们通过连续添加步骤(100-76,1-0, 25-1,76-25)=(24,1,24,51)
import itertools
step = itertools.cycle((24, 1, 24, 51))
abcd = 3176
while abcd < 10**4:
if abcd**2 % 10000 == abcd:
print("Solution: {}".format(abcd))
abcd += next(step)
并且可以再次减少到顶部所示的单线(/双线).