---
# System prepended metadata

title: 'Algorithmen und Datenstrukturen: Blatt 9'
tags: [Algorithmen und Datenstrukturen, Informatik, Uni]

---

# Algorithmen und Datenstrukturen: Blatt 9

## Aufgabe 1

### 1a)

#### i)

Pseudocode:

```java=
setTime(int x)
  Button[] t = {25, 10, 5, 1}
  List sequence
  int remaining = x
  for (int i = 0) to 3 do
    if(remaining >= t[i]) then
      int j = |_x/t[i]_|
      remaining = remaining - j*x
      while(j > 0) do
        sequence.add(t[i])
        j--
  return sequence
```

##### ii)

Der Algorithmus terminiert, da die kleinste Taste t[4] 1 Sekunde liefert
und nur ganzzahlige Sekunden benötigt werden.

### 1b)

Gegeben: eine Mikrowelle mit den Tasten **[10][7][3][1]**.  
Beispiel: **x = 25**.  
Vorgehen bei dem Algorithmus aus Aufgabe 1a) liefert die Sequenz: **[10,10,3,1,1]**.
Die optimale Sequenz: **[10,7,7,1]**.

###### tags: `Algorithmen und Datenstrukturen` `Informatik` `Uni`
