Evklidov algoritem je učinkovit algoritem za izračun največjega skupnega delitelja dveh števil in ga označimo z gcd(a,b), kjer predpostavimo, da a >= b. Na kratko ga lahko opišemo kot:
gcd(a,0) = a- V nasprotem primeru zapišemo
akot:a = b*q + r.gcd(a,b)je v tem primeru enak kotgcd(b, r). Vidimo, da po nekaj časa bor = 0in to bo končni rezultat.
Implementiraj funkcijo gcd(a,b), ki vrne največji skupni deljitelj števil a in b. Poskrbi, da bo funkcija delovala pravilno, tudi če uporabnik poda argumenta v poljubnam vrstnem redu.
Primeri: gcd(15, 5) = gcd(5, 15) = 5, gcd(1234, 23456), gcd(12, 56) = 4, gcd(14, 21) = 7
Implementiraj funkcijo lcm(a,b), ki vrne najmanjši skupni večkratnik števil a in b. Pri tem si pomagaj z prej implementirano funkcijo, saj velja: gcd(a,b)*lcm(a,b) = a*b.
Za problem 5 (https://projecteuler.net/problem=5) potrebujemo funkcijo lcm izboljšati, da bo lahko izračunala lcm več števil. Pri tem si bomo pomagali s funkcijo reduce. Reduce počasi združuje pare argumentov, dokler ne pride do končnega rezultata. Lep primer je reduce za seštevanje. Operacija + (kot gcd) sprejme dva argumenta. Če pa hočemo dobiti vsoto celega seznama jo moramo uporabiti večkrat:
sum([1,2,3,4]) = (((1+2) + 3) + 4) = ((3 + 3) + 4) = (6 + 4) = 10. To najlažje naredimo kar s for zanko, kjer si hranimo zadnji rezultat (v zgornjem primeru 1,3,6).
- napiši funkcijo
reduce_plus, ki sprejme seznam in sešteje vse elemente (POZOR, uporaba vgrajene funkcijesumje prepovedana)
Na enak način lahko postopamo pri gcd in lcm, za katera velja gcd(a,b,c) = gcd(gcd(a,b), c) (seveda za poljubno število argumentov).
- Napiši funkciji
reduce_gcdinreduce_lcm, kigcdinlcmaplicirata na seznam števil Primeri:gcd(12, 16, 20) = 4, lcm(12, 16, 20) = 240), lcm(1,2,3, ..., 10) = 2520.
Funkcija fakulteta je zelo uporabna na različnih področjih. Označimo jo z n! in je definirana kot produkt števil do 1: 10! = 1*2*3*4*5*6*7*8*9*10, 3! = 1*2*3 = 6. Za lažje delo si definiramo tudi 0! = 1.
- Definiraj funkcijo
fakulteta(n), ki vrne fakulteto številan(lahko predpostaviš, da bon >= 0).
S pomočjo zgornjih funkcij lahko rešiš problem 5 na dva načina (uporabi reduce_gcd in fakultetaali reduce_lcm).
Implementiraj oba in se prepričaj da delujeta pravilno. Preizkusi oba tudi za večji N, ali je kakšna razlika v hitrosti?
Problem 13 (https://projecteuler.net/problem=13)
Ker python zna računati s poljubno veliki števili, je problem relativno lahek. Treba je prebrati števila in jih sešteti. Poskusi prvih 10 števk dobiti s programom. https://stackoverflow.com/questions/30037808/multiline-editing-in-visual-studio-code, https://www.sublimetext.com/docs/3/column_selection.html.
Namig: Ali znaš dobiti zadnjih 10 števk? Ali znaš obrniti število, kaj pa če ga prej pretvoriš v str?
Problem 11 (https://projecteuler.net/problem=11)
Treba je najti največji produkt v mreži (v katerikoli smeri). Iz vhoda si naredi seznam številk, in preveri vse potrebne kombinacije (s programom seveda).
Ker smo leni in si ne želimo pisati vejice na vsa vmesna mesta bomo raje uporabili .split metodo na nizu. (Če ti je lažje, jo napiši na konec vrstice, pa še to naredi za vse hkrati https://stackoverflow.com/questions/30037808/multiline-editing-in-visual-studio-code.
Definiraj funkcijo razcep(n), ki vrne seznam parov: praštevilsko razcep n. Prvi element para naj bo praštevilo, drugi pa potenca.
razcep(8) = [(2,3)], razcep(2468) = [(2,2), (617,1)], razcep(12345) = [(3,1), (5,1), (823,1)], ker 2**3 = 8, 3*5*823=12345.
- https://projecteuler.net/problem=9
- https://projecteuler.net/problem=7
- https://projecteuler.net/problem=22
- Spomnite se branja iz datotek: https://docs.python.org/3/tutorial/inputoutput.html#reading-and-writing-files
- Najlažje kar tako:
f = open("vhodna_datoteka.txt, "r"); celotna_vsebina = f.read()
- https://projecteuler.net/problem=16
- https://projecteuler.net/problem=20
- https://projecteuler.net/problem=10
- https://projecteuler.net/problem=14