如何处理:
写出你自己的无限精度"sum"产品";,以及";以";函数,将数字表示为0和9之间的数字,最低有效数字在前。因此:0表示为空列表[],10表示为[0,1]。您可以假设数字是非负数(不需要负数或减法)。
我有一些函数可以转换为和从中转换。
例如:iint(5387) == [7, 8, 3, 5]
和pint([7, 8, 3, 5]) == 5387
def iint(n):
# list of all digits in the int
digits = [int(x) for x in str(n)]
# reverse the list
digits.reverse()
return digits
def pint(I):
# new int c
c = 0
# iterates through list
for i in range(len(I)):
# add to c digit in the list multiplied by 10^of its position in the list. 1, 10, 100, 1000 ect.
c = c + I[i] * (10 ** i)
return c
# add two infinite integers
def iadd(I, J):
pass
首先将只是转换回CCD_ 3进行计算;解决问题";。
不是在寻找一个完整的解决方案,只是一些关于iadd()
从哪里开始的指针,因为我完全被难住了。我想在你得到iadd()
之后,剩下的应该足够简单了。
对于编写iadd
函数,一种方法是使用测试驱动开发;编写测试输入和预期输出。assert
表示它们相等,然后重写函数,使其通过测试用例。
在需要将两个数字列表相加在一起的特定情况下;你怎么用手做的"(正如一条评论所指出的)是一个很好的起点。你可能会
- 从最低有效数字开始
- 将单个数字相加(包括前一个数字的进位,如果有的话)
- 携带";高";如果结果是>9
- 记录添加的结果
- 从步骤2循环,直到用完较短的数字
- 如果你有一个进位数字";剩余,";处理得当
- 如果输入数字中的一个数字比另一个数字多;剩余的";数字
下面的代码片段应该有助于给出一些想法:
for d in range(min(len(I),len(J))):
added = I[d] + J[d]
digit = added%10 + carry
carry = added//10
还有一些测试案例可以尝试:
assert iadd([1], [1]) == [2] # 1 + 1 == 2
assert iadd([0,1], [1]) == [1,1] # 10 + 1 == 11
assert iadd([9,1], [1]) == [0,2] # 19 + 1 == 20
assert iadd([9,9,9,9,9], [2]) == [1,0,0,0,0,1] # 99,999 + 2 == 100,001
assert iadd([4,0,2], [9,2,3,4,1]) == [3,3,5,4,1] # 201 + 14,329 == 14,533
Itertools的zip_lengest对于实现加法操作应该非常有用。
例如:
def iint(N): return [int(d) for d in reversed(str(N))]
def pint(N): return int("".join(map(str,reversed(N))))
from itertools import zip_longest
def iadd(A,B):
result = [0]
for a,b in zip_longest(A,B,fillvalue=0):
result[-1:] = reversed(divmod(a+b+result[-1],10))
while result and not result[-1]: result.pop(-1) # remove leading zeros
return result
a = iint(1234)
b = iint(8910)
print(iadd(a,b)) # [4, 4, 1, 0, 1] (10144)
对于乘法,你应该确保中间结果低于100
def iprod(A,B):
result = []
for iA,a in enumerate(A):
if not a: continue
result = iadd(result,[0]*iA+[a*d for d in B]) # a*d+9 <= 90
return result
print(iprod(a,b)) # [0, 4, 9, 4, 9, 9, 0, 1] 10994940
对于幂运算,您需要将过程分解为合理数量的乘法。这可以通过将指数分解为2的幂并将结果乘以基数的复数平方(对于1位)来实现。但是您需要制作一个除以2的函数来实现它。
这种策略是基于这样一个事实,即将基数乘以各种幂,再加上这些幂:
A^7 * A^6 = A^13
任何数字都可以表示为二次幂的和:
13 = 1 + 4 + 8,
所以
A^13 = A^1 * A^4 * A^8.
这将A^B的乘法次数减少到2log(B),这比A本身乘以B-1倍要少得多(尽管我们将处理更大的数字)。
def idiv2(N):
result = N.copy() or [0]
carry = 0
for i,d in enumerate(reversed(N),1):
result[-i],carry = divmod(result[-i]+carry*10,2)
return result if result[-1] else result[:-1]
def ipow(A,B):
result, a2n = [1], [] # a2n is compounded squares A, A^2, A^4, A^8, ...
while B:
a2n = iprod(a2n,a2n) if a2n else A
if B[0]%2 : result = iprod(result,a2n)
B = idiv2(B)
return result
print(ipow(iint(12),iint(13)))
# [2, 7, 0, 9, 7, 3, 5, 0, 2, 3, 9, 9, 6, 0, 1] 106993205379072
print(len(ipow(a,b))) # 27544 digits (takes a long time)
可以通过创建一个专门的平方函数并使用它来代替iprod(a2n,a2n)来实现进一步的优化