Apple компаниясының кассир-бағдарламашы туралы тапсырмасы

Apple компаниясының кассир-бағдарламашы туралы тапсырмасы — Бұл Apple-дегі сұхбаттарда сұралатын өте кең таралған мәселе. Мұның бәрі қандай да бір бағдарламалау тілінде жүзеге асыру қажет қарапайым тапсырмаға байланысты.

Сіз кассир болып толық емес жұмыс күнін алдыңыз деп елестетейік. Бірнеше күннен кейін сіздің БАСШыңыз  сіздің бағдарламашы екеніңізді біліп, шағын бағдарлама жазуыңызды сұрайды.

Apple компаниясының кассир-бағдарламашы туралы тапсырмасы

Бағдарлама екі параметрді қабылдайды:

1. Ақша сомасы
2. Барлық ықтимал монета номиналдарын қамтитын массив7

Орындаудан кейін бағдарлама монеталардың барлық ықтимал номиналдарында көрсетілген ақша сомасын шығарудың барлық мүмкін тәсілдерінің санын беруі керек. Мысалы, номиналы бар монеталардан 5 цент қажет болса 

1, 2 и 3, онда сіз 5 санын аласыз.Бұл ықтимал нұсқалар болғандықтан:

1. 1+1+1+1+1
2. 1+2+2
3. 1+1+3
4. 3+2
5. 1+1+1+2

Мәселенің шешімі

Біз тапсырманы Python бағдарламалау тілі арқылы орындаймыз, бірақ іс жүзінде бұл маңызды емес, өйткені біз үшін ең бастысы — бағдарлама алгоритмін түсіну.Бағдарламада біз динамикалық массивке ие боламыз  

doing_n_cents, онда біз берілген монета номиналдарынан соманы алудың барлық мүмкін тәсілдерінің санын жазамыз. Бастапқыда біз бұл массивті номиналдары жоқ 0 сомасына жинаймыз. Кейінірек біз бір жаңа номинал қосып, массивімізді қайта жасаймыз.Біз барлық ықтимал номиналдармен барлық операцияларды жасағандықтан, енді соманы қосу керек. Бұл жай ғана жасалады. Есіңізде болсын, бізде қазірдің өзінде 0-ге тең сома, сондай-ақ монеталардың барлық номиналдары бар. Бұл жаңа сан бар мән ретінде жазылады:  

higher_amount_remainder = higher_amount - coin.

Сонымен, Python-дағы шешім коды:

def change_possibilities_bottom_up(amount, denominations):
    doing_n_cents = [0] * (amount + 1)
    doing_n_cents[0] = 1
 
    for coin in denominations:
        for higher_amount in range(coin, amount + 1):
            higher_amount_remainder = higher_amount - coin
            doing_n_cents[higher_amount] += doing_n_cents[higher_amount_remainder]
 
    return doing_n_cents[amount]
    
denominations = [1, 2, 3]
print (change_possibilities_bottom_up(5, denominations))

doing_n_centsТүсінікті болу үшін, егер біз 5 және номиналдардың ішінен барлық ықтимал опциялардың санын іздейтін болсақ, массив нені қамтитынының мысалы келтірілген  [1, 3 и 5]:

===========
key:
a = higher_amount
r = higher_amount_remainder
===========
 
============
for coin = 1:
============
[1, 1, 0, 0, 0, 0]
 r  a
 
[1, 1, 1, 0, 0, 0]
    r  a
 
[1, 1, 1, 1, 0, 0]
       r  a
 
[1, 1, 1, 1, 1, 0]
          r  a
 
[1, 1, 1, 1, 1, 1]
             r  a
 
============
for coin = 3:
=============
[1, 1, 1, 2, 1, 1]
 r        a
 
[1, 1, 1, 2, 2, 1]
    r        a
 
[1, 1, 1, 2, 2, 2]
       r        a
 
============
for coin = 5:
=============
[1, 1, 1, 2, 2, 3]
 r              a
 
 
final answer: 3

KazItLearn 2023