[P.....2]

Mirki z #python i #programowanie. Ponieważ awansowałem z pozycji 183 758 na pozycję 89 312 w rankingu codewars (a to zobowiązuje). Postanowiłem zmierzyć się z trudniejszymi zadaniami ( @Masterczulki - na razie NASA musi radzić sobie sama). No to śmiechom nie było końca, a teraz do rzeczy:

mamy funkcję, która w automacie vendingowym wydaje resztę z monet, które są na liście przekazanej parametrem:

def optimalnumberofcoins(n, coins):

results = []
indexstart = 3
counter = 0

for i in range(3, -1, -1):
print(i)
counter = 0
left = int(n)
iTmp = i

while left > 0:
#change lower then denomination
if left % coins[iTmp] == left:
iTmp -= 1
elif left % coins[iTmp] >= 1:
counter +=1
left = left - coins[iTmp]
else:
left = left - coins[iTmp]
counter +=1
results.append(counter)
print("Rozpoczęto od nominału",i, "Monet wydano", counter)


return min(results)

test funkcji poniżej:

Test.assertequals(optimalnumberofcoins(76, [1, 3, 4, 10]), 9)

Ponieważ nie zawsze wydawanie od największych nominałów jest najbardziej efektywne pod względem liczby monet, stąd w pętli sprawdzałem przebiegi dla przypadków, kiedy mniejsze nominały niż największe dają lepszy rezultat,

Ale OP okazał się być wyjątkowo autystyczny i sprawa wygląda tak, że wcale nie musi lecieć wydawanie po kolei, a może być bardziej efektywny przypadek, gdzie wydajemy

7 * 10 + 1 * 3 + 1 * 3 => 9 monet

niż np.

7 * 10 + 1 * 4 + 2 * 1 => 10 monet.

I nie wiem jak to ugryźć, może ma ktoś pomysł.

Przyszło mi do głowy brutalne liczenie po kolei, ale podejrzewam że musi być metoda. Może jakaś podpowiedź?

#python #programowanie

[S.....s]

@Praetorian2002: no spoko, ale co ma ten kod robić?

[P.....2]

@SuppressWarnings: Wydawać monety. Generalnie wprowadzona jest kwota ktorą ma wydać oraz lista z dostępnymi nominałami. Funkcja, która sprawdza ma podaną kontrolną ilość monet do wydania. I tutaj się wykładam, bo ja jestem w stanie zrobić tak, że jadę od największych nominałów, miele, liczę ile bilonu mam wydać, jak skończę, to zmniejszam licznik i sprawdzam, czy nie będzie bardziej efektywnie zacząć od mniejszego nominału, aż do najmniejszego. Ale OP ustawił taki test

[S.....s]

@Praetorian2002: ale jak wydawać te monety? losowo czy jest jakiś warunek np. najmniejsza liczba monet?

[P.....2]

@SuppressWarnings: no właśnie wychodzi na to że ma wydać jaknajmniej i tu się wykładam,

[S.....s]

@Praetorian2002: zrobiłbym coś na kształt BFSa - tylko że sąsiadów masz kolejne monety, i np. nigdy nie idziesz do wyższej
daj mi 10 minut to spróbuje napisać xd

[P.....i]

@Praetorian2002: dam Ci sposób, tzn. faktycznie wymyśliłbyś jakąś metodę zachłanna, ale jeśli chcesz poznać dokładnie jak to się robi szukaj w google pod hasłem change making problem.

[P.....2]

@SuppressWarnings: ja myślałem właśnie że to będzie jakieś drzewko decyzyjne, ale niestety to nie mój poziom. Trochę to dziwne, bo na levelu 6kyu takie zadanie wisi.

[P.....2]

@Proxima_Centauri: Spoko, ale chyba odpuszcze, bo to nie ma sensu. Skoro ja z podstawami kuleję, to po co mam się porywać na rozwiązywanie problemu na zasadzie: nie umiem, ale ctrl c ctrl v i lepienie.

Z metod czasochłonnych, to myślałem nad chamskim przeszukiwaniu tej listy i liczeniu na zasadzie

1. Biorę 4 pozniej 3 pozniej 2 pozniej 1 results.append(counter)
2. biorę 4 pozniej 2 pozniej 1 results.append(counter)
3. biore 4 pozniej

[S.....s]

@Praetorian2002: https://pastebin.com/WgJE7Be8

[P.....2]

@SuppressWarnings: Dzięki Mirku, teraz muszę to przełożyć na nasze :)

[aseeon_]

@Praetorian2002: https://en.wikipedia.org/wiki/Change-making_problem

[P.....2]

@SuppressWarnings: @aseeon_: Panowie jednak się poddałem - jeszcze nie ten poziom.