Advertisement
Bisqwit

Tira 2021s tehtäväsarja 9 // Joel Yliluoma

Nov 14th, 2021 (edited)
457
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
Python 3.76 KB | None | 0 0
  1. """ Joelin ratkaisut Helsingin yliopiston Tietorakenteet ja algoritmit-kurssin
  2.    viikon 9 harjoitustehtäviin https://cses.fi/tira21s/list/ .
  3.    Nämä ratkaisut eroavat tarkoituksella malliratkaisuista. Niiden pääasiallinen
  4.    tarkoitus on inspiroida ja antaa ideoita sellaisille opiskelijoille, jotka
  5.    haluavat nähdä ohjelmoinnin taiteena — tai kenties vaikka yksinkertaisina
  6.    matemaattisina lausekkeina. Vastaukset ovat tarkoituksella erittäin tiiviitä.
  7.    Missään nimessä niitä ei tule tulkita esimerkkeinä hyvistä ohjelmointitavoista!
  8.    Discordissa saa vapaasti kysyä, jos jokin kohta herättää kysymyksiä.
  9.    Tehtäväsarja 8: https://pastebin.com/5u166swH
  10.    Tehtäväsarja 9: https://pastebin.com/Vs2CNwQA
  11.    Tehtäväsarja 10: https://pastebin.com/jeXQ1JnT
  12.    Tehtäväsarja 11: https://pastebin.com/pTh4ZwFE
  13.    Tehtäväsarja 12: https://pastebin.com/eJ8HMRCF
  14.    Tehtäväsarja 13: https://pastebin.com/ETpqtDBY
  15. """
  16.  
  17. import math                 # 9.3 Hyppely
  18. def count(n, a, b, p = lambda A,B,f=math.gamma: f(A+B+1)/(f(A+1)*f(B+1))):
  19.   return round(sum(p(A,B) for(A,B) in ((A, (n-a*A)/b) for A in range(n//a + 1) if not(n-a*A)%b)))
  20.  
  21. def find(r):                # 9.4 Yhden ero
  22.   best = [1]
  23.   for b in range(1, len(r)):
  24.     best.append( max(1,1,*(best[a]+1 for a in range(b) if abs(r[b]-r[a]) == 1)))
  25.   return max(best)
  26.  
  27. def count(r, bad=9**9):     # 9.5 Hirviöt
  28.   cache,w,h,f = {},len(r[0]),len(r), lambda x,y,c: bad if c=='#' else \
  29.     (c=='@') + min(memoize(cache, f, (x-1,y, r[x-1][y]))if x else bad if y else 0,
  30.                    memoize(cache, f, (x,y-1, r[x][y-1]))if y else bad if x else 0)
  31.   return (min(bad-1, f(w-1, h-1, r[w-1][h-1])) + 1) % bad - 1
  32.  
  33. def count(t):               # 9.6 Kolikot
  34.   sums = set()
  35.   for i in t: sums.update([s+i for s in sums], [i])
  36.   return len(sums)
  37.  
  38. cache = {}                  # 9.7 Bittipoisto
  39. def count(s):
  40.   return sum(memoize(cache, count, [s[:i]+s[i+2:]])
  41.              for i in range(len(s)-1) if s[i]==s[i+1]) if len(s) else 1
  42.  
  43. import math                 # 9.8 Kurssi
  44. def count(x, c = 7, n_over_k = lambda k,n,l=math.lgamma: l(n+1) - l(k+1) - l(n-k+1)):
  45.    return round(sum( (math.exp(sum(n_over_k(i,8) for i in s))
  46.                       for s in ([5 + ((p>>i*2)&3) for i in range(c)] for p in range(1<<c*2))
  47.                       if sum(s) == x) ))
  48.  
  49. # Tehtävien 9.5 ja 9.7 käyttämä apufunktio, joka toteuttaa muistin:
  50. def memoize(cache, u, p=()):
  51.   k = hash(p)
  52.   if k in cache: return cache[k]
  53.   result   = u(*p)
  54.   cache[k] = result
  55.   return result
  56. """
  57. Huom. Tehtävissä 9.3 ja 9.8 käytetyt funktiot gamma ja lgamma toteuttavat
  58.       laskennan (x-1)! ja ln((x–1)!), eli kertomafunktion (engl. factorial).
  59.  
  60.       Näin ollen esim. kombinaatio (n yli k), jonka kaava on n! / (k! · (n–k)!),
  61.       voidaan laskea seuraavasti: gamma(n+1) / (gamma(k+1) * gamma(n+k+1))
  62.       tai näin:                   exp(lgamma(n+1) – lgamma(k+1) – lgamma(n+k–1))
  63.  
  64.       Logaritmisesta gammafunktiosta on se etu, että se välttää kolossaalisen suurten
  65.       numeroiden käsittelyn laskennan välivaiheissa. Lisäksi se yksinkertaistaa jakolaskut
  66.       vähennyslaskuiksi ja kertolaskut yhteenlaskuiksi.
  67.       Liukulukujen epätarkkuudesta johtuen on kuitenkin mahdollista, että esim. arvon 54
  68.       sijaan vastaukseksi tuleekin 53.99999999996 tai 54.00000000002. CSES-järjestelmä
  69.       ei tällaisia tuloksia hyväksy. Virhe on sitä todennäköisempi, mitä useampi
  70.       laskutoimitus suoritetaan. Tästä syystä funktion lopputuloksen laskennan ympärillä
  71.       on yksi round()-lauseke.
  72.  
  73.       Gammafunktiota käytetään mm. fysiikassa, jossa on käyttöä myös funktion arvoilla
  74.       sellaisilla parametreilla, jotka eivät ole kokonaislukuja.
  75. """
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement