大数算法_python_

def addition(a,b): #计算加法的函数 result = [] len1 = len(a) len2 = len(b) #计算出a和b字符串的长度 carry = 0 while len1 and len2: len1 -=1 len2 -=1 sum = ord(a[len1])+ord(b[len2])-2*ord('0')+carry #每次算出每一位对应相加的和 if sum>=10: #如果大于10，则有进位，取余数进1 carry = 1 sum-=10 else: carry = 0 result.append(sum) #将结果添加进列表中 while len1: #如果len2等于0，说明a较长，后面只需对a进行操作即可 len1 -= 1 sum = ord(a[len1])-ord('0')+carry if sum>=10: carry = 1 sum -= 10 else: carry = 0 result.append(sum) if carry == 1: result.append(carry) #最后都加完后如果进位为1，则需再将进位加上 return result #返回结果列表 def subraction(a,b): #计算减法的函数 len1 = len(a) len2 = len(b) result = [] carry = 0 while len2: len2-=1 len1-=1 num = ord(a[len1])-ord(b[len2])-carry #每次处理每一位上的减法 if len1 == 0 and num<0: return -1 #说明a<b，超出限度 if num<0: carry = 1 num+=10 else: carry = 0 result.append(num) while len1: len1 -= 1 num = ord(a[len1])-ord('0')-carry if num<0: carry = 1 num+=10 else: carry = 0 result.append(num) n_0 = 0 for i in range(len(result)-1,-1,-1): #为了去除所有的先导0 if result[i] == 0: n_0+=1 else: break if n_0 == len(result): return [0] return result[0:len(result)-n_0] #为了除去先导0 def mulit(a,b): #计算乘法的函数 if a == '0' or b == '0': return [0] length = len(a) + len(b) + 1 #乘积的总长度是a和b长度之和加1 result = [0]*length num1 = list(a) num2 = list(b) num1.reverse() num2.reverse() for i in range(0,len(num1)): for j in range(0,len(num2)): result[i+j] += int(num1[i])*int(num2[j]) #乘积的i+j位为num1（即a)的第i位和num2（即b）的第j位的乘积 carry = 0 for i in range(0,length): num = carry + result[i] #对进位进行处理，模10去余，除10进位 carry = int(num/10) result[i] = num%10 n_0 = 0 for i in range(len(result) - 1, -1, -1): # 为了去除所有的先导0 if result[i] == 0: n_0 += 1 else: break return result[0:len(result)-n_0] def division(a,b): #计算除法的函数，同时输出商和余数 num1 = len(a) num2 = len(b) a_list = list(a) b_list = list(b) #将字符串转化为列表，更容易进行计算 result = [0] * (len(a) - len(b) + 1) while num1>=num2: add_zero = num1 - num2 #记录需要在b后添加的0的个数（保持a和b位数一致，加快减法速度） for i in range(0,add_zero): b_list.append('0') #在后面添加0，相当于将b扩大了10的n次倍，再和a做减法，加快除法速度 sub_result = subraction(a_list,b_list) #将除法转化为多次减法运算。 if sub_result == -1: #如果sub_result = -1,说明a<b,将b后添加的0去掉一个 add_zero -=1 if add_zero >= 0: b_list.pop() sub_result = subraction(a_list,b_list) else : #如果此时添加的0小于0，说明之前没有添加0，可以退出循环，除法结束 a_list.reverse() break sub_result.reverse() for i in range(0,len(sub_result)): sub_result[i] = chr(sub_result[i] + ord('0')) if sub_result[0] != '0': result[add_zero] += 1 a_list = sub_result #a_list的结果等于之前的减法结果 for i in range(0,add_zero): b_list.pop() num1 = len(sub_result) if num1<num2: a_list.reverse() n_0 = 0 for i in range(len(result) - 1, -1, -1): # 为了去除所有的先导0 if result[i] == 0: n_0 += 1 else: break for i in range(len(result)-n_0-1,-1,-1): #输出商 print(result[i],end ="") print() for i in range(len(a_list)-1,-1,-1): #输出最后的余数 print(a_list[i],end="") num1 = input("please input a: ") #输入a num2 = input("please input b: ") #输入b add_result = addition(num1,num2) #对两个数做加法 sub_result = subraction(num1,num2) #对两个数做减法 mul_result = mulit(num1,num2) #对两个数做乘法 for i in range(len(add_result) - 1, -1, -1): print(add_result[i], end="") #输出加法结果 print() for i in range(len(sub_result) - 1, -1, -1): print(sub_result[i], end="") #输出减法结果 print() for i in range(len(mul_result) - 1, -1, -1): print(mul_result[i], end="")#输出乘法结果 print() div_result = division(num1,num2) #对两个数做除法，同时输出最后的余数（实现a%b的操作） print() input("按Enter键继续：")