R1T11P5ZL3BNZ

I_R_W14_M37_C++ Algorytmy zachłanne

Źródło: Scott Webb, domena publiczna.
Już wiesz

  • czym charakteryzują się algorytmy zachłanne,

  • na czym polega zagadnienie algorytmiczne, jakim jest problem wydawania reszty,

  • jak zastosować podejście zachłanne przy rozwiązaniu problemów,

  • jakie są ograniczenia metody zachłannej i dlaczego algorytmy zachłanne nie zawsze znajdują najlepsze rozwiązanie dla danego problemu.

Teraz czas sprawdzić swoją wiedzę i umiejętności w praktyce.

Ćwiczenie 1
R1LR1KDOOLUM7
Wymyśl pytanie na kartkówkę związane z tematem materiału.
Ćwiczenie 2
RLFKXU79G1D3Z
Czy dla reszty równej 57 i nominałów 20, 9, 6, 3 i 2 algorytm zachłanny zadziała poprawnie? Możliwe odpowiedzi: 1. Tak, 2. Nie
Ćwiczenie 3
R1V3R1EN8197M
Wyznacz ciąg nominałów, które może wybrać zachłanny algorytm wydawania reszty. Możliwe odpowiedzi: 1. 9 9 9 7 1, 2. 12 7 6 3, 3. 7 7 7 2 2 2 1, 4. 8 8 4 3
Ćwiczenie 4
RKSZCEQMHBT27
Jakie monety może wybrać aslgorytm zachłanny, jeśli reszta do wydania równa jest 36? Możliwe odpowiedzi: 1. 9 9 9 9, 2. 10 8 6 6 6, 3. 9 9 8 6 4, 4. 11 11 11 1 1 1
Ćwiczenie 5
R1AAE8K38OETO
Jakiej reszty nie wyda algorytm zachłanny jeśli dostępne nominały to 8, 7, 5, 4 i 3? Możliwe odpowiedzi: 1. 94, 2. 122, 3. 65, 4. 112
Ćwiczenie 6
R197RDU2ENFA5
Algorytm zachłanny wydawania reszty może niepoprawnie dobrać monety, ale poprawnie zwrócic monety. Możliwe odpowiedzi: 1. Prawda, 2. Fałsz
Ćwiczenie 7
R1DEAA3D1HV4Q
Wstaw w tekst w odpowiedniej kolejnośći nominały, które zostaną użyte przez zachłanny algorytm wydawania reszty równej 159.
Ćwiczenie 8
R1NDPQNCOBKN5
Połącz w pary wartość reszty z monetami, które może użyć algorytm zachłanny do ich wydania? Mam nieograniczony dostęp do monet 9, 4, 3 i 2. 46 Możliwe odpowiedzi: 1. 9 3, 2. 9 9 9 9 4 3, 3. 9 9 9 9, 4. 4 4 12 Możliwe odpowiedzi: 1. 9 3, 2. 9 9 9 9 4 3, 3. 9 9 9 9, 4. 4 4 43 Możliwe odpowiedzi: 1. 9 3, 2. 9 9 9 9 4 3, 3. 9 9 9 9, 4. 4 4 8 Możliwe odpowiedzi: 1. 9 3, 2. 9 9 9 9 4 3, 3. 9 9 9 9, 4. 4 4
Ćwiczenie 9
R14F9JC5HA81E
Jeśli możemy użyć monety jedno złotowej niezależnie od pozostałych nominałów algorytm zawsze zwróci optymalny wynik dla reszty całkowitoliczbowej? Możliwe odpowiedzi: 1. Prawda, 2. Fałsz
Ćwiczenie 10

Zapisz za pomocą pseudokodu algorytm zachłannego wydawania reszty. W algorytmie wykorzystaj tablicę nominałów, ale uwzględnij to, że każdego nominału można użyć tylko raz.

Program powinien wyświetlić informację o wykorzystanych nominałach oraz komunikat, czy reszta została wydana poprawnie.

Przykładowe wyjście dla reszty 912 i nominałów 500, 200, 100, 50, 20, 10, 5, 2, 1:

Linia 1. Wykorzystano nominał dwukropek 500. Linia 2. Wykorzystano nominał dwukropek 200. Linia 3. Wykorzystano nominał dwukropek 100. Linia 4. Wykorzystano nominał dwukropek 50. Linia 5. Wykorzystano nominał dwukropek 20. Linia 6. Wykorzystano nominał dwukropek 10. Linia 7. Wykorzystano nominał dwukropek 5. Linia 8. Wykorzystano nominał dwukropek 2. Linia 9. Wykorzystano nominał dwukropek 1. Linia 10. Reszta nie została zwrócona poprawnie.

Specyfikacja:

Dane:

  • resztaDoWydania – liczba naturalna; wartość reszty do wydania

  • n – liczba naturalna; liczba dostępnych nominałów

  • nominały – tablica liczb naturalnych; tablica dostępnych nominałów posortowana malejąco

Wynik:

  • komunikat dotyczący wykorzystanych nominałów i tego, czy reszta została zwrócona poprawnie.

RJXRZGZPG77GH
Wybierz jedno nowe słowo poznane podczas dzisiejszej lekcji i ułóż z nim zdanie.
Implementacja
I_R_W14_M38_C++ Podejście zachłanne. Najkrótsza droga w grafie