Diferencia entre revisiones de «Práctica 2: Complejidad (Algoritmos III)»
De Cuba-Wiki
(No se muestran 4 ediciones intermedias del mismo usuario) | |||
Línea 1: | Línea 1: | ||
{{Back|Algoritmos y Estructuras de Datos III}} | |||
==Ejercicio 02.01:== | ==Ejercicio 02.01:== | ||
log(2,n) | log(2,n) + 1 | ||
==Ejercicio 02.02:== | ==Ejercicio 02.02:== | ||
Línea 59: | Línea 61: | ||
<br>a) | <br>a) | ||
<br>b) | <br>b) | ||
<pre> | |||
import math | |||
import sys | |||
def primes(n): | |||
if n==2: return [2] | |||
elif n<2: return [] | |||
s=range(3,n+1,2) | |||
mroot = n ** 0.5 | |||
half=(n+1)/2-1 | |||
i=0 | |||
m=3 | |||
while m <= mroot: | |||
if s[i]: | |||
j=(m*m-3)/2 | |||
s[j]=0 | |||
while j<half: | |||
s[j]=0 | |||
j+=m | |||
i=i+1 | |||
m=2*i+3 | |||
return [2]+[x for x in s if x] | |||
def isprime(aNumber): | |||
if aNumber < 2: return False | |||
if aNumber == 2: return True | |||
if (( aNumber / 2 ) * 2 == aNumber) : | |||
return False | |||
else: | |||
klist = primes(int(math.sqrt(aNumber+1))) | |||
for k in klist[1:]: | |||
if (( aNumber / k ) * k == aNumber ): return False | |||
return True | |||
a = int(sys.argv[1]) | |||
b = int(sys.argv[2]) | |||
i = 2 | |||
while(i < max(a,b)): | |||
if isprime(a): | |||
if (b%a == 0): | |||
b = b/a | |||
a = a/a | |||
else: | |||
break | |||
elif isprime(b): | |||
if a%b == 0: | |||
a = a/b | |||
b = b/b | |||
else: | |||
break | |||
else: | |||
if isprime(i): | |||
if(a%i == 0 and b%i == 0): | |||
a = a/i | |||
b = b/i | |||
else: | |||
i = i + 1 | |||
else: | |||
i = i + 1 | |||
print str(a) + "/" + str(b) | |||
</pre> | |||
<br>c) | <br>c) | ||
==Ejercicio 02.09:== | ==Ejercicio 02.09:== | ||
<br>a) | <br>a) No recursivo | ||
<pre> | |||
import math | |||
import sys | |||
##mientras b ? 0 repetir las tres instrucciones siguientes: | |||
## | |||
## r ? resto de a entre b (dar a r el valor del resto de a por b) | |||
## a ? b (el nuevo valor de a es el antiguo valor de b) | |||
## b ? r (el nuevo valor de b es el valor de r) | |||
## | |||
##* el resultado es a (su último valor). | |||
a = sys.argv[1] | |||
b = sys.argv[2] | |||
a = float(a) | |||
b = float(b) | |||
while b != 0: | |||
r = a % b | |||
a = b | |||
b = r | |||
print a | |||
</pre> | |||
Recursivo | |||
<pre> | |||
import sys | |||
import math | |||
def Euclides(a,b): | |||
if b == 0: | |||
return a | |||
else: | |||
r = a%b | |||
return Euclides(b,r) | |||
a = sys.argv[1] | |||
b = sys.argv[2] | |||
a = float(a) | |||
b = float(b) | |||
print Euclides(a,b) | |||
</pre> | |||
<br>b) | <br>b) | ||
<br>c) | <br>c) | ||
Línea 126: | Línea 235: | ||
<br>b) | <br>b) | ||
[[Category: Prácticas]] |
Revisión del 02:32 23 mar 2009
Ejercicio 02.01:
log(2,n) + 1
Ejercicio 02.02:
No. Base 1 requiere espacio O(n), y las demas O(log n)
Ejercicio 02.03:
(Cuentas Cuentas..)
a)
b)
c)
Ejercicio 02.04:
a)
i. f = n <= 1*n (todo n) -> f es O(n)
ii. f = 3*n^2 + 7*n + 4 <= 4*n^2 (n>=8) -> f es O(n^2)
iii.f = n^i <= 1*n^j (todo n) <=> i < j -> f es O(n^j) <=> i < j
iv. f = n*log n <= 1*n^2 (todo n) -> f es O(n^2)
b)
Sup. Ex. k en R / n! <= k* r^n <=> n!/r^n <= k. Pero lim{n->∞} n!/r^n = ∞ (ABS)
Ejercicio 02.05:
a) O(1)
b) O(d)
c) O(n)
d) O(n^2)
Ejercicio 02.06:
a)
b)
c)
Ejercicio 02.07:
a)
int bin2dec(string s) res = 0; para i = |s|-1..0 si (s[i]=='1') res += 2^i; devolver res;
b) No. Podria no parar nunca
c) Si
d)
string dec2bin(int n) res = <>; while (n != 0) si (n % 2 != 0) res += '1'; sino res += '0'; n /= 2; devolver res;
Ejercicio 02.08:
a)
b)
import math import sys def primes(n): if n==2: return [2] elif n<2: return [] s=range(3,n+1,2) mroot = n ** 0.5 half=(n+1)/2-1 i=0 m=3 while m <= mroot: if s[i]: j=(m*m-3)/2 s[j]=0 while j<half: s[j]=0 j+=m i=i+1 m=2*i+3 return [2]+[x for x in s if x] def isprime(aNumber): if aNumber < 2: return False if aNumber == 2: return True if (( aNumber / 2 ) * 2 == aNumber) : return False else: klist = primes(int(math.sqrt(aNumber+1))) for k in klist[1:]: if (( aNumber / k ) * k == aNumber ): return False return True a = int(sys.argv[1]) b = int(sys.argv[2]) i = 2 while(i < max(a,b)): if isprime(a): if (b%a == 0): b = b/a a = a/a else: break elif isprime(b): if a%b == 0: a = a/b b = b/b else: break else: if isprime(i): if(a%i == 0 and b%i == 0): a = a/i b = b/i else: i = i + 1 else: i = i + 1 print str(a) + "/" + str(b)
c)
Ejercicio 02.09:
a) No recursivo
import math import sys ##mientras b ? 0 repetir las tres instrucciones siguientes: ## ## r ? resto de a entre b (dar a r el valor del resto de a por b) ## a ? b (el nuevo valor de a es el antiguo valor de b) ## b ? r (el nuevo valor de b es el valor de r) ## ##* el resultado es a (su último valor). a = sys.argv[1] b = sys.argv[2] a = float(a) b = float(b) while b != 0: r = a % b a = b b = r print a
Recursivo
import sys import math def Euclides(a,b): if b == 0: return a else: r = a%b return Euclides(b,r) a = sys.argv[1] b = sys.argv[2] a = float(a) b = float(b) print Euclides(a,b)
b)
c)
d)
Ejercicio 02.10:
a)
b)
c)
d)
e)
Ejercicio 02.11:
Ejercicio 02.12:
Ejercicio 02.13:
a)
b)
c)
Ejercicio 02.14:
a)
b)
c)
d)
e)
f)
Ejercicio 02.15:
a)
b)
c)
Ejercicio 02.16:
a)
b)
c)
d)
e)
Ejercicio 02.17:
a)
b)
c)
Ejercicio 02.18:
a)
b)
c)
Ejercicio 02.19:
a)
b)
c)
Ejercicio 02.20:
Ejercicio 02.21:
Ejercicio 02.22:
a)
Algoritmo:
1.si (actual != b) avanzo 2.sino volver 1 lugar hacia atras 3.si (cinta == ultimo guardado) tachamos cinta con b nos movemos al anterior y guardamos (pero si es blanco ir a SI) volvemos a 1 sino ir a NO
b)