     
P 48 (2020/2021) 5 29
k[0][i] = 0
for w in range(W+1):
k[w][0] = 0
for w in range(1, W+1):
for i in range(1, N+1):
w_i, p_i = weights[i-1],
prices[i-1]
if w_i > w:
k[w][i] = k[w][i-1]
else:
k[w][i] = max(k[w][i-1],
k[w-w_i][i-1] + p_i)
return k[W][N]
Ta tehnika računanja reši problem v približno W ¨
N korakih, kar je precej bolj učinkovito, kot če bi
preverili vse možnosti. Bralci ste tudi spodbujeni,
da preverite, ali podana programska koda izračuna
enake številke, kot so dane v tabeli 2. Lahko pa po-
skusite rešiti primer z npr. petimi ali več predmeti in
se prepričate o pravilnosti in enostavnosti postopka.
Literatura
[1] R. Bellman, Eye of the Hurricane: An Autobio-
graphy, World Scientific, 1984.
ˆ ˆ ˆ
Rešitev
nagradne
uganke
B̌ K
Bralcem smo v članku 21 aritmetičnih vprašanj
o številu 2021 v prejšnji številki zastavili naslednjo
uganko: Za katera naravna števila n se število n! v
običajnem desetiškem zapisu konča z natanko 2021
ničlami? Do 14. marca 2021 smo v uredništvu pre-
jeli dve rešitvi, obe pravilni: iskano število sploh ne
obstaja. Uspešna reševalca Ivan Lisac iz Kopra in An-
drej Jakobčič iz Novega mesta bosta za nagrado pre-
jela knjigo o teoriji števil iz ponudbe DMFA – zalo-
žništva. Rešitev, do katere lahko pridemo tudi brez
računalnika, je zapisana v nadaljevanju.
Označimo število končnih ničel števila n! z ozna-
ko tpnq. Kot je bilo opisano že v članku, je število
tpnq enako eksponentu prafaktorja 5 v prafaktoriza-
ciji števila n!, saj vsaka končna ničla nastane z mno-
ženjem para prafaktorjev 2 in 5. Ker je med 1 in
n natanko rn5 s večkratnikov števila 5, natanko r
n
52 s
večkratnikov števila 25 in tako dalje, lahko za dani
n vrednost tpnq izračunamo po De Polignacovi (ozi-
roma Legendrovi) formuli tpnq “
ř8
k“1
”
n
5k
ı
.
Da bi določili število n z lastnostjo tpnq “ 2021,
je potrebno razmišljati v obratno smer. Števila n se-
veda ni mogoče direktno izraziti iz enačbe. Ker pa
za funkcijo celi del velja rxs ď x, lahko z uporabo
formule za vsoto geometrijske vrste dobimo oceno
tpnq “ 2021 ă
8
ÿ
k“1
n
5k
“ n
5
8
ÿ
k“0
ˆ
1
5
˙k
“ n
5
¨ 1
1 ´ 15
“ n
4
oziroma n ą 8084. Za n “ 8085 zdaj z uporabo
De Polignacove formule dobimo tp8085q “ 2018, to-
rej je treba n nekoliko povečati. Opazimo lahko, da
zaradi preštevanja večkratnikov števila 5 velja, da je
tpnq ą tpn ´ 1q, če je n večkratnik števila 5, sicer
pa je tpnq “ tpn ´ 1q. Zato hitro ugotovimo, da je
tp8090q “ . . . “ tp8094q “ 2019 in tp8095q “ . . . “
tp8099q “ 2020, toda tp8100q “ 2022, saj je 8100
deljivo s 25. Dokazali smo, da iskano število n ne
obstaja.
Omenimo še, da lahko ročno računanje z De Poli-
gnacovo formulo precej pohitrimo z uporabo znane
zveze rn{pabqs “ rrn{as{bs, po kateri lahko rekur-
zivno izračunamo izraze oblike rn{pks. Za števili
n “ 8085 in p “ 5 dobimo denimo r8085{5s “ 1617,
r8085{52s “ r1617{5s “ 323, r8085{53s “ r323{5s “
64, r8085{54s “ r64{5s “ 12, r8085{55s “ r12{5s “ 2
in r8085{56s “ r2{5s “ 0, od koder sledi tp8085q “
1617 ` 323 ` 64 ` 12 ` 2 ` 0 “ 2018.
ˆ ˆ ˆ