一、高精度
(一)使用高精度的原因
在计算机中处理非常大或非常小的数值时,确保计算结果的精确性和准确性。在特定情况下,可以自己实现高精度计算的数据结构和算法,例如使用字符串或数组来表示大数,并实现基本的加、减、乘、除操作。
(二)高精度加法
1、方法
(1)描述:从最低位开始加法计算,利用carry变量来维护进位值。
(2)步骤
①初始化:将两个数用列表存储,反转两个列表以便从最低位开始相加。初始化一个空字符串 ans 用于存储计算结果。初始化 carry 变量为 0,用于存储进位。
②逐位相加:遍历两个反转后的列表,逐位相加。对于当前位,将 carry 和当前位的两个数字相加。计算当前位的和 sum,更新当前位的结果为 sum%10,并更新 carry 为 sum//10。将当前位的结果追加到 ans。
③处理剩余进位:如果所有位处理完毕后 carry 不为 0,则将 carry 追加到 ans。
④反转 ans 字符串以获得最终结果。
2、题目和代码
def add(a,b):
carry=0;ans=[]
i=0;j=0
while i<len(a) or j<len(b) or carry:
res=carry
if i<len(a):
res+=int(a[i])
i+=1
if j<len(b):
res+=int(b[j])
j+=1
carry=res//10
res=res%10
ans.append(res)
return ans[::-1]
def main():
a=[x for x in input()];A=a[::-1]
b=[x for x in input()];B=b[::-1]
res=add(A,B)
print("".join(map(str,res)))
main()
(三)高精度减法
1、方法
(1)与高精度加法的不同:高精度减法与高精度加法的主要不同在于需要处理两个数的大小比较,以及减法操作中的借位。
(2)比较大小:在进行减法之前,需要比较两个数的大小,确定被减数和减数。【如果比较过后将题目中的减数和被减数交换了,只需要在最后输出结果的时候加上负号。】
- 如果位数不同:确定位数大的为被减数。例如,题目中的被减数是12,减数是311,那么根据位数比较,311被确定为被减数,12被确定为减数,结果最后加个负号就可以了。从12-311变成了-(311-12),更符合运算思维。
- 如果位数相同:确定值大的为被减数。
(3)具体操作:
- 逐位相减并处理借位:从右向左(从最低位到最高位)逐位相减,如果 a 的当前位小于 b 的当前位,则需要向高位借位,借位后的当前位值加10,并将 carry 设为1。如果没有借位,carry 设为0。
- 处理前导零:前导零就是301-300=001,前面的两个0就是前导零,需要去除。
2、题目和代码
def compare(a,b):
if len(a)!=len(b):
return len(a)-len(b)
else:
for i in range(len(a)):
if a[i]!=b[i]:
return a[i]-b[i]
return 0
def subtract(a,b):
carry=0;ans=[]
i=0
while i<len(a):
res=a[i]-carry
if i<len(b):
res-=b[i]
if res<0:
carry=1
else:
carry=0
res=(res+10)%10
ans.append(res)
i+=1
ans=ans[::-1]
while len(ans)>1 and ans[0]==0:
ans.pop(0)
return ans
def main():
a=[int(x) for x in input()];A=a[::-1]
b=[int(x) for x in input()];B=b[::-1]
res=compare(a,b)
if res>0:
ans=subtract(A,B)
print("".join(map(str,ans)))
elif res<0:
ans=subtract(B,A)
print("-"+"".join(map(str,ans)))
else:
print(0)
main()
(四)高精度乘法
1、方法
- 结果存储:利用ans数组存储结果,已知一个m位的数与一个n位的数相乘,结果的最大位数为m+n,因此ans数组长度设置为m+n。
- 乘法操作:①逐位相乘:从被乘数的最低位开始计算,每一位与乘数的每一位相乘。将乘积结果放在对应的结果数组的正确位置上,ans[i+j+1] 表示乘积直接影响的结果位。②处理进位:每次相乘后,计算当前位的结果,同时处理进位。如果有进位,将其加到更高一位,即ans[i+j]。③判断ans数组最高位,ans[0]是否为0,如果是的话去除前导零返回。
2、代码
def mul(a,b):
ans=[0]*(len(a)+len(b))
for i in range(len(a)-1,-1,-1):
x=a[i]
for j in range(len(b)-1,-1,-1):
ans[i+j+1]+=x*b[j]
ans[i+j]+=ans[i+j+1]//10
ans[i+j+1]%=10
index=1 if ans[0]==0 else 0
return ans[index:]
def main():
a=input();b=input()
if a=='0' or b=='0':
print(0)
else:
a=[int(x) for x in a]
b=[int(x) for x in b]
ans=mul(a,b)
print("".join(map(str,ans)))
main()
(五)高精度除法
1、方法
- 存储:用数组C存储商,用变量r存储余数。
- 操作步骤:①初始化:初始余数r为0,C初始化为空列表。②(1)从被除数的最高位开始进行除法操作(2)在每轮循环中更新余数r的值为r=10*r+a[i],a[i]为被除数当前位(比如233÷3,从最高位2开始除以3,余下来的r=2,再下一位除法时除以3的就变成了23=2*10+3,再除以3。以此类推。)(3)计算当前位的商并添加到结果数组中,c.append(r//b)。(4)余数r更新:r=r%b。
2、代码
def div(a,b):
r=0;c=[]
for i in range(len(a)):
r=r*10+a[i]
c.append(r//b)
r=r%b
while len(c)>1 and c[0]==0:
c.pop(0)
return c,r
def main():
a=list(map(int,input()))
b=int(input())
c,r=div(a,b)
print("".join(map(str,c)))
print(r)
main()
二、前缀和
(一)一维前缀和
1、定义
假设A是一个一维数组,A[i]表明A中第i个元素。对于数组A,可以定义一个前缀和数组P,使得P[i]表示A中第一个到第i个元素之和。即:
P[i]=A[1]+A[2]+...+A[i]
对于P数组第一个元素,由于没有元素可以累加,设P[0]=0。
任意区间[l,r]的和可以在常数时间内被查询:区间和=P[r]-P[l-1]。
其中构建过程为:初始化P[0]=0,而P[i]=P[i-1]+A[i]。
2、应用
通过预处理数组,使得任意区间的和可以在常数时间内被查询。
3、题目和代码
def main():
n,m=map(int,input().split())
nums=list(map(int,input().split()));nums=[0]+nums
p=[0]*(n+1)
for i in range(1,n+1):
p[i]=p[i-1]+nums[i]
for _ in range(m):
l,r=map(int,input().split())
print(p[r]-p[l-1])
main()
(二)二维前缀和
1、定义
①A是一个二维数组,A[i][j]代表第i行第j列元素,设前缀和数组P,有P[i][j]代表A中左上角(1,1)的元素到A中(i,j)的所有元素的和。
②构建P数组方式如下:
③求前缀和方式如下
2、应用
用于快速计算二维数组(通常是矩阵)中任意子矩阵的元素和。
3、题目和代码
def main():
n,m,q=map(int,input().split())
nums=[]
for _ in range(n):
row=list(map(int,input().split()))
nums.append(row)
p=[[0]*(m+1) for _ in range(n+1)]
for i in range(1,n+1):
for j in range(1,m+1):
p[i][j]=p[i-1][j]+p[i][j-1]-p[i-1][j-1]+nums[i-1][j-1]
for _ in range(q):
x1,y1,x2,y2=map(int,input().split())
res=p[x2][y2]-p[x1-1][y2]-p[x2][y1-1]+p[x1-1][y1-1]
print(res)
main()
三、差分
(一)一维差分
1、定义
设有一个数组A,A[i]代表第i个元素。定义差分数组D为:D[i]=A[i]-A[i-1],代表第i个元素和第i-1个元素之间的差值。通常D[1]=A[1]。
2、应用
快速计算相邻元素差值或恢复原始数据序列。
3、题目和代码
def insert(b,l,r,c):
#给[l,r]区间内每个数nums[i]都加上c
#此时b[l]和b[r+1]发生变化
#b[l]=nums[l]-nums[l-1],此时nums[l]加上c了,因此b[l]+c
#b[r+1]=nums[r+1]-nums[r],此时nums[r]加上c了,因此b[r+1]-c
b[l]+=c
b[r+1]-=c
def main():
n,m=map(int,input().split())
#改动后nums[i]表示的就是第i个元素
nums=list(map(int,input().split()));nums=[0]+nums
#b[1]=a[1]-a[0]=a[1]
#由于差分操作中b[r+1],为了保证不越界,b数组长度设置为n+2
b=[0]*(n+2)
#构建差分数组
#在第i个位置插入nums[i],b[i]+=nums[i]
#而前面在第i-1个位置的时候,b[(i-1)+1]-=nums[i-1]
#因此b[i]=nums[i]-nums[i-1]
for i in range(1,n+1):
insert(b,i,i,nums[i])
for _ in range(m):
l,r,c=map(int,input().split())
insert(b,l,r,c)
#还原,从头开始还原,因为b[1]=a[1],b[2]=a[2]-a[1],...
for i in range(1,n+1):
b[i]+=b[i-1]
print(" ".join(map(str,b[1:n+1])))
main()
(二)二维差分
1、定义
2、题目和代码
def insert(b,l1,r1,l2,r2,c):
b[l1][r1]+=c
b[l1][r2+1]-=c
b[l2+1][r1]-=c
b[l2+1][r2+1]+=c
def main():
n,m,q=map(int,input().split())
nums=[]
for _ in range(n):
row=list(map(int,input().split()))
nums.append(row)
b=[[0]*(m+2) for _ in range(n+2)]
for i in range(1,n+1):
for j in range(1,m+1):
insert(b,i,j,i,j,nums[i-1][j-1])
for _ in range(q):
x1,y1,x2,y2,c=map(int,input().split())
insert(b,x1,y1,x2,y2,c)
for i in range(1,n+1):
for j in range(1,m+1):
b[i][j]+=b[i-1][j]+b[i][j-1]-b[i-1][j-1]
for i in range(1,n+1):
for j in range(1,m+1):
print(b[i][j],end=" ")
print()
main()
标签:map,前缀,nums,int,基础课,差分,range,ans,input
From: https://blog.csdn.net/Willowii/article/details/140545765