WorksheetsMetoda zachłanna
Total questions: 15
Worksheet time: 8mins
Name
Class
Date
1.
Na czym polega fundamentalna zasada działania algorytmu opartego na podejściu zachłannym?
a)
Na dzieleniu głównego problemu na mniejsze, niezależne podproblemy i łączeniu ich rozwiązań.
b)
Na dokonywaniu w każdym kroku wyboru, który w danym momencie wydaje się najlepszy (lokalnie optymalny).
c)
Na analizowaniu wszystkich możliwych rozwiązań w celu znalezienia globalnego optimum.
d)
Na losowym wybieraniu kolejnych kroków w nadziei na znalezienie dobrego rozwiązania
2.
Czy algorytm zachłanny zawsze gwarantuje znalezienie globalnie optymalnego rozwiązania problemu?
a)
Nie, często prowadzi do rozwiązania przybliżonego, które jest bliskie optymalnemu, ale niekoniecznie najlepsze.
b)
Tak, ponieważ w każdym kroku wybiera najlepszą dostępną opcję, co sumarycznie prowadzi do najlepszego wyniku.
c)
Tak, ale tylko w przypadku problemów, które można rozwiązać w czasie wielomianowym.
d)
Nie, algorytmy zachłanne z założenia nigdy nie znajdują rozwiązania optymalnego, a jedynie dopuszczalne.
3.
Dlaczego w programach realizujących algorytm wydawania reszty zaleca się unikanie typów zmiennoprzecinkowych (np. float) do przechowywania kwot pieniężnych?
a)
Ponieważ typy te nie pozwalają na przechowywanie wartości ujemnych, które mogą być potrzebne w obliczeniach.
b)
Ponieważ operacje na liczbach zmiennoprzecinkowych są znacznie wolniejsze od operacji na liczbach całkowitych.
c)
Ponieważ binarne reprezentacje niektórych ułamków dziesiętnych są niedokładne, co prowadzi do błędów zaokrągleń.
d)
Ponieważ standardowe biblioteki nie obsługują formatowania walutowego dla typów zmiennoprzecinkowych.
4.
Jaka jest zalecana metoda implementacji problemu wydawania reszty, aby uniknąć błędów związanych z precyzją liczb zmiennoprzecinkowych?
a)
Używanie typu danych o podwójnej precyzji (double) zamiast pojedynczej (float).
b)
Przechowywanie kwot jako ciągów znaków (string) i konwertowanie ich na liczby tylko w ostatecznym momencie.
c)
Zaokrąglanie wyniku po każdej operacji dodawania lub odejmowania.
d)
Przekształcenie wszystkich kwot na najmniejszą jednostkę (np. grosze) i operowanie na liczbach całkowitych.
5.
W "problemie kinomana", który polega na wybraniu jak największej liczby filmów do obejrzenia z danego harmonogramu, która strategia zachłanna gwarantuje znalezienie optymalnego rozwiązania?
a)
Wybieranie w pierwszej kolejności najkrótszych dostępnych filmów.
b)
Sortowanie filmów według ich czasów zakończenia i wybieranie kolejnych, które nie kolidują z poprzednio wybranym.
c)
Wybieranie filmów, które mają najmniej kolizji z innymi seansami w harmonogramie.
d)
Wybieranie w pierwszej kolejności filmów, które zaczynają się najwcześniej.
6.
Rozważmy nietypowy system monetarny z nominałami {1, 4, 6}. Jaką resztę wydałby algorytm zachłanny dla kwoty 8?
a)
4 + 4
b)
1 + 1 + 1 + 1 + 1 + 1 + 1 + 1
c)
4 + 1 + 1 + 1 + 1
d)
6 + 1 + 1
7.
Który z podanych problemów jest klasycznym przykładem problemu optymalizacyjnego, do którego rozwiązania często stosuje się podejście zachłanne?
a)
Obliczanie NWD dwóch liczb metodą Euklidesa.
b)
Problem wyboru zajęć (problem kinomana).
c)
Sortowanie bąbelkowe listy liczb.
d)
Sprawdzanie, czy w tekście występuje dany wzorzec.
8.
W implementacji algorytmu dla problemu kinomana, sortowanie listy filmów według czasów zakończenia jest kluczowe, ponieważ:
a)
chroni program przed błędami dostępu do elementów listy poza jej zakresem.
b)
zapewnia, że program szybciej znajdzie jakiekolwiek rozwiązanie.
c)
upraszcza to kod, eliminując potrzebę stosowania zagnieżdżonych pętli.
d)
dzięki niemu kolejne lokalnie optymalne wybory składają się na globalnie optymalne rozwiązanie.
9.
Co oznacza stwierdzenie, że polski system monetarny jest tak skonstruowany, że dla problemu wydawania reszty metoda zachłanna działa w sposób optymalny?
a)
Oznacza to, że wszystkie nominały są potęgami tej samej liczby, co upraszcza obliczenia.
b)
Oznacza to, że liczba dostępnych monet każdego nominału w kasie jest zawsze nieskończona.
c)
Oznacza to, że każda kwota reszty może być wydana przy użyciu dokładnie jednej monety lub banknotu.
d)
Oznacza to, że wydanie reszty za pomocą największych dostępnych nominałów zawsze prowadzi do użycia minimalnej możliwej liczby monet i banknotów.
10.
W kodzie programu `Wydawanie_reszty` , pętla `while` jest kluczowa dla algorytmu. Jaki warunek poprawnie definiuje, jak długo pętla powinna się wykonywać, aby sprawdzić wszystkie nominały dla pozostałej reszty? Uzupełnij brakujący fragment: `while ______:`
a)
reszta > 0
b)
reszta > 0 and i < N
c)
reszta >= NOMINALY[i]
d)
i < N
11.
Dlaczego pierwsza wersja programu do wydawania reszty, operująca na liczbach zmiennoprzecinkowych (`float`), mogła zwracać niedokładne wyniki, np. dla kwoty 7.85 zł?
a)
Ponieważ algorytm zachłanny nie działa dla polskiego systemu monetarnego.
b)
Z powodu błędów zaokrągleń wynikających z binarnej reprezentacji ułamków dziesiętnych.
c)
Ponieważ pętla `while` kończyła się zbyt wcześnie.
d)
Z powodu błędnej kolejności nominałów w liście `NOMINALY`.
12.
W poprawionej wersji programu `Wydawanie_reszty2` (str. 154), problem niedokładności rozwiązano przez operowanie na liczbach całkowitych (groszach). Który fragment kodu poprawnie wczytuje i konwertuje kwotę reszty na grosze?
a)
reszta_zlote = int(input("Podaj liczbę złotych reszty: ")) reszta_grosze = int(input("Podaj liczbę groszy reszty: ")) reszta = reszta_zlote * 100 + reszta_grosze
b)
reszta = float(input("Podaj kwotę reszty: "))
c)
reszta = int(float(input("Podaj kwotę reszty: ")) * 100)
d)
reszta = int(input("Podaj kwotę reszty w groszach: "))
13.
W algorytmie sortowania użytym w problemie kinomana, kluczowy jest warunek pętli `while`. Uzupełnij brakujący fragment, który zapobiega wyjściu poza początek listy: `while ______ and koniec[j] > pom_koniec:`
a)
j > 0
b)
j >= 0
c)
j > pom_koniec
d)
i < N
14.
W którym z podanych przypadków podejście zachłanne do problemu wydawania reszty MOŻE NIE znaleźć rozwiązania optymalnego (czyli wydać więcej monet niż to konieczne)?
a)
Dla systemu monetarnego o nominałach {1, 2, 5, 10}.
b)
Dla systemu monetarnego o nominałach {1, 5, 10, 25}.
c)
Dla systemu monetarnego o nominałach {1, 6, 10} przy wydawaniu reszty 12.
d)
Dla dowolnego systemu, w którym najmniejszym nominałem jest 1.
15.
W funkcji `Wybierz` dla problemu kinomana znajduje się pętla `for i in range(1, N):`. Jaki jest cel rozpoczęcia tej pętli od indeksu 1, a nie 0?
A.
B.
C.
D.
a)
Jest to błąd w kodzie; pętla powinna zaczynać się od 0.
b)
Ponieważ filmy są numerowane od 1 do N.
c)
Aby uniknąć błędu `IndexError` przy odwoływaniu się do `poczatek[i-1]`.
d)
Ponieważ pierwszy film (o indeksie 0) jest zawsze wybierany jako część optymalnego rozwiązania.
100 %
