Programmier-Aufgaben in C: Anwendungen von Feldern, Zeigern und Funktionen

Programmieraufgaben zur Anwendung von Feldern und Zeigern, die im Sinne der strukturierten Programmierung zu lösen sind. Die Quelltexte sollen in reinem C geschrieben werden, also keine Konzepte verwenden, die nur in C++ verfügbar sind.

Einordnung des Artikels

Spezielle Zahlen

Perfekte Zahlen

Eine natürliche Zahl n heißt perfekte Zahl, wenn die Summe ihrer Teiler genau n ergibt. Dabei wird 1 zu den Teilern gerechnet, aber nicht n selbst.

Beispiel:

Die Zahlen 6 und 28 sind perfekte Zahlen.

6 besitzt die Teiler 1, 2, 3 und es ist 6 = 1 + 2 + 3.

28 besitzt die Teiler 1, 2, 4, 7, 14 und es ist 28 = 1 + 2 + 4 + 7 + 14.

Implementieren Sie eine Funktion, die alle perfekten Zahlen unterhalb einer gegebenen Schranke N berechnet und ausgibt.

Harshad-Zahlen

Diskutieren Sie für sämtliche im Folgenden beschriebenen Funktion, wie ihr geeigneter Funktionskopf lautet.

Eine natürliche Zahl wird als Harshad-Zahl bezeichnet, wenn sie durch ihre Quersumme teilbar ist.

Implementieren Sie eine Funktion isHarshad(), die prüft, ob eine Zahl n eine Harshad-Zahl ist.

Der Name Harshad-Zahl leitet sich von dem Sanskrit-Wort harsha (= Freude) ab.

Beispiele:

  1. Die Quersumme von 11 ist gleich 2 und daher ist 11 keine Harshad-Zahl.
  2. Dagegen hat 12 die Quersumme 3 und daher ist 12 eine Harshad-Zahl.

Implementieren Sie eine Funktion getHarshads(), die alle Harshad-Zahl unterhalb einer gegebenen Schranke N berechnet und ausgibt. Berechnen Sie alle Harshad-Zahlen für N < 100 000.

Warum sind alle dreistelligen Zahlen, die nur eine Ziffer enthalten, (also zum Beispiel 666) Harshad-Zahlen?

Welche der Harshad-Zahlen sind multiple Harshad-Zahlen? Damit ist gemeint, dass bei Division einer Harshad-Zahl durch ihre Quersumme wieder eine Harshad-Zahl ensteht.

Berechnen Sie alle multiplen Harshad-Zahlen für N < 100 000.

Beispiel:

  1. Die Zahl 180 ist eine multiple Harshad-Zahl, denn 180 ist durch 9 teilbar. Das Ergebnis der Division ist 180 : 9 = 20 und 20 ist wiederum eine Harshad-Zahl (durch 2 teilbar).
  2. Dagegen ist 204 keine multiple Harshad-Zahl. Sie ist zwar eine Harshad-Zahl, da 204 : 6 = 34. Aber 34 ist nicht durch 7 teilbar und somit keine Harshad-Zahl.

Sich selbst beschreibende Zahlen

Eine natürliche Zahl x heißt sich selbst beschreibend, wenn gilt:

  1. Die Zahl x hat höchstens 10 Stellen.
  2. Hat x genau N Stellen (also 1 ≤ N ≤ 10), dann beschreiben die Ziffern von x, wie oft die Ziffern 0, 1, 2, ..., 9 in x vorkommen und zwar nach folgender Regel:
  • Die erste (vorderste) Stelle von x gibt an, wie oft die 0 in x vorkommt;
  • die zweite Stelle gibt an, wie oft die 1 in x vorkommt;
  • ...;
  • die N-te Stelle von x gibt an, wie oft die Ziffer N-1 in x vorkommt.

Beispiele:

Die Zahl x = 1 beschreibt sich nicht selbst; sie beschreibt die Zahl 0.

Die Zahl 2020 ist sich selbst beschreibend:

  • sie enthält zweimal die Ziffer 0,
  • keine 1,
  • zweimal die Ziffer 2 und
  • keine 3.
0 1 2 3
2 0 2 0

Die Zahl x = 6210001000 ist sich selbst beschreibend, da

  • in x genau 6 Nullen vorkommen,
  • in x zweimal die 1 vorkommt,
  • in x einmal die 2 vorkommt,
  • keine 3, 4, 5, 7, 8, 9 vorkommen,
  • aber eine 6 (daher eine 1 an der 7. Stelle von vorne gezählt).
0 1 2 3 4 5 6 7 8 9
6 2 1 0 0 0 1 0 0 0

Schreiben Sie ein Programm, das alle sich selbst beschreibenden Zahlen 1 ≤ x ≤ 1011 - 1 berechnet und ausgibt.

Das Zahlenspiel 3, 5, 11

Für ein Zahlenspiel zwischen zwei Spielern A und B gelten folgende Regeln:

  1. Zu Beginn wird eine natürliche Zahl 20 < n < 1000 aufgeschrieben.
  2. Die Spieler A und B sind abwechselnd am Zug, wobei A beginnt.
  3. Bei jedem Zug muss ein Spieler eine der Zahlen 3, 5, 11 von n abziehen; die Differenz ist das neue n.
  4. Erreicht ein Spieler mit seinem Zug das Ergebnis n = 0, so hat er gewonnen. Ist n < 0, so hat der Spieler verloren.

Die folgende Tabelle zeigt einen möglichen Spielverlauf, der mit n = 22 startet; gezeigt ist immer die Zahl, die der Spieler bei seinem Zug erzeugt hat:

A B
17
12
9
6
1
  • Hier hat also A im ersten Zug 5 abgezogen, so dass n = 17 entsteht.
  • Anschließend hat B ebenfalls 5 abgezogen, wodurch n = 12 ensteht.
  • Und so weiter.
  • Im letzten Zug hat A die Zahl n = 1 erzeugt, womit B eine negative Zahl erzeugen muss.
  1. Analysieren Sie den Spielverlauf und finden Sie heraus, ob
    • A den Gewinn erzwingen konnte und mit Hilfe einer geschickten Strategie gewonnen hat oder
    • ob B eigentlich hätte gewinnen können (und durch einen Fehler den Sieg verpasst hat).
  2. Falls sich ein Gewinn erzwingen lässt: Ist die Zahl, die man abziehen muss, eindeutig gegeben oder gibt es mehrere Möglichkeiten?
  3. Implementieren Sie eine Funktion nextMove(), die zu einer gegebenen Zahl n berechnet, ob sich der Gewinn erzwingen lässt und welche Zahl (aus 3, 5, 11) dazu ausgewählt werden muss. Falls sich der Gewinn nicht erzwingen lässt, soll 3 ausgewählt werden (um das Spiel möglichst lange am Laufen zu halten und dem Gegner die Möglichkeit zu einem Fehler zu geben).
  4. Implementieren Sie eine weitere Funktion randomNextMove(), die immer durch Zufall eine der Zahlen 3, 5, 11 auswählt.
  5. Implementieren Sie eine Funktion play(), die durch Zufall eine Zahl 100 < n < 1000 auswählt und die beiden Funktionen nextMove() und randomNextMove() gegeneinander spielen lässt.
  6. Stellen Sie durch zahlreiche Wiederholungen von play() fest, wie groß in etwa die Gewinnwahrscheinlichkeiten der beiden "Strategien" sind.
  7. Diskutieren Sie: ändert sich die Strategie nextMove(), wenn die Spielregeln geändert werden, und in jedem Zug eine der Zahlen 3, 5, 9 abgezogen werden muss.
  8. Schreiben Sie die Implementierungen von nextMove() und randomNextMove() so um, dass die 3 möglichen Zahlen, die abgezogen werden können, Eingabewerte der Funktionen sind. Testen Sie nextMove() mit den Zahlen 3, 5, 9.

Auswertung einer Zufallsfolge

A) Legen Sie ein Projekt an und führen Sie die Funktion printRandomValues() aus, deren Implementierung im folgenden Listing gezeigt ist:

void printRandomValues(int n){
    srand(time(0));

    for (int i = 0; i < n; ++i) {
        int random_value = rand() % 6 + 1;
        printf(" %d ", random_value);
    }
}
  • Informieren Sie sich in der C-Dokumentation über die Eigenschaften der Funktionen rand() und srand().
  • Beschreiben Sie die Arbeitsweise der oben angegebenen Funktion printRandomValues().
  • Diskutieren Sie insbesondere das Verhalten der Funktion printRandomValues(), wenn man den Befehl srand(time(0)); aus Zeile 2 weglässt.

B) Schreiben Sie die Funktion printRandomValues() so um, dass man auf die Zufallsfolge aus der main()-Funktion heraus zugreifen kann. Die Zufallsfolge soll später ausgewertet werden.

C) Erzeugen Sie Zufallsfolgen der Länge n = 10 und werten Sie diese Folgen aus.

Die Auswertung soll beinhalten:

  • Ausgabe der Positionen innerhalb der Zufallsfolge, an der eine 6 steht.
  • Berechnung der Anzahl der 6 innerhalb der Zufallsfolge.
  • Berechnung der Anzahl, wie oft die Zahlenfolge (1, 2, 3) innerhalb der Zufallsfolge vorkommt.

D) Erzeugen Sie 1000 Zufallsfolgen der Länge n = 10 und berechnen Sie die relativen Häufigkeiten der Ereignisse

"die erste 6 erscheint beim k-ten Wurf", k = 1, 2,, ..., 10, sowie

"keine 6 bei n Würfen".

E) Lassen Sie die theoretischen Wahrscheinlichkeiten für die oben genannten Ereignisse von einer Funktion berechnen und stellen Sie die Ergebnisse mit den relativen Häufigkeiten in einer Tabelle gegenüber. Achten Sie dabei darauf, dass die Zahlen mit geeigneter Genauigkeit angegeben werden. Zur Berechnung der theoretischen Wahrscheinlichkeiten können Sie von einem Laplace-Würfel ausgehen.

Ziehung der Lottozahlen

Im Folgenden werden einige Funktionen beschrieben, die nur mit ihrem Namen benannt sind; Eingabewerte, Rückgabewerte und ob sie mit call by value oder call by reference arbeiten, ist nicht genannt. Diskutieren Sie für alle diese Funktionen:

  • Wie lautet der geeignete Funktionskopf?
  • Sollen oder müssen sie mit call by value oder call by reference arbeiten?

Oben wurde in der Aufgabe Auswertung einer Zufallsfolge eine Funktion vorgestellt, die eine Zufallsfolge ausgibt. Schreiben Sie diese Funktion so zu einer Funktion draw() um, dass sie die Ziehung der Lottozahlen "6 aus 49" simulieren kann (ohne Superzahl). Die gezogenen Lottozahlen sollen nicht nur ausgegeben werden, sondern später weiterverarbeitet werden.

Die von draw() erzeugten Lottozahlen müssen syntaktisch korrekt, was durch eine weitere Funktion isDraw() überprüft werden soll. Syntaktisch korrekt heißt hier:

  • Es werden 6 Zahlen von 1 bis 49 gezogen.
  • Die Zahlen werden aufsteigend sortiert angegeben.
  • Keine Zahl darf mehrfach vorkommen.

Implementieren Sie eine weitere Funktion score(), die zu gezogenen Lottozahlen und einem Lotto-Tip feststellt, wie viele Richtige der Tip enthält.

Implementieren Sie eine weitere Funktion gamble() mit folgenden Eigenschaften:

  • Der Nutzer soll aufgefordert werden einen Lotto-Tip abzugeben. Die Eingabe erfolgt über die Konsole.
  • Nach erfolgter Eingabe soll geprüft werden, ob es sich um einen korrekten Lotto-Tip handelt. Falls nicht, wird eine Warnung ausgegeben und das Programm beendet.
  • Ist der Lotto-Tip korrekt, wird das Programm fortgesetzt.
  • Dazu werden so lange neue Lottozahlen gezogen, bis der Nutzer zum ersten Mal 4 oder mehr Richtige hat. Dabei werden die gezogenen Zahlen nicht ausgegeben.
  • Die Serie der erzeugten Lottozahlen wird ausgewertet:
    • Es wird ausgegeben, wie viele Ziehungen simuliert wurden.
    • Es wird ausgegeben, bei wie vielen Ziehungen der Nutzer 0, 1, 2, 3 Richtige hatte.

Diskutieren Sie, wie man die Funktion gamble() geeignet in mehrere Teil-Funktionen aufspaltet.

Berechnung der Schwerpunktskoordinate und des Massenträgheitsmomentes

Weiter oben wurde die Funktion printRandomValues() beschrieben, die Zufallsfolgen erzeugen kann. Schreiben Sie diese Funktion so zu einer Funktion randomSequence() um, dass sie

  • eine Folge von Zufallszahlen der Länge n im Intervall [min; max] erzeugt,
  • die Zahlen sollen jetzt nicht mehr ganzzahlig sein, sondern mit 2 Nachkommastellen abgespeichert werden können.

Abbildung 1: Oben: Koordinatensystem mit drei speziellen Koordinaten und einer Drehachse bei x = d. Unten: An den drei Koordinaten befinden sich Massenpunkte (die unterschiedlichen Massen sind durch die Größe der Kreise angedeutet). Rechts: die Formeln zur Berechnung der Schwerpunktskoordinate und des Massenträgheitsmomentes.Abbildung 1: Oben: Koordinatensystem mit drei speziellen Koordinaten und einer Drehachse bei x = d. Unten: An den drei Koordinaten befinden sich Massenpunkte (die unterschiedlichen Massen sind durch die Größe der Kreise angedeutet). Rechts: die Formeln zur Berechnung der Schwerpunktskoordinate und des Massenträgheitsmomentes.

Implementieren Sie zwei weitere Funktionen, die zu gegebenen, gleich langen Feldern von x-Koordinaten und Massen

  • die Schwerpunktskoordinate sowie
  • das Massenträgheitsmoment

berechnen. Dabei soll die Funktion zur Berechnung des Massenträgheitsmomentes einen weiteren Eingabewert haben: die x-Koordinate der Drehachse.

Erzeugen Sie mit randomSequence() einen Vektor mit 20 x-Koordinaten im Intervall [-10; 10] und 20 Massen im Intervall [0; 100].

Berechnen Sie die Schwerpunktskoordinate der Massenverteilung (siehe Abbildung 1, dort für nur 3 Massen).

Berechnen Sie das Massenträgheitsmoment der Massenverteilung, wobei die Drehachse die x-Koordinaten -10, -9, ..., 9, 10 annehmen soll; die Drehachse steht senkrecht auf der x-Achse (siehe Abbildung 1).

Überprüfen Sie, ob die berechneten Massenträgheitsmomente den Satz von Steiner erfüllen.

Diskutieren Sie, wie man die Funktionen zur Berechnung der Schwerpunktskoordinate und des Massenträgheitsmomentes auf ein drei-dimensionales Problem übertragen kann. Wie wird man dann die Lage der Drehachse beschreiben müssen?

Darstellung von Polynomen als Folgen

Polynome können eindeutig durch ihre Koeffizienten beschrieben werden, wenn man sich darauf einigt, in welcher Reihenfolge sie angegeben werden.

So ist etwa

x4 - 4x2 - 3x - 5

gleichwertig zur Folge (niedrigste Potenz zuerst, höchste Potenz zuletzt)

(-5, -3, -4, 0, 1)

Ein Polynom vom Grad n ist somit gleichwertig zu einer Folge der Länge n+1. Die Koeffizienten werden im Folgenden als ganzzahlig angenommen.

A) Implementieren Sie Funktionen zum

  • Differenzieren eines Polynoms,
  • Addieren zweier Polynome,
  • Multiplizieren zweier Polynome.

Diskutieren Sie, welchen Funktionskopf die entsprechenden Funktionen haben.

Testen Sie diese Funktionen mit den Polynomen

p1 (x) = x4 - 4x2 - 3x - 5

p2 (x) = -2x6 + 6x5 - 3x4 + 2x.

B) Berechnen Sie mit Hilfe der Funktionen aus A) die ersten 10 Zeilen des Pascalschen Dreiecks.

Abbildung 2: Definition der Fakultät und des Binomialkoeffizienten (Gleichung 1 und 2) und der wichtigsten Formeln zur Berechnung des Pascalschen Dreiecks. Üblicherweise werden die Einträge des Pascalschen Dreiecks über die Binomialkoeffizienten berechnet; hier wird ein anderer Zugang gewählt.Abbildung 2: Definition der Fakultät und des Binomialkoeffizienten (Gleichung 1 und 2) und der wichtigsten Formeln zur Berechnung des Pascalschen Dreiecks. Üblicherweise werden die Einträge des Pascalschen Dreiecks über die Binomialkoeffizienten berechnet; hier wird ein anderer Zugang gewählt.

C) Implementieren Sie eine Funktion, die zu einem als Folge gegebenen Polynom und einem x-Wert den Funktionswert des Polynoms berechnet (sowohl x- als auch y-Wert als double).

D) Berechnen Sie für die Polynome p1 und p2 von oben eine Wertetabelle mit den x-Werten:

-5, -4.5, -4, ..., 4, 4.5, 5.

Monte-Carlo Flächenberechnung

In den Abbildungen 3 und 4 ist eine Methode dargestellt, wie man eine Integration auf reines Abzählen zurückführen kann; als zu integrierende Funktion wird jeweils

f(x) = x

gewählt und die Integrationsgrenzen sind 0 und 1.

In Abbildung 3 ist zu erkennen, dass das Rechteck [0;1] × [0;1] mit einem Gitter von Punkten überzogen wird; hier sind es 11 · 11 = 121 Gitterpunkte. Eine Näherung für die Fläche unter der Kurve von f(x) erhält man, indem man abzählt,

  • wie viele Punkte unter (oder auf) der Kurve liegen (hier 1 + 2 + ... + 11 = 66),
  • wie viele Punkte insgesamt dargestellt sind (hier 121)

und anschließend mit einem Dreisatz auf die gesuchte Fläche schließt:

121 Punkte entsprechen einer Fläche von 1,

66 Punkte entsprechen der gesuchten Fläche.

Als Näherung für das gesuchte Integral erhält man somit 66/121.

In Abbildung 4 ist zu sehen, dass man anstelle des Gitters auch zufällig gewählte Punkte verwenden kann, womit man ein leicht abweichenden Näherungswert erhält.

Die Genauigkeit dieser Integrationsmethode lässt sich leicht steigern, indem man mehr Punkte verwendet.

Abbildung 3: Darstellung der Funktion f(x) = x (blau) zusammen mit 121 Gitterpunkten (rot); durch Abzählen kann man eine Näherung für die Fläche unter f(x) bestimmen.Abbildung 3: Darstellung der Funktion f(x) = x (blau) zusammen mit 121 Gitterpunkten (rot); durch Abzählen kann man eine Näherung für die Fläche unter f(x) bestimmen.

Abbildung 4: Darstellung der Funktion f(x) = x (blau) und 121 zufällig gewählten Punkten im Rechteck.Abbildung 4: Darstellung der Funktion f(x) = x (blau) und 121 zufällig gewählten Punkten im Rechteck.

A) Implementieren Sie eine Funktion, die zu einem gegebenen Rechteck [a; b] × [c; d] ein Gitter mit N · M Punkten erzeugt, wobei man sich die "Dichte" der Punkte pro Einheitsintervall vorgeben kann; in Abbildung 3 sind es 11 Punkte pro Intervall der Länge 1.

B) Implementieren Sie die entsprechende Funktion, die die gleiche Anzahl an Zufallspunkten im Rechteck [a; b] × [c; d] erzeugt. Dazu müssen Sie wieder die oben gezeigte Funktion zur Berechnung von Zufallsfolgen geeignet umschreiben.

C) Implementieren Sie eine weitere Funktion, die zu den gegebenen Punkten (Gitter oder Zufallspunkte) und einer gegebenen Funktion f(x) den Näherungswert für das Integral von f(x) von a bis b berechnet.

Testen Sie diese Funktion mit f(x) = x und dem Rechteck [0; 1] × [0; 1].

D) Berechnen Sie näherungsweise das Integral der Funktion exp(-x2) von - 1 bis 1. (Wenn Sie mit der Standard-Normalverteilung vertraut sind, können Sie das Integral transformieren und den gesuchten Wert aus einer geeigneten Tabelle ablesen.)

E) Der Einheitskreis wird dem Quadrat mit Seitenlänge 2 einbeschrieben. Erzeugen Sie Zufallspunkte, die innerhalb des Quadrats liegen. Aus der Anzahl der Punkte, die innerhalb des Kreises liegen, kann man eine Näherung für die Kreiszahl π berechnen.

Abbildung 5 zeigt eine Realisierung mit 900 Zufallspunkten, aus denen sich als Näherung von π ergibt:

π ≈ 3.169.

Abbildung 5: Approximation für π.Abbildung 5: Approximation für π.

F) Implementieren Sie diese näherungsweise Berechnung von π mit den oben erklärten Methoden.

G) Berechnen Sie näherungsweise die Fläche zwischen den Polynomen p1(x) und p2(x) aus der Aufgabe zur Darstellung von Polynomen als Folgen (siehe Abbildung 6). Diskutieren Sie, inwiefern sich diese Aufgabe von den beiden vorherigen Integrationen unterscheidet.

Abbildung 6: Darstellung der Polynome p1(x) (blau) und p2(x) (rot).Abbildung 6: Darstellung der Polynome p1(x) (blau) und p2(x) (rot).

H) Diskutieren Sie:

  • Wie groß sollte man etwa die "Dichte" der Punkte pro Einheitsintervall wählen, um die Integrale auf zwei Nachkommastellen genau zu berechnen?
  • Kann man aus den Beispielen eine Folgerung ziehen, ob die Näherung für das Integral mit den Gitterpunkten oder den Zufallspunkten besser ist?

Berechnungen am Schachbrett

1. Das n×m-Schachbrett

Ein n×m-Schachbrett besteht offensichtlich aus n · m Feldern.

Die Berechnung der Anzahl der Felder des n×m-Schachbrettes soll rekursiv auf die Berechnung der Anzahl der Felder des (n-1)×(m-1)-Schachbrettes zurückgeführt werden.

Als Abbruchbedingung kann dabei verwendet werden:

  • Ist n = 1, dann hat das Schachbrett m Felder,
  • ist m = 1, dann hat das Schachbrett n Felder.

Implementieren Sie eine Funktion fields(int n, int m) , die die Anzahl der Felder rekursiv berechnet.

2. Anzahl der Quadrate, die ein n×n-Schachbrett enthält

Es ist klar, dass ein n×n-Schachbrett genau n2 Felder enthält. Aber wie viele Quadrate kann man auf dem Schachbrett bilden?

Für kleine n kann man dies leicht abzählen und erhält:

  • n = 1: 1 Quadrat
  • n = 2: 5 Quadrate (4 mit Seitenlänge 1, eines mit Seitenlänge 2).

Implementieren Sie eine Funktion squares(int n), die zu einer gegebenen Seitenlänge des Schachbrettes die Anzahl der in ihm enthaltenen Quadrate berechnet.

Hinweis: Achten Sie darauf, keine Quadrate mehrfach zu zählen.

Züge von Schachfiguren

Die 8 × 8 Felder eines Schachbrettes werden mit 0, 1, ..., 63 bezeichnet, wie es in der folgenden Tabelle zu sehen ist.

0 1 2 3 4 5 6 7
8 9 10 11 12 13 14 15
16 17 18 19 20 21 22 23
24 25 26 27 28 29 30 31
32 33 34 35 36 37 38 39
40 41 42 43 44 45 46 47
48 49 50 51 52 53 54 55
56 57 58 59 60 61 62 63

Ein Läufer kann entlang der Diagonalen ziehen, ein Turm kann nur geradeaus ziehen. Die Dame vereinigt die Zugmöglichkeiten von Läufer und Turm.

Gesucht sind Funktionen für folgende Aufgaben:

  • Wie viele mögliche Züge kann eine Figur (Dame, Turm, Läufer) ausführen, wenn sie auf einem gegebenen Feld steht. Dabei kann sie nicht auf das Feld ziehen, auf dem sie gerade steht und es wird angenommen, dass keine andere Figur im Weg steht.
  • Auf welche Felder kann eine Figur ziehen, wenn sie auf einem gegebenen Feld steht? (Annahmen wie oben)

Implementieren Sie diese Funktionen und diskutieren Sie, welchen geeigneten Funktionskopf die entsprechenden Funktionen haben.

Durch die Nutzung dieser Website erklären Sie sich mit der Verwendung von Cookies einverstanden. Außerdem werden teilweise auch Cookies von Diensten Dritter gesetzt. Genauere Informationen finden Sie in unserer Datenschutzerklärung sowie im Impressum.