1    # Mohó algoritmus az érmék minimális számának megtalálásához
2    
3    def moho_cimletezes(osszeg):
4        cimletek=[1,2,5,10,20,50,100,500,1000]
5        cimlet_db={
6            1:0,2:0,5:0,10:0,
7            20:0,50:0,100:0,
8            500:0,1000:0
9        }
10       felhasznalt_cimletek = []
11       i=-1
12       while i>=-len(cimletek):            # negatív index: visszafelé haladunk
13           while osszeg>=cimletek[i]:      # keressük a lehető legnagyobb címletet
14               osszeg-=cimletek[i]         # csökkentjük vele az összeget
15               felhasznalt_cimletek.append(cimletek[i]) # elhelyezzük a listánkban
16               cimlet_db[cimletek[i]]+=1   # a felhasznált címlet darabszámát növeljük
17           i-=1    #index csökkentése (azaz balra lépés a címleteken)
18   
19       for i in range(len(felhasznalt_cimletek)):
20           print(felhasznalt_cimletek[i], end=' ')
21       print('\nDarabra:')
22       for c, db  in reversed(cimlet_db.items()): #.items(): dict key és value együtt
23           if db!=0:
24               print(c,':',db)
25       
26   
27   # >>>>>>>>>>>>>>>>>> F Ő M O D U L >>>>>>>>>>>>>>>>>>>
28   if __name__ == '__main__':
29       valtando=int(input('A cimletezendő összeg: '))
30       print('A megadott összeg minimális cimletezése:')
31       moho_cimletezes(valtando)
32