Informatik I - Übung 5

Pascal Schärli

pascscha@student.ethz.ch

22.03.2019

Was gibts heute?

  • Self-Assesment
  • Nachbesprechung
  • Best-Of Vorlesung:
    • Pre/Post Conditions
    • Funktionen
    • Stepwise Refinment (&Program of the Week)
  • Vorbesprechung

Pascal Schärli 22.03.2019

Self-Assesment

Pascal Schärli 22.03.2019

Nachbesprechung

Pascal Schärli 22.03.2019

Bild: look again by corpus delicti from the Noun Project

Loop Analysis

Pascal Schärli 22.03.2019

unsigned int n;
std::cin >> n;

unsigned int x = 1;
if (n > 0) {
  unsigned int k = 0;
  bool e = true;
  do {
    if (++k == n) { 
      e = false;
    }
    x *= 2;
  } while(e);
}
std::cout << x << std::endl;

Was berechnet diese Programm?

\(2^n\)

Was ist der Wertebereich für n?

\(n \in [0\dots 31]\)

Zeige, das das Programm für alle \(n \in [0 \dots 31]\) terminiert

Das Programm terminiert für \(n = 0\) wegen dem if-Block.

Für \(n \in [1 \dots 31], n \in \mathbb{N} \) ist (\k\) streng monoton steigend mit Startwert 0.

Daher muss irgendwann \(k = n \) gelten und das Programm terminiert.

Vorlesung

Pascal Schärli 22.03.2019

Pre / Post Conditions

Pascal Schärli 22.03.2019

double f (double i,
          double j,
          double k) {

    if (i > j) {
        if (i > k) {
            return i;
        }
        else{
            return k;
        }
    }
    else {
        if (j > k) {
            return j;
        }
        else {
            return k;
        }
    }
}

Precondition:

Postcondition:

Nicht nötig

// POST: return value is
//        the maximum of
//        i,j and k

Pre / Post Conditions

Pascal Schärli 22.03.2019

double g (int i, int j) {
    double r = 0.0;
    for (int k = i; k <= j; ++k){
        r += 1.0 / k;
    }
    return r;
}

Precondition:

Postcondition:

// POST: return value is the sum
//        1/i + 1/(i+1) + ... + 1/j
// PRE: 0 not contained
//       in {i, ..., j}

Funktionen

#include <iostream>

int f (int i) {
    return i * i;
}

int g (int i) {
    return i * f(i) * f(f(i));
}

void h (int i) {
    std::cout << g(i) << "\n";
}

int main () {
    int i;
    std::cin >> i;
    h(i);
    return 0;
}

Was ist der Output von diesem Programm, vorausgesetzt es gibt keine Overflows?

  i *  f(i)  *   f( f(i) )

\(= i ^{7}\)

Pascal Schärli 22.03.2019

  i *  f(i)  *   f( f(i) ) 
= i *  (i*i) *   f( f(i) ) 

  i *  f(i)  *   f( f(i) ) 
= i *  (i*i) *   f( f(i) ) 
= i *  (i*i) *   f(  i*i )
  i *  f(i)  *   f( f(i) ) 
= i *  (i*i) *   f( f(i) ) 
= i *  (i*i) *   f(  i*i )
= i *  (i*i) *  ((i*i)*(i*i))

Perfect Numbers

Eine "Perfekte" Zahl ist eine Zahl, welche gleich der Summe all ihrer Teiler ist.

Beispiel:

  1. \(28 = 1 + 2 + 4 + 7 + 14\) ist perfekt
  2. \( 12 < 1 + 2 + 3 + 4 + 6 \) ist nicht perfekt.

 

"Skizziert" auf Papier eine Funktion, welches Zählt, wie viele dieser Perfekten Zahlen in einem Intervall [a,b] existieren.
 

#include <iostream>
#include "perfect.h"

bool is_perfect(unsigned int number) {
    // [...]
}

unsigned int count_perfect( unsigned int a,
                            unsigned int b) {
    // [...]
}

int main () {
    // input
    unsigned int a;
    unsigned int b;
    std::cin >> a >> b;

    // computation and output
    unsigned int count = count_perfect(a, b);
    
    // output
    std::cout << count << std::endl;
		
    return 0;
}

Pascal Schärli 22.03.2019

Perfect Numbers

#include <iostream>
#include "perfect.h"

bool is_perfect(unsigned int number) {
    unsigned int sum = 0;
    for (unsigned int d = 1; d < number; ++d) {
        if (number % d == 0) {
            sum += d;
        }
    }
    return sum == number;
}

unsigned int count_perfect( unsigned int a,
                            unsigned int b) {
  unsigned int count = 0;
  for (unsigned int i = a; i <= b; ++i) {
    if (is_perfect(i)) {
      std::cerr << i << std::endl;
      count++;
    }
  }
  return count;
}

Pascal Schärli 22.03.2019

Stepwise Refinment

Pascal Schärli 22.03.2019

Grosse Aufgaben von Grund auf zu programmieren kann häufig überwältigend wirken

  • Wo soll man starten?
  • Was für Funktionen brauchen wir?
  • Wie soll man das Programm strukturieren?

 

Diese grossen Aufgaben können in kleine überschaubare Probleme aufgeteilt werden. \(\rightarrow\) stepwise approach

Stepwise Refinment

Pascal Schärli 22.03.2019

Vorgehensweise

  1. Gliederung
    Grobe Struktur mit Kommentaren
  2. Verfeinern
    1. Genauere Kommentare
    2. Programmieren
    3. (Hypothetische) Funktionsaufrufe

Pascal Schärli 22.03.2019

Program of the Week

Stepwise Refinment

Pascal Schärli 22.03.2019

int main(){
        // Initialize Variables






	// Play Game
















        
        // Check who won






	
	return 0;
}

int main(){
        // Initialize Variables:
        //     1. Number of Sticks to start with
        //     2. Starting player




    	// Play Game:
        //     Loop while Game hasn't finished:
        //        1. Display Sticks that are left to User
        //        2. Check who's turn it is and let that instance play
        //        3. Perform the move and notify the user
        //        4. Change who's turn it is











        
        // Check who won






	
	return 0;
}

int main(){
	//The number of sticks at the start of the game
	unsigned int sticksLeft = 17;

	//Indicates wether the computer can start or not.
	bool computersTurn = true;


    	// Play Game:
        //     Loop while Game hasn't finished:
        //        1. Display Sticks that are left to User
        //        2. Check who's turn it is and let that instance play
        //        3. Perform the move and notify the user
        //        4. Change who's turn it is











        
        // Check who won






	
	return 0;
}
int main(){
	//The number of sticks at the start of the game
	unsigned int sticksLeft = 17;

	//Indicates wether the computer can start or not.
	bool computersTurn = true;


	while(sticksLeft > 0){
		// Display game state
		
                
                // Let correct instance play









		//Switch players

	}

	 // Check who won






	
	return 0;
}

int main(){
	//The number of sticks at the start of the game
	unsigned int sticksLeft = 17;

	//Indicates wether the computer can start or not.
	bool computersTurn = true;


	while(sticksLeft > 0){
		// Display game state
		printSticks(sticksLeft);

		if(computersTurn){ // Computer plays



		}
		else{ // Human plays



		}
		//Switch players
		computersTurn = !computersTurn;
	}

	 // Check who won






	
	return 0;
}

int main(){
	//The number of sticks at the start of the game
	unsigned int sticksLeft = 17;

	//Indicates wether the computer can start or not.
	bool computersTurn = true;


	while(sticksLeft > 0){
		// Display game state
		printSticks(sticksLeft);

		if(computersTurn){ // Computer plays
			unsigned int amount =  computerPlayer(sticksLeft);
			std::cout << "The computer takes " << amount << " sticks." << std::endl;
			sticksLeft -= amount;
		}
		else{ // Human plays
			unsigned int amount =  humanPlayer(sticksLeft);
			std::cout << "You take " << amount << " sticks." << std::endl;
			sticksLeft -= amount;
		}
		//Switch players
		computersTurn = !computersTurn;
	}

	 // Check who won






	
	return 0;
}

int main(){
	//The number of sticks at the start of the game
	unsigned int sticksLeft = 17;

	//Indicates wether the computer can start or not.
	bool computersTurn = true;


	while(sticksLeft > 0){
		// Display game state
		printSticks(sticksLeft);

		if(computersTurn){ // Computer plays
			unsigned int amount =  computerPlayer(sticksLeft);
			std::cout << "The computer takes " << amount << " sticks." << std::endl;
			sticksLeft -= amount;
		}
		else{ // Human plays
			unsigned int amount =  humanPlayer(sticksLeft);
			std::cout << "You take " << amount << " sticks." << std::endl;
			sticksLeft -= amount;
		}
		//Switch players
		computersTurn = !computersTurn;
	}


        if(computersTurn){
		std::cout << "The computer won, too bad." << std::endl;
	}
	else{
		std::cout << "You won, congratulations!" << std::endl;
	}
	
	return 0;
}
  1. Gliederung
    Grobe Struktur mit Kommentaren
  2. Verfeinern
    1. Genauere Kommentare
    2. Programmieren
    3. (Hypothetische) Funktionsaufrufe
  1. Gliederung
    Grobe Struktur mit Kommentaren
  2. Verfeinern
    1. Genauere Kommentare
    2. Programmieren
    3. (Hypothetische) Funktionsaufrufe
  1. Gliederung
    Grobe Struktur mit Kommentaren
  2. Verfeinern
    1. Genauere Kommentare
    2. Programmieren
    3. (Hypothetische) Funktionsaufrufe
  1. Gliederung
    Grobe Struktur mit Kommentaren
  2. Verfeinern
    1. Genauere Kommentare
    2. Programmieren
    3. (Hypothetische) Funktionsaufrufe

Stepwise Refinment

Pascal Schärli 22.03.2019

//PRE:  Number of sticks that are left on the field
//POST: the number of sticks n the user wants to take.
//      1 >= n >= 3
int humanPlayer(int sticksLeft){
        // Tell User what to do	


        // Ask for input until valid input is given
	








        // return user input
}
//PRE:  Number of sticks that are left on the field
//POST: the number of sticks n the user wants to take.
//      1 >= n >= 3
int humanPlayer(int sticksLeft){
        // Tell User what to do	


        // Ask for input until valid input is given
        //    1. Ask for input
        //    2. Notify user if input is invalid	
        //    3. Repeat until valid input






        // return user input
}
//PRE:  Number of sticks that are left on the field
//POST: the number of sticks n the user wants to take.
//      1 >= n >= 3
int humanPlayer(int sticksLeft){
        std::cout << "How many sticks would you like to take? ";
        int nSticks;

        // Ask for input until valid input is given
        //    1. Ask for input
        //    2. Notify user if input is invalid	
        //    3. Repeat until valid input






        // return user input
}
//PRE:  Number of sticks that are left on the field
//POST: the number of sticks n the user wants to take.
//      1 >= n >= 3
int humanPlayer(int sticksLeft){
        std::cout << "How many sticks would you like to take? ";
        int nSticks;

        do {
        //    1. Ask for input
        //    2. Notify user if input is invalid	
        




        } while(nSticks < 1 or nSticks > 3 or nSticks > sticksLeft);

        // return user input
}
//PRE:  Number of sticks that are left on the field
//POST: the number of sticks n the user wants to take.
//      1 >= n >= 3
int humanPlayer(int sticksLeft){
        std::cout << "How many sticks would you like to take? ";
        int nSticks;

        do {
            std::cin>> nSticks;
            if(nSticks < 1 or nSticks > 3){
		std::cout << "Please enter a value between 1 and 3. ";
	    }
	    else if(nSticks > sticksLeft){
		std::cout << "There are only " << sticksLeft << " sticks left. ";
	    }
        } while(nSticks < 1 or nSticks > 3 or nSticks > sticksLeft);

        // return user input
}
//PRE:  Number of sticks that are left on the field
//POST: the number of sticks n the user wants to take.
//      1 >= n >= 3
int humanPlayer(int sticksLeft){
        std::cout << "How many sticks would you like to take? ";
        int nSticks;

        do {
            std::cin>> nSticks;
            if(nSticks < 1 or nSticks > 3){
		std::cout << "Please enter a value between 1 and 3. ";
	    }
	    else if(nSticks > sticksLeft){
		std::cout << "There are only " << sticksLeft << " sticks left. ";
	    }
        } while(nSticks < 1 or nSticks > 3 or nSticks > sticksLeft);

        return nSticks;
}

Stepwise Refinment

Pascal Schärli 22.03.2019

//PRE:  Number of sticks that are left on the field
//POST: the number of sticks n the computer wants to take.
//      1 >= n >= 3
int computerPlayer(int sticksLeft){
        // calculate number of returned sticks

        // check that calculated number is legal



	// return calculated amount
}
//PRE:  Number of sticks that are left on the field
//POST: the number of sticks n the computer wants to take.
//      1 >= n >= 3
int computerPlayer(int sticksLeft){
        int amount = (sticksLeft-1) % 4;

        // check that calculated number is legal



	// return calculated amount
}
//PRE:  Number of sticks that are left on the field
//POST: the number of sticks n the computer wants to take.
//      1 >= n >= 3
int computerPlayer(int sticksLeft){
        int amount = (sticksLeft-1) % 4;

        if(amount == 0){
	    amount = 1;
	}

	// return calculated amount
}
//PRE:  Number of sticks that are left on the field
//POST: the number of sticks n the computer wants to take.
//      1 >= n >= 3
int computerPlayer(int sticksLeft){
        int amount = (sticksLeft-1) % 4;

        if(amount == 0){
	    amount = 1;
	}

	return amount;
}

Vorbesprechung

Pascal Schärli 22.03.2019

1: Perpetual calender

Pascal Schärli 15.03.2019

Was für ein Wochentag war am 22.05.1996?

Schreibt ein Programm, welches zu einem beliebigen Datum den Wochentag herausfinden kann.

Tipps:

  • Teilt die komplexe Aufgabe in kleine machbare Teilschritte auf. (Stepwise Refinment)
  • Es gibt die Gaußsche  Wochentagsformel, die darf man aber nicht verwenden.

2: Run-Length Encoding

Pascal Schärli 15.03.2019

0 0 0 0 0 0 0 0 0
1 1 1 1 1 1 1 1 1 1 1
2 2 2 2 2 2 2 2 2 2 2
3 3 3 3 3 3 3 3 3
4 4 4 4 4 4 4 4 
5 5 5 5 5 5 5 5 5 5 5 5
6 6 6 6 6 6 6 6 6 6 
7 7 7 7 7 7 7 7 7 7 
8 8 8 8 8 8 8
9 9 9 9 9 9 9 9 9 9 9 9 9

\(9\cdot "0", 11\cdot "1" ,\)

\(11\cdot "2", 9\cdot "3",\)

\(8 \cdot"4", 12\cdot "5", \)

\(12\cdot "6", 8\cdot "7",\)

\(7\cdot "8", 13\cdot "9" \)

 9 0 11 1
11 2  9 3
 8 4 12 5
12 6  8 7
 7 8 13 9

In dieser Aufgabe bauen wir uns einen Algorithmus um Byte-Sequenzen zu Komprimieren

2: Run-Length Encoding Tipps

Pascal Schärli 15.03.2019

0 0 0 0 0 0 0 0 0
1 1 1 1 1 1 1 1 1 1 1
2 2 2 2 2 2 2 2 2 2 2
3 3 3 3 3 3 3 3 3
4 4 4 4 4 4 4 4 
5 5 5 5 5 5 5 5 5 5 5 5
6 6 6 6 6 6 6 6 6 6 
7 7 7 7 7 7 7 7 7 7 
8 8 8 8 8 8 8
9 9 9 9 9 9 9 9 9 9 9 9 9
 9 0 11 1
11 2  9 3
 8 4 12 5
12 6  8 7
 7 8 13 9

Decode:

Wiederhole bis -1:

  1. Lese Anzahl Wiederholungen n
  2. Lese Wert b
  3. Gib Wert b genau n-mal aus

 

Encode:

Wiederhole bis -1:

  1. Setze Counter c auf 1
  2. Lies Wert b
  3. Lies so lange b, bis anderer Wert kommt & erhöhe Counter
  4. Output: Counter Wert 
// POST: returns true if 0 <= value <= 255, otherwise false
bool is_byte(int value){/*...*/}

// PRE:  1 <= runlength <= 255, and value is a byte.
// POST: outputs run length encoded bytes of tuple
void output(unsigned int run_length,
            unsigned int value){/*...*/}

// POST: reads byte sequence and outputs encoded bytes
void encode(){/*...*/}


// POST: reads byte sequence and outputs decoded bytes
void decode(){/*...*/}

3: Run-Length Encoding Reloaded

Pascal Schärli 15.03.2019

0 1 2 3 4 5 6 7 8 9
1 0 1 1 1 2 1 3 1 4 1 5 1 6 1 7 1 8 1 9

Für Bytes mit run-length 1 (keine Wiederholung) ist der Algorithmus sehr ineffizient.

X

X

X

X

X

X

X

X

0: Einzelner Wert

1: Run-Length

Wert / Run-Length

3: Run-Length Encoding Reloaded

Pascal Schärli 15.03.2019

0 0 1 2

Sequenz Dezimal

00000000
00000000
00000001
00000010
10000020
00000000
00000001
00000010
130 1 2
200 20 20 20
11001000
00010100
00010100
00010100
10000001
11001000
10000011
00010100
129 200 131 20

Sequenz Binär

Encoding Binär

Encoding Dezimal

Sequenz Dezimal

Sequenz Binär

Encoding Binär

Encoding Dezimal

Viel Spass!

Pascal Schärli 22.03.2019