Esercizi di Programmazione (compito a casa della lezione dell'15 Maggio)
Indice |
1
Scrivere un programma ricorsivo che stampi tutte le configurazioni di 8 regine poste su di una scacchiera tali che nessuna delle 8 regine ne metta in scacco un'altra
Domenico. Prof. Davoli ho chiesto lumi ad un amico e mi ha risposto che il metodo più facile per risolvere questo problema è il backtracking, cioè fare, come mi ha detto questo amico, il percorso all'indietro, in pratica se si arriva in una posizione di stallo bisogna eliminare la regina e ricominciare da una cella più avanti nella colonna in cui ho eliminato la regina. Quindi se ho capito bene la funzione che ha spiegato Lei, cioè quella ricorsiva: se la regina corrente è a posto richiama se stessa per mettere la prossima regina, altrimenti ritorna. Il problema che mi ha tratto in inganno è che questo mio amico mi ha parlato di backtracking. E' così?
rd(Jun 02): si' e' un caso di backtracking. Questo e' un esercizio-sfida (ma non e' poi tanto complesso). Si puo' risolvere cosi': mettete una regina nella prima riga. La prima regina puo' essere posta in una qualsiasi casella della scacchiera. Occorre provare poi a mettere la seconda regina nella seconda riga. Ci saranno alcune posizioni non possibili perche' la seconda sarebbe in scacco rispetto alla prima. Per ogni posizione possibile della seconda regina si prova a mettere la terza regina sulla terza riga. In questo caso le possibilita' sono ancora meno perche' la terza regina deve evitare di essere in scacco rispetto alla prima e rispetto alla seconda. Tutti i casi nei quali riuscite a collocare le 8 regine sono soluzioni del problema.
Provo a dirlo in altre parole (cosi' con due spiegazioni potete prendere quella che vi risulti piu' chiara). Ovviamente non si possono mettere due regine su una riga, sarebbero in scacco. Allora potremmo costruire l'albero di tutte le posizioni delle regine, una per riga. La prima regina puo' essere messa in 8 caselle diverse e cosi' la seconda e cosi' via. L'albero avrebbe 8^8 (otto all'ottava) foglie cioe' 16777216 foglie. Un po' tante. Allora durante la costruzione dell'albero vengono potati i rami che sicuramente non portano a soluzione perche' la regina che stiamo collocando e' in scacco rispetto a una delle precedenti. (NB potare i rami dell'albero e' una definizione in "informatichese" corretto, questa operazione si chiama anche in Inglese tree pruning).
Domenico. Quindi Prof Davoli, considerato che le regine si muovono in diagonale, verticale e orizzontale di un qualsiasi numero di passi, e considerato anche che le combinazioni possibili sono 92, ma è già difficile riuscirne a trovare una, questa potrebbe la soluzione grafica.
R . . . . . . . . . . . . R . . . . . . . . . R . . R . . . . . . . . . . . R . . . . R . . . . . R . . . . . . . . . . R . . .
rd: questa e' una delle 92 soluzioni che il programma deve stampare. Come formato dell'output e' molto chiaro. Domenico: 2 Giugno 2014 - Ore 21:04 - Sicuramente sarà sbagliato, ma ci sto provando da ieri pomeriggio. Vediamo un pò. Renzo Davoli: 2 giugno 2014 - Ore 23.50 - Questa soluzione non e' sbagliata, e' scorretta. Vuole cortesemente spiegare Lei a tutti i suoi colleghi perche'? Domenico:'3 Giugno 2014 - Ore 00.10 - Scorretta? Forse perché qualche amico ha cercato di aiutarmi? Non capisco. Lo spieghi Lei a me e a miei colleghi, perché tutto ciò' è scorretto. rd: Certamente. 'Domenico: 3 Giugno 2014 - Ore 10:20 (Ora di buco a scuola). Praticamente Lei sta insinuando che ho copiato. Bene. Allora: 1) Le avevo detto che ieri pomeriggio un amico mi aveva parlato di backtracking e in serata mi ha postato l'esercizio (se l'ha copiato da Internet non lo so). 2) Lei stesso dice sempre che si può copiare, ma poi bisogna spiegare o comprendere ciò che si copia (su questo sono d'accordo con Lei). 3) Qualche settimana fa, qualche mio/a collega aveva inserito in questa pagina (anzi negli esercizi dell'8 Maggio)un esercizio sulla ricorsione che ancora non avevamo fatto. Ma Lei è stato molto più gentile. C'è l'ha con me? (non è necessario rispondere, è evidente). 4) Senza offesa per tutti i miei colleghi, ma mi pare che la maggioranza si è fatta e si fa aiutare...ma secondo Lei di chi è la colpa? Cioè, perché ci facciamo sempre aiutare da qualcuno? Perché con Lei non capiamo? Ed ancora, si è chiesto in questi giorni, come mai molti miei colleghi si stanno ritirando?Ogni tanto si faccia qualche domanda e se non si sa rispondere, Giovedì glielo dico io di chi è la colpa.
from sys import exit
#Disegna scacchiera
def draw(n):
global file
for y in range(0,n):
for x in range(0,n):
if scacchiera[y][x]:
file.write("#")
else:
file.write("O")
file.write("\n")
file.write("-"*(n+3)+"\n")
#Funzione di Verifica della Soluzione
def _control(n):
for x in range(0,n):
for y in range(0,n):
if scacchiera[x][y]:
for t in range(0,n):
if scacchiera[t][y] and t!=x: return 0
for t in range(0,n):
if scacchiera[x][t] and t!=y: return 0
for t in range(-n,n):
if (x-t)>=0 and (y-t)>=0 and (x-t)<n and (y-t)<n:
if scacchiera[x-t][y-t] and (x-t)!=x and (y-t)!=y: return 0
for t in range(-n,n):
if (x-t)>=0 and (y-(-t))>=0 and (x-t)<n and (y-(-t))<n:
if scacchiera[x-t][y-(-t)] and (x-t)!=x and (y-(-t))!=y: return 0
return 1
#Funzione Backtracking
def backtracking(n,row):
if row<0:
if _control(n):
draw(n)
return
if not _control(n):
return
for x in range(0,n):
if scacchiera[x][row]==0:
scacchiera[x][row]=1
backtracking(n,row-1)
scacchiera[x][row]=0
return
n=input("Valore n:> ")
path=raw_input("Percorso file:> ")
if n<2:
print "Impostazioni errate."
exit()
file=open(path,"w")
#Crea la scacchiera n*n
scacchiera=[]
for t in range(0,n):
scacchiera.append([0]*n)
print "Elabaorazione in corso.."
backtracking(n,n-1)
print "Operazione terminata."
file.close()
2
usando i dizionari Scrivere un programma che presa in input una stringa metta in output il codice morse del testo inserito. Es. "renzo" diventa "._. .. _. __.. ___" Estensione (un po' piu' difficile!), scrivere un programma che faccia l'operazione inversa: preso in input il morse mostri la stringa corrispondente.
Esercizio svolto da Marta Breda
MorseEncoding = {}
MorseEncoding[" "] = "......."
MorseEncoding["A"] = ".-"
MorseEncoding["B"] = "-..."
MorseEncoding["C"] = "-.-."
MorseEncoding["D"] = "-.."
MorseEncoding["E"] = "."
MorseEncoding["F"] = "..-."
MorseEncoding["G"] = "--."
MorseEncoding["H"] = "...."
MorseEncoding["I"] = ".."
MorseEncoding["J"] = ".---"
MorseEncoding["K"] = "-.-"
MorseEncoding["L"] = ".-.."
MorseEncoding["M"] = "--"
MorseEncoding["N"] = "-."
MorseEncoding["O"] = "---"
MorseEncoding["P"] = ".--."
MorseEncoding["Q"] = "--.-"
MorseEncoding["R"] = ".-."
MorseEncoding["S"] = "..."
MorseEncoding["T"] = "-"
MorseEncoding["U"] = "..-"
MorseEncoding["V"] = "..-"
MorseEncoding["W"] = "...-"
MorseEncoding["X"] = "-..-"
MorseEncoding["Y"] = "-.--"
MorseEncoding["Z"] = "--.."
MorseEncoding["1"] = ".----"
MorseEncoding["2"] = "..---"
MorseEncoding["3"] = "...--"
MorseEncoding["4"] = "....-"
MorseEncoding["5"] = "....."
MorseEncoding["6"] = "-...."
MorseEncoding["7"] = "--..."
MorseEncoding["8"] = "---.."
MorseEncoding["9"] = "----."
MorseEncoding["0"] = "-----"
parola = raw_input('Inserire la parola da codificare in alfabeto morse: ')
result = ""
i = 0
while i < len( parola ):
result += MorseEncoding[ parola[ i ].upper() ]
i += 1
print result
3
Scrivere un programma ricorsivo che dato n e m fornisca in output il valore del coefficiente binomiale n su m (quello del triangolo di Tartaglia) esercizio svolto da Franca (rd: ottimo, sfrutta l'ottimizzazione descritta nei commenti agli esercizi dell'8 maggio).
'''Calcolo del coefficiente binomiale (n k) in forma ricorsiva
Esercizio n.3 (autore: franca)'''
import math
def binomio(n,k):
if k<1:
return 1
else:
return (n-k+1)*binomio(n,k-1)//k
print("Coefficiente binomiale in forma ricorsiva")
print("")
print("Inserire i numeri di riga e colonna del coefficiente binomiale")
print("")
n=-1
while n<0 or k<0 or k>n:
n=int(input("Numero di riga (grado del binomio) n "))
k=int(input("Numero di colonna k "))
print("")
if k==0 or k==n:
b=1
else:
b=binomio(n,k)
print("Il valore del coefficiente binomiale è ",b)
4
usando i dizionari Scrivere un programma che prese in input un numero imprecisato di stringhe ponga in output la statistica della frequenza delle lettere che compaiono (cioe' quale e' la frequenza della 'a', della 'b' etc.) Il conteggio deve aver luogo senza tenere in cosiderazione se le lettere sono maiuscole o minuscole. Svolto da Cati utilizzando libro e slide del corso.
parola=raw_input("inserisci una parola: ")
ConteggioLettere={}
for i in parola:
ConteggioLettere [i]=ConteggioLettere.get (i,0)+1
ConteggioLettere=ConteggioLettere.items()
ConteggioLettere.sort()
print ConteggioLettere
Da quel che ho capito get rimanda il valore della chiave incrementato in base alla frequenza (+1 per ogni volta che compare). Con la funzione items()ritorna una lista di tuple nella forma (chiave, valore) o (key, value), in cui la lista contiene tutti i dati del dizionari.
5
Scrivere una funzione ricorsiva che data una stringa la restuisca invertita (l'ultimo carattere deve diventare il primo e viceversa). Svolto da Silvia.
def inverti(s):
if len(s) == 1 :
return s
ss = inverti(s[1:])+s[0]
return ss
if __name__=="__main__":
str0 = raw_input("inserisci la stringa: ")
print("La stringa invertita e': " + inverti(str0))
6
Scrivere una funzione ricorsiva che calcoli il prodotto scalare fra vettori e un programma che ne provi il funzionamento. (rd: ottimo... si poteva anche controllare len(vettA)>0 e nel caso fosse falso restituire 0).
''' Esercizio svolto da Runa'''
def prodScal(vettA, vettB):
if len (vettA)>1:
return float(vettA[0])*float(vettB[0]) + prodScal (vettA[1:], vettB[1:])
else:
return float(vettA[0])*float(vettB[0])
vettA = raw_input("inserite il primo vettore\t").split()
vettB = raw_input("inserite il secondo vettore\t").split()
n = 0
if len(vettA)==len(vettB):
n=prodScal(vettA, vettB)
print n
else:
print "I vettori hanno cardinalita' differente "
7
Scrivere un programma ricorsivo che prenda in input n stringhe della stessa lunghezza e ponga in output l'output trasposto: la prima riga deve essere composta dai primi caratteri di tutte le stringhe, la seconda riga contiene tutti i secondi caratteri delle stringhe e cosi' via. (estensione: se le stringhe in input hanno lunghezza diversa, portarle tutte ad avere la lunghezza di quella massima aggiungendo spazi in coda alle stringhe piu' corte).
8
Usando la ricorsione scrivere le funzioni capaci di calcolare il minimo comune multiplo e il massimo comun divisore fra due numeri (eseguito da Gaetana) rd: Ottimo.
def MCD(a, b): #funzione del Massimo comune divisore in forma ricorsiva
if b==0:
return a
else:
return MCD(b,a%b)
def mcm(a,b):#funzione del minimo comune multiplo
return (a*b)/MCD(a,b)
n1=input("Dammi il primo numero: ")
n2=input("Dammi il secondo numero: ")
mass_com_div = MCD(n1,n2)
min_com_mult = mcm(n1,n2)
print "Il MCD = ", mass_com_div
print "Il mcm = ",min_com_mult
9
Scrivere una funzione ricorsiva che dato un numero restituisce vero/falso a seconda che il numero introdotto sia o meno un numero triangolare Commenti alle soluzioni (rd)
'''Esercizio svolto da Runa'''
def Triang (somma, contatore, verif):
contatore += 1
somma += contatore
if somma < verif:
b= Triang (somma, contatore, verif)
return b
elif somma == verif:
return True
else:
return False
numContr = int(raw_input("Inserire il numero da controllare\t"))
verificato = Triang (0, 0, numContr)
if verificato:
print ("Il numero inserito e' Triangolare")
else:
print ("Il numero inserito NON e' Triangolare")
10
Scrivere una funzione ricorsiva che conti quante cifre decimali ha un numero intero (e.g. numdigit(12345) sia 5, numdigit(24) sia 2). Svolto da Silvia. Commenti alle soluzioni (rd)
def numdigit(num):
if abs(num)/10 == 0 :
return 1
numApp = numdigit(num/10) + 1
return numApp
if __name__=="__main__":
num0 = input("inserisci un numero intero: ")
print("Il numero di cifre decimali e': " + str(numdigit(num0))
11
Scrivere una funzione ricorsiva che preso in input un numero e una base converta il numero in quella base (es. 10 in base 3 e' 31, 3 volte 3**1 + 1. 93 in base 3 e' 312)
'''Esercizio svolto da Runa'''
def convert (num, base):
def con(numero, base):
if numero<base:
s.append (numero)
else:
con(numero//base, base)
s.append(numero%base)
s=[]
con (num, base)
covertito = ""
for x in range(len(s)):
covertito +=str(s[x])
return int(covertito)
x = input ("Inserire un numero e una base (es. 10, 2):\t")
numero, base = x.split(',')
numero = int(numero)
base = int (base)
s=convert (numero,base)
print (s)
12
Scrivere una funzione ricorsiva che data una stringa, elimini da essa tutte le vocali. es novowels("Bologna e' turrita") -> "Blgn ' trrt" svolto da Silvia. rd: e' una soluzione corretta.
vowels = {'a','e','i','o','u'}
def novowels(s):
if len(s) == 0 :
return ''
if s[0] in vowels:
ss = novowels(s[1:])
else:
ss = s[0] + novowels(s[1:])
return ss
if __name__=="__main__":
str0 = raw_input("inserisci la stringa: ")
print("La stringa invertita e': " + novowels(str0))
13
Scrivere una funzione ricorsiva che faccia la somma fra vettori (i vettori siano memorizzati come liste). (Estensione: fare una seconda funzione che sommi matrici) (Altra estensione, se le matrici o i vettori non hanno la stessa dimensione interpretare tutti i valori mancanti come zeri).
14
Scrivere una funzione ricorsiva che data un valore ed una lista di valori ordinati in modo non decrescente inserisca il nuovo elemento nella lista mantenendola ordinata. es: ninsert(10,[1,3,4,5,15,22])->[1,3,4,5,10,15,22]) Commenti alle soluzioni (rd)
Compito svolto da Alice B
def inserisciordinato(lista,e):
if len(lista)==0:
return [e]
if len(lista)==1:
if lista[0]>e:
return [e]+lista
else:
return lista+[e]
if len(lista)>1:
p1=lista[0:len(lista)//2]
p2=lista[len(lista)//2:len(lista)]
if lista[len(lista)//2]>e:
return inserisciordinato(p1,e)+p2
else:
return p1+inserisciordinato(p2,e)
listaInput=input("inserici la prima lista di numeri").split(',')
lista1=[]
for i in listaInput:
lista1.append(int(i))
e=int(input("inserici un numero"))
lista=inserisciordinato(lista1,e)
print(lista)
15
Scrivere una funzione ricorsiva che data una tupla, fornisca in output una lista di tuple che comprenda tutte le possibili rotazioni della tupla stessa, es. rott((1,2,3,4))->[(1,2,3,4),(2,3,4,1),(3,4,1,2),(4,1,2,3)]
16
Scrivere una funzione ricorsiva che fonda (merge) due liste ordinate. La lista in output deve contenere tutti gli elementi di entrambe le liste, essere ordinata (scrivere l'algoritmo di fusione, non usare sort o altre funzioni gia' presenti) merge([1,3,5],[0,2,4,42])->[0,1,2,3,4,5,42] rd: ottimo. Nell'esempio ordina stringhe, ma funzionerebbe anche con interi.
'''esercizio svolto da Alice B'''
def listmerge(l1,l2):
if len(l1)==0:
print ('caso base l1 vuota')
return l2
if len(l2)==0:
print ('caso base l2 vuota')
return l1
if(l1[0]>l2[0]) :
return l2[:1]+listmerge(l1,l2[1:]);
else:
return l1[:1]+listmerge(l1[1:],l2);
lista1=input("inserici la prima lista di numeri").split(',')
lista2=input("inserici la seconda lista di numeri").split(',')
lista3=listmerge(lista1,lista2)
print('il risultato delle liste ordinate è ',lista3)
17
Usando il metodo format, scrivere un programma che prese in input coppie nome-valore ponga in output l'istogramma. I valori devono essere posti in ordine decrescente. Es.
Italia 10 Francia 7 Germania 8 Grecia 2 output: Italia ********** Germania ******** Francia ******* Grecia **
19
Scrivere una versione della funzione ricorsiva vista a lezione per il riconoscimento delle stringhe palindrome che funzioni anche per le frasi palindrome. Ritorna True/False a seconda se la frase data in Input e' o no palindroma. Deve riconoscere per esempio: "ai lati d'Italia" "Anna di sera se c'e Cesare si danna" Come vedete spazi, punteggiatura, minuscole e minuscole non contano. Esercizio svolto da Agostino Commenti alle soluzioni (rd)
palindroma=(raw_input("inserisci la stringa:"))
print("la stringa inserita e':")
print(palindroma)
def palin(palindroma):
x=len(palindroma)
if x==0 or x==1:
return "palindroma"
if palindroma[0]==palindroma[x-1]:
return palin(palindroma[1:x-1])
else:
return "non palindroma"
print (palin(palindroma))
19
Scrivere una funzione ricorsiva che, data una stringa, restituisca la stessa stringa correttamente spaziata: - fra le parole deve essere presente un carattere spazio, non piu' di uno - prima dei simboli di punteggiatura non ci deve essere uno spazio, dopo si'. es.
input: Ei fu.Siccome immobile , dato il mortal sospiro,stette la spoglia immemore output: Ei fu. Siccome immobile, dato il mortal sospiro,stette la spoglia immemore
