Paolo Boldi

Problemi per la lezione del 22/11

• [Caratteri] Scrivete un programma che, dopo aver letto una stringa, stampi tutti e soli i caratteri da cui è composta senza ripetizioni. L'ordine in cui i caratteri vengono stampati è irrilevante. Ad esempio, se la stringa letta fosse caricatore il programma dovrebbe stampare caritoe oppure una qualunque sua permutazione.
• [Identità ciclica] Due stringhe v e w sullo stesso alfabeto sono dette ciclicamente equivalenti sse esistono due stringhe x,y tali che v=xy e w=yx. È facile vedere che questo definisce una relazione di equivalenza sul monoide libero, le cui classi si chiamano collane. Scrivete un programma che, lette due stringhe, determini se sono ciclicamente equivalenti oppure no.
• [Rimpiazzare] La classe String contiene un metodo che consente di rimpiazzare tutte le occorrenze di un certo carattere, o di una certa stringa, con un altro carattere, o stringa. Trovate questo metodo consultando la documentazione delle API, e poi scrivete un programma che operi come segue:
  • legge due stringhe, diciamo x e y
  • inizia quindi un ciclo di lettura di stringhe: ogni volta che legge una stringa, la stampa dopo aver sostituito tutte le occorrenze di x con y
  • quando l'utente inserisce la stringa vuota, il programma termina.
• [Approssimazione di radici (1)] Supponete di avere un razionale q>1. La sua radice quadrata sarà compresa nell'intervallo (1,q); un modo per approssimarla consiste nel procedere come segue: si parte dall'intervallo (1,q) e si guarda se il suo punto medio ((q+1)/2) ha un quadrato maggiore o minore di q. Se il suo quadrato è esattamente q, abbiamo trovato la radice quadrata. In caso contrario, abbiamo determinato un intervallo più piccolo in cui cercarla (si tratterà di (1,(q+1)/2) oppure ((q+1)/2,q)). Scrivete un programma che, dopo aver letto una frazione maggiore di uno, effettui 10 passi di iterazione, e stampi la frazione risultante alla fine del procedimento. Verificate che i valori ottenuti sono buone approssimazioni della radice quadrata, p.es., stampando il valore trovato e quello cercato come numeri double; vi ricordo che per calcolare la radice quadrata di un double x si deve scrivere Math.sqrt(x)
• [Approssimazione di radici (2)] Modificate il programma di approssimazione delle radici in modo da garantire che il quadrato della frazione ottenuta come risultato differisca da quella data in input per meno di una certa soglia di tolleranza inserita dall'utente sottoforma di frazione.
• [Converti in binario] Scrivete un programma che, dopo aver letto un intero, lo stampi in binario (ad es., leggendo 5 dovrebbe stampare 101). Notate che per convertire l'intero nella sua rappresentazione binaria potete produrre (stringhe da) un carattere per volta a partire da destra, e per accumulare i caratteri potete usare il metodo di concatenazione delle stringhe.