Fakultät n! berechnung

Alphabet

int x[1000]; // grosse Zahl

Das sind 1000 kleine Zahlen, und nicht eine große Zahl.

[cpp]
cout << "Zahl*3="<<ergebnis;
[/cpp]

Diese Zeile in main() duerfte nicht funktionieren, denn Variable ergebnis ist nicht deklariert.

Knecht

Hallo,

bei der Berechnung von Fakultäten ist es immer ein wenig problematisch, die Stellen abzuschätzen um nicht so viel zeit damit zu verbringen, über Stellen zu laufen die den Wert Null besitzen. Eine Möglichkeit dazu ist, die Stirling'sche Formel etwas zu verbigen.

Eine nicht sehr sauber programmierte Lösung für Dein Problem wäre demnach wie folgt

#include <iostream>

#define	_USE_MATH_DEFINES
#include <cmath>

// function to estimate the number of
// digits of the factorial of number
int faculty(unsigned short int *&dgs, int number)
{
	// estimate the number of digits
	int mxdigits = int((number * log(long double(number / M_E)) + 0.5L * log(long double(2L * M_PI * number))) / log(10.0L) + 3.5L);

	// digits of n! will be stored in array dgs backwards
	dgs = new unsigned short int [mxdigits]();
	dgs[0] = 1;

	// n! = 2*3*4....(n-1)*n
	long loopcounter = 0;
	for (int k = 2; k <= number; k++) 
	{
		int carry = 0;

		// multiply k with every digit of (k-1)! to get k!
		for (int j = 0; j < mxdigits; j++)
		{
			int dg_old = dgs[j];
			dgs[j] = (k*dg_old + carry)%10; // remainder (of division by 10)
			carry  = (k*dg_old + carry)/10; // carry

			loopcounter++;
		}
	}

	// printing n!: highest digit dgs[count] first, lowest digit dgs[0] last. 
	int mxdigits_ex = mxdigits;
	while (dgs[mxdigits_ex-1] == 0)
		mxdigits_ex--;

	std::cout << "mxdigits (estimated) = " << mxdigits << std::endl;
    std::cout << "mxdigits (exact) = " << mxdigits_ex << std::endl;
	std::cout << "\nTo calculate the factorial the programm run the loop " << loopcounter << " times!\n";
	return mxdigits_ex;
}

void printFactorial(unsigned short int *fac, int digits)
{
	for (int i = digits - 1; i >= 0; i--)
		std::cout << fac[i];
}

void main(void)
{
	// input 
	int n;                       
	std::cout << "Enter a positive integer: \n";  
	std::cin >> n;

	unsigned short int *fac = 0;
	int digits = faculty(fac, n);
	std::cout << "The factorial of " << n << " ist ";
	printFactorial(fac, digits);
	std::cout << std::endl;

	delete[] fac;
	return 0;
}

Ich hoffe das hilft Dir weiter.

Viele Grüße

GPC

Hallo,

die Fakultät kann man eigentlich ganz einfach folgendermaßen berechnen:

//Rekursiv
  unsigned FacultyR(unsigned N) {
    return (N!=1) ? N*FacultyR(N-1) : 1;
  };

  //Iterativ
  unsigned FacultyI(unsigned N) {
    unsigned res=N;
    while (N!=1)
      res *= --N;

    return res;
  };

Wenn unsigned int nicht reicht, musst du halt in die Compiler-Doku schauen und herausfinden, was er dir an 64bit Ganzzahltypen anbietet (z.B. unsigned long long o.ä.).

MfG

GPC

Braunstein

Für 60! sollte auch ein 64Bit-Datentyp nicht reichen. Da braucht man schon was spezielles. Entweder selber geschrieben oder eine Bibliothek wie GMP, NTL ...

Knecht

GPC schrieb:

Hallo,

die Fakultät kann man eigentlich ganz einfach folgendermaßen berechnen:
//Rekursiv
  unsigned FacultyR(unsigned N) {
    return (N!=1) ? N*FacultyR(N-1) : 1;
  };

  //Iterativ
  unsigned FacultyI(unsigned N) {
    unsigned res=N;
    while (N!=1)
      res *= --N;
    
    return res;
  };
Wenn unsigned int nicht reicht, musst du halt in die Compiler-Doku schauen und herausfinden, was er dir an 64bit Ganzzahltypen anbietet (z.B. unsigned long long o.ä.).

MfG

GPC

Auf meinem PC bekomme ich bei diesem Verfahren bereits bei 13! einen overflow

GPC

Hallo,

ja, schon gut. Meine Originalbeispiele benutzen die GMP. Da ich aber davon ausgehen musste, dass der OP diese nicht hat, habe ich mich darauf beschränkt, den grundlegenden Ablauf zu zeigen.

MfG

GPC

markmilan

@knecht

das programm von dir funktioniert irgendwie nicht ganz. es bricht ab wenn ich eine zahl eingebe. ich habe versucht das programm zu überarbeiten aber ich habe es nur noch schlimmer gemacht. könntest du bitte nochmal schauen woran es liegen kann das wäre echt super.

markmilan

hab hier noch ein programm geschrieben. ist eher so ein einfaches programm. ich kann bis 10! berechnen aber danach spinnt er. ich glaube es liegt daran das ich nicht genug speichplatz habe bzw. das nicht genügent speicherplatz reserviert ist. kann mir da einer helfen??

#include <iostream.h>
#include <conio.h>

int main()
{
cout << "Geben Sie eine Zahl ein: ";
int Zahl;
cin >> Zahl;
int x = Zahl-1;
int Res = Zahl;
  while (x > 1)
  {
  cout << Res << " * " << x << " = " << Res * x << endl;
  Res *= x;
  x--;
  }  
cout << "Die Fakultaet von " << Zahl << " ist: " << Res;
getch();
return 0;    
}

Braunstein

Das liegt einfach daran, das in ein int einfach keine Zahl größer als 10! reinpasst.

Swordfish

Mit unsigned long (4 Bytes) solltest bis 12! kommen. Mit unsigned long long (8 Bytes, Microsoft Compiler: unsigned __int64) bis 64!. Für alles was darüber hinausgeht zum Beispiel mit gmp.

Greetz, Swordfish

GPC

Swordfish schrieb:

Mit unsigned long (4 Bytes) solltest bis !12 kommen. Mit unsigned long long (8 Bytes, Microsoft Compiler: unsigned __int64) bis !64. Für alles was darüber hinausgeht zum Beispiel mit gmp.

Greetz, Swordfish

FYI: Das Ausrufezeichen kommt bei Fakultäten hinter der Zahl: 12!

Swordfish

@GPC: Besten dank, man .. ist .... ja ....... LERNFÄHIG *gggrrrrrr*

Greetz, Swordfish

Knecht

markmilan schrieb:

@knecht

das programm von dir funktioniert irgendwie nicht ganz. es bricht ab wenn ich eine zahl eingebe. ich habe versucht das programm zu überarbeiten aber ich habe es nur noch schlimmer gemacht. könntest du bitte nochmal schauen woran es liegen kann das wäre echt super.

bau einfach mal ein

getch();

vor der return Anweisung in der main ein, das sollte helfen (hast du bei deinem Programm ja auch gemacht ;))

Swordfish

Knecht schrieb:

bau einfach mal ein
getch();
vor der return Anweisung in der main ein, das sollte helfen (hast du bei deinem Programm ja auch gemacht ;))

ist weder ISO/IEC 9899:TC2 noch ISO-IEC 14882:1998.

Automatisches Schließen verhindern

Greetz, Swordfish