Aufgabe 2: Bitonische Folgen Assignment

Gegeben sei eine Liste von ganzen Zahlen a = [a0, a1, . . . , ak, ak+1, . . . an−1]. Wir wollen überprüfen, ob es einen Index k gibt, sodass a0 ≤ a1 ≤ ... ≤ ak und ak ≥ ak+1 ≥... ≥ an−1. Eine Folge mit dieser Eigenschaft heißt bitonisch. 

1. Schreiben Sie ein Unterprogramm is_bitonic(a), dem eine Liste a von ganzen Zahlen übergeben wird und das den entsprechenden Wahrheitswert zurückgibt, ob die Folge bitonisch ist oder nicht. 

2. Schreiben Sie eine rekursive Funktion max_bitonic(a), die das maximale Element einer bitonischen Folge bestimmen kann. Verwenden Sie als Lösungsansatz das Divide-and- Conquer Prinzip (analog zur binären Suche). 

Scaffold Head

import sys _print = print print = lambda msg, *args, **kwargs: _print('#'+str(msg), *args, **kwargs)

Scaffold Foot

lists = [eval(l) for l in sys.stdin] # 1 for l in lists: _print(is_bitonic(l)) # 2 for l in lists[:-1]: _print(max_bitonic(l))

Start time:

Do 14 Dez 2017 14:00:50

End time:

Do 21 Dez 2017 23:00:34

General test timeout:

10.0 seconds

Tests

[1, 2, 3, 4, 5, 4, 3, 2, 1]
[1, 2, 3, 4, 4, 4, 3, 2, 1]
[-3, -2, -1, 0, -1, -2, -3]
[-6, -3, -2, 1, -6]
[1, 2, 4, 5, 4, 6]

True
True
True
True
False
5
4
0
1