Algorythmus gesucht

Algorythmus gesucht (22 Beiträge, 40 Mal gelesen)

Du bist nicht angemeldet. [ Login/Registrieren ]

Ich knobel grad an 'nem mathematischen Problem und vielleicht hat ja
schon jemand 'nen guten Algo dafür.

Ich bräuchte eine Implementierung für

n! / k! / l! / m!

die mir keine 32 Bit Zahl (wegen des recht grossen n!) sprengt,
wobei gilt

k + l + m = n

Das Ergebnis selbst ist selten grösser als 2^8, da n selbst im
Normalfall unter 2^3 bleibt (n! bleibt jedoch nur für n<=12 unter
2^32...).

Bin mir sicher, dass ich nicht der erste bin der vor dem Problem
steht, aber in Wahrscheinlichkeitsrechnung hab ich halt damals nicht
aufgepasst (weil... naja, brauchst ja als technischer Informatiker
eh nie...

).

Dank im Voraus.

Vielleicht kann ich helfen - hab mir die folgendes aber auch gerade erst ueberlegt:
ich gehe davon aus dass n! / k! / l! / m! gleich
n! / (k! * l! * m!) ist also kein Doppelbruch sondern wie bei
n ueber k in der Wahrscheinlichkeitsrechnung
Um moeglichst kleine Zahlen zu erhalten musst Du Zaehler und Nenner
kuerzen - dass geht wenn Du alle Zahlen in ihre Primfaktoren zerlegst - Ich erklaere es an einem Beispiel
10! / (5! * 3! * 2!) erweitert man auf

(1*2*3*4*5*6*7*8*9*10) / ((1*2*3*4*5)*(1*2*3)*(1*2)) erweitert man auf

(1*2*3*(2^2)*5*(2*3)*7*(2^3)*(3^2)*(2*5))/(1*2*3*(2^2)*5)*(1*2*3)*(1*2)

nun fasst man alle potenzen gleicher basis zusammen so bleiben nur mehr die primzahlen ueber (1 kann man natuerlich weglassen)

((2^8)*(3^4)*(5^2)*7)/((2^5)*(3^2)*5) jetzt kuerzt man durch

und hat das Ergebnis (2^3)*(3^2)*5*7 = 2520
Wenn ich auch nicht weiss ob es einen einfacheren Algorithmus gibt
(ich bezweifle es) so ist er nicht sehr schwer zu implementieren
(ausser vielleicht in Prolog oder Lisp)

Auf die Primfaktorenzerlegung bin ich auch schon gekommen, nur isses
halt sauschwer das Ganze sinnvoll zu implementieren.

Vor allem die Zahlen als Primfaktoren herzustellen ist nich so
einfach, oder anders gesagt, so umständlich dass es mir ein bisserl
zu viel Rechenzeit frisst.

Oder kennt jemand 'nen guten Algo dafür?

ja
ich sags dir aber nicht

Na gut, aber zumindest mal ist damit festgestellt dass es einfacher
geht.

Werd ich mal die grauen Zellen anwerfen.

Danke!

Wenn es dir zu langsam geht ... im schlimmsten Fall steigst halt
mal von C++ auf Prozessornähe um ... ich denke da mal an
Assembler

Heh. Ich werd mal hier den Algo 'reinstellen wenn er fertig ist,
wennst den auf Assembler ummodeln kannst ...

Nö, sorry, aber mit Assembler hab ich vor Jahren aufgehört, ich
grab's nur mehr aus wenn was ansteht, was man ohne nimmer machen
kann. Die modernen Compiler sind eh schon um einiges besser beim
Optimieren als Du's händisch je könntest.

Also jetzt fangt nicht an ueber Performance zu diskutieren
Ich schlage noch einmal vor die Primfaktorzerlegung zu verwenden
Das dauert keinen Augenschlag lange
ich denke eher der Algorithmus macht Probleme
Du musst ja keinen optimierten Algorithmus fuer riesige Zahlen
wie in der Kryptographie verwenden sondern einfach iterativ durchprobieren - aber da ich vermute dass es Dir zuviel Aufwand
macht selbst zu programmieren (Schande!!!) hier ein Link:

http://pauli.uni-muenster.de/java/prim.html

Ein kleines Java Programm und die Funktion zerlege() erledigt die
Primfaktorzerlegung und speichert die einzelnen Werte im Vektor v

Nun kanns doch kein Problem mehr sein

Hmm... gar nicht dumm...

ich hab sowas ähnliches angedacht gehabt, hab's aber dann verworfen
weil's doch bald recht overheadlastig wird. Der flaw in dem Algo ist
dass er alle ungeraden Zahlen durchprobiert, nicht nur die Primen.
Da's allerdings nicht so viele nichtprime ungeraden Zahlen < 20
gibt, und der flaw zum erstenmal beim Faktorieren von 83 'nen
unnötigen cycle verbrädt (sofern ich jetzt nicht irgendwo 'n
Denkfehler hab) isses wahrscheinlich schneller als mein aktueller.

Andererseits gehört Wurzelziehen nicht grad zu den schnellsten
Operationen, ich glaub ich werd's den Divisor zum
Vergleich quadrieren anstatt die Wurzel der Prüfzahl zu ermitteln,
geht schneller.

Werd's mal ausprobiern, DANKE!

Ich hätte mal 'ne Frage. Hab zu Hause das C++ - Kompendium von
Markt&Technik sowie einige Skripten, die nicht schlecht ist.

Aber die Skripten sind zu beschränkt und das Kompendium erklärt
erst im letzten Kapitel, wie man auf Dateien zugreift usw.

Irgendwie erinnert mich das Ding an ein Grammatikbuch, nur mit
Grammatik allein kann man keine Sprache lernen.

Also hätte ich eine Frage: Kennt ihr ein Buch, in dem C bzw. C++
gut beschrieben ist, und zwar stufenweise, das heisst man fängt mit
was einfachem an, macht schon bald einmal ein SINNVOLLES Programm
(zB irgendeine Datei einlesen und nach einem Buchstaben
durchsuchen) und verbessert seine Kenntnisse kontinuierlich?

Am Idealsten wäre ein Buch, in dem die mathematischen Dinge auch
gleich erklärt sind aber so etwas gibt es sicher nicht. Welche
Mathematikkenntnisse braucht man, um C++ zu erlernen? Gibt es auch
da gute Literatur?

Ist es sinnvoll C/C++ kombiniert zu lernen oder nacheinander oder
überhaupt nur noch C++?

Fragen über Fragen! Aber ihr werdet mir doch sicher weiterhelfen,
oder? Sonst hol ich wieder mein Assemblerbuch raus! Das war weit
einfacher und ohne Mathematikkenntnisse schon sinnvoll einsetzbar.

Zuerst zu flys Problem, wenn du mit VC++ programmierst versuche den
Datentyp _int64 damit kommst du schon ganz schön weit. Wenn du dich
wirklich in das Thema, der großen Zahlen vertiefen willst, dann
besorg dir die Lektüre von Gustav Knuth, die Algorithmensammlung
ist so ziemlich der *TRÖT* der Informatik, da gibt es fast zu
jedem Problem eine Antwort.
Zum Thema C++, muß ich sagen, es ist nicht getan die Sprache an
sich zu lerenen, sondern auch die Philosophie die dahinter steckt.
C++ ist eine Weiterentwicklung von C, die um die Element der OOP
erweitert wurde. Vergiß die Idee, gleich alles auf einmal zu
lernen. Du brauch überhaupt keine Mathematik für C++, für die
Algorithmen schon, aber das kommt später. Lerne zuerst die Sprache
und die Mathematik und dann kombiniere sie. Das Buch "Algotithmen
in C" ist nicht so schlecht, aber wenn du keine Ahnung von der
Sprache hast, ist es wie ein spanisches Dorf für dich. Also Schritt
für Schritt, wenn du C nicht brauchst, überspringe es, du lernst
nur, wie du es nicht machen sollst. Kaufe oder kopier dir lieber
Stroustroup, ist die Bibel des C++, aber für den Anfgang zu schwer.
Ein gutes Einstiegsbuch ist das Buch von Tom Swan.

Sorry, aber ich werd's unter Garantie nicht unter VC entwickeln, der
Source muss durch 'nen ANSI C++ durch können, ohne MS-Internen
Klimbim.

Ausserdem wär' mir persönlich 'n Also lieber, der das
Durchdividieren "vorher" macht und nicht erstmal alles auffaktoriert
wenn's im Endeffekt zum Gutteil eh nicht notwendig sein wird. Ergibt
'ne Mörderdivision die am Schluss dann als Ergebnis "5" liefert, ist
doch unnötig.

Es bringt dir wirklich nicht viel, wenn du mit C++ anfängst, wenn
du kein C kannst. Meiner Meinung das beste Buch zum C-Lernen ist "C-
Programmierung lernen" von Andrè Willms, ISBN: 3-8273-1405-4. Fängt
von Null an und baut Schritt für Schritt auf. Und wenn du das Buch
beherrst, kannst einmal C und dann kannst ein Buch für C++ kaufen.
mfg, Megaman

Naja Fly, dann suche mal hier http://remus.rutgers.edu/~rhoads, ich
bin sicher dort wirst du fündig.
Ich bin überhaupt nicht der Meinung, dass Leute mit C anfangen
sollen. Wir brauchen nicht sehr viele Leute die Devicetreiber
schreiben. Ich will hier nicht auf die Problematik der
Softwaretechnik eingehen. Aber das Schreiben von Software ist wie
das Malen von einem Bild. Man lernt zuerst die Technik, aber guter
Code ist mehr als nur Technik, man braucht auch Inspiration.
Immer wenn ich solche Newbies von der Uni bekomme, die glauben,
guter Code bestehe darin, dass man alles in einer Zeile schreibt
und das möglichst unleserlich, brauch ich immer ziemlich viel
*TRÖT*, sie wieder auf den rechten Pfad zu bringen. UML oder andere
OO-Techniken werden noch sehr sträflich vernachläßigt.

Ich muß die Absolventen aber auch ihn Schutz nehmen, da die Uni
auch keine große Hilfe ist, sich das nötige Wissen anzueignen. Viel
zu viel Theorie (ist auch billiger) und zuwenig Praxis.

Also noch einmal C++ rules und in ein paar Jahren vielleich C#, wer
weiß.

Jaja, so Perlen wie

if (!c=e&d(c)?d(e):d(c+e)) ...

Hauptsache alles passt in eine Zeile und kein Schwein kann's lesen.
Aber schaut ultratoll aus. Obwohl ich mich manchmal schon frag, ob
er die Übung mit seinem Beitrag zum Obfuscated C-Code Contest
verwechselt hat.

Effizienter Code ist übrigens auch nicht immer der mit den wenigsten
Zeilen. Es ist der kleinste, nur erkaufst Du Dir die Kürze oft mit
unnötigen bedingten Sprüngen.

Anyway. Auch OOP ist nicht der Weisheit letzter Schluss. Ich hab'S
mehr als einmal erlebt dass jemand ein Problem mit Krampf in eine
Klasse stopfen musste obwohl's einfach keinen Sinn machte und nur
zusätzlichen Overhead. Es gibt einfach kein "bestes" Verfahren. Es
gibt Verfahren, die sind immer Mist, aber DAS Verfahren für alle
Lebenslagen hat noch keiner entwickelt.

Übrigens, Danke für die Seite. Obwohl ich zu meiner Schande gestehen
muss, ich hab nichtmal die Hälfte verstanden. Werd' mal schauen ob
Wahrscheinlichkeitsrechnung nächstes Semester gelesen wird...

Danke, Leute, für die vielen Buchtipps!

Damit ich mir bei der Auswahl etwas leichter tu':

Was kann ich mit C und was mit C++ machen?

Ich möchte nämlich nicht nur irgendein Pimperle-Programm schreiben
können, sondern ein bisschen hinter die Kulissen auch blicken,
deshalb habe ich mich ja auch schon mit Assembler ein wenig
beschäftigt.

Brauchen tu' ich es in erster Linie für Linux. Ich denke, dass ich
hier - sollte ich effizient Source-Codes weiterbearbeiten wollen, C
auch brauchen werde und nicht nur C++, oder?

Nun, was ist der Unterschied...

Das Problem ist, wenn ich einfach jetzt sag, "C++ ist C mit Klassen"
kommt "Was ist 'ne KLasse?".

Nun, vereinfacht gesagt ist eine Klasse ist eine Struktur, die
zusätzlich Funktionen kapselt. Zusätzlich kann's Sachen erben und
vererben von und an Eltern- und Kinderklassen und vieles, vieles
mehr. Und da beginnt das nächste Problem: Es ist nicht leicht, die
Vorteile von objektorientierter Programmierung (also der Sums mit
Klassen) zu erklären, wenn man's nicht "angreifen" kann, also C
nicht kennt und daher nicht die Probleme, die es ergibt und die man
mit C++ elegant lösen kann.

Es ist wie mit Pointern, es fällt schwer den Sinn dahinter zu
erklären. Weil das Problem, das sie lösen, nicht intuitiv erfassbar
ist sondern sich erst beim Programmieren selbst zeigt.

Mein Vorschlag: Lerne C. Lerne es gut. Lerne, mit verketteten Listen
zu arbeiten und mit Pointerstrukturen. Lerne, rekursiv zu
programmieren.

Und dann, genau dann, lerne C++. Und Du wirst erleichtert aufatmen
und seufzen und feststellen, dass plötzlich alles viel, viel
leichter wird.

Versuchs mal mit LISP !

Das is dann ein knapper Fünfzeiler ...

wollte eigendlich nur sagen, dass mir wieder eingefallen is
was ich an Mathematik so gehasst hab... das viele und lange
Nachdenken von dem man Kopfweh bekommen kann (spätestens
man für eine Formel schon die 5 Seite benutzt und auf einen
Denkfehler auf der ersten draufkommt...

)

wollt das eigendlich nur so erwähnen..ich schätz ja, dass ich
hier nicht der einzige bin der nicht unbedingt Mathe als sein
Lebenselexier betrachtet..

hehe...

Ähm Fly, nur so aus interesse...den Code gibts nirgens im Netz
für diese Berechnung die du brauchst??

so long

PyroTFD

Nö, glaub ich nicht. Ich will meine Berechnung für'n
Wahrscheinlichkeitsalgorithmus (ja, inzwischen hab ich 'rausgefunden
wie man das Sch...wort richtig schreibt) für den Ausgang von
Würfelwürfen bei 'nem Rollenspiel verbessern. Derzeit geht's nur gut
für weniger als 12 Würfel (weil dann die 2^32 Schranke bei 13!
fällt).

Ich hab mich ehrlich gesagt auch gewundert, dass da noch niemand was
brauchbares geschrieben hat. Immerhin ist Primfaktorenzerlegung DAS
hochwichtige Superproblem beim RSA-Knacken.

Nur beschäftigen die sich halt nicht mit so kleinen Zahlen... Und
die Wahnsinnsalgos die irgendwo bei 2^Phantasie zum "greifen"
anfangen brauch ich halt ned. Ausserdem dauern die länger als wenn
ich's so mach wie ich's jetzt mach.

Ich hab jetzt einen Algo entwickelt, der darauf basiert dass eine
nichtprime Zahl als Produkt zweier natürlicher Zahlen dargestellt
werden kann. D.h. ich bau mir die Zahlen der Reihe nach auf (also 2,
3, 4, ...) und wenn ich eine nichtprime Zahl vor mir hab, verweise
ich einfach auf die beiden Produkte (also bei 8 z.B. auf 4 und 2)
und verlasse mich auf die Lösung, die es für beide Produkte gibt.
Das ist zwar normalerweise nicht SOOOOOO effizient (weil ich alle
Zahlen bis zu der Zahl die ich faktorieren will haben muss), aber
ich HABE ja alle Zahlen bis zu dieser Zahl faktoriert, schliesslich
ermittle ich das Produkt aller Zahlen bis zu dieser.

Und damit geht's ganz gut. Nur isses derart rekursiv dass ich Angst
hab ich spreng mir irgendwann bei grösseren Zahlen damit den Stack.
Allerdings... 20 Würfel wird so ziemlich das Maximum sein, das
jemals irgendein Supercharacter in die Finger kriegt...

Eine ganz primitive Idee (ohne Primfaktorzerlegugn) ist die, dass
du die einfelnen Faktoren einfach umsortierst:

n!/(k!m!l!) ==
(1*2*3*3*...*n)/(1*2*..*(k-1)*k * 1*2*...*(m-1)*m * 1*...*(l-1)*l)
==
(1/1)*(2/2)*...*(n/n)*( (n+1)/1) * (n+3)/2 *...* (n+m)/m *
1/1*2/2*...*(n+m+l)/l

Die einzelnen dabei auftretenden Brueche sind dann eigentlich sehr
schoen klein, und die ganze Rechnung besteht nur aus
Multiplikationen, sodass die groesste auftretende Zahl auch das
Endergebnis ist...

Natuerlich musst du da wegen der paar Rechenoperationen mehr halt
mal schauen, wie es so mit dem Fehler aussieht, aber der duerfte
sich in vertraeglichem Mass halten.

Reinhold

Dieses Forum ist eine frei zugängliche Diskussionsplattform.
Der Betreiber übernimmt keine Verantwortung für den Inhalt der Beiträge und behält sich das Recht vor, Beiträge mit rechtswidrigem oder anstößigem Inhalt zu löschen.
Datenschutzerklärung