Riprendo questo che trovo interessanteLa seguente espressione aritmetica senza parentesi dà come risultato -3.
1-2+3-4+5-6 = -3
Se collochiamo due parentesi così, il risultato diventa -1.
1-2+3-(4+5-6) = -1
Aggiungi parentesi in modo da ottenere il risultato più grande possibile
(massimizzare il risultato).
Aggiungi parentesi in modo da ottenere il risultato più piccolo possibile
(minimizzare il risultato).
Come si può scrivere un programma per computer che risolva questo tipo di problemi, con n numeri e n-1 operatori +, -, *, / ?
La prima cosa che mi viene in mente è di raggruppare tutte le somme, in modo che rimangano solo sottrazioni. Ottengo così il minimo
1-(2+3)-(4+5)-6 = -19
Se adesso raggruppo ulteriormente tutte le operazioni dopo il primo meno, trasformo l'ultima parte in positivo. Ottengo così il massimo
1-((2+3)-(4+5)-6) = 11
Questa potrebbe essere una regola generale, ma se aumento il numero di elementi e inserisco gli altri operatori, il ragionamento potrebbe non essere così immediato
Proviamo allora a scrivere un programma che risolva da solo il problema.
La prima cosa che mi viene in mente è di provare tutte le possibili combinazioni, ma questo significa esplorare tutti i possibili raggruppamenti all'interno delle parentesi.
Prendiamo come esempio n = 6 avremo, come sottogruppi di primo livello
[1,1,1,1,1,1] = 1-2+3-4+5-6 = -3
[2,1,1,1,1] = (1-2)+3-4+5-6 = -3
[2,2,1,1] = (1-2)+(3-4)+5-6 = -3
[2,2,2] = ...
[3,1,1,1]
[3,2,1]
[3,3]
[4,1,1]
[4,2]
[5,1]
Per ognuno di questi dobbiamo considerare le possibili permutazioni, mantenendo l'ordine dei numeri
ad esempio [5,1] = (1-2+3-4+5)-6 = -3
mentre [1,5] = 1-(2+3-4+5-6) = 1
A questo punto dobbiamo considerare che ogni sottogruppo con più di due elementi genera ulteriori raggruppamenti
ad esempio [3,2,1] genera [(2,1),2,1] e [(1,2),2,1] da moltiplicare per le 6 permutazioni possibili
Dobbiamo ora scrivere alcune routine:
- una che genera tutti i raggruppamenti di primo livello (e tutti gli altri in cascata)
- una che genera le permutazioni di un certo gruppo
- una che genera tutte le possibili combinazioni in modo iterativo
- una che ricompone le formule e ne valuta il risultato
Usiamo Python, per diversi motivi:
- ha una funzione che genera le permutazioni senza scrivere il relativo codice (anche negli esempi di Decimal Basic c'è un codice pronto)
- ha una funzione che valuta direttamente il risultato di una formula contenuta in una stringa
- non si devono dimensionare gli array, possiamo ingrandirli a piacere finché c'è memoria disponibile
Ed ecco il nostro listato
Codice: Seleziona tutto
# importa la funzione di permutazione dal modulo itertools
from itertools import permutations as pms
#ricava i sottogruppi di primo livello di un insieme di n elementi
def sottogruppi(n):
s = [[1]*n] # crea un array di n volte 1
p = 0
q = [1] # gruppo da ricavare
while q[0] < n-1: # itera il processo finché non si
q[p] += 1 # arriva al sottogruppo [n-1,1]
r = q[:p+1]
r.extend([1]*(n-sum(q))) # completa il sottogruppo
s.append(r) # salva il sottogruppo
if sum(q)<n-1: # passa all'elemento successivo
p += 1
q.append(1)
else: # risale all'elemento precedente
while (sum(q)>=n or q[p]==q[p-1]) and p>0:
q = q[:p]
p -= 1
return s # restituisce l'insieme dei sottogruppi
# ricava le permutazioni di un gruppo
def permuta_gruppo(r):
q = []
for p in pms(r,len(r)): # usa la funzione di permutazione
if p not in q: q.append(p) # elimina gli elementi ripetuti
return q
# separa i numeri dai segni
def separa_segni(f):
k = ''
g = [] # lista dei numeri
h = [f[0]] # lista dei segni
for i in range(1,len(f)):
if '0'<=f[i]<='9': # accorpa le cifre dei numeri maggiori di 9
k += f[i]
else:
g.append(k) # inserisce il numero nella lista
k = ''
h.append(f[i]) # inserisce il segno nella lista
g.append(k)
return g, h # restituisce le liste
# compone un'unica lista di sottogruppi con tutte le permutazioni
def permuta_sottogruppi(n):
p = []
for i in sottogruppi(n):
for j in permuta_gruppo(i): p.append([str(x) for x in j])
return p
f = '1-2+3-4+5-6' # formula in ingresso
if f[0]!='-': f = '+'+f # aggiunge '+' se non presente all'inizio
maxr = minr = eval(f) # imposta il valore massimo e minimo al valore base
print (f, '=', maxr)
g, h = separa_segni(f) # separa i numeri dai segni
n = len(g)
p = permuta_sottogruppi(n) # lista dei sottogruppi di livello 1
# processa la lista dei sottogruppi fino ad ottenere tutte le combinazioni
# per qualsiasi livello di parentesi
x = True
q = p.copy()
while x:
x = False
p = q.copy()
q = []
for i in p:
r = []
for j in range(len(i)):
if i[j]=='1' or i[j]=='(' or i[j]==')': r.append(i[j])
if i[j]=='2': r.extend(['(', '1', '1', ')']); x = True
if i[j]>'2':
k = permuta_sottogruppi(int(i[j]))
s = r.copy()
for l in k:
r = s.copy()
r.append('(')
r.extend(l)
r.append(')')
r.extend(i[j+1:])
q.append(r)
x = True
break
else:
q.append(r)
# compone le stringhe con le formule e le valuta
for j in q:
r = ''
m = 0
p = False
for k in j:
if k=='(':
if not p: r = r + h[m]
p = True
r += k
if k=='1':
if not p: r = r + h[m]
p = False
r += g[m]
m += 1
if k==')': r += k
s = round(eval(r),9) # valuta la formula
if s>maxr:
print(r, '=', s, '>>>') # stampa la formula solo se maggiore
maxr = s
if s<minr:
print(r, '=', s, '<<<') # stampa la formula solo se minore
minr = s
Codice: Seleziona tutto
+1-2+3-4+5-6 = -3
+1-(2+3)-4+5-6 = -9 <<<
+1-2+3-(4+5)-6 = -13 <<<
+1-(2+3)-(4+5)-6 = -19 <<<
+1-(2+3-4)+5-6 = -1 >>>
+1-(2+3-4+5-6) = 1 >>>
+1-(2+3-(4+5)-6) = 11 >>>Codice: Seleziona tutto
-15*33+21/8/9*11+77/3 = -466.125
-15*(33+21)/8/9*11+77/3 = -98.08333333333333 >>>
-15*33+21/8/(9*11)+77/3 = -469.3068181818182 <<<
-15*33+21/8/9*(11+77)/3 = -486.44444444444446 <<<
-15*(33+21)/(8/9)*11+77/3 = -9998.083333333334 <<<
-15*(33+21)/8/(9*11)+77/3 = 24.643939393939394 >>>
-15*33+21/(8/9)*(11+77)/3 = 198.0 >>>
-15*(33+21)/(8/9)*(11+77)/3 = -26730.0 <<<
-15*33+21/(8/9)*(11+77/3) = 371.25 >>>
-15*(33+21)/(8/9)*(11+77/3) = -33412.5 <<<
-15*33+21/(8/(9*11+77)/3) = 891.0 >>>
-15*33+21/(8/(9*(11+77))/3) = 5742.0 >>>
-15*(33+21)/(8/(9*11+77)/3) = -53460.0 <<<
-15*(33+21)/(8/(9*(11+77))/3) = -240570.0 <<<