Sprawdź się

Pokaż ćwiczenia:

RcnwrURtY6shd1

Ćwiczenie 1

R1e9rnExuu2LG1

Ćwiczenie 2

RNNkYlV8cyNeJ1

Ćwiczenie 3

Ćwiczenie 4

Napisz program, który znajdzie minimalną liczbę monet potrzebnych do wydania zadanej kwoty, zakładając, że mamy do dyspozycji nieograniczoną liczbę monet o danych nominałach. Przyjmujemy, że rozwiązanie istnieje. W rozwiązaniu użyj programowania dynamicznego.

Specyfikacja problemu:

Dane:

monety – lista zawierająca dostępne nominały monet; lista liczb naturalnych
reszta – wartość, którą należy wymienić na dostępne nominały; liczba naturalna

Wynik:

liczba_monet – minimalna liczba monet potrzebna do wydania reszty; liczba naturalna

Działanie programu przetestu przetestuj dla następujących danych:

monety = [1, 3, 7, 9]
reszta = 59

Wynik działania programu dla podanych danych:

Rf9fyTxl24z7K

RheBjwwHBqRs1

def wydanie_reszty(monety, reszta):
	liczba_monet = 0
	m = [0 for _ in range(reszta + 1)]
	nieskonczonosc = 1000000

	for v in range(1, reszta + 1):
		m[v] = nieskonczonosc
		k = nieskonczonosc

		for moneta in monety:
			if v - moneta >= 0:
				k = m[v - moneta]

			if v < nieskonczonosc and k + 1 < m[v]:
				m[v] = k + 1

	liczba_monet = m[-1]
	return liczba_monet


if __name__ == '__main__':
	monety = [1, 3, 7, 9]
	reszta = 59

	print(wydanie_reszty(monety, reszta))

Ćwiczenie 5

Dany jest pręt długości dlugosc oraz lista cen za pręty długości od 1 do dlugosc. Pręt można pociąć na kawałki, ale tylko w ten sposób, aby długość każdego fragmentu była liczbą całkowitą. Napisz program, który zwróci maksymalną cenę, jaką można uzyskać za pręt o zadanej długości po jego pocięciu, przy danej liście z cenami (nieprzecięty pręt również jest możliwym rozwiązaniem).

Specyfikacja problemu:

Dane:

dlugosc – długość danego w zadaniu pręta; liczba naturalna
ceny – lista cen za odpowiednie długości pręta; lista liczb naturalnych o długości długosc

Wynik:

maksymalna_wartosc – maksymalna cena za odpowiednio pocięty pręt; liczba naturalna

Działanie programu przetestu przetestuj dla następujących danych:

ceny = [1, 5, 8, 9, 10, 17, 18, 20]
dlugosc = 8

Wynik działania programu dla podanych danych:

RMj2RiotSciIs

RmnR1zeeN1fJ7

def ciecie_preta(ceny, dlugosc):
	maksymalna_dlugosc = 0
	if dlugosc == 0:
		return 0

	ceny_posrednie = [0 for _ in range(dlugosc + 1)]

	for i in range(1, dlugosc + 1):
		for j in range(1, i + 1):
			if ceny_posrednie[i] < ceny[j - 1] + ceny_posrednie[i - j]:
				ceny_posrednie[i] = ceny[j - 1] + ceny_posrednie[i - j]

	maksymalna_dlugosc = ceny_posrednie[-1]
	return maksymalna_dlugosc


ceny = [1, 5, 8, 9, 10, 17, 18, 20]
dlugosc = 8
print(ciecie_preta(ceny, dlugosc))

Prezentacja multimedialna

Dla nauczyciela