3. Fakultät berechnen!!! von 0 bis 20 (sehr dringend)

Fakultät berechnen!!! von 0 bis 20 (sehr dringend)

  • ?

    hall o muß die Fakultät von 0 bis 20 berechen

    also

    0 1
    1 1
    2 3
    3 6
    4
    .
    .
    .
    20

    habe es versucht!! habe es jedoch nicht hinbekommen!! mein Problem lag bei 0 1 und 1 1

    Meine Code#include

    <iostream> 
using namespace std;

int main()
{

int z,i=1;
int sum=0;
cin>>z;
do 
{sum+=i++;
cout <<i-1<<"   ";
cout << sum<<"\n";}
while (i<=z);

system ("pause");
return 0;
}

    Wäre cool wenn mir jemand einen Vorschlag machen könnte!! (nach möglichkeit nicht rekursiv)

    ist leider sehr wichtig und dringend für mich

    Gruß Joschi

    0
  • B

    Such doch einfach mal hier im C++-Forum nach "Fakultät" (bzw "*Fakultät*") 🙂

    0
  • ?

    joschii schrieb:

    ist leider sehr wichtig und dringend für mich

    Wieso ? Schreibst du morgen ne Klausur 🙂

    Fakultät: Du willst also die Fakultät von 0 bis 20. Weißt du das dies bedeutet das du das Produkt aller Zahlen von 0 bis 20 berechnen musst ? ( 0 Spezialfall = 1 )

    D.h. Du läufst alle Zahlen von 1 - 20 durch ( for-Schleife ) und speicherst dir das produkt immer in ner Variablen.

    0
  • B

    ohne, meinst ihr mit (sehr dringend) machen wir uns mehr mühe zu helfen? im gegenteil

    long fak=1;
for(int k=0; k< 0; k++,fak*=k);
    0
  • P

    BorisDieKlinge schrieb:

    long fak=1;
for(int k=0; k< 0; k++,fak*=k);

    gibt dann für immer und eqig fak==1, k==0 🙄

    [cpp]const int k_max = 20;
    for (int k=0, long fak=1; k<k_max; fak *= ++k)
    cout << k << ' ' << fak << '\n';

    0
  • C

    Oder eine klassische O(1)-Loesung, fuer den Fall, dass man sich das Rechnen sparen will:

    unsigned long long fac(int n) {
  static const unsigned long long f[] = {
    1,1,2,6,24,120,720,5040,40320,362880,3628800,39916800,
    479001600,6227020800,87178291200,1307674368000,
    20922789888000,355687428096000,?,?,?};
  return f[n];
}

    Damit das bis n = 20 funktioniert musst du nur noch die letzten drei Zahlen eintragen.

    0
  • B

    der breich muss durch "0" ersetzt werden..

    0
  • S

    oder näherungsweise wenn das reicht 😃

    #define MATH_E   2.718281828459045235360287471352662
#define MATH_PI2 6.283185307179586476925286766559

double Factorial_Stirling(const double x)
{
  return (sqrt(MATH_PI2 * x) * pow(x / MATH_E, x));
}
    0
  • B

    @sunday: coole sache

    0
  • F

    Oder so:

    #include <numeric>
#include <vector>
#include <iostream>
//...
int multiply(int a, int b){ return a * b; }
//...
std::vector<int> values;
int fakof = 20;
for(int i = 1; i <= fakof; ++i) values.push_back(i);
int fak = accumulate(values.begin(), values.end(), 1, multiply);
std::cout << fakof << "! = " << fak << std::endl;
//...

    Geht eigentlich ein Funktion Pointer auf einen Operator eines atomaren Typs?

    0
  • A

    Wenn wir schon alle Möglichkeiten vorstellen fehlt natürlich auch noch die Variante mittels Template-Metaprogrammierung zur Compilezeit:

    template <unsigned int a> struct fac;

template <> struct fac<0>
{ enum { Result = 1 }; };

template <unsigned int a> struct fac
{ enum { Result = a * fac<a-1>::Result}; };

    cu André

    0
  • W

    Fellhuhn schrieb:

    Oder so:

    #include <numeric>
 #include <vector>
#include <iostream>
//...
int multiply(int a, int b){ return a * b; }
//...
std::vector<int> values;
int fakof = 20;
for(int i = 1; i <= fakof; ++i) values.push_back(i);
int fak = accumulate(values.begin(), values.end(), 1, multiply);
std::cout << fakof << "! = " << fak << std::endl;
//...

    Geht eigentlich ein Funktion Pointer auf einen Operator eines atomaren Typs?

    was Du meinst - ist ein Funktor - in diesem Fall multiplies< int > aus <functional>.

    Und wenn schon Fakultät mit STL, dann aber richtig:

    #include <functional>   // multiplies
#include <numeric>      // partial_sum
#include <vector>

// --  erzeugt alle Fakultäten von 1! bis n! und schreibt sie nach *out
template< typename T, typename Out >
void generate_fac( int n, Out out )
{
    std::vector< T > x( n, 1 );
    std::partial_sum( x.begin(), x.end(), x.begin() );
    std::partial_sum( x.begin(), x.end(), out, std::multiplies< T >() );
}

    .. und folgender Aufruf

    #include <iostream>
#include <iterator>     // ostream_iterator

int main()
{
    using namespace std;
    generate_fac< double >( 20, ostream_iterator< double >( cout, "\n" ) );
    cout << endl;
    return 0;
}

    schreibt dann alle Fakultäten von 1! bis 20! auf stdout.

    Sunday schrieb:

    #define MATH_E   2.718281828459045235360287471352662
#define MATH_PI2 6.283185307179586476925286766559

    besser:

    #include <cmath>
namespace math
{
    const double pi = std::acos( -1.0 );
    const double e = std::exp( 1.0 );
}

    Gruß
    Werner

    0
  • O

    Wenn du einfach nur die Zahlen willst, kannst du den Windowstaschenrechner benutzen. (Bei Ansicht "wissenschaftlich" einstellen)

    0
  • ?
     

    #Fakultaet.py

def fak(n):
	fak=1
	for i in range(1,n+1):
		fak=fak*i
	print fak

n=1
while n<>0:
	n=input('Geben Sie eine Zahl ein:')
	fak(n)

    Python hat sehr lange Integer. Man kann also selbst die Fakultaet von 1000 berechnen. Ich habe gehört, dass es so lange Integer auch für C++ geben soll. Ich weiß aber leider nicht wie. Hat jemand einen Tip?

    0
  • B

    long long double

    0
  • C

    pythonfan schrieb:

    Ich habe gehört, dass es so lange Integer auch für C++ geben soll. Ich weiß aber leider nicht wie. Hat jemand einen Tip?

    Die Standardlib bietet keine fertigen langen integer. Solange es nicht superschnell sein soll, genuegt aber zum Beispiel so eine Loesung:

    #include <vector>
#include <iostream>
using namespace std;

typedef int int_t; // needs to be signed
typedef vector<int_t> Bignum;
const int_t BASE = 10;

ostream& operator<<(ostream& out, const Bignum& a) {
  size_t i = a.size();
  while(i && !a[i - 1]) --i;
  while(i--)
    out << a[i];
  return out;
}

void normalize(Bignum& a) {
  int_t c = 0;
  for(size_t i = 0; i < a.size(); ++i) {
    int_t t = a[i] + c;
    a[i]    = t % BASE;
    c       = t / BASE;
  }
  for(; c > 0; c /= BASE)
    a.push_back(c % BASE);
}

Bignum fac(int_t n) {
  Bignum sol(1, 1);
  for(; n; normalize(sol), --n)
    for(size_t i = 0; i < sol.size(); ++i)
      sol[i] *= n;
  return sol;
}

int main() {
  while(1) {
    int_t n;
    cin >> n;
    cout << fac(n) << endl;
  }
}

    Fakultaet von 1000 ist damit kein Problem.

    Wenn es schneller sein soll, nimmt man wahrscheinlich besser etwas fertiges wie GMP. Allerdings ist deren Implementierung natuerlich viel laenger als die 42 Zeilen, die der Code oben in Anspruch nimmt.

    0
  • W

    BorisDieKlinge schrieb:

    long long double

    .. gibt's das? und wenn schon, selbst 'long double' ist bei Microsoft VC8 (und kleiner nehme ich an) auch nur ein double.

    Wenn man den Datentyp flexibel halten will, sollte man zunächst die Algorithmen anpassen. Sowohl für die Berechnung der Fakultät ...

    template< typename T >
T fac( int x )
{
    T erg(1);
    for( ; x > 1; --x )
        erg *= x;
    return erg;
}

    ... als auch für die Berechnung der Näherung nach der Stirlingformel.

    #include <cmath>

namespace math
{
    const double pi = std::acos( -1.0 );
    const double e = std::exp( 1.0 );
}
// ---  berechnet n! nach der Näherungsformel von Stirling
template< typename T >
T fac_stirling( int n )
{
    using std::pow;     // überlasse dem Compiler, welches pow&sqrt er nimmt
    using std::sqrt;
    const T x( n );
    return sqrt( 2 * math::pi * x ) * pow( x / math::e, n );  // <- das ist math :: pi!
}

    Mit int als Datentyp ist schon bei weniger als 20! Schluss und auch double (oder long double ) trägt nur bis 170! (Bem.: bei 32bit und double 8Byte). Für wirklich große Zahlen muss man das T mit etwas anderem ersetzen.

    Statt eines BigInt (ewig lange Zahlenkolonnen!) oder eines BigDouble bietet es sich an, einfach den Logarithmus einer Zahl statt der Zahl selbst zu nutzen. Dann reicht intern auch ein double!

    Mit Hilfe der boost.operators reduziert sich der redundante Code und raus kommt:

    #include <boost/operators.hpp>
#include <boost/io/ios_state.hpp>
#include <cmath>
#include <iostream>
#include <iomanip>

class Log10 : public
    boost::multiplicative< Log10,
    boost::multiplicative2< Log10, double
    > >
{
public:
    Log10( double x ) : m_lgx( std::log10( x ) ) {}

    // --   Operatoren '*' und '/' auch in Kombination mit double
    Log10& operator*=( const Log10& b )
    {
        m_lgx += b.m_lgx;  // aus Multiplikation wird Addition
        return *this;
    }
    Log10& operator*=( double b )
    {
        m_lgx += std::log10( b );
        return *this;
    }
    Log10& operator/=( const Log10& b )
    {
        m_lgx -= b.m_lgx;  // aus Division wird Subtraktion
        return *this;
    }
    Log10& operator/=( double b )
    {
        m_lgx -= std::log10( b );
        return *this;
    }
    friend Log10 operator/( double a, Log10 b )
    {
        b.m_lgx = std::log10( a ) - b.m_lgx;
        return b;
    }

    // --   freie Funktionen
    friend Log10 pow( Log10 x, double ex )
    {
        x.m_lgx *= ex; // aus Potenzieren wird Multiplizieren
        return x;
    }
    friend Log10 sqrt( Log10 x )
    {
        x.m_lgx /= 2;
        return x;
    }

    // --   Ausgabe
    template< typename E, typename Traits > friend
        std::basic_ostream< E, Traits >& operator<<( std::basic_ostream< E, Traits >& out, Log10 x )
    {
        const double ex = std::floor( x.m_lgx );
        if( out.flags() & std::ios_base::scientific || std::abs( ex ) > 5 )
        {
            out << std::pow( 10.0, x.m_lgx - ex ) 
                << out.widen( out.flags() & std::ios_base::uppercase? 'E': 'e' );
            if( x.m_lgx >= 0.0  &&  (out.flags() & std::ios_base::showbase) == 0 )
                out << out.widen('+');
            boost::io::ios_flags_saver ifs( out );
            boost::io::ios_precision_saver ips( out, 0 );
            boost::io::basic_ios_fill_saver< E, Traits > iflls( out, out.widen('0') );
            return out << std::fixed << std::setw( 3 ) << ex;
        }
        return out << std::pow( 10.0, x.m_lgx );
    }

private:
    // --   Members
    double m_lgx;
};

    und schon ist auch die Fakultät von einer Million kein Problem mehr. Mit folgendem kleinen Programm

    int main()
{
    using namespace std;
    int N = 1000000;
    cout << N << "!= " << fac< Log10 >( N ) << endl;
    cout << N << "!= " << fac_stirling< Log10 >( N ) << "  nach Stirling" << endl;
    return 0;
}

    .. erhält man als Ausgabe

    1000000!= 8.26393e+5565708
1000000!= 8.26393e+5565708  nach Stirling

    Gruß
    Werner

    0
Anmelden zum Antworten