Polynomdivison (Algorithmen)
Die Aufgabe ist es, ein Programm zu schreiben bei dem man ein Polynom und einen Teiler eingeben kann. Beispielsweise "+4x^3+8x^2-1x-2" als Polynom und "+1x+2" als Teiler. Anschließend wird die Polynomdivision ausgeführt und am Ende soll die Rechnung und das Resultat ausgegeben werden:
(+4x^3 +8x^2 -1x -2) : (+1x +2) = +4x^2 -1
https://de.wikipedia.org/wiki/Polynomdivision
Bemerkung und Tipps: Der einfachste Fall enthält nur Polynemdivisionen ohne Rest. Zur weiteren Vereinfachung können Sie die Aufgabe so lösen, dass nur einziffrige Parameter und Exponenten vorkommen; es soll ja nicht unbedingt eine Übung zum korrekten Einlesen, sondern zur korrekten Division sein.
1 Kommentare
2 Lösung(en)
#-------------------------------------------------------------------------------
# Name: polynom_division.py
# Purpose:
#
# Author: Ruben Sidon
#
# Created: 10.03.2019
# Copyright: (c) Ruben Sidon 2019
#-------------------------------------------------------------------------------
def sort_key(elem):
return -elem[0] #das minuszeichen damit es von gross nach klein sortiert wird
def poly_sort(L):
if len(L) == 0:
return []
U = [] #hier kommen jetzt alle laengen der teilpolynome rein
for i in L:
U.append(len(i))
R = [] #hier kommen jetzt alle potenzen der teilpolynome rein
for a in range(len(U)):
#sortieren der potenzen von X
if U[a] == 2:
R.append(0)
elif U[a] == 3:
R.append(1)
else:
R.append(int(L[a][4]))
U.clear() #die Liste U wird zurueckgesetzt
for o, p in zip(R, L): #liste erstellen [[potenz1, polynom1], [potenz2, polynom2], ...]
U.append([o,p])
U.sort(key=sort_key) #nach potenzen sortieren (gross nach klein)
X = list(zip(*U)) #listen wieder auseinander trennen
return list(X[1]) #nur die liste von den polynomen zurueckgeben
def zerlege(polynom):
_list = []
polynom += "+" #damit das letzte teilpolynom auch rausgesplitted wird
beginning_index = 0 #damit wird die stelle festgelegt wo der string gesplitted wird
for i in range(len(polynom)-1):
if polynom[i+1] == "+" or polynom[i+1] == "-":
_list.append(polynom[beginning_index:i+1])
beginning_index = i+1 #hier wird diese stelle "weitergeschoben"
return poly_sort(_list) #wird vor der rueckgabe sortiert zur sicherheit, falls man nicht nach potenzen geordnet eingegeben hat
def durch_x_teilen(p): #funktion die ein (teil)polynom durch X teilt
for i in range(len(p)-1):
if p[i] == "^":
z = int(p[i+1]) - 1
if z > 1:
p = p[:i+1] + str(z)
elif z == 1:
p = p[:i]
elif len(p) == 3:
p = p[0:2]
return p
def mit_teiler_multi(p, t):
result = []
for a in range(len(t)):
if t[a][0] == p[0]: #bestimmung des vorzeichens
result.append("+")
else:
result.append("-")
result[a] += str(int(p[1]) * int(t[a][1])) #bestimmung des koeffizienten
if len(t[a]) == 2:
result[a] += p[2:]
else: #bestimmung der potenz von X
expo_1 = 0
expo_2 = 0
if len(t[a]) > 3:
expo_1 = int(t[a][4])
elif len(t[a]) == 3:
expo_1 = 1
else:
expo_1 = 0
if len(p) > 3:
expo_2 = int(p[4])
elif len(p) == 3:
expo_2 = 1
else:
expo_2 = 0
if expo_1+expo_2 > 1:
result[a] += "x^" + str(expo_1+expo_2)
else:
result[a] += "x"
return result
def change_vz(pol): #funktion die das vorzeichen eines teilpolynoms wechselt
if pol[0] == "+":
pol = "-" + pol[1:]
else:
pol = "+" + pol[1:]
return pol
def substraktion(P1, P2, S1, S2):
S1 = change_vz(S1) #vorzeichen wechseln weil ein - vor der klammer sein muss
S2 = change_vz(S2) #hier genauso
_startP = [P1, P2, S1, S2] #die teilpolynome die zusammenaddiert werden
_real_result = [] #das ergebnis, welches die funktion zurueckgibt als liste
_blacklist = [0, 1, 2, 3] #durch die blacklist werden keine teilpolynome doppelt verrechnet
for i in range(len(_startP)):
for u in range(len(_startP)):
if len(_startP[i]) == len(_startP[u]) and i != u and i in _blacklist and u in _blacklist:
if len(_startP[i]) <= 3 or _startP[u][4] == _startP[i][4]:
_blacklist.remove(i)
_blacklist.remove(u)
num1 = int(_startP[u][1])
num2 = int(_startP[i][1])
if _startP[u][0] == "-": #bei negativem vorzeichen die gegenzahl verwenden
num1 = -num1
if _startP[i][0] == "-":
num2 = -num2
if num1+num2 >= 0:
if len(_startP[i]) > 2:
_real_result.append("+"+str(num1+num2)+_startP[i][2:])
else:
_real_result.append("+"+str(num1+num2))
else:
if len(_startP[i]) > 2:
_real_result.append(str(num1+num2)+_startP[i][2:])
else:
_real_result.append(str(num1+num2))
for x in _blacklist:
_real_result.append(_startP[x]) #teilpolynome mit denen nicht gerechnet wurde, werden auch zurueckgegeben
for g in range(3): #3 mal wird das durchgelaufen, weil es bei einem mal komischer weise nicht genau genug removed
for h in _real_result: #wenn ein koeffizient 0 ist, wird das teilpolynom geloescht
if int(h[1]) == 0:
_real_result.remove(h)
return poly_sort(_real_result) #vor der rueckgabe wird die liste noch sortiert von der selbstgeschriebenen sort funktion
def main():
#test 1
#poly_list = zerlege("+2x^4-5x^3+6x^2-9x+2")
#teiler_list = zerlege("+1x-2")
#test 2
#poly_list = zerlege("+4x^3+8x^2-1x-2")
#teiler_list = zerlege("+1x+2")
#test 3
#poly_list = zerlege("+1x^3-8x-8")
#teiler_list = zerlege("+1x+2")
print("Guten Tag! Erst das Polynom, dann den Teiler eingeben!")
poly_list = zerlege(input("polynom eingeben: "))
teiler_list = zerlege(input("teiler eingeben: "))
subtraktions_poly = []
result = []
#hier beginnt das hauptprogramm
result.append(durch_x_teilen(poly_list[0])) #der erste teil der loesung ist das erste teilpolynom durch X geteilt
subtraktions_poly = mit_teiler_multi(result[len(result)-1], teiler_list) #festlegung des polynoms, welches subtrahiert wird
r = substraktion(poly_list[0], poly_list[1], subtraktions_poly[0], subtraktions_poly[1]) #ergebnis der subtraktion (unterm bruchstrich)
counter = 2
while counter < len(poly_list): #die schleife wird wiederholt bis das ergebnis gefaellt ist
if len(r) != 0:
result.append(durch_x_teilen(r[0]))
else:
result.append(durch_x_teilen(poly_list[counter]))
subtraktions_poly = mit_teiler_multi(result[len(result)-1], teiler_list)
if len(r) == 1:
r = substraktion(r[0], poly_list[counter], subtraktions_poly[0], subtraktions_poly[1])
counter += 1
elif len(r) == 0:
r = substraktion(poly_list[counter], poly_list[counter+1], subtraktions_poly[0], subtraktions_poly[1])
counter += 2
else:
r = substraktion(r[0], r[1], subtraktions_poly[0], subtraktions_poly[1])
print("("," ".join(poly_list),")", " : ","(", " ".join(teiler_list), ") = ", " ".join(result)) #ausgabe der rechnung mit ergebnis
input("\n")
pass
if __name__ == '__main__':
main()
Lösung von: Ruben Sidon (WRG Bendorf)
#MAN KANN EINGEBEN: +14x^8 -826x^2 +3.2x
#also Zahlenwerte bis zu 3 Stellen oder einstellig mit einer #Nachkommastelle
#(+1x^4 -1.5x^3 -1x^2 +5.5x -6) : (+1x -1.5) = +1x^3 -^x +4
#(+4x^3 -3x +1) : (+1x +1) = +4x^2 -4x +1
#(+1x^3 -2x^2 -8x +21) : (+1x +3) = +1x^2 -5x +7
#(+1x^2 +200x) : (+1x +200) = +1x
#-------------------------------------------------------------------------------
# Name: polynom_division_advanced.py
# Purpose:
#
# Author: Ruben Sidon
#
# Created: 15.03.2019
# Copyright: (c) Ruben Sidon 2019
#-------------------------------------------------------------------------------
def get_value(p, change_grad = 0): #funktion die den koeffizienten sowie den grad zurueckgibt
grad = 0
koeff = 0
#unterscheidung nach der laenge des strings
if len(p) == 2:
koeff = int(p[1])
grad = 0
elif len(p) == 3:
if p[2] == "x":
koeff = int(p[1])
grad = 1
else:
koeff = int(p[1:])
grad = 0
elif len(p) == 4:
if p[3] == "x":
koeff = int(p[1:3])
grad = 1
elif p[2] == "." or p[2] == ",":
koeff = float(float(p[1]) + (float(p[3]) / 10))
grad = 0
else:
koeff = int(p[1:])
grad = 0
elif len(p) == 5:
if p[2] == "." or p[2] == ",":
koeff = float(float(p[1]) + (float(p[3]) / 10))
grad = 1
elif p[2] == "x":
koeff = int(p[1])
grad = int(p[4])
else:
koeff = int(p[1:4])
grad = 1
elif len(p) == 6:
koeff = int(p[1:3])
grad = int(p[5])
elif len(p) == 7:
if p[2] == "." or p[2] == ",":
koeff = float(float(p[1]) + (float(p[3]) / 10))
grad = int(p[6])
else:
koeff = int(p[1:4])
grad = int(p[6])
return [koeff, grad + change_grad] #rueckgabe
def sort_key(elem):
return -elem[1] #das minuszeichen damit es von gross nach klein sortiert wird
def poly_sort(L):
if len(L) != 0:
U = [] #deklaration der liste U
for i in range(len(L)):
tmp = get_value(L[i])
U.append([L[i], tmp[1]])
U.sort(key=sort_key) #nach potenzen sortieren (gross nach klein)
X = list(zip(*U)) #listen wieder auseinander trennen
return list(X[0]) #nur die liste von den polynomen zurueckgeben
def zerlege(polynom):
_list = []
polynom += "+" #damit das letzte teilpolynom auch rausgesplitted wird
beginning_index = 0 #damit wird die stelle festgelegt wo der string gesplitted wird
for i in range(len(polynom)-1):
if polynom[i+1] == "+" or polynom[i+1] == "-":
_list.append(polynom[beginning_index:i+1])
beginning_index = i+1 #hier wird diese stelle "weitergeschoben"
for p in range(len(_list)): #wenn man +x anstatt +1x schreibt
if len(_list[p]) == 1 and _list[p][0] == "x":
_list[p] = "+1x"
elif _list[p][1] == "x":
_list[p] = _list[p][0]+"1x"
return poly_sort(_list) #wird vor der rueckgabe sortiert zur sicherheit, falls man nicht nach potenzen geordnet eingegeben hat
def durch_x_teilen(p): #funktion die ein (teil)polynom durch X teilt
x = get_value(p, -1)
if x[1] == 0:
p = p[0]+str(x[0])
elif x[1] == 1:
p = p[0]+str(x[0])+"x"
else:
p = p[0]+str(x[0])+"x^"+str(x[1])
return p
def mit_teiler_multi(p, t):
result = []
for a in range(len(t)):
if t[a][0] == p[0]: #bestimmung des vorzeichens
result.append("+")
else:
result.append("-")
poly_info = [get_value(p), get_value(t[a])]
result[a] += str(poly_info[0][0] * poly_info[1][0]) #bestimmung des koeffizienten
if poly_info[0][1]+poly_info[1][1] == 1:
result[a] += "x"
elif poly_info[0][1]+poly_info[1][1] > 1:
result[a] += "x^"+str(poly_info[0][1]+poly_info[1][1])
return result
def change_vz(p): #funktion die das vorzeichen eines teilpolynoms wechselt
if p[0] == "+":
p = "-" + p[1:]
else:
p = "+" + p[1:]
return p
def substraktion(P1, P2, S1, S2):
S1 = change_vz(S1) #vorzeichen wechseln weil ein - vor der klammer sein muss
S2 = change_vz(S2) #hier genauso
_startP = [P1, P2, S1, S2] #die teilpolynome die zusammenaddiert werden
_real_result = [] #das ergebnis, welches die funktion zurueckgibt als liste
_blacklist = [0, 1, 2, 3] #durch die blacklist werden keine teilpolynome doppelt verrechnet
for i in range(len(_startP)):
for u in range(len(_startP)):
i_info = get_value(_startP[i])
u_info = get_value(_startP[u])
if i_info[1] == u_info[1] and i != u and i in _blacklist and u in _blacklist:
_blacklist.remove(i)
_blacklist.remove(u)
if _startP[u][0] == "-": #bei negativem vorzeichen die gegenzahl verwenden
u_info[0] = -u_info[0]
if _startP[i][0] == "-":
i_info[0] = -i_info[0]
if u_info[0]+i_info[0] >= 0:
if i_info[1] == 0:
_real_result.append("+"+str(i_info[0]+u_info[0]))
elif i_info[1] == 1:
_real_result.append("+"+str(i_info[0]+u_info[0])+"x")
else:
_real_result.append("+"+str(i_info[0]+u_info[0])+"x^"+str(i_info[1]))
else:
if i_info[1] == 0:
_real_result.append(str(i_info[0]+u_info[0]))
elif i_info[1] == 1:
_real_result.append(str(i_info[0]+u_info[0])+"x")
else:
_real_result.append(str(i_info[0]+u_info[0])+"x^"+str(i_info[1]))
for x in _blacklist:
_real_result.append(_startP[x]) #teilpolynome mit denen nicht gerechnet wurde, werden auch zurueckgegeben
for g in range(3): #3 mal wird das durchgelaufen, weil es bei einem mal komischer weise nicht genau genug removed
for h in _real_result: #wenn ein koeffizient 0 ist, wird das teilpolynom geloescht
if int(h[1]) == 0:
_real_result.remove(h)
if _real_result == []:
_real_result.append("+0")
return poly_sort(_real_result) #vor der rueckgabe wird die liste noch sortiert von der selbstgeschriebenen sort funktion
def main():
print("Guten Tag! Erst das Polynom, dann den Teiler eingeben!")
poly_list = zerlege(input("polynom eingeben: "))
teiler_list = zerlege(input("teiler eingeben: "))
subtraktions_poly = []
result = []
#hier beginnt das hauptprogramm
result.append(durch_x_teilen(poly_list[0])) #der erste teil der loesung ist das erste teilpolynom durch X geteilt
subtraktions_poly = mit_teiler_multi(result[len(result)-1], teiler_list) #festlegung des polynoms, welches subtrahiert wird
r = substraktion(poly_list[0], poly_list[1], subtraktions_poly[0], subtraktions_poly[1]) #ergebnis der subtraktion (unterm bruchstrich)
counter = 2
while not r[0] == "+0" or counter != len(poly_list): #die schleife wird wiederholt bis das ergebnis gefaellt ist
if r[0] != "+0":
result.append(durch_x_teilen(r[0]))
else:
result.append(durch_x_teilen(poly_list[counter]))
subtraktions_poly = mit_teiler_multi(result[len(result)-1], teiler_list)
if r[0] == "+0":
r = substraktion(poly_list[counter], poly_list[counter+1], subtraktions_poly[0], subtraktions_poly[1])
counter += 2
elif len(r) == 1:
r = substraktion(r[0], poly_list[counter], subtraktions_poly[0], subtraktions_poly[1])
counter += 1
else:
r = substraktion(r[0], r[1], subtraktions_poly[0], subtraktions_poly[1])
print("("," ".join(poly_list),")", " : ","(", " ".join(teiler_list), ") = ", " ".join(result)) #ausgabe der rechnung mit ergebnis
input("\n")
if __name__ == '__main__':
main()
Lösung von: Ruben Sidon (WRG Bendorf)
Aktionen
Neue Lösung hinzufügen
Bewertung
Durchschnittliche Bewertung:
Kommentare (1)