Aufgaben

Es wird nicht erwartet, dass Sie alle Aufgaben schnell während des Kurses runterschreiben. Es sind mit Absicht viele, es reicht wenn Sie etwa die Hälfte (gründlich) bearbeiten.

Grün markierte sind das Minimalprogramm, die sollten auf jeden Fall bearbeitet werden. Rot gekennzeichnete sind anspruchsvoller und v.a. für diejenigen gedacht, die schon Programmierkenntnisse mitbringen.

Warmlaufübungen
- Erstellen Sie das "Hello world" Programm im Editor, dann kompilieren und ausführen.
- Dasselbe mit der "Fahrenheit/Celsius" Konversion
  modifizieren Sie es: Schrittweite, Bereich, umdrehen in Celsius $\Rightarrow$ Fahrenheit.
Quadrat– und Kubik–Zahlen
(a) Erstellen Sie ein Programm, dass die Quadrat– und Kubik–Zahlen von 1 bis 150 ausgibt und am Ende die Summe der Quadrat– bzw. Kubik–Zahlen
(b) Demonstrieren Sie folgende mathematische Identität für :

$\ensuremath{\displaystyle \sum_{i=1}^n i^3 = \left( \sum_{i=1}^n i \right)^2}$
Integer und Fließkommazahlen Machen Sie sich mit der binär– bzw. hexadezimal-Darstellung von Zahlen vertraut.
(a)
Drucken Sie Integerzahlen z.B. von -10 – 10:
```
#include <iostream>
#include <iomanip>
using namespace std; // declare namespace
int main()
{
  for ( int i=-10;i<=10;i++) 
    cout <<dec <<setw(6) <<i <<setw(10) <<hex <<i <<endl; 
}   // end-main
```
(b)
Drucken Sie Floating-point-zahlen z.B. von -1/16 – 16:
```
#include <cstdio>
#include <cmath>
using namespace std; // declare namespace
int main()
{
  union { long l; double x; } u;  // ugly hack
  for ( int i=-4;i<=4;i++) {
    u.x = pow(2., i);
    printf("%f %lX \n", u.x, u.l );
  }
}   // end-main
```
Hinweis: Rückgriff auf C-printf() um double Zahlen in hex auszugeben
(c)

Lassen Sie das Programm tdouble.cpp laufen.
Warum "können Rechner nicht rechnen" ?

(d)

Genauigkeit von double Operationen: Reduzieren Sie schrittweise
double eps = 1.;
while (...)
   eps /= 2.;
addieren Sie's zu
   onePlusEps = 1.0 + eps;
solange bis
   if ( onePlusEps == 1.0 ) ...

Analog für float (32-bit floating-point Zahlen)
Bit Operationen
Programmieren Sie die binäre Ausgabe von Integerzahlen mit Hilfe von Bit Operationen.
z.B.: 5 -> 101
Hinweis: Bit 15 in n abfragen mit z.B.: if ( ( ( 1 <<15) & n ) != 0 )
Fibonacci–Zahlen
Fibonacci–Zahlen spielen eine wichtige Rolle in der Zahlentheorie und haben viele interessante Eigenschaften. Sie sind definiert als: $\ensuremath{\displaystyle F_n = F_{n-1} + F_{n-2};\, F_0 = 0, \,F_1 = 1}$
(a) Erstellen Sie eine Liste der Fibonacci–Zahlen. Bis zu welchem kann man es in C++ mit long berechnen ?
(b) Demonstrieren Sie dass gilt: $\ensuremath{\displaystyle F_{n+1} \cdot F_{n-1} - F_n^2 = (-1)^n}$
Prim–Zahlen
(a) Erstellen Sie ein Programm, das testet ob eine gegebene Zahl eine Primzahl ist.
(b) Erweitern Sie das Programm, so dass es abzählt wieviele Primzahlen es gibt, die kleiner als eine vorgegebene Zahl sind, z.B. $1\,000\,000$ .
Hinweis: Es geht nicht darum einen schnellen Algorithmus zu finden, machen Sie's so simpel wie möglich.
(c) Sieb des Erasthones ist ein klassisches Verfahren zur Bestimmung aller Primzahlen zwischen $\ensuremath{ 2}$ und $\ensuremath{ n}$ . Der Algorithmus geht folgendermassen:
- Erstelle Liste aller Zahlen von $\ensuremath{ 2}$ bis $\ensuremath{ n}$
- Nimm schrittweise jede Zahl $\ensuremath{ i}$ dieser Liste, falls sie nicht gestrichen ist.
- Streiche alle Vielfachen von $\ensuremath{ i}$ aus der Liste
Am Ende bleiben genau die Primzahlen übrig in der Liste. (Tipp: Im Programm Liste am besten als bool array implementieren, Test auf Vielfaches mit modulo Operator: m%i == 0 )
Lineare Algebra
(a) Vektoroperationen: Legen Sie 2 Arrays mit den Elementen { 0.3, 1.8, -2.2} bzw { -2.5, 3.8, 0.4} an und berechnen Sie das Skalarprodukt und das Vektorprodukt.
(b) Erstellen Sie Funktionen zur Berechnung von Skalar- und Vektorprodukt. Welches Problem tritt bei der Funktion für Vektorprodukt auf?
(c) Matrixmultiplikation: Schreiben Sie ein Programm zur Multiplikation dieser beiden Matrizen:
double C[3][3] = { { 0.61, 0.24, 1.16 }, { 0.14, -0.82, 0.92 }, { -1.25, 0.96, -0.23 } };
double D[3][3] = { { 0.40, -0.68, -0.68 }, { 0.65, -0.75, 0.23 }, { 0.52, 0.51, 0.31 } };
Pointer
(a) Was macht folgender C++ Code?
```
#include <iostream>
using namespace std;
int main ()
{
  int i = 42, j = 1024;
  int *p1 = &i, *p2 = &j;
  *p2 = *p1 * *p2;
  *p1 *= *p1;
}
```
(b) Das Programm tpointer.cpp enthält eine kryptische Mischung aus Pointer- und Zahlen-Arithmetik, die aber für C Programme durchaus typisch ist. Gehen Sie das Prgramm durch und versuchen Zeile für Zeile vorherzusagen was passiert. Anschliessend mit cout ... Ausgaben überprüfen oder im Debugger ( ddd) laufen lassen.
Funktion für Fakultät
Schreiben Sie eine Funktion fak( int n), zur Berechnung der Fakultät . Machen Sie jeweils eine Version die einen long, float, double Wert zurückgibt lfak(n), ffak(n), dfak(n).
Bis zu welchem lässt sich bei den jeweiligen Typen berechnen ?
Verwenden Sie dabei unterschiedliche Algorithmen: Schleife und rekursive Aufrufe.
Power Funktion
Schreiben Sie eine Funktion power( double x, int n), die ganzzahlige Potenzen () berechnet.
(a) Rufen Sie die power(x,n) Funktion in einem Hauptprogramm, das zunächst Werte für x sowie n von stdin (Tastatur) einliest. Das geht im Prinzip ganz einfach:
cin >>x; cin >>n;
(b) x und y sollen als Argumente übergeben werden: main( int argc, char** argv)
Dazu muss man die character strings in argv in double bzw int umwandeln, z.B. mittels:
double x = atof(argv[1]);
int n = atoi(argv[2]);
Swap Funktion
Programmieren Sie eine Funktion swap( sometype x, sometype y), die bei Aufruf swap( a, b) die Werte der Argumente vertauscht, d.h anschliessend enthält a den ursprünglichen Wert von b und umgekehrt.
Funktionen
Gehen Sie die Programme funcarg.cpp und funcovl.cpp durch, versuchen Sie die Ausgabe bei jedem Schritt vorauszusagen bevor Sie es laufen lassen.
Rekursive Funktion
Ein Paradebeispiel für Rekursion ist Euklid's Algorithmus zur Bestimmung des
Größten Gemeinsamen Teilers zweier Zahlen $\bgroup\color{blue}$GGT( a, b)$\egroup$ .

$\bgroup\color{blue}$\displaystyle GGT(a,b) = \left\{ \begin{array}{rl} GGT( b, a... ...}\,\mathrm {teilbar\, ist} \\ b & \mathrm {sonst} \end{array} \right. $\egroup$

Erstellen Sie eine solche Funktion in C++
Lean Programming
Existierender C code ist oft knapp bis kryptisch; hier ein Beispiel
```
     double x[10];
     double *p = &x[10];
     while ( p != x) *--p = 0.0;
```
Können Sie's nachvollziehen ?
Wem das zu läppisch ist soll's mal hiermit versuchen: gedicht.c
(Wer's nicht gleich versteht, einfach mal kompilieren und laufen lassen ... gcc -o gedicht gedicht.c verwenden)
Zahlen einlesen und sortieren
In der Datei numbers.dat finden Sie eine Liste mit 100 Fließkommazahlen.

(a)

Lesen die Zahlen in einen Array oder STL Vector ein ein. (File-I/O in C++ siehe I/O Basics)

(b)

Finden Sie kleinsten und größten Wert.

(c)

Verwenden Sie die C Standardfunktion qsort um die Zahlen zu sortieren und sortiert auszugeben.

(d)

Alternativ können Sie den STL Algorithmus sort verwenden um die Zahlen zu sortieren und sortiert auszugeben.
Hinweis: #include <algorithm>
Advent of Code 2020 Aufgabe 1
Gutes Programmier-Training ist das alljährliche advent-of-code. Hier die Einstiegs-Aufgabe aus 2020:
In aoc1.dat finden Sie Liste von Zahlen.
(a) Finden Sie die beiden Zahlen deren Summe 2020 ergibt.
(b) Finden Sie die drei Zahlen deren Summe 2020 ergibt.
Fehlersuche
(a) Im Verzeichnis BadCode finden Sie einige simple C++ source files, die entweder typische Fehler beim Kompilieren, Linken oder Ausführen verursachen, oder zumindest Warning–Messages erzeugen, wenn man zum Kompilieren die Optionen -O -Wall verwendet:
g++ -O -Wall -c xxx.C
Versuchen Sie jeweils den Fehler oder das Problem herauszufinden und zu korrigieren.
(b) Folgendes Programm zum Primzahlen-Zählen wurde sehr nachlässig geschrieben, es enthält etliche Compiler- und Syntax-fehler. Korrigieren Sie die Fehler und bringen Sie das Programm zum Laufen.
```
bool isPrime(long i)
{
  for( long test = 2; test < i; test++) {
    if(i%test = 0) {
      return false;
    }
  }       
  return true;
}
    
int Main()
{ // count number of prime numbers smaller than n_loops
  long n_loops =  50000,
  Long n_primes;
  for( long i = 0, i < n_1oops; i++) {
    if( isprime(i) ) {
      n_primes++;
    }
    cout << n_primes << " primes found " << endl;
    }
}
```
Advent-of-Code 2019-4
Advent-of-Code ist jährliche Programmier-Challenge zur Adventszeit (https://adventofcode.com). Die Aufgaben der ersten Tage sind noch halbwegs machbar, hier ein Beispiel vom 4. Tag 2019:
Guessing 6–digit password
- digit range: 197487-673251
- Two adjacent digits are the same (like 22 in 122345).
- Going from left to right, the digits never decrease; they only ever increase or stay the same (like 111123 or 135679).
Other than the range rule, the following are true:
- 111111 meets these criteria (double 11, never decreases).
- 223450 does not meet these criteria (decreasing pair of digits 50).
- 123789 does not meet these criteria (no double).
(a) How many different passwords within the range given in your puzzle input meet these criteria?
Further rule: the two adjacent matching digits are not part of a larger group of matching digits.
- 112233 meets these criteria because the digits never decrease and all repeated digits are exactly two digits long.
- 123444 no longer meets the criteria (the repeated 44 is part of a larger group of 444).
- 111122 meets the criteria (even though 1 is repeated more than twice, it still contains a double 22).
(b) How many different passwords within the range given in your puzzle input meet all of the criteria?