Fehler bei einem Greedy Programm



  • Aufgabe 2 c)
    http://www-ai.math.uni-wuppertal.de/SciComp/teaching/ss11/info2/Ueb/blatt5_ss11.pdf
    Hier kann man sich die entsprechenden .txt Dateien runterladen
    http://www-ai.math.uni-wuppertal.de/SciComp/teaching/ss11/info2/Ueb/Blatt5/

    a und b gemacht, verzweifle nur gerade an der c. Ich verstehe die Aufgabe so:
    Hier haben wir eine Liste, bei der ich per Greedy Methode möglichst viele Auftragsmengen finden soll. Diese Liste besteht aus zwei Spalten, linke für den Anfang und die rechte für das Ende der jeweiligen Menge. Man fängt mit der Auftragsmenge 10 : 15 an (erster Eintrag in der Liste) und sucht dann in der linken Spalte nach einem Wert, der gleich oder grösser 15 ist. In diesem Fall ist es der Wert an der 7. Stelle die 19 : 28. Das heisst man hat
    10 : 15
    19 : 28
    Als nächstes sucht man in der linken Spalte nach einer Zahl die größer gleich 28 ist, in diesem Fall 40 41, dann sucht man nach einem Wert grösser gleich 41 usw. usf.. Das habe ich auch als Funktion in dem vorgefertigtem Programm geschrieben, nur leider will das Programm nicht das ausgeben, was ich haben will.
    Theoretisch müsste die Ausgabe diese sein:
    10 15
    19 28
    40 41
    46 48
    49 50
    51 57
    etc.

    Meine ist nur:
    10 15
    19 28
    62 65
    82 83

    Wo liegt der Fehler? Ich rufe das Programm so auf nach dem compilen: a.exe < auftrag100.txt

    #include <stdio.h>
    
    #define N_MAX 1000
    
    typedef int termin[N_MAX];
    void auftrag_greedy(termin s, termin e, int n)
    /*eigenen Code implementieren*/
    {
    	int i;
    	int naechster_auftrag(int x)
    	{
    
    		for (i=0; i < n ; i++)
    		{
    			/*Suche nach dem naechste Auftragsanfang, der groesser/
    			gleich als das Aufrtagsende ist*/
    			if( s[i]>=e[x] )
    			{
    				printf("%u %u\n", s[i], e[i]);
    				x=e[i]; /*Suche mit dem neuem Auftragsende als x
    						gespeichert*/
    
    				naechster_auftrag(x);
    			}
    		}
    	}
    	printf("Die Lösung nach der Greedymethode ist\n");
    	printf("%u %u\n",s[0],e[0]);
    	naechster_auftrag (0); /*Erster Auftrag*/
    
    }
    
    int main(void)
    {
      int i, n;
      termin s, e;
    
      scanf("%d",&n);
      for( i = 0 ; i < n ; i += 1 ){
        scanf("%d",&(s[i]));
        scanf("%d",&(e[i]));
      }
    
      auftrag_greedy(s, e, n);
    
      return 0;
    }
    


  • Du schreibst s[i]>=e[x] und x=e[i]
    Soll x der Index oder der Wert sein?

    Es scheint ja zu funktionieren, aber lokale Funktion (naechster_auftrag() in auftrag_greedy() ) dürften in C nicht gehen:
    http://www.c-plusplus.net/forum/286251
    Oder habe ich etwas verpasst? 😕




  • Soll x der Index oder der Wert sein?

    Man sieht den Wald vor lauter Bäumen nicht mehr 😃 Habe noch eine zweite Variable für den Index hinzugefügt und das Programm klappt jetzt. Ich bedanke mich vielmals.



  • Warum eine 2. Variable?
    Ein x = i; hätte es doch auch getan.



  • Sehe ich das richtig, dass du dort eine Funktion innerhalb einer Funktion angelegt hast?
    Ist doch eigentlich nicht unbedingt erlaubt oder?

    Außerdem hat

    int naechster_auftrag(int x)
    

    gar kein return?



  • It0101 schrieb:

    Außerdem hat

    int naechster_auftrag(int x)
    

    gar kein return?

    deavilaxn schrieb:

    naechster_auftrag (0); /*Erster Auftrag*/
    

    Er will ja auch keinen, wie es aussieht 🤡

    Ich find' eh die "void main()"-Coder am Besten!



  • Pretty schrieb:

    Er will ja auch keinen, wie es aussieht 🤡

    Dann sollte er das auch klar aussagen und die Funktionen als void definieren.


Log in to reply