Sprawdź się

Pokaż ćwiczenia:

R2T9o1CUS7hBI1

Ćwiczenie 1

RrZKthqvjUW9Q1

Ćwiczenie 2

RlYe3xpB7cjLp1

Ćwiczenie 3

Ćwiczenie 4

Napisz program, który znajdzie minimalną liczbę monet potrzebną do uzyskania zadanej reszty. Zakładamy, że mamy do dyspozycji nieograniczoną liczbę monet o danych nominałach. Zakładamy też, że dane nominały pozwalają na wydanie zadanej kwoty. W rozwiązaniu użyj programowania dynamicznego.

Specyfikacja problemu:

Dane:

reszta – kwota do wydania; liczba naturalna
monety – tablica zawierająca dostępne nominały monet; tablica liczb naturalnych

Wynik:

liczbaMonet – minimalna liczba monet potrzebna do wydania zadanej kwoty; liczba całkowita

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

int reszta = 34;
int[] monety = new int[] {8, 5, 3, 2};

Wynik działania programu dla podanych danych:

RXGiuY6zijCvf

Program wypisuje minimalną liczbę monet, która jest potrzebna do wydania zadanej kwoty. Zapoznaj się z poniższym kodem startowym, a w kolejnym kroku uzupełnij jego fragment w odpowiednim miejscu. Następnie sprawdź, czy całe rozwiązanie jest zgodne z twoimi przewidywaniami.

RUIEV35VzIwAR

Linia 1. public class WydawanieReszty otwórz nawias klamrowy. Linia 2. public static int maksymalnaWartosc znak równości 1000000 średnik. Linia 4. public static int wydawanie podkreślnik reszty otwórz nawias okrągły int reszta przecinek int otwórz nawias kwadratowy zamknij nawias kwadratowy monety zamknij nawias okrągły otwórz nawias klamrowy. Linia 5. int liczbaMonet średnik. Linia 6. int otwórz nawias kwadratowy zamknij nawias kwadratowy d znak równości new int otwórz nawias kwadratowy reszta plus 1 zamknij nawias kwadratowy średnik. Linia 8. d otwórz nawias kwadratowy 0 zamknij nawias kwadratowy znak równości 0 średnik. Linia 10. for otwórz nawias okrągły int i znak równości 1 średnik i otwórz nawias ostrokątny reszta plus 1 średnik i plus plus zamknij nawias okrągły otwórz nawias klamrowy. Linia 11. d otwórz nawias kwadratowy i zamknij nawias kwadratowy znak równości maksymalnaWartosc średnik. Linia 12. int k znak równości maksymalnaWartosc średnik. Linia 14. for otwórz nawias okrągły int moneta dwukropek monety zamknij nawias okrągły otwórz nawias klamrowy. Linia 15. if otwórz nawias okrągły i zamknij nawias ostrokątny znak równości moneta zamknij nawias okrągły otwórz nawias klamrowy. Linia 16. k znak równości d otwórz nawias kwadratowy i minus moneta zamknij nawias kwadratowy średnik. Linia 17. zamknij nawias klamrowy. Linia 19. if otwórz nawias okrągły i otwórz nawias ostrokątny maksymalnaWartosc ampersant ampersant k plus 1 otwórz nawias ostrokątny d otwórz nawias kwadratowy i zamknij nawias kwadratowy zamknij nawias okrągły otwórz nawias klamrowy. Linia 20. d otwórz nawias kwadratowy i zamknij nawias kwadratowy znak równości k plus 1 średnik. Linia 21. zamknij nawias klamrowy. Linia 22. zamknij nawias klamrowy. Linia 23. zamknij nawias klamrowy. Linia 25. liczbaMonet znak równości d otwórz nawias kwadratowy reszta zamknij nawias kwadratowy średnik. Linia 26. return liczbaMonet średnik. Linia 27. zamknij nawias klamrowy. Linia 29. public static void main otwórz nawias okrągły String otwórz nawias kwadratowy zamknij nawias kwadratowy args zamknij nawias okrągły otwórz nawias klamrowy. Linia 31. int reszta znak równości 34 średnik. Linia 32. int otwórz nawias kwadratowy zamknij nawias kwadratowy monety znak równości new int otwórz nawias kwadratowy zamknij nawias kwadratowy otwórz nawias klamrowy 8 przecinek 5 przecinek 3 przecinek 2 zamknij nawias klamrowy średnik. Linia 34. System kropka out kropka println otwórz nawias okrągły wydawanie podkreślnik reszty otwórz nawias okrągły reszta przecinek monety zamknij nawias okrągły zamknij nawias okrągły średnik. Linia 35. zamknij nawias klamrowy. Linia 36. zamknij nawias klamrowy.

public class WydawanieReszty {
	public static int maksymalnaWartosc = 1000000;

	public static int wydawanie_reszty(int reszta, int[] monety) {
		int liczbaMonet;
		int[] d = new int[reszta + 1];

		d[0] = 0;

		for(int i = 1; i < reszta + 1; i++) {
			d[i] = maksymalnaWartosc;
			int k = maksymalnaWartosc;

			for (int moneta : monety) {
				if (i >= moneta) {
					k = d[i - moneta];
				}

				if (i < maksymalnaWartosc && k + 1 < d[i]) {
					d[i] = k + 1;
				}
			}
		}

		liczbaMonet = d[reszta];
		return liczbaMonet;
	}

	public static void main(String[] args) {

		int reszta = 34;
		int[] monety = new int[] {8, 5, 3, 2};

		System.out.println(wydawanie_reszty(reszta, monety));
	}
}

Ćwiczenie 5

Dany jest pręt o pewnej długości dlugosc oraz tablica z cenami za pręty o długościach od 1 do dlugosc. Pręt można pociąć na mniejsze fragmenty (jednak muszą mieć długość będącą liczbą naturalną) i sprzedać je osobno w celu uzyskania jak największej wartości. Napisz program, który zwróci maksymalną wartość, jaką można otrzymać za pręt o zadanej długości. W rozwiązaniu wykorzystaj programowanie dynamiczne.

Specyfikacja problemu:

Dane:

dlugosc – długość danego pręta; liczba naturalna
ceny – tablica z cenami za pręty długości od 1 do dlugosc; tablica liczb naturalnych

Wynik:

maksymalnaWartosc – maksymalna wartość, jaką można uzyskać za sprzedanie pręta o zadanej długości przy danych cenach; liczba naturalna

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

int[] ceny = {1, 5, 8, 9, 10, 17, 18, 20};
int dlugosc = 8;

Wynik działania programu dla podanych danych:

R1NW86eHKOrkC

Program wypisuje maksymalną wartość, jaką można uzyskać, sprzedając pręt o zadanej długości, przy danych cenach. W poniższym polu znajduje się kod startowy, uzupełnij go we wskazanym miejscu.

R1YJVkMEbfb6a

Linia 1. public class CieciePreta otwórz nawias klamrowy. Linia 2. public static int ciecie podkreślnik preta otwórz nawias okrągły int otwórz nawias kwadratowy zamknij nawias kwadratowy ceny przecinek int dlugosc zamknij nawias okrągły otwórz nawias klamrowy. Linia 3. int maksymalnaWartosc średnik. Linia 4. if otwórz nawias okrągły dlugosc znak równości znak równości 0 zamknij nawias okrągły. Linia 5. return 0 średnik. Linia 7. int otwórz nawias kwadratowy zamknij nawias kwadratowy ceny podkreślnik posrednie znak równości new int otwórz nawias kwadratowy dlugosc plus 1 zamknij nawias kwadratowy średnik. Linia 8. for otwórz nawias okrągły int i znak równości 0 średnik i otwórz nawias ostrokątny dlugosc plus 1 średnik i plus plus zamknij nawias okrągły otwórz nawias klamrowy. Linia 9. ceny podkreślnik posrednie otwórz nawias kwadratowy i zamknij nawias kwadratowy znak równości 0 średnik. Linia 10. zamknij nawias klamrowy. Linia 12. for otwórz nawias okrągły int i znak równości 1 średnik i otwórz nawias ostrokątny dlugosc plus 1 średnik i plus plus zamknij nawias okrągły otwórz nawias klamrowy. Linia 13. for otwórz nawias okrągły int j znak równości 1 średnik j otwórz nawias ostrokątny i plus 1 średnik j plus plus zamknij nawias okrągły otwórz nawias klamrowy. Linia 14. if otwórz nawias okrągły ceny podkreślnik posrednie otwórz nawias kwadratowy i zamknij nawias kwadratowy otwórz nawias ostrokątny ceny otwórz nawias kwadratowy j minus 1 zamknij nawias kwadratowy plus ceny podkreślnik posrednie otwórz nawias kwadratowy i minus j zamknij nawias kwadratowy zamknij nawias okrągły. Linia 15. ceny podkreślnik posrednie otwórz nawias kwadratowy i zamknij nawias kwadratowy znak równości ceny otwórz nawias kwadratowy j minus 1 zamknij nawias kwadratowy plus ceny podkreślnik posrednie otwórz nawias kwadratowy i minus j zamknij nawias kwadratowy średnik. Linia 16. zamknij nawias klamrowy. Linia 17. zamknij nawias klamrowy. Linia 19. maksymalnaWartosc znak równości ceny podkreślnik posrednie otwórz nawias kwadratowy dlugosc zamknij nawias kwadratowy średnik. Linia 20. return maksymalnaWartosc średnik. Linia 21. zamknij nawias klamrowy. Linia 23. public static void main otwórz nawias okrągły String otwórz nawias kwadratowy zamknij nawias kwadratowy args zamknij nawias okrągły otwórz nawias klamrowy. Linia 24. int otwórz nawias kwadratowy zamknij nawias kwadratowy ceny znak równości otwórz nawias klamrowy 1 przecinek 5 przecinek 8 przecinek 9 przecinek 10 przecinek 17 przecinek 18 przecinek 20 zamknij nawias klamrowy średnik. Linia 25. int dlugosc znak równości 8 średnik. Linia 26. System kropka out kropka println otwórz nawias okrągły ciecie podkreślnik preta otwórz nawias okrągły ceny przecinek dlugosc zamknij nawias okrągły zamknij nawias okrągły średnik. Linia 27. zamknij nawias klamrowy. Linia 28. zamknij nawias klamrowy.

public class CieciePreta {
	public static int ciecie_preta(int[] ceny, int dlugosc) {
		int maksymalnaWartosc;
		if (dlugosc == 0)
			return 0;
		
		int[] ceny_posrednie = new int[dlugosc + 1];
		for (int i=0; i < dlugosc + 1; i++) {
			ceny_posrednie[i] = 0;
		}

		for (int i=1; i < dlugosc + 1; i++) {
			for (int j=1; j < i + 1; j++) {
				if (ceny_posrednie[i] < ceny[j - 1] + ceny_posrednie[i - j])
					ceny_posrednie[i] = ceny[j - 1] + ceny_posrednie[i - j];
			}
		}

		maksymalnaWartosc = ceny_posrednie[dlugosc];
		return maksymalnaWartosc;
	}

	public static void main(String[] args) {
		int[] ceny = {1, 5, 8, 9, 10, 17, 18, 20};
		int dlugosc = 8;
		System.out.println(ciecie_preta(ceny, dlugosc));
	}
}

Prezentacja multimedialna

Dla nauczyciela