Übungsaufgaben - “Brett” (C)

Martin Sulzmann

Überblick

Kompletter Programmcode der Aufgabe findet sich hier.

Zwei-dimensionales Brett mit Rahmen

Wir betrachten ein zwei-dimensionales Brett bestehend aus Zeichen ’ ‘, ’x’, ‘o’ und ‘!’. Die Repräsentation in C ist wie folgt.

struct Brett {
  char* p;
  int reihe;
  int spalte;
};

Beachte. Zeichen sind gespeichert in einem (ein-dimensionalen) char Array.

Hier sind ein paar einfache Beispiele inklusive einer Ausgabefunktion.

void zeichneBrett(struct Brett brett) {
  int i,j;

  for(i=0; i<brett.reihe; i++) {
    printf("\n");
    for(j=0; j<brett.spalte; j++) {
      int index = i * brett.spalte + j;
      printf("%c",brett.p[index]);
    }

  }
}


void beispiel1() {


  printf("\n*** Beispiel 1 ***\n");

  // 2-dim Array c entspricht im Speicher folgendem Array.
  char c[4*5] = {' ', ' ', ' ', ' ', '!',
          ' ', 'x', 'x', ' ', ' ',
          '!', ' ', ' ', ' ', 'o',
          'o', 'o', 'x', ' ', 'x'};

  struct Brett brett = {c, 4, 5};

  zeichneBrett(brett);

}

void beispiel2() {

  printf("\n*** Beispiel 2 ***\n");

  char c[4][5] = { {' ', ' ', ' ', ' ', '!'},
           {' ', 'x', 'x', ' ', ' '},
           {'!', ' ', ' ', ' ', 'o'},
           {'o', 'o', 'x', ' ', 'x'} };

  // 2-dim => 1-dim.
  char* p = &c[0][0];
  struct Brett brett = {p, 4, 5};
  zeichneBrett(brett);

}

Beachte.

Zwei-dimensionale Arrays werden der “Reihe” nach im Speicher abgelegt.

Ausdruck p[index] entspricht *(p+index).

Aufgabe

Zeichne das Brett mit Rahmen. beispiel1 soll folgende Ausgabe liefern:

*** Beispiel 1 (Rahmen) ***

-------
|    !|
| xx  |
|!   o|
|oox x|
-------

Checke das Brett auf erlaubte Zeichen

C hat keinen Booleschen Datentyp.

Konvention: 0 entspricht false und verschiedenen von 0 entspricht true.

Wir können mittels “enums” unseren eigenen Booleschen Datentyp definieren.

enum Bool {
  False = 0,
  True = 1,
};

void printB(enum Bool b) {
  if(b == False) {
    printf("False");
  } else {
    printf("True");
  }
}

Gegeben sind folgende Funktionalitäten um zu ueberpruefen, ob ein Brett nur erlaubte Zeichen enthält.

char erlaubteZeichen[4] = { ' ', 'x', 'o', '!' };

enum Bool checkBrett(struct Brett b) {
  int i,j;

  for(i=0; i < b.reihe * b.spalte; i++) {
    enum Bool ok = False;
    for(j=0; j<4; j++) {
      if(b.p[i] == erlaubteZeichen[j]) {
    ok = True;
      }
    }
    if(!ok) {
      return False;
    }
  }
  return True;
}

void beispiel1Check() {


  printf("\n*** Beispiel 1 (mit Check) ***\n");

  // 2-dim Array c entspricht im Speicher folgendem Array.
  char c[4*5] = {' ', ' ', ' ', ' ', '!',
          ' ', 'x', 'x', ' ', ' ',
          '!', ' ', ' ', ' ', 'o',
          'o', 'o', 'x', ' ', 'x'};

  struct Brett brett = {c, 4, 5};

  zeichneBrett(brett);

  printf("\n Check: ");
  printB(checkBrett(brett));

}

Aufgaben

Gebe Brett für welches checkBrett den Wert False liefert.

Gebe Alternative Implementierung von checkBrett welche die “single exit point rule” befolgt. Dies bedeutet:    1. In dieser Funktion gibt es genau ein return Statement.    2. Dieses befindet sich am Ende der Funktion.

Gebe eine semi-formale sprachliche Beschreibung des Algorithmus implementiert von checkBrett. Verwende ein AI Tool, um aus der sprachlichen Beschreibung ein lauffähiges C-Programm zu generieren.

Brett Transformationen

Gegeben folgender Programmcode.

void replaceChar(struct Brett b, char alt, char neu) {
  int i;

  for(i=0; i < b.reihe * b.spalte; i++) {
    if(b.p[i] == alt) {
      b.p[i] = neu;
    }
  }
}

void beispiel3() {

  printf("\n*** Beispiel 3 ***\n");

  char c[4][5] = { {' ', ' ', ' ', ' ', '!'},
           {' ', 'x', 'x', ' ', ' '},
           {'!', ' ', ' ', ' ', 'o'},
           {'o', 'o', 'x', ' ', 'x'} };

  char* p = &c[0][0];
  struct Brett brett = {p, 4, 5};
  zeichneBrett(brett);
  replaceChar(brett,'!','x');
  zeichneBrett(brett);
}

Aufgaben

Aufgabe

C verwendet call-by-value. Wieso sind die Updates (Ersetzungen) von replace sichtbar?

Aufgabe

Wir verwenden eine Abbildungstabelle, repräsentiert als ein Array mit Elementen vom Typ struct M. Vervollständige den Programmcode von replace.

struct M {
  char alt;
  char neu;
};

void replace(struct Brett b, struct M a[], int n) {
  // TODO
}

Z.B. folgendes Beispiel (beispiel4)

void beispiel4() {

  printf("\n*** Beispiel 4 ***\n");

  char c[4][5] = { {' ', ' ', ' ', ' ', '!'},
           {' ', 'x', 'x', ' ', ' '},
           {'!', ' ', ' ', ' ', 'o'},
           {'o', 'o', 'x', ' ', 'x'} };

  char* p = &c[0][0];
  struct Brett brett = {p, 4, 5};
  zeichneBrett(brett);
  struct M a[] = { { ' ', 'x'},
           { 'o', '!'} };
  printf("\n\n Replace liefert \n");
  replace(brett,a, 2);
  zeichneBrett(brett);
}

liefert die Ausgabe

*** Beispiel 4 ***

    !
 xx
!   o
oox x

 Replace liefert

xxxx!
xxxxx
!xxx!
!!xxx

Aufgabe

Betrachtet folgendes Beispiel (beispiel5). Ausgabe ist wie folgt.

*** Beispiel 5 ***

    !
 xx
!   o
oox x

 Replace liefert

    !
 oo
!   !
!!o o

 Replace liefert

    !
 !!
!   !
!!! !

Beachte. Die Abbildung ist nicht idempotent. Eine Abbildung ist idempotent wenn mehrfache Anwendungen das gleiche Ergebnis liefern. Dies ist hier nicht der Fall. Erste Anwendung liefert.

 Replace liefert

    !
 oo
!   !
!!o o

Zweite Anwendung liefert eine verschiedenes Ergebnis.

 Replace liefert

    !
 !!
!   !
!!! !

Ihre Aufgabe. Implementiere folgende Funktion, welche überprüft, ob die Abbildung idempotent ist. Hinweis. Die Menge “alt” und “neu” muss disjunkt sein.

enum Bool idempotent(struct M a[], int n) {
  // TODO
  return False;
}

void beispiel5() {

  printf("\n*** Beispiel 5 ***\n");

  char c[4][5] = { {' ', ' ', ' ', ' ', '!'},
           {' ', 'x', 'x', ' ', ' '},
           {'!', ' ', ' ', ' ', 'o'},
           {'o', 'o', 'x', ' ', 'x'} };

  char* p = &c[0][0];
  struct Brett brett = {p, 4, 5};
  zeichneBrett(brett);
  struct M a[] = { { 'o', '!'},
           { 'x', 'o'} };
  printf("\n\n Replace liefert \n");
  replace(brett,a, 2);
  zeichneBrett(brett);
  printf("\n\n Replace liefert \n");
  replace(brett,a, 2);
  zeichneBrett(brett);
}

Testverfahren

Welche Testverfahren haben Sie bisher kennengelernt?

Wir betrachten ein weiteres Testverfahren, bekannt unter dem Namen Property-Based Testing (aka Invarianten Test, …).

Die Idee ist folgt.

  1. Erstelle eine Property, die immer gilt.
  2. Generiere Testdaten und wende diese auf die Property an

Beispiele

Properties (Eigenschaften)

Verschiedene “check Brett” Implementierungen liefern das gleiche Ergebnis

Property: Für ein beliebiges Brett, prüfe ob checkBrett und checkBrettSingleReturn das gleiche Ergebnis liefern.

enum Bool propCheck(struct Brett brett) {

  if(checkBrett(brett) != checkBrettSingleReturn(brett)) {
    return False;
  }

  return True;
}

Verschiedene “replace” Implementierungen liefern das gleiche Ergebnis

Property: Für ein beliebiges Brett, prüfe ob replaceChar und replace das gleiche Ergebnis liefern.

enum Bool propReplace(struct Brett b1) {

  struct Brett b2 = copyBrett(b1);

  char a = 'x';
  char n = 'o';
  replaceChar(b1, a, n);

  struct M m[] = { { a, n }};
  replace(b2,m,1);

  return eqBrett(b1,b2);
}

Wir betrachten einen speziellen “replace” Fall. Ersetze ‘x’ durch ‘o’.

Wieso sind copyBrett und eqBrett notwendig?

Brett Hilfsfunktionen: Kopieren und Test auf Gleichheit

// Kopiere n Zeichen von s nach t.
// Annahme: n ist > 0
void copy(char* s, int n, char* t) {
  int i = 0;
  while(i < n) {
    t[i] = s[i];
    i++;
  }
}


// Brett Kopie ("clone")
struct Brett copyBrett(struct Brett b1) {
  struct Brett b2;

  b2.p = (char*)malloc(b1.reihe * b1.spalte * sizeof(char));

  b2.reihe = b1.reihe;
  b2.spalte = b1.spalte;
  copy(b1.p, b1.reihe*b1.spalte, b2.p);

  return b2;
}


enum Bool eqBrett(struct Brett b1, struct Brett b2) {
  int i;

  if(! (b1.reihe == b2.reihe && b1.spalte == b2.spalte)) {
    return False;
  }

  for(i = 0; i < b1.reihe * b1.spalte; i++) {
    if(b1.p[i] != b2.p[i]) {
      return False;
    }
  }

  return True;
}

Generierung Testdaten

Aufgabe: Generiere ein beliebiges Brett (mit erlaubten Zeichen).

Hier ist eine Lösung.


char genZeichen() {
  int index = rand() % 4;
  return erlaubteZeichen[index];
}

char* genReihe(int n) {
  char* reihe = (char*)malloc(n * sizeof(char));
  int i;

  for(i = 0; i<n; i++) {
    reihe[i] = genZeichen();
  }

  return reihe;
}

struct Brett genBrett(int reihe, int spalte) {
  struct Brett brett;
  char* q;
  int i;

  brett.reihe = reihe;
  brett.spalte = spalte;
  brett.p = (char*)malloc(reihe * spalte * sizeof(char));
  q = brett.p;

  for(i = 0; i < reihe; i++) {
    copy(genReihe(spalte),spalte,q);
    q = q + spalte;
  }

  return brett;
}

Verbessere obige Lösung wie folgt.

QuickCheck (“replace”)

void beispiel6() {

  printf("\n*** Beispiel 6 (QuickCheck Replace) ***\n");

  int i;

  for(i=0; i<10; i++) {
    struct Brett testData = genBrett(4,5);
    printf("\n*** Test %d", i);
    zeichneBrett(testData);
    if(propReplace(testData) == True) {
      printf("\nOK");
    } else {
      printf("\nFAIL");
    }
  }

}

Vorteile im Vergleich zu traditionellen Testverfahren.