Schriftliches Dividieren Rekursiv Programmieren?
Hi,
Kennt jemand einen Algorithmus um schriftliches Dividieren zu programmieren und das Ergebnis in einem Array zu speichern? (oder einfach gleich als Float / Double)
Direkt als Antwort, als Link oder auch nur ein Ansatz ist ausreichend
Danke
2 Antworten
https://www.ra.informatik.tu-darmstadt.de/fileadmin/user_upload/Group_RA/tgi2/rechenwerke.pdf
http://elektroniktutor.de/digitaltechnik/dualsys.html
Division im DualsystemBei der Division im Dezimalsystem ist das Ergebnis oft eine Zahl mit
endlichen oder unendlichen Nachkommastellen und unterscheidet sich so
von den anderen Grundrechenarten. Im Dualsystem ist die Division durch
Zweierpotenzen als Umkehrung der Multiplikation durch die
Rechtsverschiebung der Bitfolge durchführbar. Dieses
Rechtsshift-Verfahren ist auf Zweierpotenzen beschränkt. Eine Rundung
findet nicht statt. Nach rechts aus dem Bitmuster fallende Stellen
werden verworfen.
Das Verfahren zur Division durch eine beliebige Dualzahl ist
vergleichbar mit der schriftlichen Division im Dezimalsystem. Die
Subtraktion der Zwischenergebnisse erfolgt nach dem weiter oben
beschriebenen Verfahren mit Zweierkomplementen. Ein bleibender
Divisionsrest wird nicht berücksichtigt und wie oben abgeschnitten.
vielen Dank fürs Sternchen ;-)
Da Du nach schriftlicher Division fragst, gehe ich davon aus, dass Du einen rekursiven Algorithmus suchst, der das uebliche Schema nachahmt, das auch ein Mensch bei schriflicher Division anwenden wuerde, oder? Es handelt sich um eine Uebungsaufgabe zur Rekursion?
Gesucht ist also eine Funktion div, die zu zwei positiven ganzen Zahlen n und d die Ziffernfolge der Ganzzahldivision n/d und den Rest bestimmt. Bspw. soll gelten:
div(955, 7) = [[0, 1, 3, 6], 3]
Zuerst die Notation der verwendeten Operationen: Listen notiere ich in eckigen Klammern [...], "/" bedeutet Ganzzahldivision und "%" bedeutet modulo. dec(n) zerlegt eine Zahl n in die Liste ihrer Ziffern, f(L) gibt das erste Element einer Liste L zurueck, r(L) gibt eine Liste ohne ihr erstes Element zurueck und a(L, n) haengt eine Zahl n hinten an die Liste L. Nun die (endrekursive) Definition:
alg(L,n,d,R) :=
╔ [a(R,n/d),n%d] f. L=[]
╚ alg(r(L),10*(n%d)+f(L),d,a(R,n/d)) sonst
div(n,d) := alg(dec(n),0,d,[])Fuer obigen Aufruf laeuft das Programm also so:
div(955, 7)
--> alg([9,5,5], 0, 7, [])
--> alg([5,5], 9, 7, [0])
--> alg([5], 25, 7, [0,1])
--> alg([], 45, 7, [0,1,3])
--> [[0,1,3,6],3]
Python schuetzt sich auf diese Art vor Stack-Overflows. Dazu ein Beispiel; betrachte folgende Funktion:
sumUp(n) :=
╔ 0 f. n=0
╚ n + sumUp(n-1) sonst
Der Aufruf sumUp(5) summiert nun die natuerlichen Zahlen von 0 bis 5 auf; zwischendurch staut sich aber Kontext auf:
sumUp(5)
--> 5 + sumUp(4)
--> 5 + (4 + sumUp(3))
--> 5 + (4 + (3 + sumUp(2)))
--> 5 + (4 + (3 + (2 + sumUp(1))))
--> 5 + (4 + (3 + (2 + (1 + sumUp(0)))))
--> 5 + (4 + (3 + (2 + (1 + 0))))
--> ...
--> 15
Diese nicht ausgewerteten Zwischenergebnisse gammeln auf dem Stack herum und fuehren fuer grosse n zu einem Stack-Overflow. Schleppt man bei der rekursiven Definition aber Zwischenergebnisse mit, kann man dieses Problem beheben:
alg(n,a) :=
╔ a f. n=0
╚ alg(n-1,a+n) sonst
sumUp(n) := alg(n,0)Wenn ich mich richtig erinnere, ist Python aber leider nicht "schlau genug", um zu erkennen, welche Funktionen obiges Problem eben nicht verursachen - daher wird zu tiefe Rekursion generell verboten. Welche Parameter man aber genau umstellen muss, um Python beliebige Rekursionstiefe zu erlauben, weiss ich leider nicht...
Wenn es Dir aber wirklich um ein Problem in der Anwendung geht (was Du btw. gerne in Deiner Originalfrage haettest verraten koennen), wuerde ich Dir einen iterativen Algorithmus empfehlen und nicht Rekursion. Wenn Du durch eine nicht-negative ganze Zahl n teilst, dann weisst Du ja, dass es hoechstens n Nachkommastellen im Ergebnis gibt (bis es sich evtl. periodisch wiederholt).
Vielleicht koennte dieses kleine Programm Dir eine Anregung geben:
def dec(n):
x, R = n, []
while (x > 0):
R.insert(0, x%10)
x //= 10
return R
# compute n/d up to m decimal places
def div(n, d, m):
L, P, D, r, ct = dec(n), [], [], 0, 0
for i in range(0, len(L)):
r = 10*(r%d)+L[i]
P.append(r//d)
while (ct < m):
ct += 1
r = 10*(r%d)
D.append(r//d)
return (P, D)
print(div(1,4,10))
print(div(955,7,10))
Danke :) war keine Übungsaufgabe, ich hab nur für ein anderes Programm einen Algorithmus gebraucht, der sehr schnell möglichst viele Nachkommastellen in einer Liste ausrechnet. Habs etwas anders gelöst, allerdings kommt ab ca 8000 Nachkommastellen die Meldung, dass es zu viele Rekursionen gab. Ich habe alles in eine Klasse geschrieben, damit ich es in andere Python Dateien importieren kann, in die Klasse habe ich eine Funktion geschrieben um die Präzision zu erhöhen indem ein Counter die Rekursion begrenzt. Mit sys passe ich die Rekursionsbegrenzung an, aber es kommt ab ca 8000 trotzdem die Fehlermeldung. Kannst du mir weiterhelfen? Du scheinst dich nämlich auszukennen