Falsche Variablen-Typen bei Fakultät-Berechnung

Ehemaliges Mitglied Erhaltene Danke: 1

- Nachträglich durch die Entwickler-Ecke gelöscht -

Logikmensch · Beiträge: 390 Win XP Delphi 2007 Prof., XE2, XE5

Meine ganz pragmatische, völlig unwissenschaftliche und unmathematische Empfehlung:
Arbeite bei solchen Berechnungen zentral mit dem Extended-Typ. Intern wird bei Delphi ohnehin jede Gleitkommazahl (egal ob Single, Double etc.) in diesen Typ konvertiert.

Ich würde auch durchaus bei der Fakultät-Funktion auf den Typ Extended gehen. Sooooooo viel schlechtere Programmierpraxis ist das nicht, auch wenn ich mit Dir schon übereinstimme, dass das Ergebnis der n! Funktion vom Typ her ein Ganzzahl-Wert ist. Aber da Du dabei schnell sehr große Zahlen bekommst und Extended sehr exakt ist, kommst Du damit vielleicht besser hin als mit Int64.

Alternativ (oder ergänzend) könntest Du die Berechnungen auch noch in try...except...end -Blöcke einschließen und im tatsächlichen Überlaufs-Falle z.B. den Wert 0 zurückliefern statt eine Fehlermeldung zu erhalten.

_________________
Es gibt keine Probleme - nur Lösungen!

Horst_H · Verfasst: Fr 22.02.08 08:54

Hallo,

Du suchst Binomialverteilung:
de.wikipedia.org/wiki/Binomialverteilung
ich habe, um de riesigen Fakultätswerten zu entgehen, die Berechnungen mit logarithmierten Werte gemacht.
www.developia.de/for...ewtopic.php?t=116793
Du siehst, dort ist die Anzahl 1e6 , unmöglich die Fakultät sinnvoll mit extended zu berechnen.
Selbst dort kommt als Summe aller Anteile 1 heraus.

Hier mal mit n= 1000, da dann ab p,q = 0.5 der Anteil anders gerechnet wird.
Die Werte der Anteile könnte man bei Bedarf auch in einem Feld speichern.

markieren

Delphi-Quelltext

1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
14:
15:
16:
17:
18:
19:
20:
21:
22:
23:
24:
25:
26:
27:
28:
29:
30:
31:
32:
33:
34:
35:
36:
37:
38:
39:
40:
41:
42:
43:
44:
45:
46:
47:
48:
49:
50:
51:
52:
53:
54:
55:
56:
57:
58:
59:
60:
61:
62:
63:
64:

program BinomAnteil;
{$APPTYPE CONSOLE}
uses
  sysutils;
const
  ANZAHL = 1000;
var
  i,n,k : longint;
  q,p,Faktor,logFaktor,logAnteil,Anteil,SummeAnteile,MittlererWert: double;

  WerteFeld :array[0..ANZAHL-1] of double;


Procedure WerteFeldBelegen;
var
  i: longint;
begin
  For i := 0 to ANZAHL-1 do
    WerteFeld[i] := WerteFeld[i]+i/(ANZAHL-1);
end;

BEGIN
  WerteFeldBelegen;
  writeln(ANZAHL,' Werte von ',WerteFeld[0]:0:0,'..',WerteFeld[Anzahl-1]:0:0,' aufsteigend');
  //n = ANZAHL-1 (0..ANZAHL-1) hat ANZAHL Elemente
  n := ANZAHL-1;
  for k := 1 to 19 do
    begin
    p := k/20;
    q := 1.0-p;
    Faktor := p/q;
    logFaktor := ln(Faktor);
    //Anteil(n,k) = (n ueber k)*p^(n-k)*(1-p)^k
    //=>Anteil(n,k)/Anteil(n,k-1) = (n-k+1)/k*p/q
    //Werte an der Stelle 0 = (n ueber 0)*q^n*p^0=q^n
    logAnteil := n*ln(q);
    Anteil := exp(logAnteil);//=q^N
    SummeAnteile := Anteil;
    MittlererWert := SummeAnteile*WerteFeld[0];
    if Anteil > 0 then
      begin
      for i := 1 to N do
         begin
         Anteil := Anteil/i*(n-i+1)*Faktor;//=(n überk)*p^i*q^(n-i);
         if Anteil = 0 then
            break;
         MittlererWert := MittlererWert+Anteil*WerteFeld[i];
         SummeAnteile := SummeAnteile+Anteil;
         end;
      writeln('Werte fuer ',p:4:3,' ist ',MittlererWert:15:9,'   ',SummeAnteile:15:2);
      end
    else
      begin
      for i := 1 to N do
         begin
         logAnteil := logAnteil-ln(i)+ln(ANZAHL-I)+logFaktor;
         Anteil := exp(logAnteil);
         MittlererWert := MittlererWert+Anteil*WerteFeld[i];
         SummeAnteile := SummeAnteile+Anteil;
         end;
      writeln('Werte fuer ',p:4:3,' ist ',MittlererWert:15:9,'   ',SummeAnteile:15:2,' log');
      end;
end;
end.

Gruß Horst

Gausi · Verfasst: Fr 22.02.08 09:47

Wenn man bei Integer bleiben möchte, kann man N über P auch mit Hilfe des Pascalschen Dreiecks berechnen. Dafür braucht man nur ein 2D-Array entsprechender Größe, was man bis zur gewünschten Größe mit Werten füllt.

Edit: Hab meinen alten Code gefunden:

markieren

Delphi-Quelltext

1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
14:
15:
16:
17:
18:
19:

function binomial(n, k: Integer): Integer;
var x, y: Integer;
    pas_dreieck: array of array of Integer;
begin
    result:=0;
    if n-k < k then k := n-k;
    if k=0 then result := 1;
    if k=1 then result := n;
    if k>1 then
    begin
        setlength(pas_dreieck,k+1,n+1);
        for y:=0 to n do pas_dreieck[0,y] := 1;
        for y:=1 to n do pas_dreieck[1,y] := y;
        for x:=2 to k do
            for y := x to n do
                pas_dreieck[x,y] := pas_dreieck[x-1,y-1] + pas_dreieck[x,y-1];
        result := pas_dreieck[k,n];
    end;
end;

_________________
We are, we were and will not be.

Horst_H · Verfasst: Sa 23.02.08 00:02

Hallo,

n über k mittels Pascal'schen Dreieck, also nur mit Additionen zu bestimmen, ist eine witzige Idee.
Hier mal drei Varianten für n über k.
Einmal stures multiplizieren dividieren, dann Pascal'sches Dreieck komplett und dann unter Wiederbenutzung einer Zeile.
Die Grenze für INt64 bliegt für Binom bei 61/30 für die Dreick's Versionen bei 66.

markieren

Delphi-Quelltext

1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
14:
15:
16:
17:
18:
19:
20:
21:
22:
23:
24:
25:
26:
27:
28:
29:
30:
31:
32:
33:
34:
35:
36:
37:
38:
39:
40:
41:
42:
43:
44:
45:
46:
47:
48:
49:
50:
51:
52:
53:
54:
55:
56:
57:
58:
59:
60:
61:
62:
63:
64:
65:
66:
67:
68:
69:
70:
71:
72:
73:
74:
75:
76:
77:
78:
79:
80:
81:
82:
83:
84:
85:
86:
87:
88:
89:
90:

{$APPTYPE Console}
var
  k,n:integer;


function Binom(n,k:integer): int64;
var
  i : integer;
begin
  {triviales abfangen fehlt}

  //k mit n-k tauschen, falls es sich lohnt
  i := n-k;
  If k>i then
    k := i;


  result := 1;
  For i := 1 to k do
    begin
    result := (n*result) div i;// Ist immer ohne Rest
    dec(n);
    end;
end;

function binomial(n, k: Integer): Int64;
var x, y: Integer;

    pas_dreieck: array of array of Int64;
begin
    result:=0;
    if n-k < k then k := n-k;
    if k=0 then result := 1;
    if k=1 then result := n;
    if k>1 then
    begin
        setlength(pas_dreieck,k+1,n+1);
        for y:=0 to n do pas_dreieck[0,y] := 1;
        for y:=1 to n do pas_dreieck[1,y] := y;
        for x:=2 to k do
            for y := x to n do
                pas_dreieck[x,y] := pas_dreieck[x-1,y-1] + pas_dreieck[x,y-1];
        result := pas_dreieck[k,n];
    end;
end;

function binomPas(n, k: Integer): Int64;
var x, y,idx,g: Integer;
    s: array[0..1]of int64;
    pas_dreieck: array of Int64;
begin
    result:=0;
    if n-k < k then k := n-k;
    if k=0 then
      result := 1;
    if k=1 then
      result := n;
    if k>1 then
      begin
      setlength(pas_dreieck,n);
      for y:=0 to n-1 do
        pas_dreieck[y] := 1;
      for y:= 1 to n-1 do
        begin
        S[0] := 1;//:= pas_dreieck[0];
        idx:=1;
        g := y-1;
        if g>k then
          g:= k;
        for x:= 1 to g do
          begin
          S[idx] := pas_dreieck[x];
          pas_dreieck[x] := S[0]+S[1];
          idx:=1-idx; //FlipFlop 0,1,0,1,0,1,0..
          end;
        end;
       result := pas_dreieck[k]+pas_dreieck[k-1];
    end;
end;

begin
  n := 61;
  For k := 0 to n do
    begin
    writeln(n,'|',k,' = ',binom(n,k));
    writeln(n,'|',k,' = ',binomPas(n,k));
    writeln(n,'|',k,' = ',binomial(n,k));
    end;
  readln;
end.

Gruß Horst

Ehemaliges Mitglied Erhaltene Danke: 1

- Nachträglich durch die Entwickler-Ecke gelöscht -

nagel · Beiträge: 708 Win7, Ubuntu 10.10

Deine Formel ist Unsinn, wenn du n, p und x eingeben lässt, sollte es n über x sein und nicht n über p.

Ansonsten ist in deinem ursprünglichen Code ein StrToInt bei der p-Eingabe, p ist aber keine ganze Zahl, also hier StrToFloat.

Ansonsten müssen p und q natürlich noch Gleitkommazahlen sein, also beispielsweise Double.

Hoffe das war alles :wink:

.

Ehemaliges Mitglied Erhaltene Danke: 1

- Nachträglich durch die Entwickler-Ecke gelöscht -

	Mitgliederliste
	Gruppen
	Das Team
	Richtlinien
	Synonyme