| Revisión actual |
Tu texto |
| Línea 1: |
Línea 1: |
| {{Back|Algoritmos y Estructuras de Datos III}}
| |
|
| |
| ==Ejercicio 02.01:== | | ==Ejercicio 02.01:== |
| log(2,n) + 1 | | log(2,n) |
|
| |
|
| ==Ejercicio 02.02:== | | ==Ejercicio 02.02:== |
| Línea 8: |
Línea 6: |
|
| |
|
| ==Ejercicio 02.03:== | | ==Ejercicio 02.03:== |
| (Cuentas Cuentas..)
| |
| <br>a) | | <br>a) |
| <br>b) | | <br>b) |
| <br>c) | | <br>c) |
|
| |
| ==Ejercicio 02.04:== | | ==Ejercicio 02.04:== |
| <br>a) | | <br>a) |
| <br> i. f = n <= 1*n (todo n) -> f es O(n)
| |
| <br> ii. f = 3*n^2 + 7*n + 4 <= 4*n^2 (n>=8) -> f es O(n^2)
| |
| <br> iii.f = n^i <= 1*n^j (todo n) <=> i < j -> f es O(n^j) <=> i < j
| |
| <br> iv. f = n*log n <= 1*n^2 (todo n) -> f es O(n^2)
| |
|
| |
| <br>b) | | <br>b) |
| Sup. Ex. k en R / n! <= k* r^n <=> n!/r^n <= k. Pero lim{n->∞} n!/r^n = ∞ (ABS)
| |
|
| |
| ==Ejercicio 02.05:== | | ==Ejercicio 02.05:== |
| Modelo Uniforme:
| | <br>a) |
| <br>b) O(d) | | <br>b) |
| <br>d) O(n^2) | | <br>c) |
| | | <br>d) |
| Modelo Logaritmico:
| |
| <br>a) O(log(x))+O(log(y)) | |
| <br>c) O(nlog(n)) | |
| | |
| ==Ejercicio 02.06:== | | ==Ejercicio 02.06:== |
| <br>a) | | <br>a) |
| Línea 38: |
Línea 23: |
| ==Ejercicio 02.07:== | | ==Ejercicio 02.07:== |
| <br>a) | | <br>a) |
| <pre>
| | <br>b) |
| int bin2dec(string s)
| | <br>c) |
| res = 0;
| | <br>d) |
| para i = |s|-1..0
| |
| si (s[i]=='1')
| |
| res += 2^i;
| |
| devolver res;
| |
| </pre>
| |
| <br>b) No. Podria no parar nunca | |
| <br>c) Si | |
| <br>d) | |
| <pre>
| |
| string dec2bin(int n)
| |
| res = <>;
| |
| while (n != 0)
| |
| si (n % 2 != 0)
| |
| res += '1';
| |
| sino
| |
| res += '0';
| |
| n /= 2;
| |
| devolver res;
| |
| </pre>
| |
| | |
| ==Ejercicio 02.08:== | | ==Ejercicio 02.08:== |
| <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) No recursivo | | <br>a) |
| <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 220: |
Línea 78: |
| ==Ejercicio 02.20:== | | ==Ejercicio 02.20:== |
| ==Ejercicio 02.21:== | | ==Ejercicio 02.21:== |
| Construir una maquina de Turing deterministica que resuelva el problema de si un numero entero es divisible por 4
| |
|
| |
| El abecedario de esta maquina es {B,0,1}. El elemento default de la cinta es el 0 y el numero a trabajar se encuentra expresado en base uno y el mismo comiensa con una B.
| |
|
| |
| ej: 5 % 4 =? 0 ---00000000B111110000000000---
| |
|
| |
| los estado posibles son {q0,q1,q2,q3,q4,qt,qf}
| |
| el estado inicial es q0,B y el algoritmo devuelve qt si lo divide o qf sino
| |
|
| |
| <pre>
| |
| (q0,B,q0,b.+) (q1,1,q2,1.+) (q2,1,q3,1.+) (q3,1,q4,1.+) (q4,1,q1,1.+)
| |
| (q1,1,q2,1.+) (q0,0,qf,*.*) (q2,0,qf,*.*) (q3,0,qf,*.*) (q4,0,qt,*.*)
| |
| (q0,0,qf,*.*)
| |
| </pre>
| |
|
| |
| (nota al pie):la complejidad de este algoritmo me suena q es O(n) no se como demostrarlo
| |
|
| |
| ==Ejercicio 02.22:== | | ==Ejercicio 02.22:== |
| <br>a) | | <br>a) |
| Línea 246: |
Línea 87: |
| volver 1 lugar hacia atras | | volver 1 lugar hacia atras |
| 3.si (cinta == ultimo guardado) | | 3.si (cinta == ultimo guardado) |
| tachamos cinta con b | | tachamoa cinta con b |
| nos movemos al anterior y guardamos | | nos movemos al anterior y guardamos |
| (pero si es blanco ir a SI) | | (pero si es blanco ir a SI) |
| Línea 255: |
Línea 96: |
|
| |
|
| <br>b) | | <br>b) |
|
| |
|
| |
| [[Category: Prácticas]]
| |
