GRR Fyrirlestur 10: Kvik Bestun 2 PDF

Greining Reiknirita Vika 5 - Kvik Bestun Vor 2025 Hafsteinn Einarsson Yfirlit 1 Myntskipti 2 Strengjaskipting 3 Stærsta summa og margfeldi hlutstrengja 4 Aðrar útgáfur af hlutsummu vandamálinu 5 Aðrar útgáfur af hlutrunuvandamálinu 6 Lengsta sameiginlega hlutruna 7 Blandaðar runur...

Greining Reiknirita Vika 5 - Kvik Bestun Vor 2025 Hafsteinn Einarsson Yfirlit 1 Myntskipti 2 Strengjaskipting 3 Stærsta summa og margfeldi hlutstrengja 4 Aðrar útgáfur af hlutsummu vandamálinu 5 Aðrar útgáfur af hlutrunuvandamálinu 6 Lengsta sameiginlega hlutruna 7 Blandaðar runur 8 Lengsti fram/aftur hlutstrengur Myntskipti 1 / 93 Myntskiptivandamálið Dæmi Gefið mengi af myntgildum D = {1, 4, 7, 13, 28, 52, 91, 365}, leysið eftirfarandi: a) Gráðug reikniaðferð fyrir myntbreytingu tekur alltaf stærsta mögulega myntgildið sem fer ekki yfir upphæðina sem er eftir. Finnið dæmi þar sem þessi gráðuga nálgun notar fleiri myntir en nauðsynlegt er. b) Hannið og útskýrið endurkvæmt reiknirit sem finnur lágmarksfjölda mynta sem þarf til að gefa til baka hvaða upphæð k sem er með því að nota tiltæk myntgildi. Einbeitið ykkur að því að reikniaðferðin sé rétt frekar en skilvirk. c) Hannið skilvirkt kvikt bestunarreiknirit sem finnur lágmarksfjölda mynta sem þarf til að gefa til baka hvaða upphæð k sem er með því að nota tiltæk myntgildi. Lausnin ætti að vera bestuð fyrir afköst. Myntskipti 2 / 93 Lausn á a) lið Við viljum finna upphæð þar sem gráðuga reikniritið gefur ekki bestu lausnina þegar myntgildin eru D = {1, 4, 7, 13, 28, 52, 91, 365}. Myntskipti 3 / 93 Lausn á a) lið Við viljum finna upphæð þar sem gráðuga reikniritið gefur ekki bestu lausnina þegar myntgildin eru D = {1, 4, 7, 13, 28, 52, 91, 365}. Til þess að leysa þetta verkefni er betra að byrja á að leysa lið c) svo við getum leitað kerfisbundið að mótdæmi. Myntskipti 3 / 93 Lausn á a) lið Við viljum finna upphæð þar sem gráðuga reikniritið gefur ekki bestu lausnina þegar myntgildin eru D = {1, 4, 7, 13, 28, 52, 91, 365}. Til þess að leysa þetta verkefni er betra að byrja á að leysa lið c) svo við getum leitað kerfisbundið að mótdæmi. Svarið er að lægsta upphæðin sem gefur mótdæmi er 416. Gráðuga aðferðin notar þá 7 myntir: 365, 28, 13, 7, 1, 1, 1 Besta lausnin notar 5 myntir: 91, 91, 91, 91, 52 Myntskipti 3 / 93 Lausn á a) lið Við viljum finna upphæð þar sem gráðuga reikniritið gefur ekki bestu lausnina þegar myntgildin eru D = {1, 4, 7, 13, 28, 52, 91, 365}. Til þess að leysa þetta verkefni er betra að byrja á að leysa lið c) svo við getum leitað kerfisbundið að mótdæmi. Svarið er að lægsta upphæðin sem gefur mótdæmi er 416. Gráðuga aðferðin notar þá 7 myntir: 365, 28, 13, 7, 1, 1, 1 Besta lausnin notar 5 myntir: 91, 91, 91, 91, 52 Hér er forrit sem leysir þetta kerfisbundið. Myntskipti 3 / 93 Lausn á b) lið Við viljum finna lágmarksfjölda mynta fyrir upphæð k með því að nota endurkvæma nálgun. Myntskipti 4 / 93 Lausn á b) lið Við viljum finna lágmarksfjölda mynta fyrir upphæð k með því að nota endurkvæma nálgun. Hugmyndin er að fyrir hverja mynt d ∈ D prófum við að nota hana og leysa vandamálið fyrir k − d. Myntskipti 4 / 93 Lausn á b) lið Við viljum finna lágmarksfjölda mynta fyrir upphæð k með því að nota endurkvæma nálgun. Hugmyndin er að fyrir hverja mynt d ∈ D prófum við að nota hana og leysa vandamálið fyrir k − d. Við getum sett upp eftirfarandi rakningarvensl:    ef k = 0 0 MinMyntir(k) = ∞ ef k < 0   min{1 + MinMyntir(k − d)} annars d∈D Myntskipti 4 / 93 Útfærsla á endurkvæmu lausninni def min_myntir(k, D): # Grunntilfelli if k == 0: return 0 if k < 0: return float('inf') # Prófum allar myntir min_fjoldi = float('inf') for d in D: nidurstada = min_myntir(k - d, D) if nidurstada != float('inf'): min_fjoldi = min(min_fjoldi, 1 + nidurstada) return min_fjoldi Myntskipti 5 / 93 Kvik bestun Við getum notað kvika bestun til að forðast endurtekna útreikninga. Myntskipti 6 / 93 Kvik bestun Við getum notað kvika bestun til að forðast endurtekna útreikninga. Hugmyndin er að byggja upp töflu af niðurstöðum fyrir allar upphæðir frá 0 upp í k. Myntskipti 6 / 93 Kvik bestun Við getum notað kvika bestun til að forðast endurtekna útreikninga. Hugmyndin er að byggja upp töflu af niðurstöðum fyrir allar upphæðir frá 0 upp í k. Fyrir hverja upphæð i gildir: dp[i] = min{1 + dp[i − d]} þar sem i − d ≥ 0 d∈D Myntskipti 6 / 93 Útfærsla á kvikri bestun def min_myntar_kvik(k, D): # Upphafstillum dp fylkið dp = [float('inf')] * (k + 1) dp = 0 # Byggum upp lausnir for i in range(1, k + 1): for d in D: if i >= d: dp[i] = min(dp[i], 1 + dp[i - d]) return dp[k] Myntskipti 7 / 93 Dæmi um keyrslu Skoðum dæmi með k = 6 og D = {1, 4}: Myntskipti 8 / 93 Dæmi um keyrslu Skoðum dæmi með k = 6 og D = {1, 4}: dp = 0 (grunntilfelli) dp = 1 (1) dp = 2 (1 + 1) dp = 3 (1 + 1 + 1) dp = 1 (4) dp = 2 (4 + 1) dp = 3 (4 + 1 + 1) Myntskipti 8 / 93 Samanburður á lausnum Endurkvæm lausn: Einföld í skilningi Endurreiknar sömu dæmin margoft Tímaflækja: O(|D|k ) Myntskipti 9 / 93 Samanburður á lausnum Endurkvæm lausn: Einföld í skilningi Endurreiknar sömu dæmin margoft Tímaflækja: O(|D|k ) Kvik bestun: Reiknar hvert tilvik aðeins einu sinni Notar O(k) minni Tímaflækja: O(k|D|) Myntskipti 9 / 93 Yfirlit 1 Myntskipti 2 Strengjaskipting 3 Stærsta summa og margfeldi hlutstrengja 4 Aðrar útgáfur af hlutsummu vandamálinu 5 Aðrar útgáfur af hlutrunuvandamálinu 6 Lengsta sameiginlega hlutruna 7 Blandaðar runur 8 Lengsti fram/aftur hlutstrengur Strengjaskipting 10 / 93 Dæmi Gefið er fall is_word sem tekur streng og skilar True ef og aðeins ef strengurinn er gilt orð. Hannið reiknirit fyrir eftirfarandi verkefni og greinið fjölda kalla á is_word: a) Finnið fjölda mögulegra leiða til að skipta fylki A[1... n] í gild orð. Dæmi: Fyrir strenginn ARTISTOIL eru tvær lausnir: ARTIST OIL og ART IS TOIL b) Ákvarðið hvort hægt sé að skipta tveimur fylkjum A[1... n] og B[1... n] í orð á sömu stöðum. Dæmi: Fyrir A = BOTHEARTHANDSATURNSPIN og B = PINSTARTRAPSANDRAGSLAP: BOT HEART HAND SAT URNS PIN PIN START RAPS AND RAGS LAP c) Teljið fjölda mismunandi leiða til að skipta A[1... n] og B[1... n] í orð á sömu stöðum.  Upprifjun: Við höfðum skoðað hvort hægt væri að skipta streng 1 M = {} 2 def splittable(s[1...n], i): 3 if i > n: 4 return True 5 if i in M: # Ef lausnin er þekkt 6 return M[i] # Nota hana 7 for j = i to n: # Leysa endurkvæmt 8 if is_word(s, i, j): 9 cansplit = splittable(s, j + 1) 10 M[j + 1] = cansplit # Geyma lausnina 11 if cansplit: 12 return True 13 return False Strengjaskipting 12 / 93 Lausn á lið a) Byggjum á endurkvæmu lausninni fyrir splittable Látum dp[i] geyma fjölda leiða til að skipta s[i..n] Grunntilvik: dp[n + 1] = 1 (tómur strengur) Strengjaskipting 13 / 93  Niðursækin lausn á lið a) 1 def count_splits(s, i, dp=None): 2 if dp is None: # Í fyrsta kalli 3 dp = {} # Búa til minnið 4 if i > len(s): # Tómur strengur 5 return 1 6 if i in dp: # Ef lausnin er þekkt 7 return dp[i] # Nota hana 8 9 count = 0 # Telja allar leiðir 10 for j in range(i, len(s) + 1): 11 if is_word(s[i-1:j]): # Ef gilt orð fannst 12 count += count_splits(s, j + 1, dp) 13 14 dp[i] = count # Geyma lausnina 15 return count  Uppsækin lausn á lið a) 1 def count_splits(A): 2 n = len(A) 3 dp = * (n + 1) 4 dp[n] = 1 # Grunntilvik 5 6 for i in range(n-1, -1, -1): # Frá hægri til vinstri 7 for j in range(i+1, n+1): # Skoða öll möguleg orð 8 if is_word(A[i:j]): # sem byrja á stað i 9 dp[i] += dp[j] # og bæta við öllum 10 # möguleikum eftir j 11 return dp Lausn á lið a) Fjöldi kalla á is_word: O(n2 ) í versta tilfelli Auðveldara að sjá það í upsækinni lausn. Tímaflækja: O(n2 ) þar sem hvert bil á forminu i... j er í versta tilfellinu heimsótt einu sinni. Strengjaskipting 16 / 93  Uppsækin lausn á lið b) 1 def can_split_same(A, B): 2 n = len(A) 3 dp = [False] * (n + 1) 4 dp[n] = True # Grunntilvik 5 6 for i in range(n-1, -1, -1): # Frá hægri til vinstri 7 for j in range(i+1, n+1): # Skoða öll möguleg orð 8 if is_word(A[i:j]) and is_word(B[i:j]): 9 if dp[j]: # Ef rest er skiptanleg 10 dp[i] = True # þá er þetta skiptanlegt 11 break 12 13 return dp # Er hægt að skipta öllu?  Uppsækin lausn á lið c) 1 def count_same_splits(A, B): 2 n = len(A) 3 dp = * (n + 1) 4 dp[n] = 1 # Grunntilvik 5 6 for i in range(n-1, -1, -1): # Frá hægri til vinstri 7 for j in range(i+1, n+1): # Skoða öll möguleg orð 8 if is_word(A[i:j]) and is_word(B[i:j]): 9 dp[i] += dp[j] # Bæta við öllum leiðum 10 # til að skipta rest 11 12 return dp # Heildarfjöldi leiða Yfirlit 1 Myntskipti 2 Strengjaskipting 3 Stærsta summa og margfeldi hlutstrengja 4 Aðrar útgáfur af hlutsummu vandamálinu 5 Aðrar útgáfur af hlutrunuvandamálinu 6 Lengsta sameiginlega hlutruna 7 Blandaðar runur 8 Lengsti fram/aftur hlutstrengur Stærsta summa og margfeldi hlutstrengja 19 / 93 Stærsta summa og margfeldi hlutstrengja Dæmi Gefin er runa A[1... n] af tölum sem geta verið jákvæðar, neikvæðar eða núll. a) Hannið reiknirit sem finnur stærstu summu hlutstrengs A[i... j]. b) Hannið reiknirit sem finnur stærsta margfeldi hlutstrengs A[i... j]. summa=19 -6 12 -7 0 14 -7 5 margfeldi=504 Skila ætti 0 sem summu fyrir rununa sem hefur eingöngu stakið −374 og margfeldinu 1 því við leyfum að hlutstrengurinn sé tómur. Þið megið gefa ykkur að samlagningu og margföldun megi framkvæma í O(1) tíma. Stærsta samliggjandi summa - Algengt viðtalsdæmi Þetta vandamál er eitt af algengustu forritunardæmunum í atvinnuviðtölum Hefur verið notað síðan á 9. áratug síðustu aldar Stærsta summa og margfeldi hlutstrengja 21 / 93 Stærsta samliggjandi summa - Algengt viðtalsdæmi Þetta vandamál er eitt af algengustu forritunardæmunum í atvinnuviðtölum Hefur verið notað síðan á 9. áratug síðustu aldar Hentar vel til að meta: Getu til að þróa mismunandi lausnir Skilning á tímaflækju Hæfni til að bæta lausnir Stærsta summa og margfeldi hlutstrengja 21 / 93 Stærsta samliggjandi summa - Algengt viðtalsdæmi Þetta vandamál er eitt af algengustu forritunardæmunum í atvinnuviðtölum Hefur verið notað síðan á 9. áratug síðustu aldar Hentar vel til að meta: Getu til að þróa mismunandi lausnir Skilning á tímaflækju Hæfni til að bæta lausnir Við munum skoða þrjár lausnir með mismunandi tímaflækju: Einföld lausn: O(n3 ) Hlutsummulausn: O(n2 ) Kvik bestun: O(n) Stærsta summa og margfeldi hlutstrengja 21 / 93 Einföld lausn - O(n3 ) Einföld nálgun: Prófum allar mögulegar samliggjandi runur Stærsta summa og margfeldi hlutstrengja 22 / 93 Einföld lausn - O(n3 ) Einföld nálgun: Prófum allar mögulegar samliggjandi runur Ytri lykkja: Upphafspunktur i Innri lykkja: Endapunktur j Innsta lykkja: Reikna summu A[i..j] Stærsta summa og margfeldi hlutstrengja 22 / 93  Einföld lausn - O(n3 ) Einföld nálgun: Prófum allar mögulegar samliggjandi runur Ytri lykkja: Upphafspunktur i Innri lykkja: Endapunktur j Innsta lykkja: Reikna summu A[i..j] 1 def max_subarray_sum_bruteforce(A): 2 n = len(A) 3 max_sum = 0 # Tómt hlutfylki gefur summu 0 4 5 for i in range(n): 6 for j in range(i, n): 7 current_sum = 0 8 for k in range(i, j + 1): 9 current_sum += A[k] 10 max_sum = max(max_sum, current_sum) 11 12 return max_sum Stærsta summa og margfeldi hlutstrengja 22 / 93 Betri lausn með hlutsummum - O(n2 ) Getum losað okkur við innstu lykkjuna með því að nota hlutsummur Betri lausn með hlutsummum - O(n2 ) Getum losað okkur við innstu lykkjuna með því að nota hlutsummur Hlutsumma P[i] inniheldur summu allra staka frá A að A[i] Summa A[i..j] = P[j] − P[i − 1]  Betri lausn með hlutsummum - O(n2 ) Getum losað okkur við innstu lykkjuna með því að nota hlutsummur Hlutsumma P[i] inniheldur summu allra staka frá A að A[i] Summa A[i..j] = P[j] − P[i − 1] 1 def max_subarray_sum_prefix(A): 2 n = len(A) 3 if n == 0: 4 return 0 5 6 P = * (n + 1) # Reiknum hlutsummur, P = 0 fyrir i = 0 7 for i in range(n): 8 P[i + 1] = P[i] + A[i] 9 10 max_sum = 0 11 for i in range(n): 12 for j in range(i, n): 13 current_sum = P[j + 1] - P[i] 14 max_sum = max(max_sum, current_sum) 15 return max_sum Samanburður á fyrstu tveimur lausnum Einföld lausn: Einföld að skilja Minnisflækja: O(1) Tímaflækja: O(n3 ) Stærsta summa og margfeldi hlutstrengja 24 / 93 Samanburður á fyrstu tveimur lausnum Einföld lausn: Einföld að skilja Minnisflækja: O(1) Tímaflækja: O(n3 ) Hlutsummulausn: Krefst O(n) viðbótarminnis Forvinnsla tekur O(n) tíma Heildar tímaflækja: O(n2 ) Stærsta summa og margfeldi hlutstrengja 24 / 93 Samanburður á fyrstu tveimur lausnum Einföld lausn: Einföld að skilja Minnisflækja: O(1) Tímaflækja: O(n3 ) Hlutsummulausn: Krefst O(n) viðbótarminnis Forvinnsla tekur O(n) tíma Heildar tímaflækja: O(n2 ) Getum gert enn betur með kvikri bestun! (Kadane) Stærsta summa og margfeldi hlutstrengja 24 / 93 Lausn á a) lið - Kadane reiknirit Hugmyndin er að halda utan um: local_sum: Besta summan sem endar í núverandi sæti global_sum: Besta summan sem hefur fundist hingað til Stærsta summa og margfeldi hlutstrengja 25 / 93 Lausn á a) lið - Kadane reiknirit Hugmyndin er að halda utan um: local_sum: Besta summan sem endar í núverandi sæti global_sum: Besta summan sem hefur fundist hingað til Fyrir i-ta stakið í rununni: local_sum = max{A[i], local_sum + A[i]} global_sum = max{global_sum, local_sum} Stærsta summa og margfeldi hlutstrengja 25 / 93  Útfærsla á Kadane reikniritinu 1 def max_subarray_sum(A): 2 if not A: # Tómt fylki 3 return 0 4 5 local_sum = global_sum = A 6 7 for i in range(1, len(A)): 8 local_sum = max(A[i], local_sum + A[i]) 9 global_sum = max(global_sum, local_sum) 10 11 return max(0, global_sum) # 0 ef tómt hlutfylki er betra Stærsta summa og margfeldi hlutstrengja 26 / 93 Sönnun á Kadane reikniritinu - Rakningarvensl Setning Fyrir sérhvert sæti i, látum S(i) tákna stærstu summu hlutfylkis sem endar í i. Þá gildir: S(i) = max{A[i], S(i − 1) + A[i]} Með öðrum orðum, besta hlutfylkið sem endar í i er annað hvort: Stakið A[i] eitt og sér, eða Hlutfylkið sem fæst með því að bæta A[i] við besta hlutfylkið sem endar í i − 1 Við sönnum þetta með þrepun. Stærsta summa og margfeldi hlutstrengja 27 / 93 Sönnun á Kadane reikniritinu - Grunntilvik Fyrir i = 0: Eina hlutfylkið sem endar í sæti 0 er [A] Þannig að samkvæmt skilgreiningu er S(0) = A Þetta samræmist rakningarvenslum því: S(0) = max{A, (á ekki við)} = A Stærsta summa og margfeldi hlutstrengja 28 / 93 Sönnun á Kadane reikniritinu - Þrepun Þrepunarforsendan: Gerum ráð fyrir að fyrir eitthvert sæti i − 1 (þar sem i ≥ 1) reikni rakningarvenslin rétt stærstu summu sem endar í i − 1. Sérhvert hlutfylki sem endar í i getur byrjað í sæti j þar sem 0 ≤ j ≤ i. Við skoðum tvö tilvik: 1 Tilvik 1: j = i. Hlutfylkið inniheldur bara A[i] og summan er A[i] 2 Tilvik 2: j < i. Þá er hlutfylkið: A[j] + A[j + 1] + · · · + A[i − 1] + A[i] Samkvæmt þrepunarforsendu er A[j] + · · · + A[i − 1] ≤ S(i − 1) Stærsta summa og margfeldi hlutstrengja 29 / 93 Sönnun á Kadane reikniritinu - Mótsögn Gerum ráð fyrir að til sé hlutfylki sem endar í i með summu T(i) sem er stærri en S(i). Ef hlutfylkið byrjar í i: Þá er T(i) = A[i], sem er mótsögn við T(i) > max{A[i], S(i − 1) + A[i]} Ef hlutfylkið byrjar fyrir i: Þá er T(i) = (A[j] + · · · + A[i − 1]) + A[i] fyrir eitthvert j < i Liðurinn í sviganum er summa sem endar í i − 1 og er því ≤ S(i − 1) Þannig að T(i) ≤ S(i − 1) + A[i], sem er aftur mótsögn Stærsta summa og margfeldi hlutstrengja 30 / 93 Sönnun á Kadane reikniritinu - Niðurstaða Með þrepun höfum við sannað að rakningarvenslin: S(i) = max{A[i], S(i − 1) + A[i]} reikna rétt stærstu summu sem endar í sérhverju sæti i. Stærsta summan finnst svo með því að taka hámark allra S(i) gilda. Þar með er Kadane reikniritið rétt með: Tímaflækju: O(n) Minnisflækju: O(1) Stærsta summa og margfeldi hlutstrengja 31 / 93 Lausn á b) lið - Stærsta margfeldi Þar sem tölur geta verið neikvæðar þurfum við að halda utan um: max_prod: Stærsta margfeldið sem endar á i min_prod: Minnsta margfeldið sem endar á i Stærsta summa og margfeldi hlutstrengja 32 / 93 Lausn á b) lið - Stærsta margfeldi Þar sem tölur geta verið neikvæðar þurfum við að halda utan um: max_prod: Stærsta margfeldið sem endar á i min_prod: Minnsta margfeldið sem endar á i Fyrir hvern stað i: Ef A[i] er jákvæð: margföldum með max_prod Ef A[i] er neikvæð: margföldum með min_prod Stærsta summa og margfeldi hlutstrengja 32 / 93  Útfærsla á margfeldisreikniritinu 1 def max_subarray_product(A): 2 if not A: # Tómt fylki 3 return 1 4 5 max_prod = min_prod = global_max = A 6 7 for i in range(1, len(A)): 8 temp = max_prod 9 max_prod = max(A[i], max(max_prod * A[i], min_prod * A[i])) 10 min_prod = min(A[i], min(temp * A[i], min_prod * A[i])) 11 global_max = max(global_max, max_prod) 12 13 return max(1, global_max) # 1 ef tómt hlutfylki er betra Stærsta summa og margfeldi hlutstrengja 33 / 93 Sönnun fyrir margfeldisútgáfuna Setning Fyrir sérhvert sæti i gildi: Pmax i = max{A[i], A[i] · Pmax i−1 , A[i] · Pi−1 } min Pmin i = min{A[i], A[i] · Pmax i−1 , A[i] · Pi−1 } min Við sönnum þetta með þrepun. Stærsta summa og margfeldi hlutstrengja 34 / 93 Sönnun fyrir margfeldisútgáfuna - Grunntilvik Fyrir i = 0: Engin fyrri stök til að skoða Eina margfeldið sem endar í sæti 0 er stakið sjálft Því setjum við: Pmax 0 = A og Pmin 0 = A Þetta uppfyllir rakningarvenslin því: max{A} = A því liðirnir með P−1 eru ekki skilgreindir. Stærsta summa og margfeldi hlutstrengja 35 / 93 Sönnun fyrir margfeldisútgáfuna - Þrepun Gerum ráð fyrir að fyrir öll j þar sem 0 ≤ j < i gildi rakningarvenslin. Sérhvert hlutfylki sem endar í i er annað hvort: 1 Byrjar í i (þ.e. bara A[i]): Við lengjum ekki fyrra hlutfylki Stærsta summa og margfeldi hlutstrengja 36 / 93 Sönnun fyrir margfeldisútgáfuna - Þrepun Gerum ráð fyrir að fyrir öll j þar sem 0 ≤ j < i gildi rakningarvenslin. Sérhvert hlutfylki sem endar í i er annað hvort: 1 Byrjar í i (þ.e. bara A[i]): Við lengjum ekki fyrra hlutfylki 2 Lengir hlutfylki sem endar í i − 1: Margfeldið er A[i] margfaldað við fyrra margfeldi Ef A[i] > 0: Viljum margfalda við Pmax i−1 Ef A[i] < 0: Viljum margfalda við Pmin i−1 Stærsta summa og margfeldi hlutstrengja 36 / 93 Sönnun fyrir margfeldisútgáfuna - Mótsögn Gerum ráð fyrir að til sé hlutfylki sem endar í i með stærra margfeldi en Pmax i. Látum hlutfylkið byrja í sæti j < i. Þá er margfeldið: P = A[j] · A[j + 1] · · · · · A[i]. Ef við deilum með A[i] fáum við margfeldi sem endar í i − 1 sem er: Stærra en Pmax i−1 (ef A[i] > 0), eða Minna en Pmin i−1 (ef A[i] < 0) Þetta er í mótsögn við þrepunarforsenduna um að Pmax min i−1 og Pi−1 séu best fyrir sæti i − 1. Stærsta summa og margfeldi hlutstrengja 37 / 93 Sönnun fyrir margfeldisútgáfuna - Niðurstaða Með þrepun höfum við sannað að rakningarvenslin: Pmax i = max{A[i], A[i] · Pmax i−1 , A[i] · Pi−1 } min Pmin i i−1 , A[i] · Pi−1 } = min{A[i], A[i] · Pmax min gildi fyrir öll sæti i. Þar með er reikniritið rétt og: Tímaflækja: O(n) Minnisflækja: O(1) Stærsta summa og margfeldi hlutstrengja 38 / 93 Yfirlit 1 Myntskipti 2 Strengjaskipting 3 Stærsta summa og margfeldi hlutstrengja 4 Aðrar útgáfur af hlutsummu vandamálinu 5 Aðrar útgáfur af hlutrunuvandamálinu 6 Lengsta sameiginlega hlutruna 7 Blandaðar runur 8 Lengsti fram/aftur hlutstrengur Aðrar útgáfur af hlutsummu vandamálinu 39 / 93 Stærsta hlutsumman Gefið er fylki A[1... n] af rauntölum (jákvæðar, neikvæðar eða núll). Við ætlum að skoða nokkur mismunandi hlutsummuverkefni. Aðrar útgáfur af hlutsummu vandamálinu 40 / 93 Tilbrigði við stærstu samliggjandi summu (a) Dæmi a) Hringlaga fylki: Gerum ráð fyrir að A sé hringlaga fylki. Í þessu tilfelli getur samliggjandi hlutfylki verið annað hvort: Bil A[i... j] eða Viðskeyti og forskeyti A[i... n] · A[1... j] Verkefni: Hannið og greinið reiknirit sem finnur samliggjandi hlutfylki í A með stærstu mögulegu summu. Aðrar útgáfur af hlutsummu vandamálinu 41 / 93 Lausn á lið (a) - Hringlaga fylki Sérhvert hringlaga hlutfylki er annað hvort: Venjulegt (ekki hringtengd) hlutfylki, eða Fyllifylki (e. complement) af venjulegu hlutfylki Aðrar útgáfur af hlutsummu vandamálinu 42 / 93 Lausn á lið (a) - Hringlaga fylki Sérhvert hringlaga hlutfylki er annað hvort: Venjulegt (ekki hringtengd) hlutfylki, eða Fyllifylki (e. complement) af venjulegu hlutfylki Aðferð: 1 Reiknum M1 með Kadane reikniritinu ∑n fyrir venjulegt hlutfylki 2 Reiknum heildarsummu T = i=1 A[i] 3 Finnum minnstu summu samliggjandi hlutfylkis m með breyttu Kadane 4 Reiknum M2 = T − m fyrir hringtengda hlutfylkið Aðrar útgáfur af hlutsummu vandamálinu 42 / 93 Lausn á lið (a) - Hringlaga fylki Sérhvert hringlaga hlutfylki er annað hvort: Venjulegt (ekki hringtengd) hlutfylki, eða Fyllifylki (e. complement) af venjulegu hlutfylki Aðferð: 1 Reiknum M1 með Kadane reikniritinu ∑n fyrir venjulegt hlutfylki 2 Reiknum heildarsummu T = i=1 A[i] 3 Finnum minnstu summu samliggjandi hlutfylkis m með breyttu Kadane 4 Reiknum M2 = T − m fyrir hringtengda hlutfylkið Svar: Stærsta summan er { 0, ef M1 < 0 (allar tölur neikvæðar) M= max{M1 , M2 }, annars Tímaflækja: O(n) Aðrar útgáfur af hlutsummu vandamálinu 42 / 93  Python útfærsla á a) 1 def max_subarray_circular(A): 2 if not A: 3 return 0 4 5 # Standard Kadane's algorithm to get maximum subarray sum (nonwrap) 6 max_ending_here = max_so_far = A 7 for x in A[1:]: 8 max_ending_here = max(x, max_ending_here + x) 9 max_so_far = max(max_so_far, max_ending_here) 10 M1 = max_so_far 11 12 # If all numbers are negative, just return M1. 13 if M1 < 0: 14 return 0 15 16 total = sum(A) 17 # Compute the minimum contiguous subarray sum 18 min_ending_here = min_so_far = A 19 for x in A[1:]: 20 min_ending_here = min(x, min_ending_here + x) 21 min_so_far = min(min_so_far, min_ending_here) 22 M2 = total - min_so_far 23 24 return max(M1, M2) Aðrar útgáfur af hlutsummu vandamálinu 43 / 93 Tilbrigði við stærstu samliggjandi summu (b) Dæmi b) Löng hlutfylki: Fyrir gefið X ≤ n, finnið samliggjandi hlutfylki í A af lengd að minnsta kosti X sem hefur stærstu mögulegu summu. Aðrar útgáfur af hlutsummu vandamálinu 44 / 93 Lausn á lið (b) - Löng hlutfylki Aðferð: 1 Reiknum hlutsummur: ∑ i P = 0, P[i] = A[k] k=1 2 Summa hlutfylkis A[i + 1... j] er P[j] − P[i] 3 Fyrir hvert j frá X til n: Finnum mj = min0≤i≤j−X P[i] Prófum frambjóðanda P[j] − mj Aðrar útgáfur af hlutsummu vandamálinu 45 / 93 Lausn á lið (b) - Löng hlutfylki Aðferð: 1 Reiknum hlutsummur: ∑ i P = 0, P[i] = A[k] k=1 2 Summa hlutfylkis A[i + 1... j] er P[j] − P[i] 3 Fyrir hvert j frá X til n: Finnum mj = min0≤i≤j−X P[i] Prófum frambjóðanda P[j] − mj Réttmæti: Hlutfylki A[i + 1... j] er að minnsta kosti af lengd X þá og því aðeins að j − i ≥ X Við prófum allar mögulegar lengdir ≥ X Tímaflækja: O(n) Aðrar útgáfur af hlutsummu vandamálinu 45 / 93  Python útfærsla á b) 1 def max_subarray_long(A, X): 2 n = len(A) 3 if n < X: 4 return None # Not enough elements for a subarray of length X 5 6 # Compute prefix sums: P = 0, P = A, P = A+A,..., P[n] = sum(A) 7 P = * (n + 1) 8 for i in range(n): 9 P[i+1] = P[i] + A[i] 10 11 best = float('-inf') 12 curr_min = float('inf') 13 # For j from X to n (note: j indexes into P, so subarray A[i:j] has length j-i) 14 for j in range(X, n + 1): 15 # Update the minimum prefix sum for indices 0 to j-X. 16 # When j == X, the only candidate is P. 17 curr_min = min(curr_min, P[j - X]) 18 candidate = P[j] - curr_min 19 best = max(best, candidate) 20 return best Aðrar útgáfur af hlutsummu vandamálinu 46 / 93 Tilbrigði við stærstu samliggjandi summu (c) Dæmi c) Stutt hlutfylki: Fyrir gefið X, finnið samliggjandi hlutfylki í A af lengd í mesta lagi X sem hefur stærstu mögulegu summu. Aðrar útgáfur af hlutsummu vandamálinu 47 / 93 Lausn á lið (c) - Stutt hlutfylki Aðferð með rennandi glugga (e. sliding window): 1 Reiknum hlutsummur P[0... n] eins og áður 2 Notum tvíenda biðröð (deque) til að halda utan um leyfilega vísa 3 Fyrir hvert j frá 1 til n: Fjarlægjum vísana sem eru utan glugga [max(0, j − X), j − 1] Fjarlægjum P gildi hægra megin úr biðröðinni á meðan þau eru minni en P[j] Kandídatinn er P[j] − P[i∗ ] þar sem i∗ er fremst í biðröðinni Aðrar útgáfur af hlutsummu vandamálinu 48 / 93 Lausn á lið (c) - Stutt hlutfylki Aðferð með rennandi glugga (e. sliding window): 1 Reiknum hlutsummur P[0... n] eins og áður 2 Notum tvíenda biðröð (deque) til að halda utan um leyfilega vísa 3 Fyrir hvert j frá 1 til n: Fjarlægjum vísana sem eru utan glugga [max(0, j − X), j − 1] Fjarlægjum P gildi hægra megin úr biðröðinni á meðan þau eru minni en P[j] Kandídatinn er P[j] − P[i∗ ] þar sem i∗ er fremst í biðröðinni Réttmæti: Hlutfylki er í mesta lagi af lengd X þá og því aðeins að j − i ≤ X Biðröðin tryggir að við finnum minnsta P[i] gildið í glugganum Tímaflækja: O(n) því hverjum vísi er bætt við og fjarlægður í mesta lagi einu sinni úr biðröðinni Aðrar útgáfur af hlutsummu vandamálinu 48 / 93  Python útfærsla á c) 1 def max_subarray_short(A, X): 2 n = len(A) 3 if n == 0: 4 return 0 5 6 # Build prefix sums: P = 0, P[i+1] = A +... + A[i] 7 P = * (n + 1) 8 for i in range(n): 9 P[i+1] = P[i] + A[i] 10 11 best = float('-inf') 12 dq = deque() # will store indices of P in increasing order of their values, "from collections import deque" 13 14 # Start by inserting index 0 15 dq.append(0) 16 17 # For each ending index j (1