Buch Cover Buch Cover Buch Cover Buch Cover

Web-Code: - Webcode Help

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

Bitte melde dich an um einen Kommentar abzugeben

Kommentare (1)

rubasida 14. März 2019 22:12   reply report
Die Aufgabe ist von mir, ich wollte noch erwähnen, dass es reicht, wenn man nur einzahlige Eingaben machen kann. Also -22x^47 jetzt nicht zum Beispiel. Nur bis zu +9x^9.

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

Bewertung

Durchschnittliche Bewertung:

Eigene Bewertung:
Bitte zuerst anmelden

Meta

Zeit: 4
Schwierigkeit: Schwer
Webcode: hjqf-z2fu
Autor: ()

Download PDF

Download ZIP

Zu Aufgabenblatt hinzufügen