Frage zu Datentyp



  • Hallo,

    ich habe eine kleines Programm zur Berechnung des Binomialkoeffizienten geschrieben ( n!/k!*((n-k)!) )-

    Natürlich kommte es mit k! und n! zu hohen Werten, ich habe den Datentyp double verwendet, der mit aber eben bei höheren Werten nichts mehr vernünftiges Ausgibt... das Gleiche bei long.

    Kann mir wer sagen was ich da falsch mache?

    Danke & Lg



  • Beide Typen sind halt trotzdem noch begrenzt.



  • rechne doch für 20 über 5 einfach

    20/1*19/2*18/3*17/4*16/5

    dann haste nur recht kleine zwischenergebnisse.

    außerdem berechne nicht aus versehen 20 über 15, sondern if(k>n-k) k=n-k



  • Ich vermute, dass einfach soetwas gemacht hast:

    int BionomCoeff(int iN, 
                    int iK)
    {
        return (fac(iN) / (fac(iK) * fac(iN - iK)));
    }
    

    Das is naheliegend, aber ein klassisches Beispiel, wo man eben nicht direkt aus der mathematischen Formel in Code uebersetzen soll. Eine bessere Herangehensweise hier (wenn auch in Pascal):

    http://www.csc.liv.ac.uk/~ped/teachadmin/algor/dyprog.html

    (Es geht bei der Seite eigentlich um etwas anderes, aber man hat den Binomialkoeffizienten als Beispiel gewaehlt.



  • hartmut1164 schrieb:

    Eine bessere Herangehensweise hier (wenn auch in Pascal):

    ähm. hast du meine schleife gesehen?
    ich weiß nicht sicher, weshalb du da jetzt so ein monster vorschlägst.



  • volkard schrieb:

    hartmut1164 schrieb:

    Eine bessere Herangehensweise hier (wenn auch in Pascal):

    ähm. hast du meine schleife gesehen?
    ich weiß nicht sicher, weshalb du da jetzt so ein monster vorschlägst.

    Ja ich habe sie gesehen - aber bei Deiner Schleife muss von einem int-Datentyp in ein real/float-Datentyp konveriert werden, d.h. das Ergebnis ist nicht notwendigerweise ein sauberer int.

    Genau genommen ist auch kein so grosses Monster - die "eigentliche Arbeit" wird in einem Fuenfzeiler gemacht, der Rest ist "nur" die Aufarbeitung der Daten fuer eine recursive Abarbeitung.

    Ich habe schon "Monsterhafteres" geschrieben.



  • hartmut1164 schrieb:

    Ja ich habe sie gesehen - aber bei Deiner Schleife muss von einem int-Datentyp in ein real/float-Datentyp konveriert werden, d.h. das Ergebnis ist nicht notwendigerweise ein sauberer int.

    hä?

    //ungetestet
    unsigned result=1;
    for(unsigned int i=0;i<k;++i){
       result*=n-i; // *20 *19 *18 *17 *16
       result/=k+1; // /1 /2 /3 /4 /5
    }
    

    wo versteckt sich da ein float? also ich sehe keinen.



  • //ungetestet
    unsigned result=1;
    for(unsigned int i=0;i<k;++i){
       result*=n-i; // *20 *19 *18 *17 *16
       result/=k+1; // /1 /2 /3 /4 /5
    }
    

    ist offenbar falsch:

    3 über 1 sind:
    3! / (2!*1!) = 3*2 / 2*1 = 3

    n = 3
    k = 1
    
    result=1;
    //i == 0
    result = 1* (3-0) = 3
    result = 3/ (1+1) = 3/2 = 1
    //i == 1
    //i<k -> 1<1 -> false -> break
    
    result = 1
    

    also ersetzen wir die 1 durch nen i:

    //ungetestet
    unsigned result=1;
    for(unsigned int i=0;i<k;++i){
       result*=n-i; // *20 *19 *18 *17 *16
       result/=k+i; // /1 /2 /3 /4 /5
    }
    
    n = 3
    k = 1
    
    result=1;
    //i == 0
    result = 1* (3-0) = 3
    result = 3/ (1+0) = 3/1 = 3
    //i == 1
    //i<k -> 1<1 -> false -> break
    
    result = 1
    

    allerdings wäre jetzt noch zu zeigen, ob die division immer so gut klappt oder es auch passieren kann, dass der rest iwo wegfällt...

    5 über 3 = 5! / ( 3!*2!) = 5*4*3*2*1 / 3*2*1*2*1 = 5*4*3*2 / 3*2*2 = 20/2 = 10

    n = 5
    k = 3
    
    result=1;
    //i == 0
    result = 1* (5-0) = 5
    result = 5/ (3+0) = 5/3 = 1
    //i == 1
    result = 1* (5-1) = 4
    result = 4/ (3+1) = 4/4 = 1
    //i == 2
    result = 1* (5-2) = 3
    result = 3/ (3+2) = 3/5
    //i<k -> 3<3 -> false -> break
    
    result = 0
    

    hmm... offenbar stimmts noch immer nich... ^^
    naja - vrmtl sollte es result /= i+1 heißen - aber hab jz nich so die lust, es noch mal zu testen und nen compiler hab ich gerad nich zur hand 😣

    bb



  • Wenn wir die recursive Defintion nehmen kommen wir zu dieser kl. Funktion:

    int BioCof (int i_n,
                int i_k)
    {
            if ((i_k == 0) || (i_n == i_k))
                    return 1;
            else
                    return (BioCof (i_n - 1, i_k - 1) + BioCof (i_n - 1, i_k));
    }
    


  • hartmut1164 schrieb:

    Wenn wir die recursive Defintion nehmen kommen wir zu dieser kl. Funktion:

    int BioCof (int i_n,
                int i_k)
    {
            if ((i_k == 0) || (i_n == i_k))
                    return 1;
            else
                    return (BioCof (i_n - 1, i_k - 1) + BioCof (i_n - 1, i_k));
    }
    

    bitte gib auch die laufzeit an oder mach ironie-tags.
    und schreib rekursiv am besten mit k.



  • volkard schrieb:

    hartmut1164 schrieb:

    Wenn wir die recursive Defintion nehmen kommen wir zu dieser kl. Funktion:

    int BioCof (int i_n,
                int i_k)
    {
            if ((i_k == 0) || (i_n == i_k))
                    return 1;
            else
                    return (BioCof (i_n - 1, i_k - 1) + BioCof (i_n - 1, i_k));
    }
    

    bitte gib auch die laufzeit an oder mach ironie-tags.
    und schreib rekursiv am besten mit k.

    Was ich in der Realitaet machen wuerde, waere z.B. das in ein Classe kapseln und z.B. einer Vektorklasse schon berechnete Ergebnisse speichern und dann wieder auf diese zurueckgreifen. Das saehe dann etwa so aus (was so etwa in im dem o.a. Link vorgeschlagen wird):

    int BioCof::Calcu (int i_n,
                       int i_k)
    {
        if (SearchResult (i_n, i_k) == true)
            return GetResult ();
        else if ((i_k == 0) || (i_n == i_k))
            return 1;
        else
            return (AddNewResult (i_n, i_k, BioCof (i_n - 1, i_k - 1) + BioCof (i_n - 1, i_k));
    }
    

    Dadurch braucht jedes Ergebis waerend der Lebenszeit der Klasse nur einmal berechnet zu werden. Man koennte die Klasse sogar einen Datenfile schreiben lassen, den sie beim ersten Aufruf einliesst und entsprechend ergaenzt.



  • hasenhirn.



  • dumfug



  • so was hier könnte man dann immernoch später machen:
    if (SearchResult (i_n, i_k) == true) return GetResult (i_n, i_k);
    aber es bleibt eben dabei:
    um die Fakultät zu berechnen, reicht ein unsigned int eben schon bei 13 nicht mehr aus - und das ist glaube ich nicht, was wir wollen ^^
    es geht um den algorithmus zur berechnung und nicht um einen container zum speichern oder so...

    unsigned int binomial_koeffizient(unsigned int n, unsigned int k)
    {
    	if (!k)
    		return n;
    
    	if (n == k)
    		return n;
    
    	while (n < k)
    		n -= k;
    
    	if (k > n/2)
    		k = n-k;
    
    	unsigned int R=1;
    	for (unsigned int i=k+1, e(n+1); i < e; ++i)
    		R *= i;
    
    	for (unsigned int i=2, e(n-k+1); i < e; ++i)
    		R /= i;
    
    	return R;
    }
    

    am besten wäre es jetzt natürlich wieder, wenn wir das mit dem multiplizieren und dividieren abwechseln könnten - allerdings geht es eben nicht so einfach und noch dazu können wir dann nicht mehr garantieren, dass die division richtig funktioniert...

    hübsch ist es noch immer nicht, aber ich seh nicht mehr viel, was man eleganter machen könnte...

    gibt genau eine zeile, die man evtl noch optimieren könnte (die initialisierung von R und dafür einen schleifendurchlauf weniger) - aber das wird der compiler vrmtl scho selbst machen und außerdem bringt es ja ungefähr gar nix... ^^

    bb



  • unskilled schrieb:

    naja - vrmtl sollte es result /= i+1 heißen

    so ist es.

    unsigned int bf(unsigned int n,unsigned int k){
    	unsigned result=1;
    	for(unsigned int i=0;i<k;++i){
    		result*=n-i; // *20 *19 *18 *17 *16
    		result/=i+1; // /1 /2 /3 /4 /5
    	}
    	return result;
    }
    
    int main()
    {
    	cout<<bf(20,7)<<'\n';
        return 0;
    }
    

    gibt 77520 aus, das sagt auch der taschenrechner.



  • unskilled schrieb:

    am besten wäre es jetzt natürlich wieder, wenn wir das mit dem multiplizieren und dividieren abwechseln könnten - allerdings geht es eben nicht so einfach und noch dazu können wir dann nicht mehr garantieren, dass die division richtig funktioniert...

    doch, das kann man.
    jede siebente zahl ist durch sieben teilbar. unter sieben aufeinanderfolgenden zahlen ist gewiß eine darunter, die durch sieben teilbar ist. das läßt sich bestimmt zu einem hübschen beweis aufblasen.

    ich mach nen kleineren:
    n über k ist doch immer eine ganze zahl.
    nun sind aber genau die zwischenergebnisse

    20/1
    20/119/2
    20/1*19/2*18/3
    20/1*19/2*18/3
    17/4
    ...
    alles nur die zahlen 20ü0, 20ü1, 20ü2, 20ü3...
    also ist stets in der division kein fehler passiert.



  • unsigned int binomial_koeffizient(unsigned int n, unsigned int k)
    {
    	if (!k)
    		return n;//return 1
    
    	if (n == k)//if k>=n
    		return n;//retuen 1
    
    	while (n < k)//??
    		n -= k;//??
    

    aber egal, darum ging es gar nicht. ich hab gar keine tests gemacht.



  • volkard schrieb:

    unsigned int binomial_koeffizient(unsigned int n, unsigned int k)
    {
    	if (!k)
    		return n;//return 1
    
    	if (n == k)//if k>=n
    		return n;//retuen 1
    
    	while (n < k)//??
    		n -= k;//??
    

    aber egal, darum ging es gar nicht. ich hab gar keine tests gemacht.

    jopp - das erste beide stimmt natürlich 😣

    die schleife ist vrmtl schlicht falsch - iwie hab ich da was von wegen symmetrie in erinnerung gehabt, was es aber irgendwie nicht gibt 😃 also ich habs zumindest nicht auf die schnelle gefunden 😃

    von wegen * mit / abwechseln: hmm, ok... klingt gut 🤡

    bb



  • Ich denke eine Moeglichkeit waere auch das Pascalsche Dreieck auszurechenen (jeweils nur Haelfte):

    int GetWideTriangle (int  i_n)
    {
            if ((i_n % 2) == 0)
                    return i_n / 2;
            else
                    return (i_n + 1) / 2;
    }
    
    int *AllocFill (int   iHalfTriangle)
    {
            int  *aReturn;
    
            aReturn = calloc (iHalfTriangle, sizeof (int));
    
            for (int iLoop = 0, iLoop < iHalfTriangle, iLoop++)
                    aReturn [iLoop] = 1;
    
            return aReturn;
    }
    
    void RunPascal (int    *aLine,
                    int     iRow)
    
    {
            for (int iCol = 0, iCol < GetWideTriangle (iRow), iCol++)
            {
                    iReminder = aLine [iCol];
                    aLine [iCol] = aLine [iCol + 1] + iReminder;
            }
    }
    
    int BioCof (int  i_n
                int  i_k)
    {
            int    *aLine;
                    iReturn;
    
            aLine = AllocFill (GetWideTriangle (i_n));
    
            for (int iRow = 0, iRow < i_n, iRow++)
                    RunPascal (aLine, iRow);
    
            if (i_k > i_n / 2)
                    iReturn = aLine [i_n - i_k];
            else
                    iReturn = aLine [i_k];
    
            free (aLine);
    
            return iReturn;
    }
    


  • hartmut1164 schrieb:

    int GetWideTriangle (int  i_n)
    {
            if ((i_n % 2) == 0)
                    return i_n / 2;
            else
                    return (i_n + 1) / 2;
    }
    
    int GetWideTriangle (int  i_n)
    {
            return (i_n + 1) / 2;
    }
    

    bei dir ist nett, daß das ergebnis sogar immer richtig ist, wenn es in einen int paßt, also gar kein überlauf zwischendrin ist.


Anmelden zum Antworten