3. Variable ist zu klein

Variable ist zu klein

  • M

    Hallo Leute,

    ich habe 2 Funktionen geschrieben, eine, um die Fakultät auszurechnen (also n*(n-1)*(n-2) ... *2*1) und eine, um binomische Formeln auszugeben. Der Binomische Satz braucht die Fakultät, um den Binomialkoeffizienten zu berechnen. Insgesamt sieht der Binomische Satz so aus:
    \sum_{k=0}^n \left({n \atop {k}}\right) a^{n-k}b^k
    Ich habs mal so probiert:

    unsigned long fakultaet(unsigned int a)
{
  if(a==0 || a==1)
    return 1;
  else
  {
    unsigned long n=1;
    unsigned int x;

    for(x=1;x<=a;x++)
    {
      n=n*x;
    }
    return n;
  }
}

void binomAnzeigen(unsigned int n)
{
  switch(n)
  {
    case 0:
      cout << "1"; break;
    case 1:
      cout << "a + b"; break;
    case 2:
      cout << "a^2 + 2ab + b^2"; break;
    default:
      unsigned int k;
      unsigned long x, y;

      cout << "a^" << n << " + ";

      for(k=1;k<n;k++)			
      { 
	x=fakultaet(n);		           // Zähler vom Binomialkoeffizienten
	y=fakultaet(k)*fakultaet(n-k);	// Nenner vom Binomialkoeffizienten

	if(k==1) cout << n << "a^" << (n-1) << "b + ";
	else
	{
	  if(k==(n-1)) cout << n << "ab^" << k << " + ";
	  else cout << (x/y) << "a^" << (n-k) << "b^" << k << " + ";
	}
      }

      cout << "b^" << k; break;
  }
}

    Wenn n jetzt aber größer als 12 ist, ist unsigned long zu klein. Wie kann ich es anstellen, dass trotzdem das richtige Ergebnis rauskommt?

    0
  • F
     

    unsigned long long binom(int n, int k)
{
unsigned long long ret=1;
for(int i=n;i>(k>n-k?k:n-k);i--)
	ret*=i;
for(int i=(k>n-k?n-k:k);i>1;i--)
	ret/=i;
return ret;  
}

    Hiermit müßte man schon ein Stückchen weiter kommen...
    (falls long long nicht gehen sollte, mußt du halt mit long vorlieb nehmen 😉 )

    0
  • M

    Könnte mir einer mal bitte den Code kommentieren? Die Parameter der Schleife kapier ich nicht ganz...

    0
  • H

    ist (i) größer als der größere von (k) und (n-k)?

    0
  • M

    Ich weiß nicht, wieso "binom" zwei Parameter bekommen soll. Wenn
    (a+b)^4
    dann ist n=4. k ist am Anfang immer 0. Deshalb braucht das auch nicht angegeben zu werden.

    0
  • F

    Könnte mir einer mal bitte den Code kommentieren? Die Parameter der Schleife kapier ich nicht ganz...

    http://www.ica1.uni-stuttgart.de/~hilfer/de/lehre/100-online/skriptum/node34.html

    Ich weiß nicht, wieso "binom" zwei Parameter bekommen soll.

    binom berechnet n über k und nicht die Fakultät...

    0
  • M

    binom berechnet n über k und nicht die Fakultät...

    Für die Fakultät habe ich ja extra eine eigene Funktion geschrieben. binom kriegt nur den einen Parameter n, die Grundform ist ja
    (a+b)^n
    Das k ist immer gleich, ganz egal wie groß n ist.
    Aber danke für den Link!

    0
  • F

    So hatte ich das gedacht:

    void binomAnzeigen(unsigned int n)
{
  switch(n)
  {
    case 0:
      cout << "1"; break;
    case 1:
      cout << "a + b"; break;
    case 2:
      cout << "a^2 + 2ab + b^2"; break;
    default:
      unsigned int k;
      unsigned long x, y;

      cout << "a^" << n << " + ";

    for(k=1;k<n;k++)
    {
    if(k==1) cout << n << "a^" << (n-1) << "b + ";
    else
    {
      if(k==(n-1)) cout << n << "ab^" << k << " + ";
      else cout << binom(n,k) << "a^" << (n-k) << "b^" << k << " + ";
    }
      }

      cout << "b^" << k; break;
  }
}
    0
  • M

    Dann hatte ich dich falsch verstanden, fubar.
    Jetzt könnte man auch x und y aus binomAnzeigen rauswerfen, um noch ein bisschen Platz zu sparen.
    Danke für deine Hilfe!!!

    0
  • G

    mit double sollte es gehen... z.b. so:

    double fakDouble(double x)
    {
    if(x<0)
    return 0;
    if(x==0)
    return 1;
    else
    return x * (fakDouble(x-1));
    }

    0
  • J

    Eine schöne Möglichkeit ist auch sich ne Abschätzung für n über k zu besorgen und dann noch eine Primzahl p, die größer als diese Schranke ist. Mann kann dann nämlich einfach alle Schritte modulo p rechnen, also immer den Rest bezüglich Division durch p. (Mathematiker würden sagen man projiziert auf Z/pZ)
    Der Rest liegt dann zwischen 0 und p-1. Weil ja aber das Ergebnis sowieso < p ist, ist dieser Rest gerade das Ergebnis. Auf diese Art und Weise kann man auch noch für ziemlich große n rechnen, weil die Fakultät ja immer wieder mit mod p klein gehalten wird.

    MfG Jester

    0
  • J

    Ich hab mich grad mal hingesetzt und noch ein bißchen rumgerechnet.
    Ohne große Klimmzüge komme ich mit dieser Version wohl bis n=34.

    MfG Jester

    0
  • ?

    Kannste mal Code posten dann wieß ich auch wat du mit Abchätzung meins. Bin net so gut in Mathe.

    0
  • W

    Also ich benutze immer folgende Funktion

    template<typename T>
  T Binomial(unsigned n, unsigned k)
{
  if(k > n) return 0;
  if(k == n) return 1;

  T rval = 1;
  for(unsigned i = n; i != k; --i)
    rval *= i;
  for(unsigned i = n - k; i != 1; --i)
    rval /= i;

  return rval;
}
    0
  • J

    Hab den Code grad nicht greifbar. Kommt heute abend (nacht) irgendwann oder morgen früh.

    MfG Jester

    0
  • M

    Man könnte ja auch eine zu große Zahl durch 65535 teilen, den Ganzzahlwert in einer unsigned _int64 und den Rest in einer unsigned int-Variable speichern. Zur Ausgabe mit cout rechnet man dann rückwärts

    0
  • W

    *knock* *knock*. Ich habe doch eine funktionierende Lösung gepostet. Wenn du die so aufrufst...

    unsigned long long x = Binomial<unsigned long long>(n, k);
unsigned __int64 y = Binomial<unsigned __int64>(n, k);

    ...dann solltest du relativ hohe Werte erhalten können. Deine Idee mit dem dividieren funktioniert auch nur begrenzt und ist viel aufwändiger (NR sux 😃 ).

    0
  • M

    MaSTaH schrieb:

    unsigned long long x = Binomial<unsigned long long>(n, k);

    unsigned long long funktioniert bei mir nicht

    unsigned __int64 y = Binomial<unsigned __int64>(n, k);

    Mit der Variante kommst du bis 20!. Wenn du es aber machst, wie ich beschrieben hab (bloß mit zwei unsigned _int64), dann kommt man bis 34!.

    (NR sux 😃 ).

    Was heißt das???

    0
  • K

    Für die Praxis: Einfach logarithmisch rechnen mit double-Werten. Damit kommt man sehr weit!
    ln(k!) = Sum(i=1..k){ln(i)}

    #include <math.h>
double LogFak(int k)
{
	double dLogSum = 0;
	while(k > 1)
	{
		dLogSum += log((double) k);
		--k;
	}
	return dLogSum;
}
    0
  • K
     

    #define MERKE_ERSTE 1000 //Zum Beschleunigen die ersten paar Werte merken
double LogFak(int k)
{
	static int siValid = 1; //Index, bis zu dem Array-Inhalt gueltig ist
	static double sadLogFak[MERKE_ERSTE] = { 0 };
	if(k <= siValid)
		return sadLogFak[k];
	double dLogSum = saLogFak[siValid];
	int i = siValid + 1;
	while(i < MERKE_ERSTE)
	{
		dLogSum += log((double) i);
		sadLogFak[i] = dLogSum;
		++i;
	}
	siValid = i - 1;
	while(i <= k)
	{
		dLogSum += log((double) i);
		++i;
	}
	return dLogSum;
}
    0
  • M

    Sorry, kann noch keinen Logarithmus. Kannst du mir mal zeigen, was ich mit dem return-Wert anfangen soll und wieso der return-Wert bei 1 bis 999 gleich ist (wenn #define MAX_WERT 10000, dann sind sogar alle return-Werte bis 9999 gleich) 🙄 .

    0
Anmelden zum Antworten