Springerproblem

Hii,
ich Programmiere unter Ubuntu. Habe eines Lösung (Backtracking-Verfahren) für das Springerproblem geschrieben, aber komischerweise funktioniert es nicht für jede Startposition auf z.B. einem 5x5 Brett.
Hier der Code:
Hoffe die Kommentare können es erklären. Bin ein Anfänger und lerne C gerade, also jegliche Kritik ist erwünscht.
Habe ein Programm im Internet gefunden und dort gibt es für z.B. 1/0 eine Lösung aber mit meinem Programm nicht.

#include<stdio.h>
#include<time.h>
#include<stdlib.h>

#define N 5

int brett[N][N];

//Hier wird das Brett gezeichnet
void draw()
{
	int i,j;
	printf("\n");
	for(i=0; i<N; i++)
	{
		for(j=0;j<N; j++)
			printf("%d\t",brett[i][j]);
		printf("\n");
	}
	printf("\n\n");
}

//die rekrusive Fkt. als Eingabparameter die Koordinaten des pferdes und ein Zaehler um die Züge nacheinander aufzuzeigen
int move(int x,int y,int zaehler)
{
	if(zaehler == N*N)//wenn dies der Fall ist dann ist eine Lösung gefunden
	{
 		brett[x][y] = zaehler;
		draw();
		exit(1);
	}
	else if(brett[x][y] == 0)//lösung nicht gefunden
	{
		brett[x][y] = zaehler;
		//printf("<ENTER>"); getchar();			//hier kommentare enfernen, 
		//draw();									//wenn einzelne Schritte man sehen will(nicht zu empfehlen da es recht lange dauert)
		//printf("\n%d\n",zaehler);
		if(brett[x-2][y-1] == 0 && x-2<N && x-2 >= 0 && y-1 <N && y-1>=0 )
			move(x-2,y-1,zaehler+1);
		if(brett[x-2][y+1] == 0 && x-2<N && x-2 >= 0 && y+1 <N && y+1>=0 )
			move(x-2,y+1,zaehler+1);
		if(brett[x-1][y-2] == 0 && x-1<N && x-1 >= 0 && y-2 <N && y-2>=0 )
			move(x-1,y-2,zaehler+1);
		if(brett[x-1][y+2] == 0 && x-1<N && x-1 >= 0 && y+2 <N && y+2>=0 )
			move(x-1,y+2,zaehler+1);
		if(brett[x+1][y-2] == 0 && x+1<N && x+1 >= 0 && y-2 <N && y-2>=0 )
			move(x+1,y-2,zaehler+1);
		if(brett[x+1][y+2] == 0 && x+1<N && x+1 >= 0 && y+2 <N && y+2>=0 )
			move(x+1,y+2,zaehler+1);
		if(brett[x+2][y-1] == 0 && x+2<N && x+2 >= 0 && y-1 <N && y-1>=0 )
			move(x+2,y-1,zaehler+1);
		if(brett[x+2][y+1] == 0 && x+2<N && x+2 >= 0 && y+1 <N && y+1>=0 )
			move(x+2,y+1,zaehler+1);
		brett[x][y] = 0;//wieder null gesetzt also feld nicht benutzt
	}
	return 0;
}

int main()
{
	srand(time(NULL));
	int i,j,zaehler = 1;

	// Hier wird das Feld mit Nullen gefüllt, also die 0 steht für nicht betretenes Feld
	for(i=0; i<N; i++)
	{
		for(j=0; j<N; j++)
			brett[i][j] = 0;
	}
	//Hier startposition ermitteln und der funktion geben
	i=rand()%N;
	j=rand()%N;
	// Hier wird jetzt 0 und 1 als anfangsposition genommen weil es hierfür keine Lösung gibt, ansonsten wird i und j eingesetzt.
	move(0,1,zaehler);//wenn lösung gegeben, dann wird sie ausgegeben und das Programm beendet (siehe Fkt. (exit(1)))
	//wenn keine lösung gefunden, dann werden nur die Koordinaten ausgegeben 
	printf("x=%d und y=%d\n",i,j);
	return 0;

}

Die Bedingungen mit den logischen Operatoren (das && und ||) werden von links nach rechts ausgewertet. Und zwar solange, bis das Ergebnis eindeutig feststeht.

Wenn x = 0 dann steht das Ergebnis bei if(brett[x-2][y-1] == 0 && x-2<N && x-2 >= 0 && y-1 <N && y-1>=0 ) bei dem x-2<N fest.

Da ist der Ausdruck x-2<N falsch und somit der ganze Ausdruck falsch.

Da hast du aber schon das Element/Feld an der Stelle brett[-2][y-1]
Dieses Element existiert aber nicht.

Stell die ganzen Bedingugen um, so dass der Ausdruck mit dem brett[][] ganz rechts ist.

Habe grad eine Lösung von unserer Uni gefunden und dort gibt es für ein 5x5 Feld auch nicht immer eine Lösung. Hab es mit ein paar meiner Wert verglichen und es passt.
Aber wenn ich ein 6x6 Brett nehme dann passt es gut.

Also sicher das da was nicht stimmt?
Es kommt ja immer das richtige raus.

MFG

Gibt es hier keinen Edit Button?
Also jetzt verstehe ich was du meinst, werde ich sofort umstellen, danke dir.
Vllcht noch eine kurze Frage undzwar muss nicht nur eine Lsg. ausgegeben werden, sonder alle die es von der Startposition erlauben und ich frage mich, ob man das noch in meinen Code kriegen würde oder eher nicht?
Weiß nicht wie ich da grad rangehen soll.
Danke
MFG

SeppJ

Aknayirp schrieb:

Gibt es hier keinen Edit Button?

Nur, wenn du dich registrierst. Sonst könnte ja jeder deinen Beitrag ändern.

Bashar

Aknayirp schrieb:

Vllcht noch eine kurze Frage undzwar muss nicht nur eine Lsg. ausgegeben werden, sonder alle die es von der Startposition erlauben und ich frage mich, ob man das noch in meinen Code kriegen würde oder eher nicht?

Statt dem exit ein return, wenn du eine Lösung gefunden hast, sollte es tun. Es sieht übrigens so aus, als sollte move eine void-Funktion sein, der Rückgabewert ist anscheinend sinnlos.

Bashar schrieb:

Aknayirp schrieb:

Vllcht noch eine kurze Frage undzwar muss nicht nur eine Lsg. ausgegeben werden, sonder alle die es von der Startposition erlauben und ich frage mich, ob man das noch in meinen Code kriegen würde oder eher nicht?

Statt dem exit ein return, wenn du eine Lösung gefunden hast, sollte es tun. Es sieht übrigens so aus, als sollte move eine void-Funktion sein, der Rückgabewert ist anscheinend sinnlos.

Also wenn ich jetzt statt dem exit ein return schreibe, dann darf das doch keine void-Funktion sein oder?

Beim exit, wird ja das Programm beendet aber, ich verstehe nicht wieso er, wenn ich jetzt dort ein return habe, das Programm mir alle Lösungen, die von der Anfangsstartposition gegeben sind, ausgibt?
Ich habe es auch schon vertauscht das exit mit dem return und das Programm beendet, nur mit dem Unterschied das die Anweisung in der main unter des Funktionsaufrufes noch ausgeführt werden.
Hoffe du verstehst was ich meine und danke für deine Hilfe.
MFG

Bashar

Aknayirp schrieb:

Also wenn ich jetzt statt dem exit ein return schreibe, dann darf das doch keine void-Funktion sein oder?

Doch. Vielleicht weißt du nicht, dass man void-Funktionen mit return; beenden kann.

Beim exit, wird ja das Programm beendet aber, ich verstehe nicht wieso er, wenn ich jetzt dort ein return habe, das Programm mir alle Lösungen, die von der Anfangsstartposition gegeben sind, ausgibt?

Wenn du auf den Backtracking-Algorithmus schon gekommen bist, wirst du das durch kurzes Nachdenken auch verstehen.

Bashar schrieb:

Aknayirp schrieb:

Also wenn ich jetzt statt dem exit ein return schreibe, dann darf das doch keine void-Funktion sein oder?

Doch. Vielleicht weißt du nicht, dass man void-Funktionen mit return; beenden kann.

Beim exit, wird ja das Programm beendet aber, ich verstehe nicht wieso er, wenn ich jetzt dort ein return habe, das Programm mir alle Lösungen, die von der Anfangsstartposition gegeben sind, ausgibt?

Wenn du auf den Backtracking-Algorithmus schon gekommen bist, wirst du das durch kurzes Nachdenken auch verstehen.

Also das mit der void-Funkion wußte ich nicht, aber tue ich jetzt:D

Also bestimmt ist die Lösung ganz einfach, aber ich komme gerade einfach nicht drauf.
Also meine Überlegungen sind die:
Es geht ja darum, Züge zurück zu nehmen (=0 setzen) und wieder die Fkt. zu starten.
Also wenn beim ersten Mal, wenn die Lösung da ist, muss ich ja z.B. alle Züge zurücknehmen außer die ersten beiden und dann mit diesen neuen Werten, die Fkt starten. Das macht man dann angefangen mit den ersten bis zu den letzten.
Ist der Gedankengang richtig oder total falsch?
Bitte nicht hinschreiben, wie es funktioniert, will selber draufkommen. Frage mich nur, ob das logisch erscheint, was ich meine.
Danke, MFG

Also, was ich grad geschrieben habe, ist der größte Schrott.

Also nur mit dem return; hat es nicht funktioniert, ich musste die letzte Zuweisung von der Zahl erst rückgängig machen und dann funktioniert es. Aber ehrlich gesagt, weiß ich nicht wieso es das tut, weil ich komme ja nach jeder Lösung zum return und das return beendet die Fkt. doch, also wieso gehts dann weiter.
Ich mach morgen weiter.
MFG

Bashar

Aknayirp schrieb:

ich musste die letzte Zuweisung von der Zahl erst rückgängig machen

Oh, ich hatte das vergessen zu erwähnen.

Aber ehrlich gesagt, weiß ich nicht wieso es das tut, weil ich komme ja nach jeder Lösung zum return und das return beendet die Fkt. doch, also wieso gehts dann weiter.

Es ist genauso wie bei dem anderen return. Im Prinzip ist das kein Unterschied: In dem einen Fall kehrst du zurück, weil du eine Lösung gefunden hast; in dem anderen Fall kehrst du zurück, weil an dieser Stelle keine (weitere) Lösung mehr gefunden werden kann.

Danke, für deine Hilfe. Es klappt perfekt. Krass, dass es bei einem 6x6 Brett so viele verschiedene Möglichkeiten gibt.

Ich wußte jetzt nicht direkt, ob ich einen neuen Thread dafür aufmachen soll, weils ja eine andere Frage ist, aber da sie recht kurz ist, frag ich einfach hier.
Also es geht um ein Programm, indem Strings verglichen werden und die Anfangsposition des 1.Strings, wenn er denn ganz enthalten ist im 2.String, soll ausgegeben werden. Natürlich wieder rekursiv. Hab es auch geschaft.
Nur bekomme ich diese Warnungen beim compilieren:

Warnung: Vergleich zwischen Zeiger und Ganzzahl [standardmäßig aktiviert]

Bezogen auf diese Zeilen:
1. if(*str1 == NULL)

2. else if(*str2 == NULL)

3. else if(*str1 != NULL && *str2 != NULL)

Es geht bei diesen Bedingungen nur darum, zu sehen, ist in dem String ein Inhalt drin oder eher nicht. Also das Programm funktioniert so wie es soll.
Ist es falsch? Oder kann ich die Warnungen ignorieren, oder gibt es vllcht eine bessere Bedingung?

MFG

Wenn du den Zeiger vergleichen willst, muss der Dereferenzierungsoperator (der weg.

Wenn du den Inhalt vergleichen willst, schreib 0 (oder '\0') statt NULL.

NULL steht für einen ungültigen Zeiger.

Zeiger prüfen, ob der Zeiger überhaupt gültig ist.
Inhalt prüfen, ob der String zuende ist.

Alles klar, hab ich geändert, funktioniert jetzt ohne Warnungen.
Also das mit der NULL hab ich verstanden.
Der Operater "*", muss da nicht stehen, da der Zeiger durch die 0 selbst überprüft, ob Inhalt vorhanden ist. Ist das richtig so?

Noch eine kurze andere Frage:
Größter Gemeinsame Teiler Fkt. (rekursiv)

Warnung wird ausgegeben: Kontrollfluss erreicht Ende von Nicht-void-Fkt.
Es geht ja darum, dass da ein return fehlt, aber ich weiß nicht welcher Wert am sinvollsten ist, sodass die Fehlermeldung nicht kommt.

unsigned int ggt(unsigned int a, unsigned int b)
{
	printf("a = %d\tb = %d\n",a,b);
	if(b == 0)
		return a;
	else if(a > b)
		ggt(a-b,b);
	else if(a<b)
		ggt(a,b-a);
}

Nochmal zu den Zeigern:

Du musst erstmal überprüfen ob der Zeiger überhaupt gültig ist:

if(str1 == NULL)  
//   ungültiger Zeiger

Bei der verabeitung der Zeichen musst du auch das Ende der Zeichenkette erkennen.
Das Ende wird mit einer '\0' oder 0 gekennzeichnet.
Dazu musst du auf den Inhalt zugreifen.

if(*str1 !=0 && *str2 != 0) // Solange str1 und str2 noch nicht zu Ende sind

Zum ggt:
Deine Funktion gibt einen Wert zurück. Auch die Aufrufe von ggt die du in ggt aufrufst. Deren Wert musst du zurück geben.

Jap, vielen Dank, hab ich verstanden!

Hab mal jetzt "wieder" eine andere Frage:

Ich weiß nicht direkt, wie man, wenn man eine Rekursionsaufgabe bekommt, da am besten vorgeht. Wenn Angaben vorhanden sind, dann klappt es, wie z.B. die Eingabeparameter und worauf man Achten soll.
Aber z.B. habe ich jetzt eine Aufgabe, in der (klingen tut sie einfach)
vom Benutzer eine Zahl 'n' eingegeben wird und man soll die Buchstaben 'a' und 'b' n-mal aneinanderreihen mit den verschiedensten Variationen.

Bsp: n=3, aaa,aab,aba,abb,bbb ,bba ,bab ,bba
Ein Tipp ist gegeben:

Hinweis: Bei einer Lösung mittels einer rekursiven Funktion kann es hilfreich sein, einen
String-Parameter zum Zwischenspeichern von Teilwörtern zu verwenden.

Also meine Frage erst, wie man Rekursionsaufgaben am besten löst. Vllcht kann man das an der Aufgabe zeigen.
Bitte nicht die Lösung, sondern eher die Gedanken, mit der man so eine Aufgabe lösen kann.
Danke im Vorraus

MFG
Aknayirp

SeppJ

Das Grundgerüst der meisten Rekursionen ist, dass man folgendes braucht:
1. Eine Abbruchbedingung. Hier: Tiefe n erreicht
2. Irgendetwas, um Informationen an tiefere Ebenen weiter zu reichen, damit diese wissen, was sie überhaupt machen sollen. Zu diesen Informationen zählt:
-Das, woraus sich die Abbruchbedingung ergibt (Hier: Ein Zähler für die Tiefe)
-Eventuelle Nutzdaten (Hier: Ein String mit den vorherigen Ergebnissen)
-Informationen darüber, was überhaupt zu tun ist (Hier: 'a' oder 'b' anhängen)
Es kann gut sein, dass ein oder mehr dieser Informationen identisch sind. Aber irgendetwas ist auf jeden Fall da.
3. Eine Funktion, die 1. und 2. verbindet, also die Informationen entgegen nimmt, die Abbruchbedingung prüft, aufgrund der Informationen handelt und dann wieder sich selbst mit den geänderten Parametern aufruft (in der Regel mehrmals, wenn die Rekursion nicht eine unnötig komplizierte Umschreibung einer einfachen Schleife ist).

Die Aufgabe hier ist fies, da Strings in C nicht einfach so kopiert werden können. Du musst dir etwas einfallen lassen, wie du an die tieferen Instanzen echte Kopien weitergeben kannst, nicht einfach nur Zeiger auf immer die gleiche Zeichenkette. Das macht die Aufgabe besonders kompliziert. Tipp: Versuch vielleicht erst einmal mit Zahlen zu rechnen, also 111 112 121 122 usw. auszugeben.

Hey Seppj,

ich versuche dies mal zu verinnerlichen.
Die Idee es erst mit 1 und 2 zu versuchen, finde ich gut. Werde ich erst so machen. Danke dir.

MFG

Hallo, da bin ich wieder:D

Hab eine Frage zu einer Aufgabe.
Zahlen von der Kommandozeile sollen addiert werden.
Problem ist, die Zahlen werden bei mir als Zeichen abgespeichert und deshalb kriege ich es einfach nicht hin, sie aufzuaddieren.
Das war halt mein Ergebnis. Klappt, aber leider so nicht.
Wenn ich jetzt 3 4 eingebe kommt da 103 und nicht 7 raus.
Dachte vllcht mit einem Cast oder so gehts, aber auch net.

#include<stdio.h>

int main(int argc, char *argv[])
{
	int i,summe = 0;
	for(i=1; i<argc; i++)
	{
		summe = summe + *argv[i];
	}

	printf("Summe: %d\n",summe);
	return 0;
}

MFG

Du suchst die Funktion strtol()
Wenn du nicht weißt wie die aufgerufen wird, kannst du mal bei http://www.cplusplus.com/reference/clibrary/cstdlib/strtol/ schauen.

Wenn du wissen willst, warum das bei dir nicht klappt, dann schau mal in der Wikipedia unter ASCII nach.