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

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

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

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:

Beispiele:

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

Die Zahl 2020 ist sich selbst beschreibend:

0 1 2 3
2 0 2 0

Die Zahl x = 6210001000 ist sich selbst beschreibend, da

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
  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));
	int random_value;

	for (int i = 0; i < n; ++i) {
		random_value = 1 + rand() % 6;
		printf(" %d ", random_value);
	}
}

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:

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:

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:

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:

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

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

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

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,

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:

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:

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:

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:

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

Quadratische Formen

Abbildung 7 zeigt in Gleichung (1), wie eine quadratische 2×2-Matrix eine quadratische Form induziert; die Definition kann leicht für beliebige Dimensionen verallgemeinert werden, was hier nicht diskutiert wird.

Abbildung 7: Definition einer quadratischen Form und drei Beispiele für 2×2-Matrizen.Abbildung 7: Definition einer quadratischen Form und drei Beispiele für 2×2-Matrizen.

In Gleichung (2) sind drei Beispiele von 2×2-Matrizen gezeigt, für die folgende Programmier-Aufgaben gelöst werden sollen.

Hinweis:

Die folgenden Abbildungen 8 bis 11 sollen die quadratischen Formen veranschaulichen. Dazu zeigt

Abbildung 8: Darstellung der von A<sub>1</sub> erzeugten quadratischen Form als Gebirge über der xy-EbeneAbbildung 8: Darstellung der von A1 erzeugten quadratischen Form als Gebirge über der xy-Ebene

Abbildung 9: Die Functionswerte der quadratischen Form aus Abbildung 8 für Punkte (x, y) auf dem Einheitskreis (als Histogramm).Abbildung 9: Die Functionswerte der quadratischen Form aus Abbildung 8 für Punkte (x, y) auf dem Einheitskreis (als Histogramm).

Abbildung 10: Darstellung analog zu Abbildung 8 für die von der Matrix A<sub>2</sub> erzeugte quadratische Form.Abbildung 10: Darstellung analog zu Abbildung 8 für die von der Matrix A2 erzeugte quadratische Form.

Abbildung 11: Darstellung analog zu Abbildung 9 für die von der Matrix A<sub>2</sub> erzeugte quadratische Form.Abbildung 11: Darstellung analog zu Abbildung 9 für die von der Matrix A2 erzeugte quadratische Form.