Matematica senza Frontiere
Il biliardo americano è un gioco che presenta 15 palle numerate da 1 a 15 e una palla bianca.
La partita finisce quando sul tavolo rimane solamente la palla bianca.
Alla fine della loro partita Bonnie e Clyde contano i rispettivi punti.
Tutte le palle sono state vinte da uno o dall’altro giocatore.
Bonnie raggiunge il doppio dei punti di Clyde benché abbia vinto meno palle.
Indicate le suddivisioni possibili dei punti ottenuti da Bonnie.
1
Prova tutte le combinazioni, 2^15, e visualizza le liste che soddisfano i criteri.
La versione più compatta utilizza
- la ricorsione
- le liste
- le funzioni append(), len(), pop(), sum()
N=15
Bonnie=[]
Clyde =[]
def trial(palla):
if(palla > N):
if(sum(Bonnie) == 2*sum(Clyde)) and (len(Bonnie) < len(Clyde)):
print("Bonnie:", Bonnie)
print("Clyde :", Clyde)
print()
else:
Bonnie.append(palla)
trial(palla+1)
Bonnie.pop()
Clyde.append(palla)
trial(palla+1)
Clyde.pop()
trial(1)
2
Al crescere del numero di palle diventa importante evitare le operazioni dispendiose: append(), len(), pop(), sum().
N=15
Bonnie=(N+1)*[0]
Clyde =(N+1)*[0]
def visualizza(BC, SOL):
print(BC,end=": ")
for i in range(1, N+1):
if(SOL[i] == 1):
print(i,end=' ')
print()
def trial(palla, BonnieP, ClydeP, BonnieN, ClydeN):
if(palla > N):
if(BonnieP == 2*ClydeP) and (BonnieN < ClydeN):
visualizza("Bonnie",Bonnie)
visualizza("Clyde ",Clyde)
print()
else:
Bonnie[palla]=1
trial(palla+1, BonnieP+palla, ClydeP, BonnieN+1, ClydeN)
Bonnie[palla]=0
Clyde[palla]=1
trial(palla+1, BonnieP, ClydeP+palla, BonnieN, ClydeN+1)
Clyde[palla]=0
trial(1, 0, 0, 0, 0)
3
Perché provare tutte le combinazioni?
Sappiamo che “Bonnie ha vinto meno palle di Clyde” quindi deve essere BonnieN < N/2
N=15
Bonnie=(N+1)*[0]
Clyde =(N+1)*[0]
BonnieL=N/2-1
def visualizza(BC, SOL):
print(BC,end=": ")
for i in range(1, N+1):
if(SOL[i] == 1):
print(i,end=' ')
print()
def trial(palla, BonnieP, ClydeP, BonnieN, ClydeN):
if(palla > N):
if(BonnieP == 2*ClydeP):
visualizza("Bonnie", Bonnie)
visualizza("Clyde ", Clyde)
print()
elif(BonnieN < BonnieL):
Bonnie[palla]=1
trial(palla+1, BonnieP+palla, ClydeP, BonnieN+1, ClydeN)
Bonnie[palla]=0
Clyde[palla]=1
trial(palla+1, BonnieP, ClydeP+palla, BonnieN, ClydeN+1)
Clyde[palla]=0
trial(1, 0, 0, 0, 0)