nicht angemeldet
Fakultativ?
Das Produkt aller Zahlen einer Reihe, ist das Fakultativ?
Ich bin nicht ganz sicher aber ich glaube es heißt so.
Gibt es dafür in Perl eine Funktion bzw. gibt es eine Formel um das zu Berechnen ohne Schleifen?
Struppi.
-
Jetzt hab ich doch was im Internet gefunden. OK, es heißt Fakultät.
Gibt es dafür in Perl eine Funktion bzw. gibt es eine Formel um das zu Berechnen ohne Schleifen?
Struppi.
-
Hallo Struppi.
Jetzt hab ich doch was im Internet gefunden. OK, es heißt Fakultät.
Suchst du nun noch die Formel? Egal, ich schreib sie nochmal hin: n! = n * (n - 1)
Freundschaft!
Siechfred--
Nichts ist schwerer einzureißen als die Mauer in den Köpfen.-
Hallo Siechfred,
Suchst du nun noch die Formel? Egal, ich schreib sie nochmal hin: n! = n * (n - 1)
Du meinst wohl: n! = n * (n - 1)! wobei 0! = 1
Wenn man das implementieren will, sollte man es aber iterativ tun. Das ist auch nicht komplizierter als die rekursive Variante, so dass es recht unnötig ist, hier Rekursion zu verwenden.Grüße
Daniel
-
Hallo,
das ist nicht die Formel für die Fakultät:Suchst du nun noch die Formel? Egal, ich schreib sie nochmal hin: n! = n * (n - 1)
Sondern:
n * (n - 1) * (n - 2) * (n - 3) ....
n > 0 und ganzzahlig.
Gruss aus Münster,
Turtle -
Jetzt hab ich doch was im Internet gefunden. OK, es heißt Fakultät.
Suchst du nun noch die Formel? Egal, ich schreib sie nochmal hin: n! = n * (n - 1)
hehe, nee so einfach is das nicht
Einmal gibt es denn rekursiven Ansatz (wie von wahsaga richtig gesagt)
z.b. in Perl:sub fac
{
my $n = shift;
return $n > 1 $n * fac($n - 1) : 1;
}oder mit der Stirling Formel
http://de.wikipedia.org/wiki/Stirling-FormelDa aber laut anderer Quellen nicht viel mehr als die Fakultät von 19 (oder 17) auf dem Rechner geht, ist wohl so eine rekursive Schleife verkraftbar.
Struppi.
-
Hallo Struppi,
Da aber laut anderer Quellen nicht viel mehr als die Fakultät von 19 (oder 17) auf dem Rechner geht, ist wohl so eine rekursive Schleife verkraftbar.
Also mit einem Rechner kann ich 10000! in ungefähr drei Sekunden berechnen. Rekursiv macht das nicht mehr wirklich Spaß.
Wenn man sich auf 32bit-Integers beschränken will, hast Du aber vermutlich recht.Grüße
Daniel
-
Hi!
Also mit einem Rechner kann ich 10000! in ungefähr drei Sekunden berechnen. Rekursiv macht das nicht mehr wirklich Spaß.
Wenn man sich auf 32bit-Integers beschränken will, hast Du aber vermutlich recht.Wie misst du denn diese Zeit? Derive schafft 1000! in 0.593s und das auf einer eher älternen Hardware 1,6Ghz und 256MB.
Grüße,
Fabian St.--
Endlich online: http://fabis-site.net
--> XHTML, CSS, PHP-Formmailer, Linux
Selfcode: ie:% fl:| br:^ va:) ls:& fo:) rl:( n4:° ss:| de:> js:| ch:| mo:) zu:)-
Hallo Fabian,
Wie misst du denn diese Zeit? Derive schafft 1000! in 0.593s und das auf einer eher älternen Hardware 1,6Ghz und 256MB.
Der Rechner hier hat nur 1GHz und zumdem noch anderes zu tun, außerdem habe ich nicht gemessen sondern nur geschätzt. Ich wollte auch nur sagen, dass man schon Fakultäten berechnen kann, die um einiges größer sind als 17!
Grüße
Daniel
-
-
-
Hallo,
Da aber laut anderer Quellen nicht viel mehr als die Fakultät von 19 (oder 17) auf dem Rechner geht, ist wohl so eine rekursive Schleife verkraftbar.
Wirklich?
Mein alter Taschenrechner TI-30 berechnet da ja schon höhere Fakultäten: 69!Gruss,
Turtle-
Wirklich?
Keine Ahnung, hab's nicht gegen geprüft.
Mein alter Taschenrechner TI-30 berechnet da ja schon höhere Fakultäten: 69!
Hier wird das behauptet: http://www.c-plusplus.de/forum/viewtopic.php?t=81690&start=20
Struppi.
-
Wirklich?
Mein alter Taschenrechner TI-30 berechnet da ja schon höhere Fakultäten: 69!Wirklich?
Tut er bestimmt nicht. Er berechnet einen Näherungswert dafür.
Gunnar--
"Nobody wins unless everybody wins." (Bruce Springsteen)-
Hallo Gunnar,
Wirklich?
Mein alter Taschenrechner TI-30 berechnet da ja schon höhere
Fakultäten: 69!Wirklich?
Tut er bestimmt nicht. Er berechnet einen Näherungswert dafür.Und? Ein durchaus sehr uebliches Verfahren um grosse Fakultaeten zu
berechnen.Grüße,
CK--
Es ist uns nicht möglich, in einem Bereich unseres Lebens richtig zu verhalten, wenn wir in allen anderen falsch handeln. Das Leben ist ein unteilbares Ganzes.
http://wwwtech.de/
-
-
-
-
Hallo Daniel & Turtle.
n! = n * (n - 1)
Ja, es fehlte ein Ausrufezeichen am Ende, sorry.
Freundschaft!
Siechfred--
Nichts ist schwerer einzureißen als die Mauer in den Köpfen.
-
-
Peinlich ist, dass ich gar nicht die Faultät brauche.
Ich war auf der Suche nach der Lösung, wie berechnet man die Anzahl der möglichen (Spiel)Paarungen in einer Liga, wenn jeder gegen jeden Spielen kann. Da ich ein Testszenario mit 4 Mannschaften hatte, bin ich auf den Glauben verfallen ich bräuchte die Fakultät (4! = 6)
Ich brauch aber:
x = n * (n - 1) / 2 (wegen keiner Rückspiele)
3 * 2 = 6
Mal wieder was gelernt (nebenbei hatte ich noch die Gauß Methode in erwägung gezogen)
Struppi.
-
Hi Struppi!
Ich war auf der Suche nach der Lösung, wie berechnet man die Anzahl der möglichen (Spiel)Paarungen in einer Liga, wenn jeder gegen jeden Spielen kann. Da ich ein Testszenario mit 4 Mannschaften hatte, bin ich auf den Glauben verfallen ich bräuchte die Fakultät (4! = 6)
Die Fakultät von 4 ist 24, nicht 6 :-)
Grüße,
Fabian St.--
Endlich online: http://fabis-site.net
--> XHTML, CSS, PHP-Formmailer, Linux
Selfcode: ie:% fl:| br:^ va:) ls:& fo:) rl:( n4:° ss:| de:> js:| ch:| mo:) zu:)-
Hi,
Ich war auf der Suche nach der Lösung, wie berechnet man die Anzahl der möglichen (Spiel)Paarungen in einer Liga, wenn jeder gegen jeden Spielen kann. Da ich ein Testszenario mit 4 Mannschaften hatte, bin ich auf den Glauben verfallen ich bräuchte die Fakultät (4! = 6)
Die Fakultät von 4 ist 24, nicht 6 :-)
gesucht wurde ja das Fakultativ, nicht die Fakultaet.
Gruss,
Ludger--
"Die SPD im Aufwind?"
-
-
Hallo Struppi,
(...) Faultät (...)
Das hab ich sofort in die Liste meiner Lieblingstippfehler aufgenommen! *g*
Grüße + SCNR,
Utz--
Mitglied im Ring Deutscher Mäkler
-
-
-
hi,
Das Produkt aller Zahlen einer Reihe, ist das Fakultativ?
Ich bin nicht ganz sicher aber ich glaube es heißt so.jein.
fakultät nennt man in der mathematik das produkt aller zahlen von 1 bis n - ohne "lücken" dazwischen. wenn du das mit "alle zahlen einer reihe" meintest, hast du recht.
siehe auch http://de.wikipedia.org/wiki/Fakultät_(Mathematik)Gibt es dafür in Perl eine Funktion bzw. gibt es eine Formel um das zu Berechnen ohne Schleifen?
fertige funktion, wahrscheinlich nein (bin kein perl-kenner).
aber die fakultät wird sehr oft benutzt, um programmiereinsteiergn das prinzip der rekursion nahezubringen.über eine google-suche nach "fakultät rekursiv" findest du sehr schnell beispiele für die implementierung, u.a. hier http://www.ntecs.de/old-hp/uu9r/lang/html/lang-all.de.html#_link_parrot auch in perl.
gruß,
wahsaga--
"Look, that's why there's rules, understand? So that you _think_ before you break 'em." -
Hallo Struppi,
Irgendwo in diesem Thread wurde auf ein C++ Forum verweisen, wo vorgeschlagen wurde, Fakultäten mittels Primfaktorzerlegung zu berechnen. Ich habe mal einen Algorithmus gebastelt, der zwar sicher noch nicht optimal, aber schon sehr viel schneller als die herkömmliche rekursive oder iterative Variante ist.
Die Berechnung von 100000! braucht bei mir 5 min, wenn man den Algorithmus mit so großen Zahlen testet, sollte man allerdings die Ausgabe auskommentieren, da sie mehr Zeit als die eigentliche Berechnung benötigt. Schneller als die herkömmliche, rekursive implementierung ist der Algorithmus allerdings erst ab 1500.import java.util.*;
import java.math.BigInteger;public class factorial {
public static final void main(String[] args) {
int n = 10000;
long time1 = System.currentTimeMillis();
//Berechnung der Primfaktoren
Map<Integer, Integer> primes = getPrimes(n);
long time2 = System.currentTimeMillis();
BigInteger factorial = BigInteger.ONE;
//Berechnung der Fakultät mit Hilfe der Primfaktoren
for(Map.Entry<Integer, Integer> entry: primes.entrySet()) {
factorial = factorial.multiply(BigInteger.valueOf(entry.getKey()).pow(entry.getValue()));
}
long time3 = System.currentTimeMillis();
System.out.println(n + "! =" + factorial.toString(36));
System.out.println("Primfaktoren: " + (time2 - time1));
System.out.println("Multiplikation: " + (time3 - time2));
System.out.println("Gesamt: " + (time3 - time1));
}//Gibt die Primfaktoren der Fakultät von n zurück.
static Map<Integer, Integer> getPrimes(int n) {
BitSet raster = new BitSet(n - 1);
Map<Integer, Integer> primes = new TreeMap<Integer, Integer>();
int prime = 0;
while(prime != -1) {
primes.put(prime + 2, mark(prime, raster, n));
prime = next(prime, raster, n);
}
return primes;
}//Markiert einen Primfaktor und berechnet seine Häufigkeit
static int mark(int prime, BitSet raster, int n) {
int count = 0;
for(int i = prime; i < n - 1; i += prime + 2) {
raster.set(i, true);
}
prime += 2;
for(int i = prime; true; i *= prime) {
int z = (int)Math.floor(n / i);
if(z == 0) {
break;
}
count += z;
}
return count;
}//Gibt den nächsten Primfaktor zurück oder -1 wenn es keinen mehr gibt.
static int next(int prime, BitSet raster, int n) {
for(;prime < n - 1; prime++) {
if(!raster.get(prime)) {
return prime;
}
}
return -1;
}
}Grüße
Daniel
-
Hi Daniel,
das ist so kurz vor einem nützlichen Beitrag zu den Tipps und Tricks. Wärst Du da eventuell zu überreden?
Viele Grüße
Mathias Bigge-
Hallo Mathias,
das ist so kurz vor einem nützlichen Beitrag zu den Tipps und Tricks. Wärst Du da eventuell zu überreden?
Wenn ich so einen Artikel schreiben würde, würde ich mich vorher über entsprechende Algorithmen schlau machen. Diesen Ansatz wollte ich hier eigentlich nur zur Diskussion stellen. Aber für eine veröffentlichungsfähige Lösung halte ich das noch nicht.
Wenn Du meinst, dass dieses Thema für den Selfraum wirklich interessant ist, überlege ich mir, ob ich so einen Artikel schreibe.Grüße
Daniel
-
-