Diese Seite ist unverschlüsselt! Um sicherzustellen, das Ihr Passwort nicht ausgelesen werden kann, sollten Sie auf die verschlüsselte Seite wechseln!

    Herzlich Willkommen, lieber Gast!
  Sie befinden sich hier:

  Forum » C / C++ (ANSI-Standard) » n-Damenproblem (Aufgabe)
Forum | Hilfe | Team | Links | Impressum | > Suche < | Mitglieder | Registrieren | Einloggen
  Quicklinks: MSDN-Online || STL || clib Reference Grundlagen || Literatur || E-Books || Zubehör || > F.A.Q. < || Downloads   

Autor Thread - Seiten: > 1 < [ 2 ] [ 3 ]
000
03.01.2009, 21:57 Uhr
~loser
Gast


hallo,

auch wenn es einigen widerstrebt, hier kurz und knackig:
ich krieg die aufgabe nicht gelöst, und habe mittlerweile echt keine lust mehr, da sie mir schon die ganzen weihnachtsferien verdorben hatte und ich jeden abend nur davorhocken kann und nicht weiterkomm.

will mir jemand helfen?

Das Damenproblem
Auf einem Schachbrett mit n2 Feldern (n >= 4) sollen n Damen so plaziert werden, dass keine Dame eine andere schlagen kann. Im Schachspiel können Damen waagerecht, senkrecht oder diagonal jeweils beliebig weit schlagen.
Das Programm soll einen Backtracking-Algorithmus verwenden: Es wird jeweils eine Dame in
die erste Zeile der nächsten freien Spalte gesetzt und überprüft, ob diese Dame eine andere
schlagen kann. Wenn nicht, wird die nächste Dame in die nächste Spalte gesetzt und wieder
geprüft. Sollte die zuletzt gesetzte Dame jedoch geschlagen werden können, dann wird sie eine Zeile tiefer gesetzt. Wenn sie schon in der untersten Zeile steht, dann wird sie entfernt und die Dame in der Spalte davor eine Zeile tiefer gesetzt. Wenn die n-te Dame gesetzt ist und diese keine andere schlagen kann, ist eine Lösung gefunden.
Diese Art der Lösungssuche kann rekursiv durch eine Funktion Versuch programmiert werden,
die jeweils eine Dame setzt und sich dann selbst wieder aufruft.
Schreiben Sie eine Funktion Versuch, die jeweils eine Dame in die nächste freie Spalte setzt
und überprüft, ob sie sicher ist. Außerdem ist natürlich ein kurzes Hauptprogramm zu schreiben, das die Funktion Versuch geeignet aufruft. Geben Sie das Ergebnis am Bildschirm aus!
Schreiben Sie das Programm so, daß der benötigte Speicher für das Schachbrett dynamisch
allokiert wird. Lesen Sie zu Beginn des Programms die Größe des Schachbretts ein. Versuchen Sie n = 6; 7; 8; 9! Geben Sie allen allokierten Speicherplatz vor Verlassen des Programmes wieder frei!
Wieviele verschiedene Lösungen können Sie finden?
 
Profil || Private Message || Suche Download || Zitatantwort || Editieren || Löschen || IP
001
03.01.2009, 22:03 Uhr
Hans
Library Walker
(Operator)


Hi,

Zitat von ~loser:
auch wenn es einigen widerstrebt, hier kurz und knackig:
ich krieg die aufgabe nicht gelöst, und habe mittlerweile echt keine lust mehr, da sie mir schon die ganzen weihnachtsferien verdorben hatte und ich jeden abend nur davorhocken kann und nicht weiterkomm.

will mir jemand helfen?

das klingt so, als ob Du Dich damit beschäftigt hast, aber nicht weiter kommst. Also zeig uns, was Du bisher zustande gebracht hast, und wo es hakt. (Verständnissprobleme, Fehlermeldungen, etc.) Dann sind wir auch bereit, zu helfen. Alles andere wäre nur Vorsagen, und das machen wir nicht.

Hans
--
Man muss nicht alles wissen, aber man sollte wissen, wo es steht. Zum Beispiel hier: Nachdenkseiten oder Infoportal Globalisierung.
 
Profil || Private Message || Suche Download || Zitatantwort || Editieren || Löschen || IP
002
03.01.2009, 22:17 Uhr
FloSoft
Medialer Over-Flow
(Administrator)


Ansonsten ist das Problem an sich nicht soo trivial, da gibts sogar ein BOINC-Projekt zu, die sind erst bei n = 26 (da sieht man mal wie das exponentiell ansteigt das die dann relativ schnell riesige ressourcen brauchen )

Ansonsten: Hausaufgaben immer nur mit Ansatz und konkrete Fragen
--
class God : public ChuckNorris { };
Dieser Post wurde am 03.01.2009 um 22:17 Uhr von FloSoft editiert.
 
Profil || Private Message || Suche Download || Zitatantwort || Editieren || Löschen || IP
003
03.01.2009, 22:45 Uhr
loser



 zunächst habe ich die dame einfach gesetzt, indem ich das feld dann "1" nenne und die überprüfung durchgeführt, indem ich alle felder links der jeweiligen spalte, die in der gleichen zeile oder auf einer der diagonalen zu dem feld liegen, mit eins multipliziere und addiere, sodass das ergebnis stets geringer eins sein muss, wenn die dame nicht geschlagen werden kann. das konnte ich aber nur für beschränkte felder und nicht solche der dimension n realisieren. also habe ich zusätzliche felder eingefügt, die immer die summe der elemente in einer zeiler und auf den diagonalen berechnen sollen, die dann kleiner eins sein muss, aber auch hier gelang die umsetzung für 2 * n diagonalen nicht, also wenn das n variabel und nicht konkret ist.

ich habe viele quellen durchforstet (google/wikipedia in deutsch und englisch ca. die ersten drei seiten der suchergebnisse bzw alle verweise) und der algorithmus ist mir auch klar, aber ich kann es einfach nicht umsetzen, da ich erst seit kurzem programmiere.
 
Profil || Private Message || Suche Download || Zitatantwort || Editieren || Löschen || IP
004
03.01.2009, 22:47 Uhr
loser



 der bis jetzt entstandene quelltext ist einfach nur das drum herum...

ich kann den algorithmus einfach nicht umsetzen :(

zuerst habe ich es natürlich alleine versucht, und bin dann immer wieder auf neue probleme gestoßen (siehe oben), aber auch das einfache konvertieren der anleitung des algorithmus will mir nicht gelingen.


C++:
#include <iostream>
using namespace std;

void Versuch(int n, int **A)
{

???

}

int main()
{

int i, j, n=0;

cin >> n;

int **A = new int*[n];
for(i=0; i<n; i++) A[i]=new int[n];

for(i=0; i<n; i++) for(j=0; j<n; j++) A[i][j]=0;

Versuch(n, A);

cout << endl;
for(i=0; i<n; i++) {for(j=0; j<n; j++) cout << A[i][j] << " "; cout << endl << endl;}

for(i=0; i<n; i++) delete[] A[i]; delete[] A;

cout << endl;
system("PAUSE");
return 0;
}
Dieser Post wurde am 04.01.2009 um 10:28 Uhr von FloSoft editiert.
 
Profil || Private Message || Suche Download || Zitatantwort || Editieren || Löschen || IP
005
04.01.2009, 09:37 Uhr
Oliver
S2-Pixelgeneral


Naja der grundlegende Prinzip, dass du alle Spalten durchgehst, steht ja schon da.

Als Denkansatz:
Nun musst dir überlegen, wie du überprüfst, ob in der jeweils nächsten Spalte irgendein Feld bedroht ist. Dazu würde ich nicht alle Felder sperren/entsperren, weil wenn du rekursiv wieder zurückspringst und zwnagsläufig wieder entsperren musst, kann es passieren, dass 2 Damen ein Feld gesperrt haben, du müssest also zählen wieviele das waren.

Einfacher wäre es, jeweils eine bestimmte Spalte / Zeile / Diagonale 1 / Diagonale 2 zu sperren (d.h. einfach ein bool-Array für alle Spalten etc.) und dann jeweils zu prüfen, ob diese oder jene Spalte, Zeile, Diagonale beim Setzen einer neuen Damen noch frei ist. Dazu musst du dir überlegen, wie man von einem Punkt x;y (wo die Dame gesetzt wird) auf dem Schachbrett die dazugehörige Spalte... etc. ermittelt. Bei den ersten beiden ist das ja noch einfach, bei den Diagonalen dann ggf. schon ein bisschen schwieriger.
--
Demokratie ist die Diktatur der Mehrheit.

www.siedler25.org/ ( Siedler2 - Remake )
 
Profil || Private Message || Suche Download || Zitatantwort || Editieren || Löschen || IP
006
05.01.2009, 13:37 Uhr
kronos
Quotenfisch
(Operator)



Zitat:
Schreiben Sie das Programm so, daß der benötigte Speicher für das Schachbrett dynamisch
allokiert wird.

Diesen Abschnitt würde ich ignorieren, einen Schachbrett-Array zu verwenden ist hier vollkommen unsinnig. Sinnvoller ist eine Liste von Damen-Koordinaten und eine Methode, die überprüft ob zwei dieser Damen sich bedrohen.
Noch ein Hinweis: ich würde Versuch true oder false zurückgeben lassen. false, wenn die jeweilige Dame auf keines der Felder gesetzt werden konnte. true, wenn die n-te Dame gesetzt wurde, bzw. der rekursive Versuch-Aufrufe true zurückgab.
--
main($)??<-$<='?'>>2?main($-!!putchar(
(("$;99M?GD??(??/x0d??/a:???;a"+'?'/4)
??($??)+'?'/3-2-1+$%2)??''?')):'?';??>
 
Profil || Private Message || Suche Download || Zitatantwort || Editieren || Löschen || IP
007
05.01.2009, 14:46 Uhr
virtual
Sexiest Bit alive
(Operator)


www.fun-soft.de/showtopic.php?threadid=5916
--
Gruß, virtual
Quote of the Month
Ich eß' nur was ein Gesicht hat (Creme 21)
 
Profil || Private Message || Suche Download || Zitatantwort || Editieren || Löschen || IP
008
08.01.2009, 10:31 Uhr
~Justin Sayne
Gast



Zitat von kronos:
Diesen Abschnitt würde ich ignorieren, einen Schachbrett-Array zu verwenden ist hier vollkommen unsinnig. Sinnvoller ist eine Liste von Damen-Koordinaten und eine Methode, die überprüft ob zwei dieser Damen sich bedrohen.


Warum denn? Ist die Listenmethode so viel schneller?
 
Profil || Private Message || Suche Download || Zitatantwort || Editieren || Löschen || IP
009
08.01.2009, 11:09 Uhr
virtual
Sexiest Bit alive
(Operator)


Ich würde nicht alles auf die Goldwaage legen, was man im Internet liest.
Selbstverständlich ist die Listenlösung genauso unsinnig wie die Array-Lösung ;-)
--
Gruß, virtual
Quote of the Month
Ich eß' nur was ein Gesicht hat (Creme 21)
 
Profil || Private Message || Suche Download || Zitatantwort || Editieren || Löschen || IP
Seiten: > 1 < [ 2 ] [ 3 ]     [ C / C++ (ANSI-Standard) ]  


ThWBoard 2.73 FloSoft-Edition
© by Paul Baecher & Felix Gonschorek (www.thwboard.de)

Anpassungen des Forums
© by Flo-Soft (www.flo-soft.de)

Sie sind Besucher: