Informatyka 2
Nowa edycja
FilmProgramowanie w Pythonie. Algorytmy zachłanne. Wiele monet
Film omawia stosowanie algorytmów zachłannych na przykładzie wydawania reszty przy użyciu minimalnej liczby monet.
Ćwiczenie 0
Zaopatrzeniowiec dostaje listę zakupów. Martwi się, aby nie przekroczyć dopuszczalnego udźwigu po załadowaniu samochodu. Zdefiniuj funkcję zakupy(c, m, z), której parametrami są liczby worków c – cukru, m – mąki i z – ziemniaków. Worki cukru ważą 2 kg, mąki 5 kg i ziemniaków 12 kg. Udźwig samochodu wynosi 500 kg. Wynikiem funkcji jest True, gdy samochód może przewieźć zakupy, lub False, gdy zostanie przekroczony udźwig. Sprawdź działanie funkcji dla podanych poniżej parametrów.
- Wynikiem funkcji
zakupy(4, 9, 12)jestTrue. - Wynikiem funkcji
zakupy(12, 34, 43)jestFalse.
Wskazówka
Należy znaleźć łączną wagę produktów, a potem porównać wynik z 500. Łączną wagę produktów obliczamy, mnożąc liczbę worków przez ich masy, potem poszczególne liczby dodajemy do siebie.
# zdefiniuj funkcję
def zakupy(c, m, z):
pass
# testy
print(zakupy(4, 9, 12))
print(zakupy(12, 34, 43))
Wynikiem funkcji zakupy(4, 9, 38) jest False.
testResult = zakupy(4, 9, 38)==False
False
zakupy(4, 9, 38)
Wynikiem funkcji zakupy(5, 9, 37) jest True.
testResult = zakupy(5, 9, 37)==True
True
zakupy(5, 9, 37)
Wynikiem funkcji zakupy(6, 9, 37) jest False.
testResult = zakupy(6, 9, 37)==False
False
zakupy(6, 9, 37)
Ćwiczenie 1Trzy monety
Dysponujesz nieograniczoną liczbą monet o nominałach 5, 3 i 1 i masz wydać resztę przy użyciu minimalnej liczby monet. Zdefiniuj funkcję trzy(kwota), której wynikiem będzie minimalna liczba monet potrzebnych do wydania kwoty podanej jako parametr. Sprawdź działanie funkcji dla podanych poniżej parametrów.
- Wynikiem funkcji
trzy(11)jest3. - Wynikiem funkcji
trzy(99)jest21.
# zdefiniuj funkcję
def trzy(kwota):
pass
# testy
print(trzy(11))
print(trzy(99))
Wynikiem funkcji trzy(1) jest 1.
testResult = trzy(1)==1
1
trzy(1)
Wynikiem funkcji trzy(22) jest 6.
testResult = trzy(22)==6
6
trzy(22)
Wynikiem funkcji trzy(35) jest 7.
testResult = trzy(35)==7
7
trzy(35)
Ćwiczenie 2Wiele monet
Dysponujesz nieograniczoną liczbą monet o nominałach 20, 10, 5, 2 i 1 i masz wydać resztę przy użyciu minimalnej ich liczby. Zdefiniuj funkcję wiele(kwota), której wynikiem będzie minimalna liczba monet potrzebnych do wydania kwoty podanej jako parametr. Sprawdź działanie funkcji dla podanych poniżej parametrów.
- Wynikiem funkcji
wiele(11)jest2. - Wynikiem funkcji
wiele(99)jest8.
# zdefiniuj funkcję
def wiele(kwota):
pass
# testy
print(wiele(11))
print(wiele(99))
Wynikiem funkcji wiele(1) jest 1.
testResult = wiele(1)==1
1
wiele(1)
Wynikiem funkcji wiele(22) jest 2.
testResult = wiele(22)==2
2
wiele(22)
Wynikiem funkcji wiele(35) jest 3.
testResult = wiele(35)==3
3
wiele(35)
Ćwiczenie 3Ograniczona liczba monet
Dysponujesz podaną liczbą monet o określonych nominałach i masz wydać resztę przy użyciu minimalnej ich liczby. Zdefiniuj funkcję monety(kwota, nominaly, sztuki), której wynikiem będzie minimalna liczba monet potrzebnych do wydania kwoty podanej jako parametr. Sprawdź działanie funkcji dla podanych poniżej parametrów.
- Wynikiem funkcji
monety(11, [20, 10, 5, 2, 1], [100, 100, 100, 100, 100])jest2. - Wynikiem funkcji
monety(99, [20, 10, 5, 1], [1, 10, 1, 10])jest13.
# zdefiniuj funkcję
def monety(kwota, nominaly, sztuki):
pass
# testy
print(monety(11, [20, 10, 5, 2, 1], [100, 100, 100, 100, 100]))
print(monety(99, [20, 10, 5, 1], [1, 10, 1, 10]))
Wynikiem funkcji monety(21, [20, 5, 1], [1, 10, 10]) jest 2.
testResult = monety(21, [20, 5, 1], [1, 10, 10])==2
2
monety(21, [20, 5, 1], [1, 10, 10])
Wynikiem funkcji monety(21, [20, 10, 1], [0, 10, 1]) jest 3.
testResult = monety(21, [20, 10, 1], [0, 10, 1])==3
3
monety(21, [20, 10, 1], [0, 10, 1])
Wynikiem funkcji monety(55, [20, 10, 5], [3, 3, 3]) jest 4.
testResult = monety(55, [20, 10, 5], [3, 3, 3])==4
4
monety(55, [20, 10, 5], [3, 3, 3])
Ćwiczenie dodatkowe 1
Zaopatrzeniowiec ma kupić cukier, mąkę i ziemniaki. Chce załadować jak najwięcej do samochodu, ale tak, by nie przekroczyć jego udźwigu wynoszącego x kg i przewieźć jak najmniejszą liczbę opakowań. Zdefiniuj funkcję zakupy(x), której parametrem jest udźwig, a wynikiem – łączna liczba opakowań towarów. Worki cukru ważą
2 kg, mąki 5 kg i ziemniaków 12 kg. Sprawdź działanie funkcji dla podanych poniżej parametrów.
- Wynikiem funkcji
zakupy(127)jest12. - Wynikiem funkcji
zakupy(100)jest10.
# zdefiniuj funkcję
def zakupy(x):
pass
# testy
print(zakupy(127))
print(zakupy(100))
Wynikiem funkcji zakupy(23) jest 3.
testResult = zakupy(23)==3
3
zakupy(23)
Wynikiem funkcji zakupy(129) jest 13.
testResult = zakupy(129)==13
13
zakupy(129)
Wynikiem funkcji zakupy(2) jest 1.
testResult = zakupy(2)==1
1
zakupy(2)
Ćwiczenie dodatkowe 2
Zaopatrzeniowiec ma kupić cukier, mąkę i ziemniaki. Chce załadować jak najwięcej do samochodu, ale tak, by nie przekroczyć jego udźwigu wynoszącego x kg i przewieźć jak najmniejszą liczbę opakowań. Dodatkowo nie może kupić więcej niż ile opakowań jednego towaru. Zdefiniuj funkcję zakupy(x, ile), której parametrami są udźwig i maksymalna liczba opakowań jednego towaru, a wynikiem jest łączna liczba opakowań towarów. Worki cukru ważą 2 kg, mąki 5 kg i ziemniaków 12 kg. Sprawdź działanie funkcji dla podanych poniżej parametrów.
- Wynikiem funkcji
zakupy(127, 9)jest14. - Wynikiem funkcji
zakupy(127, 12)jest12.
# zdefiniuj funkcję
def zakupy(x, ile):
pass
# testy
print(zakupy(127, 9))
print(zakupy(127, 12))
Wynikiem funkcji zakupy(23, 5) jest 3.
testResult = zakupy(23, 5)==3
3
zakupy(23, 5)
Wynikiem funkcji zakupy(29, 3) jest 3.
testResult = zakupy(29, 3)==3
3
zakupy(29, 3)
Wynikiem funkcji zakupy(2, 5) jest 1.
testResult = zakupy(2, 5)==1
1
zakupy(2, 5)
Pytania quizoweMetoda zachłanna i dynamiczna
Twój wynik to: /3
-
Które ze stwierdzeń dotyczy metody zachłannej?
-
-
Czy dla każdego typu problemów algorytmy zachłanne dają optymalne rozwiązanie?
-
-
Na czym polega dynamiczne podejście do rozwiązania?
-