ok ok , ho risolto adesso devo fare un altro programma del quale, in questo momento non ho idea di come iniziarlo, mentre ci ragiono se qualcuno mi può dare un aiuto sarebbe di notevole gradimento
Questa è la traccia:
Il Bancomat
Lo sportello bancomat di una certa banca ha a disposizione banconote di taglio pari a 5 €, 10 €, 20 €, 50
€, 100 €e 500 €in quantita illimitate. Un certo numero
n di clienti e in fila la per prelevare e supponiamo
che
l'i-esimo cliente voglia prelevare
qi euro. Per semplicita puoi assumere che
qi sia multiplo di 5 €. Ad
esempio, non e ammesso prelevare 103 €oppure 272 €. Il bancomat deve soddisfare le richieste di ciascun
cliente usando il
minor numero possibile di banconote.
Risolvi i seguenti esercizi:
1. Supponiamo che un cliente voglia prelevare 20 euro. In quanti modi e possibile soddisfare le sue
richieste? Cosa succede nel caso in cui il cliente voglia prelevare 50 euro?
2. Scrivi una funzione C che riceve in ingresso un intero
b (budget) e calcola il minimo numero di
banconote necessarie per raggiungere il budget
b. Ad esempio se
b = 600 occorrono almeno tre
banconote (una da 500 €e due da 100 €e non e possibile usare un minor numero di banconote).
Se invece
b = 150 allora due banconote (una da 100 €e una da 50 €) sono sufficienti. Qual'e la
complessita della funzione proposta? Dipende dal valore di
b? Supponi che
b sia del tipo
b = 5^k, con
k intero appropriato. Possiamo stimare la complessita della funzione in questo caso?
3. Supponiamo che le richieste dei clienti siano codificate in un opportuno vettore
b tale che
b[i] rappresenti
il budget che l'utente
i-esimo. Scrivi una funzione che stampa, per ciascun cliente, il minimo
numero di banconote necessario per soddisfare le esigenze di ciascun cliente. Qual'e la complessita
dell'algoritmo proposto? Modifica la funzione in modo che restituisca il numero complessivo di
banconote erogate. Qual'e la complessita dell'algoritmo proposto?