# -*- coding: utf-8 -*-
# создаёт кортеж (a,b) из чисел a и b
def zero(a,b):
if a is None: a=0
if b is None: b=0
return (a,b)
# суммирует списки почленно
def sum(a,b):
res = []
for x,y in map(zero,a,b):
res.append((x+y)%2)
return res
# разность многочленов
def dif(a,b):
res = []
for x,y in map(zero,a,b):
res.append(x-y)
return res
# произведение
def mul(a,b):
res = []
for i in range(0,len(b)):
temp = [0 for j in range(0,i)]
for r in a:
temp.append(r*b[i]%2)
res.append(temp)
return reduce(sum,res)
# деление (осторожно, рекурсия:-))
def dev(a,b):
while len(a)>0 and a[-1]==0:
del a[-1]
if len(a)<len(b):
return [a]
k = a[-1]/b[-1]
difference = len(a)-len(b)
for i in range(difference,len(a)):
a[i] = (a[i] - b[i-difference]*k)%2
while len(a)>0 and a[-1]==0:
del a[-1]
res = [(k, difference)] + dev(a,b) # recursion
return res
def devide(a,b):
res = dev(a,b) # деление рекурсивной функцией dev
# преобразование результата из функции dev в многочлен (список)
rem = res[-1] # остаток
polynom = []
if len(res)>1:
res = res[0:-1]
polynom = [0 for i in range(0,res[0][1]+1)] # res[0][1] - это степень старшего монома
for a,x in reversed(res):
polynom[x] = a
return (polynom, rem)
# НОД
def GCD(a,b):
res = devide(a,b)
r = res[-1]
while r!=[]:
a = b
b = r
res = devide(a,b)
r = res[-1]
return b
# многочлены для тестов
a = [1,1,1,1,1,0,1,1,0,0,1]
b = [1,0,1]
print devide(a[:],b[:]) # деление
print GCD(a[:],b[:]) # НОД