Programm funktioniert für n = 20, aber für n = 50 nicht!


  • Mod

    Wenn ich das recht sehe, ist das Programm an sich fehlerfrei. Es läuft bloß furchtbar lang, da der Algorithmus ungünstig gewählt ist.

    Auch werden die Zwischenergebnisse bei diesen Werten irgendwann überlaufen, was aber keine Auswirkung auf die Laufzeit hat. Diese ist in jedem Fall ungeheuer groß.

    Effiziente Algorithmen (noch dazu ohne Probleme bezüglich der Zwischenergebnisse) zum Berechnen des Binomialkoeffizienten findest du auf Wikipedia oder in zahlreichen Threads hier im Forum. Beispielsweise dieser, der erst wenige Tage alt ist und sogar "Binomialkoeffizient" heißt:
    https://www.c-plusplus.net/forum/333411
    https://www.c-plusplus.net/forum/p2458666#2458666

    Das ist auch etwas, was man mit nur geringer Eigeninitiative selber hätte finden können.



  • Sehe ich das richtig dass binom in O(2a-b) läuft? 😮
    Dabei sieht das Ding auf den 1. Blick so harmlos aus. 🤡


  • Mod

    hustbaer schrieb:

    Sehe ich das richtig dass binom in O(2a-b) läuft? 😮
    Dabei sieht das Ding auf den 1. Blick so harmlos aus. 🤡

    Beides waren auch genau meine Gedanken, nachdem ich es mir näher angesehen hatte 😃



  • Hallo alle zusammen,

    ich habe jetzt den Binomialkoeffizienten selbst programmiert.
    Mit einer for Schleife. Dürfte ja nicht so schwer sein.
    Aber das Programm funktioniert nicht. Was mach ich falsch?

    #include <stdio.h>
    #include <stdlib.h>
    
    int binom (int a, int b){
        int i;
        int bin = 1;
        for(i=1; i<b+1; i++){
            bin = bin*(a-(i-1))/i;
        }
        return bin;
    }
    

    Als Meldung kommt
    "undefined reference to bin"

    Was habe ich denn diesmal falsch gemacht?


  • Mod



  • Es kommt die Fehlermeldung:
    "cannot open output file C:Users/..."

    Ich hatte zuerst nen Fehler drin, im zweiten Teil den ich nicht hier reinkopiert habe. Aber nach Verbesserung kam trotzdem diese "Fehlermeldung".


  • Mod

    Manchen Leuten kann man einfach nicht helfen.



  • Sorry,
    den letzten Beitrag habe ich geschrieben, ohne deinen zu lesen.
    Habe mich zuerst selbst zitiert etwas geschrieben, dann wieder gelöscht.
    Da ich keinen Account angemeldet habe, konnte ich den vorletzten Beitrag nicht editieren.

    Deswegen der neue Beitrag mit der anderen Fehlermeldung.

    Ich bin jetzt nicht so, dass ich keine Verbesserungsvorschläge annehme und mich nicht bemühe. Nur sind meine Kenntnisse halt schlecht, da alles so lange zurück liegt. Ich weiß z.B. nicht was für ein Fehlertyp das ist, den ich oben geschrieben habe.

    Ich habe die Regeln ja durchgelesen. Aber was bedeutet "Gib von vornherein an, welchen Compiler und welche IDE du benutzt". Welchen Compiler benutze ich denn und welche IDE. Wie finde ich das heraus?

    PS:
    Hatte meinen Accountnamen und PW vergessen, deswegen eher anonym geschrieben. Ich glaube ist jetzt besser mit dem Account zu schreiben, damit ich editieren etc kann.

    Edit:
    Es wäre auch besser einfach meinen Fehler zu sagen, und nicht einen Link zu geben. Ich mein z.B. "Wima du hast nicht angegeben, welchen Compiler du nutzt + Link", wäre für mich auch hilfreicher.



  • wima--09 schrieb:

    Hallo alle zusammen,

    ich habe jetzt den Binomialkoeffizienten selbst programmiert.
    Mit einer for Schleife. Dürfte ja nicht so schwer sein.
    Aber das Programm funktioniert nicht. Was mach ich falsch?

    #include <stdio.h>
    #include <stdlib.h>
    
    int binom (int a, int b){
        int i;
        int bin = 1;
        for(i=1; i<b+1; i++){
            bin = bin*(a-(i-1))/i;
        }
        return bin;
    }
    

    Als Meldung kommt
    "undefined reference to bin"

    Was habe ich denn diesmal falsch gemacht?

    Die meldung bedeutet dass bin undefiniert ist.

    Du musst bin entweder global machen, heißt du setzt ein

    int bin
    

    direkt nach include.

    Oder

    Du deklarierst es separat in der Funktion und der main.


  • Mod

    wima_carsi38 schrieb:

    Edit:
    Es wäre auch besser einfach meinen Fehler zu sagen, und nicht einen Link zu geben. Ich mein z.B. "Wima du hast nicht angegeben, welchen Compiler du nutzt + Link", wäre für mich auch hilfreicher.

    Der Code ist unvollständig und passt nicht zum Fehler. Was meinst du, warum ich sonst einen Link zu einem Beitrag gepostet habe, der erklärt, wie man vollständigen Code mit dazu passenden Fehlermeldungen erstellt? (Dein Problem fällt übrigens in die Kategorie "Linkerfehler")

    essios Analyse würde ich mich übrigens nur halb anschließen. Offensichtlich ist bin irgendwo nicht richtig definiert, aber die richtige Lösung ist sicher nicht, es einfach global zu definieren.



  • Edit siehe nächsten Beitrag



  • Hallo alle zusammen,

    Danke noch einmal für eure Hilfe.

    also ich habe das Programm von vorne geschrieben. Jetzt kommt keine Fehlermeldung.
    Wie gesagt schreibe ich ab jetzt mit dem Account, damit ich editieren kann.
    Das Problem mit "undefined reference to bin", hatte sich geklärt.
    Hat aber i-wie trotzdem nicht funktioniert.

    Jetzt ist das Problem, dass denke ich "int" nicht ausreicht.
    50 über x funktioniert bis x = 7. Ab x = 8 kommen "falsche" Zahlen raus. Ich denke, das liegt an der Speichergröße von "int". Aber "long int" oder auch "float" ändert nichts an der Tatsache.

    Der Code ist hier:

    #include <stdio.h>
    #include <stdlib.h>
    
    int binom (int a, int b){
        int i;
        int bin = 1;
        for(i=1; i<b+1; i++){
            bin = bin*(a-(i-1))/i;
        }
        return bin;
    }
    
    int main()
    {
        int c;
        c = binom(50,8);
        printf("c ist %d",c);
        return 0;
    }
    

    Und Sorry, dass ich als Anfänger viele Fehler auch bei der Problembeschreibung mache! Ich werde mich aber verbessern 🙂


  • Mod

    Manchmal muss es eben long long int sein.



  • SeppJ schrieb:

    essios Analyse würde ich mich übrigens nur halb anschließen. Offensichtlich ist bin irgendwo nicht richtig definiert, aber die richtige Lösung ist sicher nicht, es einfach global zu definieren.

    Damit war eig. die Deklaration gemeint und nicht die Definition.
    Die Definition muss man dann separat machen wie in der Funktion, sieht nämlich so aus als würde die main einen bin Wert bekommen der nur in der Funktion Deklariert ist.

    wima_carsi38 schrieb:

    Hallo alle zusammen,

    Danke noch einmal für eure Hilfe.

    also ich habe das Programm von vorne geschrieben. Jetzt kommt keine Fehlermeldung.
    Wie gesagt schreibe ich ab jetzt mit dem Account, damit ich editieren kann.
    Das Problem mit "undefined reference to bin", hatte sich geklärt.
    Hat aber i-wie trotzdem nicht funktioniert.

    Jetzt ist das Problem, dass denke ich "int" nicht ausreicht.
    50 über x funktioniert bis x = 7. Ab x = 8 kommen "falsche" Zahlen raus. Ich denke, das liegt an der Speichergröße von "int". Aber "long int" oder auch "float" ändert nichts an der Tatsache.

    Der Code ist hier:

    #include <stdio.h>
    #include <stdlib.h>
    
    int binom (int a, int b){
        int i;
        int bin = 1;
        for(i=1; i<b+1; i++){
            bin = bin*(a-(i-1))/i;
        }
        return bin;
    }
    
    int main()
    {
        int c;
        c = binom(50,8);
        printf("c ist %d",c);
        return 0;
    }
    

    Und Sorry, dass ich als Anfänger viele Fehler auch bei der Problembeschreibung mache! Ich werde mich aber verbessern 🙂

    Wenn sich durch double oder long int nichts ändert liegt es nicht an int.

    int main()
    {
        int c;
        c = binom(50,8);
        printf("c ist %d",c);
        return 0;
    }
    

    ....

    #include <stdio.h>
    #include <stdlib.h>
    
    int binom (int a, int b){
        int i;
        int bin = 1;
        for(i=1; i<b+1; i++){
            bin = bin *(a-(i-1))/i;
            printf("bin ist %d\n",bin);
        }
        return bin;
    }
    
    int main()
    {
        int c;
        c = binom(50,8);
        printf("c ist %d",c);
        return 0;
    }
    

    Rauskommt
    bin ist 50
    bin ist 1225
    bin ist 19600
    bin ist 230300
    bin ist 2118760
    bin ist 15890700
    bin ist 99884400
    bin ist 7738
    c ist 7738
    Process returned 0 (0x0) execution time : 0.177 s
    Press any key to continue.


  • Mod

    essio schrieb:

    SeppJ schrieb:

    essios Analyse würde ich mich übrigens nur halb anschließen. Offensichtlich ist bin irgendwo nicht richtig definiert, aber die richtige Lösung ist sicher nicht, es einfach global zu definieren.

    Damit war eig. die Deklaration gemeint und nicht die Definition. Die Definition muss man dann separat machen wie in der Funktion, sieht nämlich so aus als würde die main einen bin Wert bekommen der nur in der Funktion Deklariert ist.

    Und wo ist deiner Meinung nach der Unterschied zwischen einer global deklarierten Variablen und einer global definierten Variablen?

    Wenn sich durch double oder long int nichts ändert liegt es nicht an int.

    Er hat long und float geschrieben, nicht double. Und deine Schlussfolgerung ist falsch. long ist nicht garantiert größer als int. float ist in aller Regel sogar weniger genau als int. Dass deine Schlussfolgerung falsch ist, kannst du ganz leicht ausprobieren, indem du long long benutzt. Dann funktioniert der Code nämlich. long long ist nämlich garantiert 64 Bit lang, long nur mindestens 32. Was aber auch eine typische Größe für int ist. Das heißt, auf vielen Systemen sind int und long gleich genau.



  • SeppJ schrieb:

    essio schrieb:

    SeppJ schrieb:

    essios Analyse würde ich mich übrigens nur halb anschließen. Offensichtlich ist bin irgendwo nicht richtig definiert, aber die richtige Lösung ist sicher nicht, es einfach global zu definieren.

    Damit war eig. die Deklaration gemeint und nicht die Definition. Die Definition muss man dann separat machen wie in der Funktion, sieht nämlich so aus als würde die main einen bin Wert bekommen der nur in der Funktion Deklariert ist.

    Und wo ist deiner Meinung nach der Unterschied zwischen einer global deklarierten Variablen und einer global definierten Variablen?

    War die Deklaration nicht das erstellen eines Speichers für die Variable und Definition die Wertzuweisung?

    Deklaration:

    int bin;

    Definition:

    bin = 1;

    Wenn ich mich irre bedanke ich mich für die Korrektur. Bin selber schließlich nur ein Anfänger 🙂

    Er hat long und float geschrieben, nicht double. Und deine Schlussfolgerung ist falsch. long ist nicht garantiert größer als int. float ist in aller Regel sogar weniger genau als int. Dass deine Schlussfolgerung falsch ist, kannst du ganz leicht ausprobieren, indem du long long benutzt. Dann funktioniert der Code nämlich. long long ist nämlich garantiert 64 Bit lang, long nur mindestens 32. Was aber auch eine typische Größe für int ist. Das heißt, auf vielen Systemen sind int und long gleich genau.

    Du hast recht, verzeihung mein Fehler.

    Ich habe das Ergäbis, nach der double einsetzung, falsch intepretiert.

    long long kannte ich bisher noch nicht. Danke



  • ok hab meinen Fehler auch entdeckt:

    Deklaration

    Mit der Deklaration bennenen wir eine Variable und machen diese dem Compiler bekannt. D.h. der Compiler weiß nun, ob wir uns im Laufe unseres Programms beim Eintippen des Variablennames vertippt haben. Da jeder Variablenname eines Datentyps eindeutig sein muss, kann der Compiler auch den Fehler abfangen, wenn versucht wird, zwei Variablen mit dem gleichen Typ und gleichen Namen zu deklarieren.
    Definition

    Unter der Definition versteht man, dass einer Variablen ein Speicherbereich zugeteilt wird. Der Speicherbereich hat eine eindeutige Adresse und dient dazu, Werte abspeichern zu können. Mit dem Variablennamen sprechen wir im Prinzip nur einen Speicherbereich an. Eine Deklaration ohne Definition werden wir im Kapitel Zeiger kennenlernen.

    http://www.c-howto.de/tutorial-variablen-deklaration.html



  • Nochmal Danke an euch,

    also ich denke die Zahlen sind einfach zu groß. Ich versuch da anscheinend zu viel rauszukitzeln. Ich lasse das Programm jetzt so wie es ist. Kann leider nicht mehr so viel Zeit in das Programm investieren. Ich lass einfach nur Werte für a bis 30 zu am besten...

    50 über 8 ist zum Beispiel eine 9 stellige Zahl
    50 über 25 ist 15 stellige Zahl.

    @essio

    Rauskommt
    bin ist 50
    bin ist 1225
    bin ist 19600
    bin ist 230300
    bin ist 2118760
    bin ist 15890700
    bin ist 99884400
    bin ist 7738
    c ist 7738
    Process returned 0 (0x0) execution time : 0.177 s
    Press any key to continue.

    Warum wird die Zahl plötzlich kleiner? Liegt es an der Größe von "int"?
    Eigentlich muss der Wert ja nach 15890700 noch größer werden



  • Das ist ein Integer-Überlauf, verwende uintmax_t statt int.



  • essio schrieb:

    War die Deklaration nicht das erstellen eines Speichers für die Variable und Definition die Wertzuweisung?

    Deklaration:

    int bin;

    Definition:

    bin = 1;

    Nein.
    Deine "Deklaration" ist auch eine Definition, angenommen, sie steht in einem Block oder Global.
    Das ist eine Deklaration:

    extern int bin;
    

Anmelden zum Antworten