Re: Fakultät berechnen
als beispiel mal 51090942171709440000
5.10909E19 ich habe nur 6 stellen genauigkeit, kann aber eine 20stellige zahl darstellen (wenn auch ungenau). aus dem grund ist z.b. 1e300 + 1 = 1e300. die stellen an genauigkeit reichen nicht aus fuer unterscheidungen um 1 bei so grossen zahlen. reicht das soweit? wikipedia kann dir unter fliesskommazahlen mehr erzaehlen. |
Re: Fakultät berechnen
Liste der Anhänge anzeigen (Anzahl: 1)
Anbei mein Program zur exakten Berechnung der Fakultät. Einfach enpacken, im Menu auf \Factorial\Schönhage\ klicken, 50000 eingeben, return drücken, 89ms warten und Y drücken um die komplette Zahl zu sehen.
Wenn ihr im Menu \Factorial\Display shortest Primepower Path\ anklickt und dann 100 eingebt so seht ihr die Formel mit der man 100! am schnellsten berechnen kann.
Code:
Gruß Hagen
Input N! ? 100
(((((3)^2 * 3*5*7)^2 * 5*11)^2 * 13*17*19*23)^2 * 13*29*31*37*41*43*47)^2 * 11*13*17*19*29*31*53*59*61*67*71*73*79*83*89*97 * 2^97 |
Re: Fakultät berechnen
Hi, also ich soll bestimmen wie viele Endnullen 100Fakultät hat. Dafür müsste ich also 100! erstmal exakt bestimmen. Bekannticher weiße arbeitet der Computer vor meiner Nase nur auf 32 Stellen exakt, und mit integer kann ich es ja eh nicht anzeigen lassen. also hab ich mir mal gedacht, mach ich für jede ziffer/Stelle nen eigenes Feld, sodass jede integer variable nicht über 9 hinausgeht. Und am Ende soll das dann in nem Editfeld ausgegeben werden. Dazu hab ich mir diesen Quellcode ausgedacht:
Delphi-Quellcode:
Das ganze klappt auch bis zur berechnung von 10! Tadellos aber ab 11! bekomm ich den fehler: Project Project1.exe raised exception class EAccessViolation with message 'Access violation at address 0040421E in module 'Project1.exe'. Write address 0044F3A9'. Process stopped. Use Step or Run to continue.
procedure TForm1.Button1Click(Sender: TObject);
var Zahl:array[1..2, 1..170] of integer; a, b, d : string; i, c, Stelle : integer; begin for i:= 1 to 170 do begin Zahl[1,i]:=0; Zahl[2,i]:=0; end; Zahl[1,1]:=1; for i:= 1 to 11 do begin for Stelle:=1 to 170 do begin a:=inttostr(i * Zahl[1,Stelle]); b:=copy(a,length(a),length(a)); c:=strtoint(b) + Zahl[2,Stelle]; if c > 10 then begin d:=inttostr(c); d:=copy(d,length(d),length(d)); c:=strtoint(d); Zahl[2,(Stelle+1)]:=Zahl[2,(Stelle+1)] + 1; end; Zahl[2,Stelle]:=c; b:=copy(a,(length(a)-1),(length(a)-1)); if b = '' then b:= '0'; c:=strtoint(b) + Zahl[2,(Stelle+1)]; if c > 10 then begin d:=inttostr(c); d:=copy(d,length(d),length(d)); c:=strtoint(d); Zahl[2,(Stelle+2)]:=Zahl[2,(Stelle+2)] + 1; end; Zahl[2,(Stelle+1)]:=c; b:=copy(a,(length(a)-2),(length(a)-2)); if b = '' then b:= '0'; c:=strtoint(b) + Zahl[2,(Stelle+2)]; if c > 10 then begin d:=inttostr(c); d:=copy(d,length(d),length(d)); c:=strtoint(d); Zahl[2,(Stelle+3)]:=Zahl[2,(Stelle+3)] + 1; end; Zahl[2,(Stelle+2)]:=c; if i=11 then Edit1.Text:=inttostr(Zahl[2,Stelle]) + Edit1.Text; end; for Stelle:=1 to 170 do begin Zahl[1,Stelle]:=Zahl[2,Stelle]; Zahl[2,Stelle]:=0; end; end; end; Dann kommt das gleiche nochmal nur die erste adresse ist 00404242 und die zweite FFFFFFFF. Kann mir vielleicht einer helfen und mir sagen, wo ich den Fehler bzw. Denkfehler gemacht habe?? Ich hab mir das ergebnis jetzt mit dem ein post vor mir angegebenen prog angesehen, und so die aufgabe der Endnullen gelöst, wüsste trotzdem gerne mal meinen Fehler. |
Re: Fakultät berechnen
Zitat:
Wo genau kommt denn die Fehlermeldung ? |
Re: Fakultät berechnen
@salamahachy:
die Anzahl der Nullen kannst du komplett ohne Beechnung der Fakultät ausrechnen. Schau dir mal obige Expansion von 100! ganz genau an. Wichtig dabei sind alle Primzahlexponenten zur Basis 2 und Basis 5 denn nur diese können mit 2*5 = 0 im Resulat sein. Vereinfacht für die Basis 10 also so:
Delphi-Quellcode:
und komplizierter, dafür aber universeller, für alle Basen zwischen 2 bis 48 dann so:
function FactorialTrailingZerosBase10(N: Int64): Int64;
begin Result := 0; while N >= 5 do begin N := N div 5; Inc(Result, N); end; end;
Delphi-Quellcode:
Beispiel:
function FactorialTrailingZeros(const N: Int64; Base: Cardinal): Int64;
// compute count of trailing zeros to base of factorial N! const Primes: array[0..2] of Cardinal = (2,3,5); HighestPrime = 7; HighestBase = HighestPrime * HighestPrime -1; function PrimePower(N: Int64; Prime: Cardinal): Int64; begin Result := 0; while N >= Prime do begin N := N div Prime; Inc(Result, N); end; end; var I,Multiple: Cardinal; Power: Int64; begin if (Base < 2) or (Base > HighestBase) then raise Exception.CreateFmt('FactorialTrailingZeros(), Base must be between 2 upto %d', [HighestBase]); if (N < 0) then raise Exception.Create('FactorialTrailingZeros(), N must be >= 0'); Result := $FFFFFFFF; for I := Low(Primes) to High(Primes) do begin Multiple := 0; while Base mod Primes[I] = 0 do begin Base := Base div Primes[I]; Inc(Multiple); end; if Multiple > 0 then begin Power := PrimePower(N, Primes[I]) div Multiple; if Result > Power then Result := Power; end; if Base = 1 then Exit; end; Power := PrimePower(N, Base); if Result > Power then Result := Power; end; 100! == 2^97*3^48*5^24*7^16*11^9*13^7*17^5*19^5*23^4*29^3* 31^3 *37^2*41^2*43^2*47^2*53^1*59^1*61^1*67^1*71^1*73^1 *79^1*83^1*89^1*97^1 Wir möchten nun wissen wieviele Nullen zur Basis 10 am Ende stehen würden. Die Basis 10 zerlegt sich in 2*5. Also müssen wir obige Exponenten zu den Basen 2 und 5 berechnen. Also 2^97 und 5^24. Nur 2*5 kann eine 0 ergeben, logisch da 2*5 = 10 ergo zur Basis 10 == 0. Das bedeutet wir suchen den kleinsten gemeinsammen Exponnenten von 2^97 und 5^24 und das ist 24 da sie einmal in 24 und 4 mal in 97 reinpasst. Ergo 100! hat exakt 24 Nullen am Ende wenn wir das als Dezimalzahl darstellen wollen. Angenommmen wir möchten nun wissen wieviele Nullen 100! zu Basis 9 hat. 9 == 3 * 3 == 3^2. Hier haben wir die Basis 3 zum Exponenten 2. Wir berechnen wieder den Primzahlexponeten von 3 in 100! wie oben gezeigt 3^48. Da wir aber die Basis 3 eben 2 mal haben -> 3^2 müssen wir den Exponenten 48 aus 3^48 durch 2 teilen. Ergibt 24, also 24 Nullen enthält 100! am Ende wenn wir 100! im 9'er Zahlensystem darstellen. Im Zahlensystem 27 -> 3^3 müssenwir also 48 aus 3^48 durch 3 teilen ergibt dann 16 Nullen in 100! im Zahlensystem 27. Obige Funktion FactorialTrailingZeros() zerlegt nun die Basis "Base" in ihre Primzahlexponentation, zb. 36==2^2*3^2 und berechnet dann jeweils zur Basis 2 und 3 den Exponenten aus der Fakultät von N. Wir müssen also garnicht N! komplett ausrechnen um die Anzahl der endenden Nullen zu berechnen. Gruß hagen [edit] falls du mein DECMath verwendest nutzt du nachfolgende Funktion. Sie kann mit Basen bis 2^32-1 rechnen.
Delphi-Quellcode:
[/edit]
function NFactorialTrailingZeros(const N: Int64; Base: Cardinal): Int64;
// compute count of trailing zeros to base of factorial N! function PrimePower(N: Int64; Prime: Cardinal): Int64; begin Result := 0; while N >= Prime do begin N := N div Prime; Inc(Result, N); end; end; var I,Multiple,Prime,BaseRoot: Cardinal; Power: Int64; begin if Base < 2 then raise Exception.Create('NFactorialTrailingZeros(), Base must be >= 2'); if (N < 0) then raise Exception.Create('NFactorialTrailingZeros(), N must be >= 0'); InitSmallPrimes; Result := $FFFFFFFF; BaseRoot := Trunc(Sqrt(Base)); I := 0; repeat Prime := SmallPrimes[I]; if Prime > BaseRoot then Break; Inc(I); Multiple := 0; while Base mod Prime = 0 do begin Base := Base div Prime; Inc(Multiple); end; if Multiple > 0 then begin Power := PrimePower(N, Prime) div Multiple; if Result > Power then Result := Power; end; until Base = 1; if Base > 1 then begin Power := PrimePower(N, Base); if Result > Power then Result := Power; end; end; [edit=Sharky]Zur Vermeidung eines Scrollbalken habe ich in die Zeile mit der Berechnung von 100! einen Zeilenumbruch eingefügt. Mfg, Sharky[/edit] |
Re: Fakultät berechnen
Erklären wir das mal alles an einem Beispiel.
Code:
die 1 können wir entfernen sie ist die Einheit und damit irrelevant
10! = 1 * 2 * 3 * 4 * 5 * 6 * 7 * 8 * 9 * 10
Code:
Obige Zahlen setzen sich zusammen aus Primzahlen und Zusammengesetze Zahlen, wir abstrahieren mal noch weiter
10! = 2 * 3 * 4 * 5 * 6 * 7 * 8 * 9 * 10
Code:
Nun noch weiter abstrahieren
10! = 2^1 * 3^1 * 2^2 * 5^1 * 2^1 * 3^1 * 7^1 * 2^3 * 3^2 * 2^1 * 5^1
Code:
und nochmal weiter
10! = (2^1 * 2^2 * 2^1 * 2^3 * 2^1) * (3^1 * 3^1 * 3^2) * (5^1 * 5^1) * (7^1)
Code:
wir erkennen erstmal folgendes: Die Exponenten fallen immer weiter je größer die Basis wird, d.h. der Exponent zu basis 2 wird immer größer sein als die Exponenten der nachfolgenden Basen.
10! = 2^8 * 3^4 * 5^2 * 7^1
Aus diesem Grunde können wir wenn wir die Anzahl der Nullen im Dezimalsystem suchen -> 10 = 2*5 also sofort die Basis 2 vernächlässigen. Ergo: nehmen wir den Exponenten zur Basis 5 und das ist die Anzahl der gesuchten Nullen im Dezimalsystem. In unserem Beispiel von 10! also 2 Nullen. Genauer gesagt 10! hat zur Basis: 2 = 8 Nullen 3 = 4 Nullen 5 = 2 Nullen 7 = 1 Null. Zur den Basen: 4 = 2*2 = 8/2 = 4 Nullen 6 = 2*3 = 4<8 = 4 Nullen 8 = 2*2*2 = 8/3 = 3 Nullen 9 = 3*3 = 4/2 = 2 Nullen 10 = 2*5 = 2<8 = 2 Nullen 11 = 0 Nullen 12 = 2*2*3 = 8/2=4 <= 4 = 4 Nullen 13 = 0 Nullen 14 = 2*7 = 1<8 = 1 Null 15 = 3*5 = 2<4 = 2 Nullen 16 = 2*2*2*2 = 8/4 = 2 Nullen Um nun den Exponenten zur einer Basis zu finden geht man folgendermaßen vor. Man dividiert einfach das N aus N! mit der gesuchten Basis und addiert das auf einen Zähler. Also beipsiel 100! 1.) 100 / 5 = 20, +20 = 20 2.) 20 / 5 = 4, + 4 = 24 3.) 4 / 5 = 0, Schleife abbrechen Resultat = 24, ergo in 100! kommt der Term 5^24 vor. 1.) 100 / 7 = 14, +14 = 14 2.) 14 / 7 = 2, + 2 = 16 3.) 2 / 7 = 0, Schleife abbrechen Resulat 16, ergo in 100! kommt der Term 7^16 vor. Gruß Hagen |
Alle Zeitangaben in WEZ +1. Es ist jetzt 22:43 Uhr. |
Powered by vBulletin® Copyright ©2000 - 2024, Jelsoft Enterprises Ltd.
LinkBacks Enabled by vBSEO © 2011, Crawlability, Inc.
Delphi-PRAXiS (c) 2002 - 2023 by Daniel R. Wolf, 2024 by Thomas Breitkreuz