Pascal Schärli 16.10.2020
static int f(int i, int j) {
assert(i >= 0 && j >= 0);
int u = i;
int z = 0;
while (u > 0){
z = z + j;
u = u - 1;
}
return z;
}
Schleifen Invariante
Pascal Schärli 16.10.2020
Sonst wäre die Schleife noch nicht fertig
public static String encrypt(String s) {
String ret = "";
for (int i = 0; i != s.length(); ++i) {
ret = ret + (char) (s.charAt(i) + 3);
}
return ret;
}
public static String decrypt(String s) {
StringBuffer ret = new StringBuffer();
for (int i = 0; i != s.length(); ++i) {
ret.append((char) (s.charAt(i) - 3));
}
return ret.toString();
}
Starting encryption (using Strings)
Done - Duration: 3732 ms.
Starting decryption (using StringBuffers)
Done - Duration: 73 ms.
Decryption successful :-)
Pascal Schärli 16.10.2020
Pascal Schärli 16.10.2020
-
Pascal Schärli 16.10.2020
-
private static int parseTree(String kd, int offset) throws ParseException {
if (checkNext('-', kd, offset)) {
return offset + 1;
}
offset = parseNode(kd, offset);
if (checkNext('(', kd, offset)) {
offset += 1;
offset = parseSubtree(kd, offset);
if (!checkNext(')', kd, offset)) {
throw new ParseException("expected ')'", offset);
}
offset += 1;
}
return offset;
}
Pascal Schärli 16.10.2020
private static int parseSubtree(String kd, int offset) throws ParseException {
offset = parseTree(kd, offset);
while (checkNext(',', kd, offset)) {
offset += 1;
offset = parseTree(kd, offset);
}
return offset;
}
Pascal Schärli 16.10.2020
private static int parseNode(String kd, int offset) throws ParseException {
if (offset >= kd.length()) {
throw new ParseException("Expected a node", offset);
}
char c = kd.charAt(offset);
if (Character.isUpperCase(c)) {
return offset + 1;
} else {
throw new ParseException(String.format("'%c' is not a valid node name", c), offset);
}
}
Pascal Schärli 16.10.2020
Pascal Schärli 16.10.2020
1
5
9
3
9
push
pop
9
Pascal Schärli 16.10.2020
peek
4
Stack myStack = new Stack();
myStack.push(4);
System.out.println(myStack.peek());
myStack.push(2);
myStack.push(3);
System.out.println(myStack.pop());
myStack.push(1);
Program
Output
4
3
4
2
3
1
Pascal Schärli 16.10.2020
Pascal Schärli 16.10.2020
Beispiel: \(A(1,1)\)
A(1,1) // A(1,1)
A(1,1) // A(1,1)
A(1,0) // A(1,1) = A(0,A(1,0))
A(1,1) // A(1,1)
A(1,0) // A(1,1) = A(0,A(1,0))
A(0, 1) // A(1,0) = A(0,1)
A(1,1) // A(1,1)
A(1,0) // A(1,1) = A(0,A(1,0))
A(0, 1) // A(1,0) = A(0,1)
<- 2 // A(0,1) = 2
A(1,1) // A(1,1)
A(1,0) // A(1,1) = A(0,A(1,0))
A(0, 1) // A(1,0) = A(0,1)
<- 2 // A(0,1) = 2
<- 2 // A(1,0) = 2
A(1,1) // A(1,1)
A(1,0) // A(1,1) = A(0,A(1,0))
A(0, 1) // A(1,0) = A(0,1)
<- 2 // A(0,1) = 2
<- 2 // A(1,0) = 2
A(0, 2) // A(1,1) = A(0,2)
A(1,1) // A(1,1)
A(1,0) // A(1,1) = A(0,A(1,0))
A(0, 1) // A(1,0) = A(0,1)
<- 2 // A(0,1) = 2
<- 2 // A(1,0) = 2
A(0, 2) // A(1,1) = A(0,2)
<- 3 // A(0,2) = 3
A(1,1) // A(1,1)
A(1,0) // A(1,1) = A(0,A(1,0))
A(0, 1) // A(1,0) = A(0,1)
<- 2 // A(0,1) = 2
<- 2 // A(1,0) = 2
A(0, 2) // A(1,1) = A(0,2)
<- 3 // A(0,2) = 3
<- 3 // A(1,1) = 3
\(\Rightarrow A(1,1) = 3\)
\(13\)
\(65533\)
\(2^{65536} - 3 \)
\(A(0,m) = m + 1\)
\(A(n,0) = A(n-1,1)\)
\(A(n,m) = A(n-1,A(n,m-1))\)
Weitere Beispiele:
Pascal Schärli 16.10.2020
Pascal Schärli 16.10.2020
iconst_4
iconst_2
iconst_3
imul
iconst_1
isub
iadd
Bytecode
Stack
Pascal Schärli 16.10.2020
iconst_4
iconst_2
iconst_3
imul
iconst_1
isub
iadd
Bytecode
Stack
4
Pascal Schärli 16.10.2020
iconst_4
iconst_2
iconst_3
imul
iconst_1
isub
iadd
Bytecode
Stack
4
2
Pascal Schärli 16.10.2020
iconst_4
iconst_2
iconst_3
imul
iconst_1
isub
iadd
Bytecode
Stack
4
2
3
Pascal Schärli 16.10.2020
iconst_4
iconst_2
iconst_3
imul
iconst_1
isub
iadd
Bytecode
Stack
4
6
Pascal Schärli 16.10.2020
iconst_4
iconst_2
iconst_3
imul
iconst_1
isub
iadd
Bytecode
Stack
4
6
1
Pascal Schärli 16.10.2020
iconst_4
iconst_2
iconst_3
imul
iconst_1
isub
iadd
Bytecode
Stack
4
5
Pascal Schärli 16.10.2020
iconst_4
iconst_2
iconst_3
imul
iconst_1
isub
iadd
Bytecode
Stack
9
Pascal Schärli 16.10.2020
static int f(int a);
0 iload_0 [a]
1 iconst_1
2 if_icmpgt 7
5 iconst_1
6 ireturn
7 iload_0 [a]
8 iconst_1
9 isub
10 invokestatic test.Main.f(int) : int [16]
13 iload_0 [a]
14 iconst_2
15 isub
16 invokestatic test.Main.f(int) : int [16]
19 iadd
20 ireturn
static int f(int a) {
}
Bytecode
Übersetzung
Pascal Schärli 16.10.2020
Stack
a
static int f(int a);
0 iload_0 [a]
1 iconst_1
2 if_icmpgt 7
5 iconst_1
6 ireturn
7 iload_0 [a]
8 iconst_1
9 isub
10 invokestatic test.Main.f(int) : int [16]
13 iload_0 [a]
14 iconst_2
15 isub
16 invokestatic test.Main.f(int) : int [16]
19 iadd
20 ireturn
static int f(int a) {
a
}
Bytecode
Übersetzung
Pascal Schärli 16.10.2020
Stack
a
1
static int f(int a);
0 iload_0 [a]
1 iconst_1
2 if_icmpgt 7
5 iconst_1
6 ireturn
7 iload_0 [a]
8 iconst_1
9 isub
10 invokestatic test.Main.f(int) : int [16]
13 iload_0 [a]
14 iconst_2
15 isub
16 invokestatic test.Main.f(int) : int [16]
19 iadd
20 ireturn
static int f(int a) {
a 1
}
Bytecode
Übersetzung
Pascal Schärli 16.10.2020
Stack
a
1
static int f(int a);
0 iload_0 [a]
1 iconst_1
2 if_icmpgt 7
5 iconst_1
6 ireturn
7 iload_0 [a]
8 iconst_1
9 isub
10 invokestatic test.Main.f(int) : int [16]
13 iload_0 [a]
14 iconst_2
15 isub
16 invokestatic test.Main.f(int) : int [16]
19 iadd
20 ireturn
static int f(int a) {
if(a <= 1){
}
}
Bytecode
Übersetzung
Pascal Schärli 16.10.2020
Stack
a
1
a > 1
1
static int f(int a);
0 iload_0 [a]
1 iconst_1
2 if_icmpgt 7
5 iconst_1
6 ireturn
7 iload_0 [a]
8 iconst_1
9 isub
10 invokestatic test.Main.f(int) : int [16]
13 iload_0 [a]
14 iconst_2
15 isub
16 invokestatic test.Main.f(int) : int [16]
19 iadd
20 ireturn
static int f(int a) {
if(a <= 1){
1
}
}
Bytecode
Übersetzung
Pascal Schärli 16.10.2020
Stack
1
static int f(int a);
0 iload_0 [a]
1 iconst_1
2 if_icmpgt 7
5 iconst_1
6 ireturn
7 iload_0 [a]
8 iconst_1
9 isub
10 invokestatic test.Main.f(int) : int [16]
13 iload_0 [a]
14 iconst_2
15 isub
16 invokestatic test.Main.f(int) : int [16]
19 iadd
20 ireturn
static int f(int a) {
if(a <= 1){
return 1;
}
}
Bytecode
Übersetzung
Pascal Schärli 16.10.2020
Stack
1
1
static int f(int a);
0 iload_0 [a]
1 iconst_1
2 if_icmpgt 7
5 iconst_1
6 ireturn
7 iload_0 [a]
8 iconst_1
9 isub
10 invokestatic test.Main.f(int) : int [16]
13 iload_0 [a]
14 iconst_2
15 isub
16 invokestatic test.Main.f(int) : int [16]
19 iadd
20 ireturn
static int f(int a) {
if(a <= 1){
return 1;
}
a
}
Bytecode
Übersetzung
Pascal Schärli 16.10.2020
Stack
a
1
static int f(int a);
0 iload_0 [a]
1 iconst_1
2 if_icmpgt 7
5 iconst_1
6 ireturn
7 iload_0 [a]
8 iconst_1
9 isub
10 invokestatic test.Main.f(int) : int [16]
13 iload_0 [a]
14 iconst_2
15 isub
16 invokestatic test.Main.f(int) : int [16]
19 iadd
20 ireturn
static int f(int a) {
if(a <= 1){
return 1;
}
a 1
}
Bytecode
Übersetzung
Pascal Schärli 16.10.2020
Stack
a
1
static int f(int a);
0 iload_0 [a]
1 iconst_1
2 if_icmpgt 7
5 iconst_1
6 ireturn
7 iload_0 [a]
8 iconst_1
9 isub
10 invokestatic test.Main.f(int) : int [16]
13 iload_0 [a]
14 iconst_2
15 isub
16 invokestatic test.Main.f(int) : int [16]
19 iadd
20 ireturn
static int f(int a) {
if(a <= 1){
return 1;
}
a-1
}
Bytecode
Übersetzung
Pascal Schärli 16.10.2020
Stack
a
1
a-1
static int f(int a);
0 iload_0 [a]
1 iconst_1
2 if_icmpgt 7
5 iconst_1
6 ireturn
7 iload_0 [a]
8 iconst_1
9 isub
10 invokestatic test.Main.f(int) : int [16]
13 iload_0 [a]
14 iconst_2
15 isub
16 invokestatic test.Main.f(int) : int [16]
19 iadd
20 ireturn
static int f(int a) {
if(a <= 1){
return 1;
}
f(a-1)
}
Bytecode
Übersetzung
Pascal Schärli 16.10.2020
Stack
a
1
f(a-1)
a
static int f(int a);
0 iload_0 [a]
1 iconst_1
2 if_icmpgt 7
5 iconst_1
6 ireturn
7 iload_0 [a]
8 iconst_1
9 isub
10 invokestatic test.Main.f(int) : int [16]
13 iload_0 [a]
14 iconst_2
15 isub
16 invokestatic test.Main.f(int) : int [16]
19 iadd
20 ireturn
static int f(int a) {
if(a <= 1){
return 1;
}
f(a-1) a
}
Bytecode
Übersetzung
Pascal Schärli 16.10.2020
Stack
a
1
f(a-1)
a
2
static int f(int a);
0 iload_0 [a]
1 iconst_1
2 if_icmpgt 7
5 iconst_1
6 ireturn
7 iload_0 [a]
8 iconst_1
9 isub
10 invokestatic test.Main.f(int) : int [16]
13 iload_0 [a]
14 iconst_2
15 isub
16 invokestatic test.Main.f(int) : int [16]
19 iadd
20 ireturn
static int f(int a) {
if(a <= 1){
return 1;
}
f(a-1) a 2
}
Bytecode
Übersetzung
Pascal Schärli 16.10.2020
Stack
a
1
f(a-1)
a
2
static int f(int a);
0 iload_0 [a]
1 iconst_1
2 if_icmpgt 7
5 iconst_1
6 ireturn
7 iload_0 [a]
8 iconst_1
9 isub
10 invokestatic test.Main.f(int) : int [16]
13 iload_0 [a]
14 iconst_2
15 isub
16 invokestatic test.Main.f(int) : int [16]
19 iadd
20 ireturn
static int f(int a) {
if(a <= 1){
return 1;
}
f(a-1) a-2
}
Bytecode
Übersetzung
Pascal Schärli 16.10.2020
Stack
a
1
f(a-1)
a
2
a-2
static int f(int a);
0 iload_0 [a]
1 iconst_1
2 if_icmpgt 7
5 iconst_1
6 ireturn
7 iload_0 [a]
8 iconst_1
9 isub
10 invokestatic test.Main.f(int) : int [16]
13 iload_0 [a]
14 iconst_2
15 isub
16 invokestatic test.Main.f(int) : int [16]
19 iadd
20 ireturn
static int f(int a) {
if(a <= 1){
return 1;
}
f(a-1) f(a-2)
}
Bytecode
Übersetzung
Pascal Schärli 16.10.2020
Stack
a
1
f(a-1)
f(a-2)
static int f(int a);
0 iload_0 [a]
1 iconst_1
2 if_icmpgt 7
5 iconst_1
6 ireturn
7 iload_0 [a]
8 iconst_1
9 isub
10 invokestatic test.Main.f(int) : int [16]
13 iload_0 [a]
14 iconst_2
15 isub
16 invokestatic test.Main.f(int) : int [16]
19 iadd
20 ireturn
static int f(int a) {
if(a <= 1){
return 1;
}
f(a-1) + f(a-2)
}
Bytecode
Übersetzung
Pascal Schärli 16.10.2020
Stack
a
1
f(a-1)
f(a-2)
f(a-1) + f(a-2)
static int f(int a);
0 iload_0 [a]
1 iconst_1
2 if_icmpgt 7
5 iconst_1
6 ireturn
7 iload_0 [a]
8 iconst_1
9 isub
10 invokestatic test.Main.f(int) : int [16]
13 iload_0 [a]
14 iconst_2
15 isub
16 invokestatic test.Main.f(int) : int [16]
19 iadd
20 ireturn
static int f(int a) {
if(a <= 1){
return 1;
}
return f(a-1) + f(a-2);
}
Bytecode
Übersetzung
Pascal Schärli 16.10.2020
Stack
a
1
f(a-1)
f(a-2)
f(a-1) + f(a-2)
static int f(int a);
0 iload_0 [a]
1 iconst_1
2 if_icmpgt 7
5 iconst_1
6 ireturn
7 iload_0 [a]
8 iconst_1
9 isub
10 invokestatic test.Main.f(int) : int [16]
13 iload_0 [a]
14 iconst_2
15 isub
16 invokestatic test.Main.f(int) : int [16]
19 iadd
20 ireturn
static int f(int a) {
if(a <= 1){
return 1;
}
return f(a-1) + f(a-2);
}
Bytecode
Übersetzung
Pascal Schärli 16.10.2020
Stack
Pascal Schärli 16.10.2020
Pascal Schärli 16.10.2020
push(0);
push(1);
push(2);
pop();
peek();
pop();
push(3);
push(4);
peek();
pop();
0
1
3
4
0
3
3
0
3
4
A
B
C
D
Pascal Schärli 16.10.2020
Pascal Schärli 16.10.2020
0 iload_0
1 iconst_1
2 imul
3 ireturn
0 iload_0
1 iconst_1
2 if_icmple 7
5 iconst_1
6 ireturn
7 iconst_0
8 ireturn
0 iload_0
1 iconst_1
2 if_icmpge 7
5 iconst_1
6 ireturn
7 iconst_0
8 ireturn
return x * 1;
return x > 1;
return x < 1;
Pascal Schärli 16.10.2020
0 iload_0
1 iconst_2
2 irem
3 istore_1
4 iload_0
5 iconst_2
6 imul
7 istore_2
8 iload_0
9 iconst_2
10 idiv
11 istore_3
12 iload_2
13 iconst_2
14 iload_1
15 imul
16 isub
17 iload_3
18 idiv
19 ireturn
static int whichAnswerIsCorrect(int a){
int i = a%2;
int j = a*2;
int k = a/2;
return (j-2*i)/k;
}
Pascal Schärli 16.10.2020
push
Neue Daten oben auf den Stack legen
Stack myStack = Stack(4);
// […]
myStack.push(8)
[1, 4, *, *]
0 1 2 3
size = 2
[1, 4, 8, *]
0 1 2 3
size = 3
push(8)
Pascal Schärli 16.10.2020
pop
Daten von zuoberst im Stack entfernen
Stack myStack = Stack(4);
// […]
int myInt = myStack.pop();
[1, 4, 8, *]
0 1 2 3
size = 3
[1, 4, *, *]
0 1 2 3
size = 2
pop()
Pascal Schärli 16.10.2020
grow
Falls der Array voll ist, und ein weiteres push aufgerufen wird, müssen wir den Platz vergrössern
Stack myStack = Stack(4);
// […]
int myInt = myStack.push(3);
[1, 4, 8, 2]
0 1 2 3
size = 4
[1, 4, 8, 2, *, *, *, *]
0 1 2 3 4 5 6 7
size = 4
grow()
[1, 4, 8, 2, 3, *, *, *]
0 1 2 3 4 5 6 7
size = 5
push(3)
Pascal Schärli 16.10.2020
view Slide
Pascal Schärli 16.10.2020
Stack stack = new Stack(10);
// Anfangswerte auf Stack schieben
stack.push(n);
stack.push(m);
while(stack.size() > 1) {
// Neues n, m aus Stack auslesen
if(n == 0){
// A(0,m) = m + 1
}
else if(m == 0){
// A(n,0) = A(n-1,1)
}
else{
// A(n,m) = A(n-1,A(n,m-1));
}
}
Pascal Schärli 16.10.2020
Static int f(int a0,int a1,int a2){
return(a0+a1)/a2;
}
static int f(int a0, int a1, int a2);
0 iload_0
1 iload_1
2 iadd
3 iload_2
4 idiv
5 ireturn
Wie kann man Java Code zu Bytecode umwandeln?
Â
javap -c yourFile.java
Pascal Schärli 16.10.2020
Pascal Schärli 16.10.2020