Untitled

Podcast

Play an AI-generated podcast conversation about this lesson

Questions and Answers

Hver er lægsta upphæðin sem gefur mótdæmi þegar gráðug aðferð er notuð til að finna lágmarksfjölda mynta?

365
91
52
416 (correct)

Hvað gerir endurkvæma nálgunin í `MinMyntir(k)` fallinu þegar `k < 0`?

Hún skilar k.
Hún skilar 0.
Hún skilar 1.
Hún skilar ∞ (óendanleika). (correct)

Hvað er átt við með `d ∈ D` í samhengi við endurkvæmu lausnina til að finna lágmarksfjölda mynta?

`d` er ein mynt í safni mynttegunda `D`. (correct)
`d` er upphæðin sem á að skipta upp í myntir og `D` er fjöldi mynta sem notaðar eru.
`d` er fjöldi endurkvæmra kalla og `D` er dýpt endurkvæmninnar.
`d` er lágmarksfjöldi mynta og `D` er safn af upphæðum sem hægt er að skipta upp í.

Hvers vegna er kvik bestun (dynamic programming) notuð til að leysa myntskiptavandann?

Til að forðast endurtekna útreikninga og bæta afköst. (C) Signup and view all the answers

Hvaða gildi skilar `min_myntir(k, D)` fallið ef `k == 0`?

0 (D) Signup and view all the answers

Í `min_myntir` forritinu, hvað táknar `float('inf')`?

Ógilda lausn (B) Signup and view all the answers

Hver er munurinn á gráðugri aðferð og bestu lausn þegar kemur að myntskiptum?

Besta lausnin finnur alltaf lágmarksfjölda mynta, en gráðug aðferð gerir það ekki alltaf. (C) Signup and view all the answers

Hvaða kostur er við að nota töflu í kvikri bestun til að leysa myntskiptavandann?

Taflan geymir niðurstöður fyrir allar upphæðir frá 0 upp í k, sem kemur í veg fyrir endurtekna útreikninga. (B) Signup and view all the answers

Hvaða fullyrðing lýsir best tilgangi þess að leysa vandamálið um stærstu samliggjandi summu í atvinnuviðtölum?

Að meta hæfni umsækjanda til að þróa mismunandi lausnir, skilja tímaflækju og bæta lausnir. (D) Signup and view all the answers

Hver er tímaflækjan fyrir einföldu lausnina (brute force) við vandamálinu um stærstu samliggjandi summu?

O(n^3) (B) Signup and view all the answers

Hvernig er innsta lykkjan notuð í einföldu lausninni (O(n^3)) við vandamálinu um stærstu samliggjandi summu?

Til að reikna summu hlutfylkisins frá A[i] til A[j]. (A) Signup and view all the answers

Hver er kosturinn við að nota hlutsummur til að leysa vandamálið um stærstu samliggjandi summu?

Það dregur úr tímaflækjunni með því að losa sig við innstu lykkjuna. (C) Signup and view all the answers

Hver er tímaflækjan fyrir lausn sem notar hlutsummur til að finna stærstu samliggjandi summu?

O(n^2) (D) Signup and view all the answers

Hvað er hlutsumma P[i] í samhengi við lausn með hlutsummum?

Summa allra staka frá A[0] að A[i] í fylkinu A. (D) Signup and view all the answers

Hvernig er summa hlutfylkis A[i..j] reiknuð þegar hlutsummur eru notaðar?

P[j] - P[i - 1] (D) Signup and view all the answers

Hver er minnisflækjan fyrir einföldu lausnina (brute force)?

O(1) (A) Signup and view all the answers

Hver er helsti kosturinn við að nota kvika bestun (dynamic programming) til að leysa vandamálið um stærstu samliggjandi summu?

Betri tímaflækja, O(n), samanborið við O(n^2) eða O(n^3). (D) Signup and view all the answers

Hvaða fullyrðing er sönn varðandi samanburð á einföldu lausninni og hlutsummulausninni?

Hlutsummulausnin krefst meira minnis en einfalda lausnin, en hefur betri tímaflækju. (B) Signup and view all the answers

Í `can_split_same(A, B)` fallinu, hvaða hlutverki gegnir `dp[n] = True`?

Það gefur til kynna að tómi strengurinn sé alltaf gildur hlutstrengur. (D) Signup and view all the answers

Í `count_same_splits(A, B)` fallinu, hvað táknar `dp[i] += dp[j]`?

Bætir við fjölda skiptinga sem byrja á <code>i</code> við fjölda skiptinga sem byrja á <code>j</code>. (A) Signup and view all the answers

Hvert er besta viðmiðið til að velja á milli uppsveiflu (e. bottom-up) og niðursveiflu (e. top-down) nálgunar við dynamic programming (DP) vandamál?

Uppsveifla er betri þegar öll undirvandamál þurfa að vera leyst. (D) Signup and view all the answers

Hver er tímaflækjustigið fyrir `can_split_same(A, B)` fallið, gefið að `is_word()` sé O(1)?

O(n^2) (A) Signup and view all the answers

Í vandamálinu um stærstu summu hlutstrengs, hvers vegna er mikilvægt að gefa út 0 ef runan inniheldur eingöngu neikvæðar tölur?

Þetta tryggir að við skili alltaf gildri summu, þar sem tómi hlutstrengurinn hefur summu 0. (D) Signup and view all the answers

Hver er munurinn á vandamálinu um lengstu samfelldu hlutrunu og lengstu hlutrunu?

Lengsta samfellda hlutrunan krefst þess að stök séu hlið við hlið, en lengsta hlutrunan gerir það ekki. (D) Signup and view all the answers

Í vandamálinu um stærsta margfeldi hlutstrengs, hvernig meðhöndlar þú neikvæðar tölur?

Heldur utan um bæði stærsta og minnsta margfeldið hingað til. (B) Signup and view all the answers

Hvað er átt við með "minnislistun" (e. memoization) í samhengi við reiknirit?

Að vista niðurstöður kostnaðarsamra aðgerða og skila þeim aftur þegar sama inntakið kemur fyrir aftur. (A) Signup and view all the answers

Hvert er hlutverk `local_sum` breytunnar í Kadane reikniritinu?

Að halda utan um stærstu summu hlutfylkis sem endar í núverandi sæti. (A) Signup and view all the answers

Hvaða fullyrðing lýsir best hvernig Kadane reikniritið finnur stærstu summu samliggjandi hlutfylkis?

Með því að nota <code>local_sum</code> og <code>global_sum</code> til að reikna stærstu summu út frá hverju staki fylkisins. (A) Signup and view all the answers

Hvað táknar breytan `T` í reikniritinu fyrir hringtengda hlutfylkið?

Heildarsummu allra talna í fylkinu. (D) Signup and view all the answers

Í Kadane reikniritinu, hvað gerist ef `local_sum` verður neikvæð?

Þá er <code>local_sum</code> endurstillt á núverandi stak í fylkinu. (A) Signup and view all the answers

Hver er tímaflækjustigið (time complexity) fyrir Kadane reikniritið?

$O(n)$ (A) Signup and view all the answers

Hvert er hlutverk Kadane reikniritsins í samhengi við hringlaga fylki (e. circular array)?

Að finna stærstu summu venjulegs (ekki hringtengds) hlutfylkis og minnstu summu samliggjandi hlutfylkis. (D) Signup and view all the answers

Hvernig er ákveðið hvort stærsta summan `M` í hringlaga fylki sé 0?

Ef M1 er minna en 0, sem þýðir að allar tölur í fylkinu eru neikvæðar eða núll. (A) Signup and view all the answers

Af hverju er línan `return max(0, global_sum)` notuð í lok Kadane reikniritsins?

Til að útiloka möguleikann á að allar tölur í fylkinu séu neikvæðar og skila 0 í staðinn. (B) Signup and view all the answers

Hvaða fullyrðing er sönn um rakningarvensl Kadane reikniritsins, $S(i) = max{A[i], S(i − 1) + A[i]}$?

Það velur stærra gildið á milli núverandi staks og summu þess við bestu summu sem endaði í fyrra sæti. (C) Signup and view all the answers

Hver er tímaflækjustigið (e. time complexity) fyrir reikniritið sem finnur stærstu summu í hringlaga fylki?

$O(n)$ þar sem n er fjöldi staka í fylkinu. (B) Signup and view all the answers

Í sönnun á Kadane reikniritinu, hvaða hlutverki gegnir grunntilvikið þegar $i = 0$?

Það sýnir að stærsta summa sem endar í fyrsta sæti er alltaf fyrsta stakið sjálft. (D) Signup and view all the answers

Í Python útfærslunni, hvaða lína ákvarðar stærstu summu sem endar á núverandi staki (e. current element) í venjulegu Kadane útgáfunni?

<code>max_ending_here = max(x, max_ending_here + x)</code> (D) Signup and view all the answers

Hvaða breyting er gerð á Kadane reikniritinu til að finna minnstu summu samliggjandi hlutfylkis?

Skipt er út <code>max</code> fyrir <code>min</code> í samanburðinum. (B) Signup and view all the answers

Hver er ávinningurinn af því að nota Kadane reikniritið umfram aðrar aðferðir til að finna stærstu summu samliggjandi hlutfylkis?

Kadane reikniritið hefur betri tímaflækju en flestar aðrar aðferðir ($O(n)$). (B) Signup and view all the answers

Ef við erum með fylki `A = [-2, -3, 4, -1, -2, 1, 5, -3]` og við notum reikniritið til að finna stærstu summu hringlaga hlutfylkis, hvað verður `M1` (stærsta summa venjulegs hlutfylkis)?

9 (B) Signup and view all the answers

Fyrir hvaða tilvik er mikilvægt að athuga hvort allar tölur í fylkinu séu neikvæðar þegar stærsta samliggjandi hlutsumma er reiknuð í hringlaga fylki?

Þegar reikna á <code>M2</code> (stærstu summu hringtengda hlutfylkis). (D) Signup and view all the answers

Í Python útfærslunni fyrir `max_subarray_long`, hvað gerist ef lengd fylkisins `A` er minni en `X`?

Fallið skilar <code>None</code>. (C) Signup and view all the answers

Í `max_subarray_long` fallinu, hvaða hlutverki gegnir `curr_min` breytan?

Hún geymir minnstu hlutsummu sem fundist hefur hingað til, innan leyfilegs glugga. (B) Signup and view all the answers

Hver er tímaflækjan í `max_subarray_long` fallinu?

O(n) (D) Signup and view all the answers

Hvað er átt við með 'rennandi glugga' (e. sliding window) aðferðinni í samhengi við 'stutt hlutfylki' vandamálið (c)?

Aðferð til að skoða hlutfylki af fastri lengd sem 'rennur' yfir fylkið. (A) Signup and view all the answers

Hvaða gagnagrind er notuð til að halda utan um leyfilega vísa í rennandi glugga lausninni fyrir 'stutt hlutfylki' vandamálið?

Tvíenda biðröð (e. Deque) (A) Signup and view all the answers

Í lausninni fyrir 'stutt hlutfylki' vandamálið með rennandi glugga, hvers vegna er vísum sem eru utan gluggans [max(0, j − X), j − 1] fjarlægt?

Til að tryggja að við séum aðeins að skoða hlutfylki sem eru innan leyfilegrar lengdar. (B) Signup and view all the answers

Í lausninni fyrir 'stutt hlutfylki' vandamálið með rennandi glugga, hvert er hlutverk þess að fjarlægja P gildi hægra megin úr biðröðinni á meðan þau eru minni en P[j]?

Til að tryggja að við séum alltaf með lægsta mögulega P gildið í biðröðinni til að draga frá. (C) Signup and view all the answers

Hvernig er möguleg lausn fundin í 'stutt hlutfylki' vandamálinu með rennandi glugga?

Möguleg lausn er P[j] − P[i∗ ] þar sem i∗ er fremst í biðröðinni. (B) Signup and view all the answers

Flashcards

Mótdæmi gráðugrar aðferðar

Gráðug aðferð finnur ekki alltaf bestu lausnina við myntskiptivandanum.

Kerfisbundin leit

Aðferð til að leysa vandamál með því að prófa allar mögulegar lausnir kerfisbundið.