Schriftliches Dividieren Rekursiv Programmieren?

2 Antworten

Vom Fragesteller als hilfreich ausgezeichnet

https://www.ra.informatik.tu-darmstadt.de/fileadmin/user_upload/Group_RA/tgi2/rechenwerke.pdf

http://elektroniktutor.de/digitaltechnik/dualsys.html

Division im Dualsystem

Bei 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 ;-)

0

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]

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

0
@YugiohFan17

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).

0
@YugiohFan17

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))
0

BMI Rechner in C Programmieren (Fach Spezifische Softwaretechnik , so heisst das Schulfach )?

Wir sollen für die schule einen BMI Rechner programieren aber bei mir kommt immer das Gewicht als ergebnis . Thx für die Antworten im Voraus Code : (mit DEV C++ geschrieben)

include <stdio.h>

include <stdlib.h>

/* run this program using the console pauser or add your own getch, system("pause") or input loop */

float bmi(float l,float m);

int main(int argc, char *argv) {

float l; float m; float bmi_;

printf("Geben Sie ihre Koerpergewicht in Kg ein :");

scanf("%f",&m);

printf("Geben sie ihr Koerpergroesse in ein :");

scanf("%f",&l);

bmi_ = bmi(l,m);

printf("%f\n",bmi_);

system("PAUSE"); return 0; }

float bmi(float l,float m) {

return m/(l*l); }

...zur Frage

malprogramm programmieren (struktur)

wie wird ein mal/zeichenprogramm programmiert? ich habs mir so gedacht(in visual basic): ein bitmap oefters auf die form malen (ein array fuer die positionen der pinsel), dort immer wo die maus ist,dann die bemalte form speichern. wird das so gemacht?

danke im voraus

...zur Frage

schriftliches dividieren mit Kommazahlen bitte helft mir

ich geb nachhilfe und mein nachhilfe schüler versteht schriftliches di vidieren mit kommazahlen nicht, und ich kann es nicht mehr und habe bis jetzt noch keine geeignete seite gefunden könnt ihr mir helfen dank schonmal

...zur Frage

Was ist int, float und double?

Ich will mal programmieren lernen und könntet ihr mir erklären was int,float und double heißt und wofür man das braucht . Es soll noch mehr Sachen zum Programmieren geben könntet ihr mir auch von denen die Namen sagen und erklären wofür die sind.

...zur Frage

Daten aus einer MySQL Tabelle in ein JavaScript Array?

Guten Tag,

ich versuche gerade Daten aus einer MySQL Tabelle in einem Balkendiagramm auf einer HTML Seite darzustellen. Dazu verwende ich die Bibliothek Chart.js.

Über die SELECT Funktion mit php kann ich Daten aus einer MySQL Tabelle herausholen. Nun brauche ich aber die Daten in einem JavaScript Array für das Diagramm. Ich habe schon viel gegooglelt, was aber zu keinem Ergebnis führte.

Was das Programmieren betrifft bin ich ein Anfänger.

Grüße

...zur Frage

Was möchtest Du wissen?