Op welke mogelijke manieren kan je + of - of niets tussen de cijfers $$1, 2, \ldots, 9$$ (in die volgorde) zetten zodat het resultaat van de uitdrukking gelijk is aan 100? Hier is alvast een voorbeeld: \[ 1 + 2 + 34 - 5 + 67 - 8 + 9 = 100 \] Dit probleem lijkt misschien moeilijker dan het eigenlijk is. Om het op te lossen kan je proberen om het probleem op te delen in kleinere deelproblemen. Je weet wel, de klassieke verdeel-en-heers1 tactiek. Laat ons daarom beginnen met wat we al weten: \[ f(1, 2, \ldots, 9) = 100 \] Hierbij is $$f$$ de functie die de gevraagde uitdrukking teruggeeft. Dit kunnen we nu in drie gevallen opdelen: \[ \begin{cases} 1 + f(2, 3, \ldots, 9) = 100 \\ 1 - f(2, 3, \ldots, 9) = 100 \\ f(12, 3 \ldots, 9) = 100 \end{cases} \] De eerste uitdrukking gebruikt een optelling, de tweede een aftrekking en de derde voegt de eerste twee getallen samen. Als we dit herschrijven, dan krijgen we: \[ \begin{cases} f(2, 3, \ldots, 9) = 100 - 1 = 99 \\ f(-2, 3, \ldots, 9) = 100 - 1 = 99 \\ f(12, 3 \ldots, 9) = 100 \end{cases} \] Merk hierbij op dat we in de tweede uitdrukking het minteken binnen de functie geplaatst hebben. Daarna kunnen we dezelfde procedure toepassen op elk van de bovenstaande uitdrukkingen: \[ \begin{cases} 2 + f(3, 4, \ldots, 9) = 99 \\ 2 - f(3, 4, \ldots, 9) = 99 \\ f(23, 4, \ldots, 9) = 99 \\ -2 + f(3, 4, \ldots, 9) = 99 \\ -2 - f(3, 4, \ldots, 9) = 99 \\ f(-23, 4, \ldots, 9) = 99 \\ 12 + f(3, 4, \ldots, 9) = 100 \\ 12 - f(3, 4, \ldots, 9) = 100 \\ f(123, 4, \ldots, 9) = 100 \end{cases} \] Blijf deze procedure herhalen totdat de functie $$f$$ volledig weggewerkt is. Elke aftakking waarvoor de gelijkheid opgaat, correspondeert met een oplossing van het probleem. Door op je stappen terug te keren, kan je vanuit zo'n oplossing de corresponderende uitdrukking reconstrueren. Dit resulteert in 11 mogelijke oplossingen: \[ \begin{cases} 1 + 2 + 3 - 4 + 5 + 6 + 78 + 9 \\ 1 + 2 + 34 - 5 + 67 - 8 + 9 \\ 1 + 23 - 4 + 5 + 6 + 78 - 9 \\ 1 + 23 - 4 + 56 + 7 + 8 + 9 \\ 12 + 3 + 4 + 5 - 6 - 7 + 89 \\ 12 + 3 - 4 + 5 + 67 + 8 + 9 \\ 12 - 3 - 4 + 5 - 6 + 7 + 89 \\ 123 + 4 - 5 + 67 - 89 \\ 123 + 45 - 67 + 8 - 9 \\ 123 - 4 - 5 - 6 - 7 + 8 - 9 \\ 123 - 45 - 67 + 89 \end{cases} \]
We willen bovenstaand probleem generiek oplossen voor een gegeven reeks van $$n \in \mathbb{N}_0$$ strikt positieve natuurlijke getallen en een gegeven doelwaarde $$t \in \mathbb{N}$$. Elke geldige uitdrukking die we kunnen vormen met de gegeven reeks getallen kan beschreven worden door een reeks van $$n-1$$ operatoren die tussen de getallen moeten geschreven worden: een plusteken (+) voor een optelling, een minteken (-) voor een aftrekking en een verticale streep (|) om twee opeenvolgende getallen samen te voegen. De cijfers $$1, 2, \ldots, 9$$ gecombineerd met de operatoren ++|-+|-+ levert de volgende uitdrukking op:
1 + 2 + 34 - 5 + 67 - 8 + 9
Uiteraard wil niemand de procedure om het probleem op te lossen met de hand uitvoeren, dus is de vraag of je ze kan programmeren. Gevraagd wordt:
Schrijf een functie uitdrukking waaraan twee argumenten moeten doorgegeven worden: i) een reeks (list of tuple) van $$n \in \mathbb{N}_0$$ strikt positieve natuurlijke getallen (int) en ii) een reeks (str, list of tuple) van $$n - 1$$ operatoren (+, - of |). Als de gegeven argumenten niet voldoen aan deze omschrijvingen, dan moet een AssertionError opgeworpen worden met de boodschap ongeldige uitdrukking. Anders moet de functie een string (str) teruggeven met de uitdrukking die resulteert door de gegeven getallen te combineren met de gegeven operatoren. Hierbij moeten de plus- en minoperatoren telkens voorafgegaan en gevolgd worden door één enkele spatie.
Schrijf een functie uitkomst waaraan twee argumenten moeten doorgegeven worden: i) een reeks (list of tuple) van $$n \in \mathbb{N}_0$$ strikt positieve natuurlijke getallen (int) en ii) een reeks (str, list of tuple) van $$n - 1$$ operatoren (+, - of |). Als de gegeven argumenten niet voldoen aan deze omschrijvingen, dan moet een AssertionError opgeworpen worden met de boodschap ongeldige uitdrukking. Anders moet de functie de uitkomst (int) teruggeven van de uitdrukking die resulteert door de gegeven getallen te combineren met de gegeven operatoren.
Python heeft een ingebouwde functie eval2 die een gegeven uitdrukking (str) evalueert als een Python uitdrukking.
Schrijf een functie plusminus waaraan een doelwaarde $$t \in \mathbb{N}$$ (int) moet doorgegeven worden. De functie heeft ook nog een tweede optionele parameter getallen waaraan een reeks (list of tuple) van $$n \in \mathbb{N}_0$$ strikt positieve natuurlijke getallen (int) kan doorgegeven worden. Als de gegeven getallen niet voldoen aan deze omschrijvingen, dan moet een AssertionError opgeworpen worden met de boodschap ongeldige getallen. Als er niet expliciet een waarde wordt doorgegeven aan de parameter getallen, dan wordt standaard de reeks cijfers $$1, 2, \ldots, 9$$ toegekend aan deze parameter. De functie moet een verzameling (set) teruggeven met alle geldige uitdrukkingen (str) die kunnen gevormd worden met de gegeven reeks getallen en die als uitkomst de waarde $$t$$ hebben. Hierbij moeten de uitdrukkingen opgemaakt worden zoals dat gebeurt door de functie uitdrukking.
>>> getallen = (1, 2, 3, 4, 5, 6, 7, 8, 9)
>>> uitdrukking(getallen, '++|-+|-+')
'1 + 2 + 34 - 5 + 67 - 8 + 9'
>>> uitdrukking(getallen, '++-+++|+')
'1 + 2 + 3 - 4 + 5 + 6 + 78 + 9'
>>> uitdrukking(getallen, ['|', '|', '-', '|', '-', '|', '+', '|'])
'123 - 45 - 67 + 89'
>>> uitdrukking(getallen, ('|', '|', '+', '|', '-', '|', '+', '-'))
'123 + 45 - 67 + 8 - 9'
>>> uitdrukking(getallen, '||+')
Traceback (most recent call last):
AssertionError: ongeldige uitdrukking
>>> uitdrukking(getallen, '||*|/|*/')
Traceback (most recent call last):
AssertionError: ongeldige uitdrukking
>>> uitkomst(getallen, '++-+++|+')
100
>>> uitkomst(getallen, ['|', '|', '-', '|', '-', '|', '+', '|'])
100
>>> uitkomst(getallen, ('|', '|', '+', '|', '-', '|', '+', '-'))
100
>>> uitkomst(getallen, '||+')
Traceback (most recent call last):
AssertionError: ongeldige uitdrukking
>>> uitkomst(getallen, '||*|/|*/')
Traceback (most recent call last):
AssertionError: ongeldige uitdrukking
>>> plusminus(100)
{'1 + 2 + 3 - 4 + 5 + 6 + 78 + 9', '123 - 45 - 67 + 89', '123 + 45 - 67 + 8 - 9', '12 - 3 - 4 + 5 - 6 + 7 + 89', '123 + 4 - 5 + 67 - 89', '1 + 2 + 34 - 5 + 67 - 8 + 9', '12 + 3 + 4 + 5 - 6 - 7 + 89', '123 - 4 - 5 - 6 - 7 + 8 - 9', '12 + 3 - 4 + 5 + 67 + 8 + 9', '1 + 23 - 4 + 56 + 7 + 8 + 9', '1 + 23 - 4 + 5 + 6 + 78 - 9'}
>>> plusminus(20)
{'1 - 2 + 34 + 56 - 78 + 9', '12 + 3 + 4 + 5 + 6 + 7 - 8 - 9', '1 + 2 + 34 - 5 - 6 - 7 - 8 + 9', '12 - 3 + 4 + 5 - 6 + 7 - 8 + 9', '1 - 2 - 34 + 5 + 67 - 8 - 9', '1 - 23 - 4 + 56 + 7 - 8 - 9', '123 + 4 - 5 - 6 - 7 - 89', '1 + 2 + 34 + 5 + 67 - 89', '12 + 3 - 45 + 67 - 8 - 9', '12 + 3 - 4 + 5 - 6 - 7 + 8 + 9', '12 - 3 + 4 - 5 + 6 + 7 + 8 - 9', '1 - 2 + 34 + 5 + 6 - 7 - 8 - 9', '12 + 34 + 56 + 7 - 89', '12 + 3 - 4 - 5 + 6 + 7 - 8 + 9', '1 - 2 + 3 - 45 - 6 + 78 - 9'}
>>> plusminus(200)
{'123 + 4 + 5 + 67 - 8 + 9', '1 + 234 - 5 - 6 - 7 - 8 - 9', '123 - 4 + 5 - 6 - 7 + 89'}
>>> plusminus(300)
set()
>>> plusminus(500)
{'1 - 2 + 345 + 67 + 89', '1 - 234 - 56 + 789'}
>>> plusminus(501)
{'1234 + 56 - 789'}
>>> plusminus(20, [2, 3, 5, 7, 11, 13])
{'2 + 35 + 7 - 11 - 13'}
>>> plusminus(1234, (1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11))
{'1234 - 5 - 6 - 7 + 8 + 9 - 10 + 11', '1 - 2 + 345 + 6 - 7 - 8 + 910 - 11', '1234 - 5 - 6 + 7 - 8 - 9 + 10 + 11', '1234 + 5 + 6 - 7 + 8 + 9 - 10 - 11', '1234 + 5 + 6 + 7 - 8 - 9 + 10 - 11'}