Du bist nicht angemeldet.

Werbeanzeige

David Scherfgen

Administrator

  • »David Scherfgen« ist der Autor dieses Themas

Beiträge: 10 187

Wohnort: Bonn

Beruf: Wissenschaftlicher Mitarbeiter

  • Private Nachricht senden

1

22.06.2008, 15:47

#07: "Lateinisches Quadrat", K.d.C., 20.07.2008

#07: "Lateinisches Quadrat"
Typ: Kürze des Codes
Deadline: 20.07.2008
Abgabe: contest@spieleprogrammierer.de

Bitte beachten:
- Ablauf und Regeln


Aufgabenstellung:
Aus der Wikipedia: Ein lateinisches Quadrat ist ein Quadrat aus n×n Feldern, wobei jedes Feld mit einem von n verschiedenen Symbolen belegt ist, so dass jedes Symbol in jeder Zeile und in jeder Spalte jeweils genau einmal auftritt. Die Zahl n wird Ordnung des lateinischen Quadrats genannt.

Beispiele für lateinische Quadrate:

Quellcode

1
2
3
4
1 2 3 4     3 2 1     1 2     1
3 4 1 2     2 1 3     2 1
2 3 4 1     1 3 2
4 1 2 3


Diese beiden sind keine lateinischen Quadrate:

Quellcode

1
2
3
4
1 2 3 4     1 2 3 4
1 3 3 2     5 6 7 8
4 3 2 1     2 3 4 1
1 4 3 2     6 7 8 5


Ihr sollt eine Funktion implementieren, die ein Quadrat von Zahlen erhält (zeilenweise in einem Array abgespeichert) sowie die Seitenlänge. Die Funktion soll entscheiden, ob es ein lateinisches Quadrat ist oder nicht. Die Seitenlänge liegt zwischen 1 und MAX_SQUARE_SIZE (im Testprogramm als Konstante definiert). Die Zahlen im Quadrat unterliegen keiner besonderen Beschränkung. Im Testprogramm liegen sie zwischen 0 und 9999999, aber darauf dürft Ihr euch nicht verlassen.

C-/C++-Quelltext

1
2
3
4
5
6
7
8
9
10
11
12
13
// >>> DEINE FUNKTION - BITTE IMPLEMENTIEREN! <<<

// >>> BENUTZUNG DER STANDARDBIBLIOTHEK IST VERBOTEN! <<<

bool is_latin_square(const uint* p_numbers,
                     uint size)
{
    // BEGIN COUNT


    // Hier kommt dein Code!

    // true liefern, wenn das Quadrat ein lateinisches Quadrat ist, sonst false.

    return false;

    // END COUNT

}


Wie bei allen "Kürze des Codes"-Aufgaben ist die Verwendung der Standardbibliothek nicht erlaubt.
Derjenige gewinnt, der die kürzeste korrekte Lösung liefert.
Das Testprogramm arbeitet nur mit zufälligen Tests. Bei der endgültigen Bewertung werde ich auch noch einige Spezialfälle testen. Ihr solltet euch also nicht darauf verlassen, dass das Testprogramm alle Fehler aufdeckt.

Paket hier herunterladen

Das Paket besteht aus dem Quelltext der Testumgebung (inklusive Referenzimplementierung), Code::Blocks-Projekt und Token-Counter.

Viel Spaß und viel Erfolg!

Lord-archimedes

Treue Seele

Beiträge: 234

Wohnort: Hannover

  • Private Nachricht senden

2

22.06.2008, 20:39

lol @david eine echt coole Aufgabe
erst gestern fragte ich mich wann ein neuer contest kommt xD

David Scherfgen

Administrator

  • »David Scherfgen« ist der Autor dieses Themas

Beiträge: 10 187

Wohnort: Bonn

Beruf: Wissenschaftlicher Mitarbeiter

  • Private Nachricht senden

3

22.06.2008, 20:53

Gut ;)
Ich habe noch eine kleine Änderung gemacht.
Die Zahlen liegen im Testprogramm zwar zwischen 0 und 9999999, aber das muss nicht immer so sein.
Also bitte keine Arrays der Größe 10000000 ...

Gotbread

Alter Hase

Beiträge: 421

Wohnort: Kempen

Beruf: Student (Etechnik) + Hiwi

  • Private Nachricht senden

4

22.06.2008, 21:27

gibt es schon ergebnisse was die tokenanzahl betrifft ?

bin bei 118
Mfg Goti
www.gotbread.bplaced.net
viele tolle spiele kostenlos, viele hardware-basteleien :)

"Es ist nicht undicht, es läuft über" - Homer Simpson

David Scherfgen

Administrator

  • »David Scherfgen« ist der Autor dieses Themas

Beiträge: 10 187

Wohnort: Bonn

Beruf: Wissenschaftlicher Mitarbeiter

  • Private Nachricht senden

5

22.06.2008, 22:52

Bin im zweistelligen Bereich! :)
Aber ich muss noch durch extreme Brute Force-Tests herausfinden, ob meine Bedingung wirklich korrekt ist.

David Scherfgen

Administrator

  • »David Scherfgen« ist der Autor dieses Themas

Beiträge: 10 187

Wohnort: Bonn

Beruf: Wissenschaftlicher Mitarbeiter

  • Private Nachricht senden

6

23.06.2008, 00:06

Noch ein kleines Update:
Es gibt jetzt eine neue Konstante MAX_SQUARE_SIZE_SQ, die als MAX_SQUARE_SIZE * MAX_SQUARE_SIZE definiert ist.

7

23.06.2008, 14:24

Hey das zählt nicht ;) Man kommt bestimmt auch ohne aus, und dann ist es blöd wenn du neue Sachen hinzufügst!
Devil Entertainment :: Your education is our inspiration
Der Spieleprogrammierer :: Community Magazin
Merlin - A Legend awakes :: You are a dedicated C++ (DirectX) programmer and you have ability to work in a team? Contact us!
Siedler II.5 RttR :: The old settlers-style is comming back!

Also known as (D)Evil

Gotbread

Alter Hase

Beiträge: 421

Wohnort: Kempen

Beruf: Student (Etechnik) + Hiwi

  • Private Nachricht senden

8

23.06.2008, 14:28

[] !! :D :D

edit:

[] :badgrin:
Mfg Goti
www.gotbread.bplaced.net
viele tolle spiele kostenlos, viele hardware-basteleien :)

"Es ist nicht undicht, es läuft über" - Homer Simpson

David Scherfgen

Administrator

  • »David Scherfgen« ist der Autor dieses Themas

Beiträge: 10 187

Wohnort: Bonn

Beruf: Wissenschaftlicher Mitarbeiter

  • Private Nachricht senden

9

23.06.2008, 15:45

@Gotbread:
Kann ich unterbieten ;)

@Deviloper:
Ich selbst brauche die Konstante auch nicht.
Aber ich dachte, dass sie vielleicht dem einen oder anderen hilft.

Gotbread

Alter Hase

Beiträge: 421

Wohnort: Kempen

Beruf: Student (Etechnik) + Hiwi

  • Private Nachricht senden

10

23.06.2008, 16:39

[] :? (hier stand die tokenzahl)
Mfg Goti
www.gotbread.bplaced.net
viele tolle spiele kostenlos, viele hardware-basteleien :)

"Es ist nicht undicht, es läuft über" - Homer Simpson

Werbeanzeige