A26: Acht-Damen-Problem

A26: Acht-Damen-Problem

Beitragvon M.A. » 16.06.2010 20:44

Hier mal meine Lösung. Die Musterlösung macht das mit Klassen, ich nicht (da nicht gefordert und meiner Ansicht nach hier nicht nötig). Mein Quelltext ist auch nur etwa halb so lang.
Ohne Zusatzaufgaben.
Dateianhänge
damen.cpp
ÜB10 A26: Acht-Damen-Problem
(2.4 KiB) 340-mal heruntergeladen
Bild
Benutzeravatar
M.A.
 
Beiträge: 366
Registriert: 25.10.2008 16:37

Re: A26: Acht-Damen-Problem

Beitragvon CommanderTomalak » 16.06.2010 21:06

Häh, wie übergibst du denn dein Ergebnis aus der damen_in_zeile_setzen() in die main-Schleife? Dein damen-Array ist weder by reference aufgerufen noch global o0

Und hier mit Zusatzaufgaben und augenscheinlich etwas anderer Herangehensweise. Aber auch ohne Klassen (macht hier nämlich auch keinen Sinn):

Code: Alles auswählen
/*************************** TASK 26 ***************************/

// Global vars
int size, cnt = 0;
char abruption;

/**
* Task 26
* Allocate n queens on a (n x n) chess board
*/
void task26()
{
    int pos[50];
    for(int i = 0; i < 50; i++) pos[i] = -1; // Initialize with -1
   
    cout << "Which size shall the board have and how many queens do you want me to allocate?" << endl;
    cin >> size;
   
    cout << endl << "Shall I abort after first finding? (y/n)" << endl;
    cin >> abruption;
    cout << endl;
   
    if(size >= 50) { cout << "Too big size!"; return; }
   
    cnt = 0;
   
    tryPosition(pos, 0);
   
    return;
}


/**
* Try recursively all possible combinations of queens until a combination for all n rows is found
*/
bool tryPosition(int pos[50], int row)
{
    for(int i = 0; i < size; i++)
    {
        if(!getsBeaten(pos, row, i))
        {
            pos[row] = i;
           
            if(row == size-1)
            {
                // Output result
                printBoard(pos);
                return true;
            }
           
            else
            {
                if(abruption == 'y')
                {
                    if(tryPosition(pos, row+1))
                        return true;
                }
           
                else tryPosition(pos, row+1);
            }
        }
    }
   
    return false;
}


/**
* Check, if a new set queen gets beaten by any one already set
*/
bool getsBeaten(int pos[50], int row, int col)
{
    for(int i = 0; i < row; i++)
    {
        // Ignore uninitialized values (although this should not happen here, just for safety)
        if(pos[i] == -1) continue;
       
        // In the same column?
        if(pos[i] == col) return true;
       
        // Check positive diagonal
        if(i - pos[i] == row - col) return true;
       
        // Check negative diagonal
        if(i + pos[i] == row + col) return true;
    }
   
    return false;
}


/**
* Print a chess board with positions of the queens on screen
*/
void printBoard(int pos[50])
{
    cout << "Solution " << (++cnt) << endl;
   
    for(int i = 0; i < size; i++)
    {
        cout << "+";
        for(int j = 0; j < size; j++) cout << "-+";
       
        cout << endl << "|";
       
        for(int j = 0; j < size; j++)
        {
            if(pos[i] == j) cout << "X|";
            else cout << " |";
        }
       
        cout << endl;
    }
   
    cout << "+";
    for(int j = 0; j < size; j++) cout << "-+";
   
    cout << endl << endl;
}
"Das Volk hat das Vertrauen der Regierung verscherzt. Wäre es da nicht doch einfacher, die Regierung löste das Volk auf und wählte ein anderes?"
- Bertolt Brecht
CommanderTomalak
 
Beiträge: 204
Registriert: 19.01.2009 00:42
Wohnort: Karlsruhe

Re: A26: Acht-Damen-Problem

Beitragvon M.A. » 17.06.2010 00:20

CommanderTomalak hat geschrieben:Häh, wie übergibst du denn dein Ergebnis aus der damen_in_zeile_setzen() in die main-Schleife? Dein damen-Array ist weder by reference aufgerufen noch global o0

Naja, es funktioniert doch bestens, oder? ;)
So wie ich das verstanden hab, ist ein Array doch lediglich ein Zeiger auf den ersten Wert des Arrays. Wenn ich also mein array damen übergeb, dann übergeb ich ja nur die startadresse des arrays im speicher, und mit damen[1] und damen[2],... damen[x] greif ich auf Startadresse + x*(Größe des Datentyps) zu. und wenn ich dann in meiner funktion das array verändere, so verändere ich immer das original.
Simples Beispiel:
Code: Alles auswählen
#include <iostream>
using namespace std;
void tuwas(int input[]){
     input[0]=5;
     input[1]=6;
     return;
     }
int main(){
    int arr[2];
    arr[0]=0;
    arr[1]=1;
    tuwas(arr);
    cout << arr[0] << arr[1] << endl;
    return 0;
}

Wenn ich da - wie bei ner normalen Variablen - in meiner Funktion mit einer Kopie des Arrays arbeiten würde, wäre der Output ja 01, aber tatsächlich wird das Originalarray bearbeitet und der Output ist 56.
Sollte ich da etwas falsch verstanden haben, so lasse ich mich gerne eines besseren belehren. :)

// edit: Ähm... jetzt hab ich grad deinen Quelltext angeschaut und bin verwirrt. Du machst das doch ebenfalls so wie ich. Dein Array ist auch nicht global und da ist auch keine Referenz...? :?
Bild
Benutzeravatar
M.A.
 
Beiträge: 366
Registriert: 25.10.2008 16:37

Re: A26: Acht-Damen-Problem

Beitragvon CommanderTomalak » 19.06.2010 13:12

Ach du meinst, dass Arrays implizit als Referenz übergeben werden? Stimmt, da war was, ich habs auch grad nachgelesen, dass dem so ist. Aber dann wunder ich mich, warum mein Programm läuft, daran hab ich nämlich nicht gedacht :D
"Das Volk hat das Vertrauen der Regierung verscherzt. Wäre es da nicht doch einfacher, die Regierung löste das Volk auf und wählte ein anderes?"
- Bertolt Brecht
CommanderTomalak
 
Beiträge: 204
Registriert: 19.01.2009 00:42
Wohnort: Karlsruhe


Zurück zu Programmieren

Wer ist online?

Mitglieder in diesem Forum: 0 Mitglieder und 1 Gast

cron