Informatik W02

Levin Ceglie

Outline

• Admin
• Fragen zu den Aufgaben letzter Woche
• Repitition Vorlesung via Quiz
• Division und Modulo (Theorie und Aufgabe)
• Binärdarstellung
• Expressions
• Binärdarstellung von negativen ganzen Zahlen

Admin

Fragen aus letzter Woche

• Kann der Bonus von letztem Jahr übernommen werden?
  • Alle hatten recht :). Die Dozenten haben fälschlicherweise in der Vorlesung gesagt, dass man den Bonus aus dem letzten Jahr übertragen kann. In der Kursausschreibung (und auf den organisatorischen Slides) steht jedoch genau das Gegenteil. Leider hat hier die Kursausschreibung das letzte Wort und kann nicht mehr geändert werden. Also kann der Bonus aus dem letzten Jahr nicht übertragen werden.

Weiteres

• Die Testcases werden bei den Bonusaufgaben, sowie an der Prüfung am Ende durch ähnliche ausgetauscht um zu vermeiden, dass jemand die Antworten hard-coded.
• Wenn ihr ein warning vom Compiler kriegt in den Aufgaben, führt dies automatisch zu 0 Punkten (z.B. Eine Variable int a; zu initialisieren, aber sie nicht zu benutzen löst ein warning vom Compiler aus). Beachtet dies bei dem Lösen der Aufgaben.

Division und Modulo

Bei der Division mit int und unsigned int wird alles nach dem Punkt vergessen bzw. es wird immer abgerundet!

Division:

7 / 3 == 2
15 / 4 == 3
16 / 4 == 4
17 / 6 == 2

Modulo:

7 % 3 == 1
15 % 4 == 3
16 % 4 == 0
17 % 6 == 5

Bemerke: Durch Kombination der beiden Operatoren, kann man trotz Informationsverlust bei der Division die ursprüngliche Zahl wie folgt wieder bekommen

(15 % 4) * 4 + 15 % 4 == 15

Frage: Welche Frage beantwortet folgender Code:

int a;
std :: cin >> a;
if ( a % 2 == 0) {
	std :: cout << "Yes " << std :: endl;
} else {
	std :: cout << "No" << std :: endl;
}

Antwort: Ist die vom User eingegebene Zahl gerade?

Aufgabe (Even Number)

Schreibe ein C++ Programm, welches eine ganze Zahl $n$ einliesst und die nächst kleinere gerade Zahl (kann auch $n$ selbst sein) ausgiebt.
Input: Eine ganze Zahl $n$
Output:

• Falls $n\ge 0$, gebe die grösste gerade Zahl $m\le n$
• Falls $n<0$, gebe 0 aus

Beispiele: $2\to 2$, $15\to 14$, $-4\to 0$

Gemeinsame Implementation: ETH Code Expert.

Aufgabe (Last Three Digits)

Schreibe ein C++ Programm, welches für eine ganze Zahl $a\in {\mathbb{Z}}_{\ge 1000}$ die letzten 3 Ziffern ausgibt.
Input: Eine ganze Zahl $a\in {\mathbb{Z}}_{\ge 1000}$
Output: Die letzten drei Ziffern der Zahl getrennt durch einen Abstand.
Beispiele: a=15234 $\to$ 2 3 4, a=1020 $\to$ 0 2 0

Individuelle Implementation.

Hinweis: Für int a = 12453 gilt

a % 1000 == 453
a % 100 == 53
a % 1000 - a % 100 == 400

Allgemein: Für $n\in \mathbb{N}$ und $a\in {\mathbb{Z}}_{\ge 10^n}$ entspricht $(a\%10^n-a\%10^{n-1})/10^{n-1}$ der $n$-ten Ziffer von $a$.

Lösung

#include <iostream>
#include <cassert>
 
int main() {
  
  int a;
  std::cin >> a;
  
  std::cout << (a%1000 - a%100) / 100 << " ";
  std::cout << (a%100 - a%10) / 10 << " ";
  std::cout << a %10;
  
  return 0;
}

Zusatz: Überlege dir, wie man das Programm mithilfe einer for-loop verallgemeinern kann.
Hinweis für Zusatz: Verwende std::pow(basis,exponent) aus #include<cmath> um $10^n$ zu berechnen und beachte, dass std::pow() ein float zurückgibt, welcher wieder zu einem int zurückverwandelt werden muss mit (int)std::pow().

Bemerkung: Benutze Python Tutor zur interaktive Ausführen von Code.

Binärdarstellung

Frage: Wie könnten wir das Programm aus der vorherigen Aufgaben (Last Three Digits) so veränder, dass es die letzten 3 bits ausgibt?
Antwort: Ändere alle $10^n$ zu $2^n$.

Frage: Was ist die Bedeutung der $10$ bzw. $2$ in dem Programm?
Antwort: Es ist die Basis des Systems in welches wir die Zahl umwandeln.

Frage: Wie könnte ein Algorithmus aussehen, welcher die Binärdarstellung einer Zahl aus seiner Dezimaldarstellung herleitet? Wie würde man z.B. 61 ins Binärsystem umwandeln?
Antwort: Dividiere die Zahl durch 2 und behalte den Rest separat. Dividiere die neue Zahl wieder durch 2 und wiederhole dies bis du 0 erhälst.

$$\begin{array}{rl}61& =2\cdot 30+1\\ 30& =2\cdot 15+0\\ 15& =2\cdot 7+1\\ 7& =2\cdot 3+1\\ 3& =2\cdot 1+1\\ 1& =2\cdot 0+1\end{array}$$

das lesen der blauen Ziffern von unten nach oben ergibt nun die Binärdarstellung $101111$ von $61$.

Bemerke: Falls wir $61$ gegeben haben erhalten wir die $30$ bzw. die $1$ (aus der obigen Auflistung) wie folgt

61 / 2 == 30
61 % 2 == 1

Frage: Wie kann man eine Zahl in Binärdarstellung in Dezimaldarstellung umwandeln?
Antwort: Addiere die “Gewichte” aller Einsen in der Binärdarstellug

$$\begin{array}{cccccccc}\text{Bina¨r:}& 1& 0& 1& 1& 1& 1& \\ \text{Gewichte:}& 32& 16& 8& 4& 2& 1& \\ \text{Dezimal:}& 32+& 0+& 8+& 4+& 2+& 1& =61\end{array}$$

Expressions

C++ Expressions, welche Addition und Multiplikation beinhalten folgen denselben Regeln wie in der Mathematik. Wir können folgende Expression durch richtige Klammerung berechnen:

5u + 5u * 3u
5u + (5u * 3u)
5u + 15u
20u

Bemerkung: Das u steht dafür, dass es sich bei diesem Literal um ein unsigned int handelt, standard (ohne u) ist int.

Frage: Welche der folgenden Expressions sind innerhalb von C++ nicht valide? Wieso nicht? Hier sind a und b Variablen vom Typ int.
(i) 1*(2*3)
(ii) (a=1)
(iii) (1
(iv) (a*3)=(b*5)

Antwort: (iii) und (iv). (iii) ist nicht valide, da die Klammerung nicht aufgeht. (iv) ist nicht valide, da wir einem R-Wert versuchen etwas zuzuweisen.

Frage: Handelt es sich bei (i) und (ii) um einen L- oder R-Wert

Binärdarstellung von negative ganzen Zahlen

Siehe Two’s complement - Wikipedia.

Weiteres

• Falls noch nicht gemacht, wird das C++ Tutorial (auf der Vorlesungshomepage verlinkt) sehr empfohlen: E.Tutorial
• Bei Fragen könnt ihr mir jederzeit ein Email schreiben.