Übungen zur Wiederholung - Algorithmik und Datenstrukturen

1. Implementieren Sie eine Operation Dez2Bin, die eine beliebige Dezimalzahl in eine Binärzahl (=Dualzahl) umwandelt und in Form einer Zeichenkette zurückgibt.

string Dec2Bin(int num){
    string binStr = "";
    int biggestFittingPow = 0;
    bool fits = true;
    while (fits){
        int pow = pow2(biggestFittingPow);
        if (num - pow >= 0){
            biggestFittingPow++;
        }
        else{
            fits = false;
        }
    }
    for (int i = biggestFittingPow - 1; i >= 0; i--){
        int pow = pow2(i);
        if (num - pow >= 0){
            binStr += "1";
            num -= pow;
        }
        else{
            binStr += "0";
        }
    }
    return binStr;
}
 
int pow2(int pow){
    int result = 1;
 
    for (int i = 0; i < pow; i++){
        result *= 2;
    }
    return result;
}

---

Bessere Version:

Diese Methode ist deutlich schneller und eleganter:

string FastBec2Bin(int num){
  string binStr = "";
  while (num > 0){
  	int rem = num % 2;
  	binStr = rem + binStr;
  	num /= 2;
  }
  return binStr;
}

3.

Aufgabe:

Gegeben ist folgender Algorithmus: An eine Operation wird eine Kommazahl a und eine positive ganze Zahl b übergeben. Eine Kommazahl c erhält zunächst den Wert 1. Solange b größer als Null ist, wird überprüft, ob b ungerade ist. Wenn dies der Fall ist, wird c mit a multipliziert (und wieder als c gespeichert) und b um eins erniedrigt. Ist jedoch b gerade, dann wird a mit sich selbst multipliziert (und wieder als a gespeichert) und b halbiert. Sobald b Null ist, wird c zurückgegeben.

Entwerfen Sie das zugehörige Struktogramm.

public float Operation(float a, int b){
	float c = 1f;
	while (b > 0){
		if (b % 2 == 1){
			c *= a;
			b--;
		}
		else{
			a *= a;
			b /= 2;			
		}
	}	
	return c;
}

Erstellen Sie je eine Tracetabelle für a=2, b=5 sowie für a=3, b=4. Untersuchen Sie, welches Ergebnis der Algorithmus für einen beliebigen Wert von a liefert, wenn b den Wert 1 bzw. den Wert 0 hat.

#	a	b	c
0	2	5	1
1	2	4	2
2	4	2	2
3	16	1	2
4	16	0	32

Geben Sie an, welche mathematische Funktion der Algorithmus realisiert

$$c=a^b$$