Informatik I - Ãœbung 6

Pascal Schärli

pascscha@student.ethz.ch

29.03.2019

Was gibts heute?

  • Nachbesprechung
  • Best-Of Vorlesung:
    • Floats
    • Vectors
    • Referenzen
    • Constants
    • Characters
  • Vorbesprechung

Pascal Schärli 29.03.2019

Nachbesprechung

Pascal Schärli 29.03.2019

Round

Pascal Schärli 15.03.2019

// PRE:  x is roundable to a number in
//        the value range of type int
// POST: return value is the integer 
//        nearest to x, or the one 
//        further away from 0 if x lies
//        right in between two integers.
int round (double x) {
    if(x > 0){
      return x + .5;
    }
    else{
      return x - .5;
    }
}

Vorlesung

Pascal Schärli 29.03.2019

Floats

Pascal Schärli 15.03.2019

\(F*(\beta , p, e_{min} , e_{max})\)

\(\beta = 2\)

\(p = 3\)

\(e_{min} = -4\)

\(e_{max} = 4\)

dez bin


+
=
+
=

(10 + 0.5) + 0.5

dez bin
10 1.01 * 2^3
+ 0.5 0.0001 * 2^3
= 10 1.01 * 2^3
+ 0.5 0.0001 * 2^3
=
10 1.01 * 2^3

Floats

Pascal Schärli 15.03.2019

\(F*(\beta , p, e_{min} , e_{max})\)

\(\beta = 2\)

\(p = 3\)

\(e_{min} = -4\)

\(e_{max} = 4\)

dez bin
0.5 1.00 * 2^-1
+ 0.5 1.00 * 2^-1
= 1 1.00 * 2^0
+ 10 1010 * 2^0
= 12 1.10 * 2^3

(0.5 + 0.5) + 10

dez bin
+
=
+
=

Pascal Schärli 15.03.2019

  • Vektoren helfen in C++ Listen von Elementen abzuspeichern und zu verwalten.

 

  •  std::vector ist kein Primitiver Datentyp wie int oder bool
    \(\rightarrow\) sie haben noch weiter Funktionalität

 

  • Vektoren müssen zuerst mit #include <vector> aus der Standardbibliothek geladen werden.

Vektoren

Pascal Schärli 15.03.2019

  • Beim erstellen von einem neuen Vektor muss immer noch der zu speichernde Datentyp angegeben werden.
  • Bei Bedarf kann auch die Anzahl Elemente oder der Initialisierungswert gegeben werden.
std::vector<int> a;          // empty vector of ints

std::vector<float> b(5);     // five floats with value 0

std::vector<double> c(5,3);  // five doubles with value 3

Beispiele:

Vektoren

Pascal Schärli 15.03.2019

  • Mit der Funktion at kann man auf Elemente im Vektor zugreifen.
  • Wir haben Indizierung bei 0, das heisst das vorderste Element hat den Index 0.
#include <vector>
#include <iostream>

int main(){
    std::vector<int> values(5);
    for(int i = 0; i < 5; i++){
        values.at(i) = i * i;
    }

    // [..]
values -> [0, 1, 4, 9, 16]
  // [...]

  std::cout << values.at(3) << std::endl;
  values.at(0) = 5;
  std::cout << values.at(0) << std::endl;

  return 0;
}
Output:
3
5

Vektoren

Pascal Schärli 15.03.2019

Vektoren sind keine Primitive Datentypen. Sie haben noch weitere Funktionalitäten:

Name Rückgabe-Typ Funktionalität
size
unsigned int

Grösse (Länge) vom Vektor

empty
bool

true falls Vektor leer ist

push_back
void

Element am Ende hinzufügen

pop_back
void

Löscht letztes Element

back
T

Letztes Element im Vektor

Eine komplette Liste findet ihr hier unter "Member Functions"

Vektoren

Pascal Schärli 15.03.2019

#include <iostream>
#include <vector>

int main(){

    std::vector<int> test(5);
    test[1] = test.size();
    test.pop_back();
    test[2] = test.size();
    test.push_back(2);
    test[3] = test.empty();

    for(unsigned int i = 0; i < test.size(); i++){
        std::cout << test.at(i) << " ";
    }
    std::cout << std::endl;
	
    return 0;
}
0 5 4 0 2

Vektoren

Pascal Schärli 15.03.2019

std::vector<int> test(5);
0 0 0 0 0
0 5 0 0 0
0 5 0 0
0 5 4 0
0 5 4 0 2
0 5 4 0 2
std::vector<int> test(5);
test.at(1) = test.size();
std::vector<int> test(5);
test.at(1) = test.size();
test.pop_back();
std::vector<int> test(5);
test.at(1) = test.size();
test.pop_back();
test.at(2) = test.size();
std::vector<int> test(5);
test.at(1) = test.size();
test.pop_back();
test.at(2) = test.size();
test.push_back(2);
std::vector<int> test(5);
test.at(1) = test.size();
test.pop_back();
test.at(2) = test.size();
test.push_back(2);
test.at(3) = test.empty();

Vektoren

Pascal Schärli 15.03.2019

std::vector<int> v(5, 0);

v.at(5) = 3;

for(unsigned int i = 0; i < v.size(); i++){
    std::cout << v.at(i) << " ";
}
terminate called after throwing an instance
of 'std::out_of_range'

0

0

0

0

0

0

1

2

3

4

5

Indizierung bei 0 nicht vergessen! Bei Zugriff auf Daten, welche nicht existieren gibt es einen Fehler.

Inhalt

Index

Pascal Schärli 29.03.2019

#include <iostream>
#include <vector>
#include <ios>

// POST: Converts lowercase letters a-z to upper case A-Z
void char_to_upper(char& letter) {
  // TODO
}

// POST: Converts all letters to upper-case.
void to_upper(std::vector<char>& letters) {
  // TODO
}

int main () {
  // Say to std::cin not to ignore whitespace.
  std::cin >> std::noskipws;
  
  std::vector<char> letters;
  char ch;
  
  // Step 1: Read input.
  do {
    std::cin >> ch;
    letters.push_back(ch);
  } while (ch != '\n');
  
  // Step 2: Convert to upper-case.
  // TODO

  // Step 3: Output.
  // TODO
  
  return 0;  
}

Skizziert ein Programm, welches einen gegebenen Text in Grossbuchstaben umwanden kann:

H3llo World!
H3LLO WORLD!

Pascal Schärli 29.03.2019

// POST: Converts the letter to upper case.
void char_to_upper(char& letter) {
  if ('a' <= letter && letter <= 'z') {
    letter -= 'a' - 'A';  // 'a' > 'A'
  }
}
// POST: Converts all letters to upper-case.
void to_upper(std::vector<char>& letters) {
  for (unsigned int i = 0; i < letters.size(); ++i) {
    char_to_upper(letters[i]);
  }
}

Pascal Schärli 29.03.2019

int main () {
  // Say to std::cin not to ignore whitespace.
  std::cin >> std::noskipws;
  
  std::vector<char> letters;
  char ch;
  
  // Step 1: Read input.
  do {
    std::cin >> ch;
    letters.push_back(ch);
  } while (ch != '\n');
  
  // Step 2: Convert to upper-case.
  to_upper(letters);
  
  // Step 3: Output.
  for (unsigned int i = 0; i < letters.size(); ++i) {
    std::cout << letters[i];
  }
  return 0;
}

Referenzen

Pascal Schärli 29.03.2019

In C++ können wir existierende Variablen "Verlinken"

int a = 3;
int& b = a;
b = 2;
std::cout << a;
2

Referenzen

Pascal Schärli 29.03.2019

#include <iostream>

void foo(int a, int b){
    int temp = a;
    a = b;
    b = temp;
}

int main(){
    int a = 5;
    int b = 7;
    foo(a, b);
    std::cout << a << " " << b;
    return 0;
}
5 7
#include <iostream>

void foo(int& a, int& b){
    int temp = a;
    a = b;
    b = temp;
}

int main(){
    int a = 5;
    int b = 7;
    foo(a, b);
    std::cout << a << " " << b;
    return 0;
}
7 5

Call by Value

Call by Reference

Referenzen

Pascal Schärli 29.03.2019

Warum braucht es Referenzen überhaupt?

  • Referenzen erlauben uns mehrere Werte zurückzugeben in einer Funktion.

     
  • Die Ãœbergebenen Parameter müssen nicht kopiert werden.

     
  • Bestimmte Dinge können nicht kopiert werden.
void scale(double& x, double& y, double amount){
    x *= amount;
    y *= amount;
}
void read_i (Vector& v, unsigned int i);
std::ostream o = std::cout;
o << "It works!\n";
std::ostream& o = std::cout;
o << "It works!\n";
It works!
error

Referenzen

Pascal Schärli 29.03.2019

Der Rückgabetyp von Funktionen kann auch eine Referenz sein:

#include <iostream>

int square(int n){
    return n*=n;
}

int main(){
    int n = 3;
    square(square(n));

    std::cout << n;
    return 0;
}
3
#include <iostream>

int& square(int& n){
    return n*=n;
}

int main(){
    int n = 3;
    square(square(n));

    std::cout << n;
    return 0;
}
81
#include <iostream>

int square(int& n){
    return n*=n;
}

int main(){
    int n = 3;
    square(square(n));

    std::cout << n;
    return 0;
}
error: cannot bind 
non-const lvalue 
reference of type ‘int&’ 
to an rvalue of type ‘int’

Characters

Pascal Schärli 29.03.2019

Ein Character ist ein Buchstabe, welchen in C++ als 8-Bit Zahl gespeichert wird. Die Buchstaben sind mit ASCII Codiert.

"\n"
"\r"

Characters

Pascal Schärli 29.03.2019

char c1 = 'i';
std::cout << c1;
i
char c2 = 110;
std::cout << c2;
n
char c3 = c1 - 3;
std::cout << c3;
f
char c4 = c1 - 'a' + 'A';
std::cout << c4;
I

Pascal Schärli 29.03.2019

int main () {
  unsigned int length;
  std::vector<int> sequence (10);
  
  // Step 1: Read input.
  std::cin >> length;
  if (length > 10) {
    std::cout << "Bad input" << std::endl;
    return 0;
  }

  // TODO: Read Vector from std::cin
  
  // Reverse sequence;
  reverse(sequence, length);
  
  // TODO: Output Vector to std::cout
  
  return 0;
}

Skizziert ein Programm, welches einen gegebenen Vektor umdrehen kann.

0 1 2 3 4 5 6 7 8 9
// POST: the targets of i and j got their
//        values swapped
void swap (int& i, int& j) {
    // TODO
}

// PRE:  length is the real length of the
//        vector sequence.
// POST: Reverses the sequence stored in
//        the vector sequence.
void reverse(std::vector<int>& sequence,
             unsigned int length) {
    // TODO
}
9 8 7 6 5 4 3 2 1 0

Pascal Schärli 29.03.2019

// POST: the targets of i and j got their values swapped
void swap (int& i, int& j) {
    const int tmp = i;
    i = j;
    j = tmp;
}
// PRE: length is the real length of the vector sequence.
// POST: Reverses the sequence stored in the vector sequence.
void reverse(std::vector<int>& sequence, unsigned int length) {
  if (length > 1) {
    int front = 0;
    int back = length-1;
    while (front < back) {
      swap(sequence.at(front), sequence.at(back));
      ++front;
      --back;
    }
  }
}

Pascal Schärli 29.03.2019

int main () {
  unsigned int length;
  std::vector<int> sequence (10);
  
  // Step 1: Read input.
  std::cin >> length;
  if (length > 10) {
    std::cout << "Bad input" << std::endl;
    return 0;
  }
  for (unsigned int i = 0; i < length; ++i) {
    std::cin >> sequence.at(i);
  }
  
  // Step 2: Reverse sequence;
  reverse(sequence, length);
  
  // Step 3: Output
  for (unsigned int i = 0; i < length; ++i) {
    std::cout << sequence.at(i) << " ";
  }
  std::cout << std::endl;
  
  return 0;
}

Referenzen

Pascal Schärli 29.03.2019

#include <iostream>

int foo (int a, int b) {
    a += b;
    return a;
}

int main() {
    int a = 0;
    int b = 1;
    for (int i=0; i<5; ++i) {
        b = foo (a, b);
        std::cout << b << " ";
    }
    return 0;
}
1 1 1 1 1

Was ist der Output von diesem Programm?

Referenzen

Pascal Schärli 29.03.2019

#include <iostream>

int foo (int& a, int b) {
    a += b;
    return a;
}

int main() {
    int a = 0;
    int b = 1;
    for (int i=0; i<5; ++i) {
        b = foo (a, b);
        std::cout << b << " ";
    }
    return 0;
}
1 2 4 8 16

Was ist der Output von diesem Programm?

Referenzen

Pascal Schärli 29.03.2019

#include <iostream>

int foo (int a, int& b) {
    a += b;
    return a;
}

int main() {
    int a = 0;
    int b = 1;
    for (int i=0; i<5; ++i) {
        b = foo (a, b);
        std::cout << b << " ";
    }
    return 0;
}
1 1 1 1 1

Was ist der Output von diesem Programm?

Const

Pascal Schärli 15.03.2019

Mit dem Keyword const kann man bestimmen, dass gewisse Variabeln Konstant sind, sich also nicht veränderen können.

 

  • Das kann dazu führen, dass das Programm schneller läuft.
     
  • Bei komplizierteren Funktionen kann es helfen um sicherzugehen, dass bestimmte Werte sicher nirgends verändert werden.

Compile-Error

Pascal Schärli 15.03.2019

#include <iostream>

int foo(const int x){
	x = 5;
	return x;
}

int main(){

    std::cout << foo(3) << std::endl;
    
    return 0;
}
error: assignment of read-only parameter ‘x’

Runtime Error

Pascal Schärli 15.03.2019

#include <iostream>

int& foo(int x){
	x = 5;
	return x;
}

int main(){

    std::cout << foo(3) << std::endl;
    
    return 0;
}
Segmentation fault (core dumped)

Vorbesprechung

Pascal Schärli 29.03.2019

Pascal Schärli 29.03.2019

T foo (S i)
{
    return ++i;
}
1. T = int,        S = int
2. T = int,        S = const int
3. T = int,        S = int&
4. T = int&,       S = int
5. T = const int&, S = int&
  1. Sind die Funktionen Semantisch Korrekt
    (Tipp: Compile Errors)
  2. Falls ja, kann die Funktion auch fehlerfrei ausgeführt werden? (Tipp: Runtime Errors)
  3. Falls ja, gebt eine möglichst Präzise Post-Condition an.

Pascal Schärli 29.03.2019

Schreibt folgendes Programm:

  1. Lies so lange Integer ein, bis ein negativer Integer kommt und speichere diese (Ohne den negativen) in einem Vektor v
  2. Lies eine weitere Zahl n ein
  3. Zähle wie viele Male n im Vektor v vorkommt

Tipps:

  • Strukturiert das Programm in Funktionen

     
  • Benutzt keine Funktionen welche noch nicht besprochen wurden!
void read_vector(std::vector<int> & values) {/*...*/}
int occurrences(const std::vector<int> & values, int toFind) {/*...*/}

Pascal Schärli 29.03.2019

Schreibt folgendes Programm:

  1. Lies so lange Integer ein, bis ein negativer Integer kommt und speichere diese (Ohne den negativen) in einem Vektor v
  2. Bestimmt die Länge der längsten  streng monoton steigenden Untersequenz.
22 35 4 16 42 3 -1
3

Tipps:

Jetzt könnt ihr eure einlese-Funktion von der Aufgabe 2 wiederverwenden

Pascal Schärli 29.03.2019

Schreibt folgendes Programm:

  1. Lies einen Integer, welcher die Länge des Vektors festlegt
  2. Lies alle Werte vom Vektor ein
  3. Sortiere diese Werte mit Bubble Sort

Tipps:

  • Wenn ihr den Algorithmus nicht versteht gibt es online unzählige Erklärungen dazu
  • Ihr müsst eine eigene Print-Funktion für den Vektor machen

Program of the Week

Pascal Schärli 29.03.2019

Viel Spass!

Pascal Schärli 29.03.2019