# Vererbung Quelle: https://dev.inf.zone/exercises/08/inheritance/ [Video auf YouTube](https://www.youtube.com/watch?v=xfZhb6lmxjk) ## Aufgabe **Auf einen Blick** - **Was:** Sie vervollständigen `inheritance.c`, ein Programm, das die Vererbung von Blutgruppen-Allelen in einer Familie über drei Generationen simuliert: ein Kind, seine zwei Eltern und seine vier Großeltern. - **Aufruf:** `./inheritance` – ohne Argumente, ohne Eingabe. - **Ausgabe:** der Stammbaum mit den zwei Allelen jeder Person. Die Allele sind zufällig und ändern sich von Lauf zu Lauf. - **Ihre Arbeit:** die zwei Funktionen `create_family` und `free_family`. Alles andere in `inheritance.c` bleibt unverändert. ### So funktioniert die Vererbung der Allele Die Blutgruppe eines Menschen wird durch zwei Allele bestimmt, also zwei Varianten desselben Gens. Für die Simulation gelten diese Regeln: 1. **Allele:** Es gibt drei Allele: `A`, `B` und `O` (im Deutschen schreibt man meist „0“ statt „O“). Jede Person hat zwei davon, gleiche (`AA`) oder verschiedene (`AB`). 2. **Älteste Generation:** Die Großeltern bekommen beide Allele zufällig. 3. **Alle anderen:** Jede Person erbt von jedem Elternteil genau ein Allel, zufällig eines der beiden. Das erste Allel stammt vom ersten Elternteil (`parents[0]`), das zweite vom zweiten (`parents[1]`). 4. **Reihenfolge:** `AO` und `OA` sind also verschiedene Ergebnisse. Möglich sind neun Kombinationen: `OO`, `OA`, `OB`, `AO`, `AA`, `AB`, `BO`, `BA`, `BB`. Hat zum Beispiel der erste Elternteil `AO` und der zweite `OB`, kann das Kind `AO`, `AB`, `OO` oder `OB` bekommen. **Beispiel** über zwei Generationen: | Person | Allele | 1. Allel | 2. Allel | | ---------------- | ------ | ------------------------------------ | ------------------------------------ | | Großelternteil 1 | `OA` | zufällig | zufällig | | Großelternteil 2 | `BO` | zufällig | zufällig | | Großelternteil 3 | `AO` | zufällig | zufällig | | Großelternteil 4 | `BO` | zufällig | zufällig | | Elternteil 1 | `AO` | `A` von Großelternteil 1 (`OA`) | `O` von Großelternteil 2 (`BO`) | | Elternteil 2 | `OB` | `O` von Großelternteil 3 (`AO`) | `B` von Großelternteil 4 (`BO`) | | Kind | `OO` | `O` von Elternteil 1 (`AO`) | `O` von Elternteil 2 (`OB`) | So gibt das Programm diese Familie aus – erst das Kind, dann jeder Elternteil, direkt gefolgt von dessen Eltern, eingerückt um vier Leerzeichen je Generation: ```text $ ./inheritance Child (Generation 0): alleles OO Parent (Generation 1): alleles AO Grandparent (Generation 2): alleles OA Grandparent (Generation 2): alleles BO Parent (Generation 1): alleles OB Grandparent (Generation 2): alleles AO Grandparent (Generation 2): alleles BO ``` Welche Blutgruppe sich aus zwei Allelen ergibt, erklärt das Video oben; eine Übersicht steht am Ende der Seite unter „Zum Weiterlesen“. Für die Aufgabe brauchen Sie das nicht. ## Demo [Terminal-Aufzeichnung ansehen](https://asciinema.org/a/64T28s31XDJ119MOp44Lfc5oY) ## Aufgabenmaterial Für diese Aufgabe werden Sie ein von uns zur Verfügung gestelltes Codegerüst vervollständigen. **Aufgabenmaterial herunterladen** Öffnen Sie VS Code entsprechend Ihrem [Setup](https://dev.inf.zone/extras/setup/). Öffnen Sie Ihr Terminalfenster und führen Sie dann `cd` aus. Die Eingabeaufforderung Ihres Terminalfensters sollte wie folgt aussehen: ```bash $ ``` Geben Sie dann ```bash wget https://dev.inf.zone/download/exercises/08/inheritance.zip ``` ein und führen Sie den Befehl mit der Eingabetaste aus, um eine ZIP-Datei namens `inheritance.zip` in den aktuellen Ordner herunterzuladen. Achten Sie darauf, dass Sie das Leerzeichen zwischen `wget` und der folgenden URL nicht übersehen, und auch kein anderes Zeichen! Führen Sie jetzt ```bash unzip inheritance.zip ``` aus, um das ZIP-Archiv in einen Ordner namens `inheritance` zu extrahieren. Sie brauchen die ZIP-Datei nicht mehr, also können Sie ```bash rm inheritance.zip ``` ausführen. Antworten Sie mit "y", gefolgt von der Eingabetaste, um die heruntergeladene ZIP-Datei zu entfernen. Führen Sie dann ```bash cd inheritance ``` aus, um in dieses Verzeichnis zu wechseln. Ihre Eingabeaufforderung sollte nun wie folgt aussehen: ```bash inheritance/ $ ``` Wenn alles wie beschrieben funktioniert hat, sollten Sie nach dem Ausführen von ```bash ls ``` eine Datei, `inheritance.c`, sehen. **Überblick über `inheritance.c`** Jede Person ist eine `struct` vom Typ `person` mit zwei Membern: - `parents`: ein Array aus zwei Pointern auf die beiden Eltern (jeweils wieder eine `person`), - `alleles`: ein Array aus zwei `char` (jeweils `'A'`, `'B'` oder `'O'`). ```c // Each person has two parents and two alleles typedef struct person { struct person *parents[2]; char alleles[2]; } person; ``` `main` initialisiert zuerst den Zufallszahlengenerator („Seeding“): ```c // Seed random number generator srand(time(0)); ``` `srand` legt fest, welche Folge von Pseudozufallszahlen spätere Aufrufe von `rand()` liefern. Weil `time(0)` die aktuelle Uhrzeit in Sekunden liefert, kommen bei jedem Lauf (in einer neuen Sekunde) andere Zahlen heraus. `srand` wird **einmal** vor dem ersten `rand()` aufgerufen – das erledigt das Codegerüst schon; Sie rufen danach nur noch `rand()` auf. `rand()` liefert eine ganze Zahl zwischen `0` und `RAND_MAX`, einer sehr großen Zahl (in der CS50-Umgebung `2147483647`). Die nötige Bibliothek `` ist bereits eingebunden. `rand()` steckt auch in der fertigen Funktion `random_allele`: ```c // Randomly chooses a blood type allele. char random_allele() { int r = rand() % 3; if (r == 0) { return 'A'; } else if (r == 1) { return 'B'; } else { return 'O'; } } ``` Wieso wird hier `rand() % 3` verwendet? Dann ruft `main` nacheinander drei Funktionen auf: ```c // Create a new family with three generations person *p = create_family(GENERATIONS); // Print family tree of alleles print_family(p, 0); // Free memory free_family(p); ``` - `create_family` legt die Familie an (`GENERATIONS` ist `3`) und gibt einen Pointer auf das Kind zurück – **Ihre Aufgabe**. - `print_family` gibt den Stammbaum aus – fertig. - `free_family` gibt den mit `malloc` reservierten Speicher wieder frei – **Ihre Aufgabe**. In `create_family` sind die beiden rekursiven Aufrufe für die Eltern schon vorgegeben; die Stellen, an denen Sie Code ergänzen, sind mit `TODO` markiert. ## Spezifikation Ändern Sie in `inheritance.c` nur die Funktionen `create_family` und `free_family`. - **`create_family(generations)`** legt eine Person und alle ihre Vorfahren über `generations` Generationen an und gibt einen Pointer auf die Person der jüngsten Generation zurück. - Für jede Person reservieren Sie mit `malloc` Speicher für eine `person`. `create_family(3)` legt also sieben Personen an: ein Kind mit zwei Eltern, von denen jedes wieder zwei Eltern hat. - Bei `generations > 1` zeigen `parents[0]` und `parents[1]` auf die beiden Eltern, die das Codegerüst schon rekursiv erzeugt. Die Allele erbt die Person nach Regel 3: `alleles[0]` zufällig eines der beiden Allele von `parents[0]`, `alleles[1]` zufällig eines der beiden von `parents[1]`. - Bei `generations == 1` (älteste Generation) sind beide `parents` `NULL`, und beide Allele kommen aus `random_allele()`. - **`free_family(p)`** gibt den Speicher von `p` und allen Vorfahren von `p` frei. Ist `p` `NULL`, tut die Funktion nichts. Die Eltern werden vor dem Kind freigegeben. ## Hilfestellung Klicken Sie auf die folgenden Tipps, um einige Ratschläge zu erhalten. Versuchen Sie aber zunächst, selbst so weit wie möglich zu kommen. **Vervollständigen der `create_family`-Funktion** Warum Rekursion? Um die Allele einer Person zu bestimmen, brauchen Sie die Allele ihrer Eltern. Für diese brauchen Sie die Allele _deren_ Eltern – und so weiter, bis zur ältesten Generation, die Sie simulieren. Wie Rekursion funktioniert, zeigt das Short [Rekursion](https://dev.inf.zone/lectures/3-algorithmen/short-3-5-rekursion/). Reservieren Sie zuerst Speicher für eine neue Person. [Erinnern Sie sich](https://dev.inf.zone/lectures/5-datenstrukturen/short-5-1-strukturen/), dass `malloc` Speicher reserviert und `sizeof(person)` die Anzahl der benötigten Bytes liefert. Bekommt `malloc` keinen Speicher, gibt es `NULL` zurück; das sollten Sie abfangen. ```c // Allocate memory for new person person *new_person = malloc(sizeof(person)); if (new_person == NULL) { return NULL; } ``` Prüfen Sie dann, ob noch Generationen zu erzeugen sind, also ob `generations > 1` ist. In diesem Fall hat das Codegerüst schon zwei Eltern, `parent0` und `parent1`, durch rekursive Aufrufe von `create_family` erzeugt. Setzen Sie die Pointer auf die Eltern und weisen Sie der neuen Person von jedem Elternteil zufällig ein Allel zu. - Über einen Pointer greifen Sie mit der Pfeilnotation auf die Member einer `struct` zu ([Strukturen](https://dev.inf.zone/lectures/5-datenstrukturen/short-5-1-strukturen/)): Ist `p` ein Pointer auf eine Person, dann ist `p->parents[0]` der Pointer auf ihren ersten Elternteil. - `rand() % 2` liefert zufällig `0` oder `1` – also einen gültigen Index für eines der beiden Allele. Mehr zu `rand()` steht im Handbuch unter [`rand`](https://manual.cs50.io/3/rand); leichter lesbar ist der Eintrag zu [`random`](https://manual.cs50.io/3/random), einer Variante, die `long` statt `int` zurückgibt. ```c // Create two new parents for current person by recursively calling create_family person *parent0 = create_family(generations - 1); person *parent1 = create_family(generations - 1); // Set parent pointers for current person new_person->parents[0] = parent0; new_person->parents[1] = parent1; // Randomly assign current person's alleles based on the alleles of their parents new_person->alleles[0] = parent0->alleles[rand() % 2]; new_person->alleles[1] = parent1->alleles[rand() % 2]; ``` Ist `generations == 1`, hat die Person keine Eltern mehr: Beide Pointer werden `NULL`, beide Allele zufällig. ```c // Set parent pointers to NULL new_person->parents[0] = NULL; new_person->parents[1] = NULL; // Randomly assign alleles new_person->alleles[0] = random_allele(); new_person->alleles[1] = random_allele(); ``` Zum Schluss gibt die Funktion den Pointer auf die neue Person zurück. ```c // Return newly created person return new_person; ``` **Implementierung der `free_family`-Funktion** `free_family` bekommt einen Pointer auf eine `person`, gibt rekursiv den Speicher aller ihrer Vorfahren frei und dann den der Person selbst. - Behandeln Sie zuerst den Basisfall: Ist `p` `NULL`, gibt es nichts freizugeben, und die Funktion kann sofort `return`en. - Andernfalls geben Sie rekursiv beide Eltern frei, bevor Sie das Kind freigeben. Umgekehrt ginge es nicht: Nach `free(p)` dürfen Sie `p->parents` nicht mehr lesen. **Achtung Spoiler**: Der folgende Code zeigt Ihnen, wie Sie genau das umsetzen können! ```c // Free `p` and all ancestors of `p`. void free_family(person *p) { // Handle base case if (p == NULL) { return; } // Free parents recursively free_family(p->parents[0]); free_family(p->parents[1]); // Free child free(p); } ``` ## Testen Führen Sie `./inheritance` mehrmals aus und prüfen Sie jede Ausgabe gegen die Regeln oben: - Die Ausgabe hat sieben Zeilen: Kind, zwei Eltern, vier Großeltern, eingerückt wie im Beispiel. - Das erste Allel jeder Person kommt beim ersten Elternteil vor, das zweite beim zweiten. - Die Allele ändern sich von Lauf zu Lauf. Weil `time(0)` nur jede Sekunde weiterzählt, liefern zwei Läufe in derselben Sekunde dieselbe Familie. ### Korrektheit Führen Sie in Ihrem Terminal den folgenden Befehl aus, um die Korrektheit Ihrer Arbeit zu überprüfen: ```bash check50 -l inf-zone/exercises/2026/inheritance ``` ### Style Führen Sie den folgenden Befehl aus, um den Stil Ihres Codes mit `style50` zu analysieren: ```bash style50 inheritance.c ``` ## Abgeben Geben Sie im Ordner `inheritance` ab: ```bash inf upload inheritance ``` Danach sehen Sie, welche Tests Ihr Programm besteht und ob die Übung für die Bonuspunkte zählt. Wie Sie `inf` installieren und sich anmelden, steht unter [Abgeben mit `inf`](https://dev.inf.zone/faq/uebung-solutions/#inf-installieren). ## Zum Weiterlesen: Von den Allelen zur Blutgruppe Für die Lösung der Aufgabe nicht nötig. Die Simulation betrachtet nur die Allele (den Genotyp), nicht die Blutgruppe selbst (den Phänotyp). Welche Blutgruppe aus zwei Allelen folgt, hängt davon ab, dass `A` und `B` gegenüber `O` dominant sind und sich gegenseitig nicht verdrängen: | Allele | Blutgruppe | | ---------------- | ---------- | | `AA`, `AO`, `OA` | A | | `BB`, `BO`, `OB` | B | | `AB`, `BA` | AB | | `OO` | 0 | Im Beispiel oben hat das Kind (`OO`) also Blutgruppe 0, obwohl seine Eltern Blutgruppe A (`AO`) und B (`OB`) haben.