Opice
Opica počne, kar pač opice počnejo: skače z drevesa na drevo. Računalnikarji pa počnemo, kar računalnikarji počnemo. Tole.
Drevesa so bila nasajena na enakih razdaljah, vendar so se nekatera posušila. Podana so "polja", na kateri so še vedno drevesa, na primer
(0, 1, 4, 5, 6, 8, 10, 11, 12, 15, 16, 18). Opica lahko preskoči dve prazni polji, torej lahko skoči iz 1 na 4. Od 0 do 18 lahko gre, recimo, tako: 0-1-4-6-8-11-12-15-18, ali pa 0-1-4-5-8-10-12-15-16-18 ali še na veliko drugih načinov.Sestavi algoritem, ki pove, na koliko načinov lahko pride od prvega do zadnjega drevesa. Sprogramiraj. Oceni časovno zahtevnost.
Če so drevesa na
(0, 1, 4, 5, 6, 8, 10, 11, 12, 15, 16, 18)je možnih poti (najbrž) 18, če so na(0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13)pa 1705.Tako pri tej kot pri vseh nadaljnjih nalogah smeš predpostaviti, da je pot možna, torej da ni nikjer luknje, ki je opica ne bi mogla preskočiti.
Pravzaprav sem lagal. Drevesa niso bila posajena na enakih razdaljah. Lahko so tudi tako:
(0, 0.8, 1.2, 3.8, 4.1, 4.2, 4.5, 6.1, 8.6, 9.0, 10.5, 12.8, 15, 17.7, 18). Opica lahko skoči za 3 enote daleč. Reši enako nalogo kot prej.Pri
(0, 0.8, 1.2, 3.8, 4.1, 4.2, 4.5, 6.1, 8.6, 9.0, 10.5, 12.8, 15, 17.7, 18)je različnih poti najbrž 216. Lahko poskusiš tudi primere iz prejšnje naloge: rezultat mora biti enak, kot ga da prejšnji program.Kaj, če je opica lena in bi rada skočila čim manjkrat? Sestavi algoritem, ki poišče zaporedje pozicij dreves, na katera bo skočila. Napiši program, oceni časovno zahtevnost.
Za gornji primer vrne
[0, 1.2, 4.2, 6.1, 9.0, 10.5, 12.8, 15, 18].Opice nekaterih dreves ne marajo, ker smrdijo. Se pravi drevesa, ne opice. No, točneje, če opica skoči na smrdljivo drevo, se še sama malo usmradi. Za vsako drevo je podano, kako močno smrdi (v novem seznamu, poleg pozicij dreves). Opica torej želi izbrati pot, pri kateri se bo čim manj usmradila, to je, pot, pri kateri bo vsota smradu vseh dreves, na katerih bo skočila, čim manjša. Sestavi algoritem, napiši program, oceni časovno zahtevnost.
Primer bi bil
pozicije = (0, 1, 2, 3, 4, 5, 7, 9.3, 10, 11, 11.1, 11.3, 14, 14.1) smrad = (0, 1, 2, 5, 2.8, 3, 1, 2, 1, 2, 2, 0, 2, 0)Najnižja cena je nabrž 5.8.
Aja, ne. Opica se je usmradila toliko, kolikor smrdi najbolj smrdljivo drevo na poti.
V tem primeru je rešitev najbrž 2.8.
Če so pozicije
[0, 0.7970911197973055, 2.9587489930391824, 3.7723680029357234, 5.008902447442285, 5.263739906571981, 6.279960513589227, 7.978504844279105, 10.470055717955693, 10.683605375623962, 12.45122284810067, 13.58309446702597, 15.56357987520201, 16.188007081429333, 17.432002943715037, 18.03540710070482, 18.255399180486634, 18.71594850035931, 20.184243173179183, 20.29587219659339, 22.979779783137992, 23.479508583633283, 24.80439198478713, 27.058399451281538, 27.724228369088333, 29.292259600437145, 31.36514685888712, 31.644069891708526, 32.75920590555635, 33.96819356026529, 34.32609005820399, 36.32132494519354, 37.927511604221635, 38.84624522726339, 40.52185408020551, 42.35909410527699, 44.32211099903517, 47.04863492041293, 48.64806602773064, 49.7146902403228, 51.37151815961714, 51.738740555487716, 52.10463310616873, 52.66143326357805, 53.19768457181697, 53.908392652290026, 53.97977395189285, 54.28888288422298, 55.47401697210187, 55.727013576417804, 56.63606482703858, 58.619828461417384, 59.50461138487908, 60.594098589559906, 61.87529787193363, 61.877948740106824, 63.08165000410926, 64.33645158023263, 65.89380657724209, 67.643572238577, 68.82293069112994, 69.10717547047311, 71.01600814800744, 73.03388734469897, 73.35834912013534, 74.94776632306399, 75.287409012742, 76.1568496108658, 76.47101575963184, 77.65807391455823, 79.06116114974147, 80.12925870704233, 80.49169825143309, 80.70953275515299, 80.90512363132623, 81.09934696699125, 82.40790924563632, 83.42350442563895, 84.97712201098608, 85.36098402729431, 87.51240967504388, 87.74574656997783, 87.7624362717896, 87.87080730481095, 89.40935552952217, 89.51171352180518, 91.10926831798143, 92.08904636388651, 92.22826719879089, 93.91187040859514, 94.07190674132983, 95.02453730844208, 95.60529008205816, 97.06424154450276, 97.13508992836181, 98.20269177052339, 98.72925279790988, 101.68728550681105, 102.16179111829963, 104.86049204768013, 105.58527393269303, 106.03683837903347, 107.94314415924855, 108.24106289987931, 109.02598209531894, 110.09234402582818, 112.78094033897591, 113.6052302391423, 115.00829734806015, 115.14256793610511, 115.7410774090702, 116.02012382633876, 118.55017416223423, 119.88166302063237, 120.48127927211382, 120.99393918881425, 121.70080281864317, 122.53761967907421, 122.76309995313079, 123.18736921226535, 123.50934773414353, 123.55710113766455, 123.75188933613929, 125.99123981299739, 126.60110293473694, 127.27545086446095, 127.87422826291753, 129.12042883589694, 130.1346957740851, 131.76530706619133, 133.25319480442235, 133.43704629627808, 134.99405022796478, 137.98237450002344, 140.7013237926352, 141.67217436489673, 142.31342228952434, 142.75249886375187, 142.8460227276672, 144.67771461211103, 146.8771574708427, 147.14028839847253, 150.10271982813234, 151.72664146876676, 152.07566449370967, 153.8841717665507, 154.80783619014412, 155.41472654489056, 156.98159123406518, 157.24698730439115, 157.38890348235373]
in smrad
[0, 1.3856137808894353, 4.385798634586444, 4.390688326557993, 4.750016737979484, 4.560205442998386, 1.5302127653143711, 1.6217113006776263, 2.550043227965291, 0.9730329687909045, 3.115674606588543, 4.666416701357303, 4.061855068001556, 4.937783666859446, 0.5698826461176387, 2.1713106008488965, 4.058561086871282, 1.2325251991966772, 1.802482007092678, 3.642965735146364, 3.6216883510945674, 1.2778033117449734, 2.845800421676841, 1.5162398892727187, 3.737159050298202, 2.1488263859653776, 2.993311069895093, 3.8925730013316766, 2.6476142504231372, 3.593121915895548, 1.8649008667477958, 3.942200167242506, 3.5762078477611765, 2.721012382623379, 2.6293348935016683, 2.1611461880701315, 3.53956243979996, 2.8702829191841337, 3.993395359124286, 0.9850814544196507, 4.375357549403533, 0.8283060062088304, 2.3765716147294014, 2.414822325221016, 0.8980433994135761, 3.2991291683703095, 2.3943245251732392, 1.3079635747614315, 3.068432888429321, 2.7899709824043626, 3.179245854059271, 4.606409366637125, 1.9873947676206187, 2.63964650756985, 3.855497753156017, 0.2506256537319751, 3.6016596589927543, 2.9350087373946336, 4.177057740261517, 0.38372811865883094, 1.6110125685899912, 4.136045274528463, 0.5920981086072308, 1.7701973989550819, 1.9496314054293613, 1.7080214993027272, 3.535400008390512, 2.3531399517796494, 3.6023868491748434, 0.6276313271575873, 1.4858048618795927, 3.691308474727001, 2.4365099774276966, 4.558395707346156, 2.154889935444046, 3.931019814259882, 1.0726014884553532, 3.8294716222052494, 4.4748287037172325, 1.408618952455793, 3.980546603724368, 1.81101521773066, 4.9966979117926105, 2.224374698036247, 3.4096733202227325, 1.5953435942689553, 3.10035714603778, 0.9060384112729558, 2.059168471991573, 1.1769182415305708, 0.5957827658282128, 0.5154746142332911, 4.324599691840606, 1.4058466855520275, 0.36107490320334834, 0.4785012652707904, 4.758014477403199, 2.3713434895534915, 4.636360025539284, 0.32376381056356984, 4.374778923849524, 2.1930247694383898, 1.1827746143334184, 3.5513531977793122, 2.7816958724280627, 3.5352497922048536, 2.8256688857808965, 4.610692523141631, 4.0097893486429665, 4.723572782581077, 3.2292294015589724, 1.944264201853589, 0.562969066145238, 3.811869455019661, 3.1545739853062966, 1.9796362545008876, 1.105027857218455, 0.1504540061955234, 2.8645202918638524, 1.5859293270138526, 1.3966365363722493, 1.2392383387202472, 0.06256073233452841, 4.246553296676935, 2.0663040802482935, 0.09943734771953927, 4.130863435575518, 3.1639902933508206, 4.15940741061825, 4.790767101878556, 1.7428312681794584, 2.4872907172020353, 4.249421041762093, 2.2057012752881184, 0.33611170081189634, 1.1948170009663095, 4.651579251240342, 1.1886889712662145, 1.6758542461881158, 2.5196969200529926, 0.01876870264201136, 1.670800111631046, 4.313226544665446, 1.597768198204201, 0.36004323588285536, 1.8681060211716471, 3.094567738457274, 2.243673752688318, 4.692767050943886, 1.0486029623353694, 0]
potem optimalna pot v nalogi 4 najbrž usmradi opico za 145.28526899282403, v nalogi 5 pa za 4.790767101878556.