Ejercicios de programación en Python
Traducido por
ScribdTranslationsEjercicios de programación en Python
Traducido por
ScribdTranslationsEjercicios de programación en Python
1) Prueba de pertenencia
Escribir una función que, dado una lista a y un objeto x, devuelva verdadero si x es un elemento de la lista.
Corrígeme
Notar que el procedimiento se interrumpe tan pronto como se encuentra una ocurrencia.
def mem(a, x) :
para k en rango(0, len(a)):
si a[k] == x : devolver Verdadero
return False
Nota: Los puristas consideran (no sin razón) que las interrupciones de bucles son prácticas bárbaras.
de programación. Podríamos así proponer la siguiente variante:
def mem(a,x) :
test = Falso ; n=len(a) ; k=0
mientras (no prueba) y k<n :
si a[k] == x : prueba = Verdadero
k += 1
devolver prueba
Por ejemplo, print(mem([2,0,1,4],3))a¢ cheFalse.
Nota: En Python, el booleano (x en a) vale True si x es un elemento de la lista a:
2) Suite definida por una relación de recurrencia
Escribir una función que, dados dos argumentos, devuelva el valor.n , donde la secuela(uk )k2Nes la suite
1 a
dé...nie paru0= 1et8k2N,uk+1 = uk+ :
2 uk
Corrige
def suite(n,a) :
u = 1
para k en rango(0,n) :
u = (u + a/u) / 2
devuelve u
Nota: Por ejemplo, print(suite(10,2)) devuelve 1.414213562373095; de hecho, se puede demostrar que la sucesión (uk )k2N
converger hacia pa.
3) Máximo de dos enteros y máximo de una lista (no vacía)
a) Escribir una función máxima que, dados dos enteros, devuelva su valor máximo.
b) Escribir una función max que, dado una lista no vacía de enteros, devuelva su valor máximo.
Por ejemplo, print(max([1,3,5,1])) da 5.
Nota: Esta función max ya está definida en Python, con la sintaxis max(iterable). También es válida
para todos los iterables (tuplas, cadenas, diccionarios, etc ...).
Corrige
def máximo(x,y) :
si x>y : regresar(x)
else : return(y)
Nota: Las palabras clave def, if, else deben estar en primera posición, por lo tanto en líneas diferentes.
def max(a) :
n = len(a) ; m=a[0]
para j en el rango(1,n) :
si a[j] > m : m = a[j]
regresar m
4) Número máximo de ceros (consecutivos) en una lista
Se supone que la función máxima definida en el ejercicio anterior es conocida.
a) Escribir una función número que, dada una lista, devuelva el número de ceros en la lista.
Por ejemplo, print(nombre([1,0,2,0,0,4])) devuelve 3.
b) Escribir una función que, dada una lista, devuelva el número máximo de ceros consecutivos en la lista.
Por ejemplo, print(nombre([1,0,2,0,0,4])) devuelve 2.
Corrige
def nombre(a) :
n = len(a) ; c=0
para j en rango(0,n) :
si a[j]==0 : c += 1
devuelve c
Observación: Se utiliza un contador c. Se recuerda que c += 1 equivale a c = c + 1.
def consecutivo(a) :
n = len(a)
c=0 ; m=0
para j en rango(0,n) :
si a[j] == 0 : c += c
sino : c=0 ; m=max(m,c)
return max(m,c)
Comentario: Se utiliza un contador cuya valor corresponde al número de ceros consecutivos en la secuencia.
curso de lectura. También se utiliza una variable que memoriza la longitud máxima de las secuencias ya leídas. Cuando se
lit une valeur non nulle, se actualiza (asignándole max(m,c)), y se pone el contador en 0. Hay que tener cuidado
en la última etapa donde debemos devolver max(m,c).
5) Ordenar por selección
a) Escribir una función indMin que devuelva el índice del mínimo (devolviendo el más pequeño si hay varios).
ejemplo, indMin([5,2,3,4,2]) devuelve 1 (los elementos están indexados a partir de 0).
b) Escribir un procedimiento intercambiar que dados una lista a y dos enteros i y j permute en a los elementos de índices
ietj. Por ejemplo: a = [1,2,3,4,5]; echange(a,0,2); print(a) a¢ che[3,2,1,4,5].
c) Escribir un procedimiento que dada una lista, ordene esta lista de tal manera que ordene sus elementos (sin modificar)
el conjunto de sus valores). Se utilizará un ordenamiento por selección (de mínimos): El principio del algoritmo consiste en
determinar la posición del elemento más pequeño y ponerlo en la primera posición (mediante un intercambio), y luego iterar el proceso
sobre el sub-arreglo restante. Se necesitan (n-1) comparaciones para determinar la posición del elemento más pequeño, por lo que se necesita
(n 1) + (n 2) +:::=21n(n-1) comparaciones para ordenar una lista según este procedimiento.
Corrígete
a) Se utiliza una variable que memoriza el índice del elemento más pequeño ya leído:
def indMin(a) :
n = len(a)
k=0
para j en rango(1,n):
si a[j] < a[k] : k = j
regresar k
b) Hay varios métodos, ya que Python permite asignaciones de pares (más generalmente de tuplas):
def intercambiar(a,i,j) :
stock = a[i]; a[i] = a[j]; a[j] = stock
def intercambio(a,i,j) :
a[i],a[j] = a[j],a[i]
c) Se utilizan dos bucles anidados: en el bucle i-ésimo, se determina (con la ayuda del bucle j) la posición k del
el elemento más pequeño en el subarreglo[ayo ; ayo+1; :::; a n 1 ], luego intercambiaráyoetak .
def tri(a) :
n = len(a)
para i en rango(n) :
k=i
para j en rango(i+1,n): si a[j]<a[k]: k = j
echange(a,i,k)
Nota: Así, a=[1,3,2,2]; tri(a); imprimir(a) a¢ che[1;2;2;3]:
6) Pruebas de permutación
Se trata de determinar si una lista de longitud corresponde a una permutación de 0;1; :::; n-1, es decir, si todo
el entero comprend entre 0 y (n - 1) aparece una y una sola vez en la lista. Se trata de escribir una función a valores
booleanas que, dada una lista de longitud, devuelve verdadero si es una permutación de {0, 1, :::, n-1}.
proponga dos métodos, el segundo siendo más eficaz que el primero (el número de operaciones es menor).
a) Escribir una primera función test1 que para todo entero i2 f0;1; :::; n 1g, verifique que existe un único elemento de
la listeavalantj, y interrumpe el procedimiento tan pronto como esta prueba es falsa.
La complejidad en el peor de los casos es O(n)2 ).
b) Escribir una primera función test2 que para todo entero i que va de 0 a n-1 construya en tiempo lineal O(n) el arreglo
Las ocurrencias de bdes, es decir, que b[j] equivale al número de términos deavalantj. Luego se verifica (en tiempo lineal O(n)).
que la tabla de ocurrencias solo contiene 1. La complejidad es O(n).
Corrigé
Cabe destacar que una instrucción con un return permite interrumpir un bucle for.
def prueba1(a) :
n=len(a)
para i en rango(n):
s=0
para j en a :
si i==j : s+=1
si s != 1 : retornar Falso
returnar True
def test2(a) :
n=len(a)
b = [0]*n l'instruction [0]*n crée la liste de longueur n contenant que des 0
para i en rango(n) : occu[a[i]] += 1
return (occu == [1]*n)
Nota: En Python, se puede probar directamente la igualdad de listas (y más generalmente de cualquier objeto). Sin embargo,
hay que tener en cuenta que la complejidad es proporcional a la longitud de la lista.
7) Búsqueda por dicotomía
En Python, el cociente de la división euclidiana de un entero por otro se obtiene mediante //. Así, si m es un
entier,(m//2) es igual a la parte entera E(m=2):
Se da un número y una lista a = (a0 ; a1 ; :::; a n 1 )de nombres clasificados por orden creciente.
Se propone determinar si seis es un elemento de la lista mediante un método de dicotomía: Supongamos que se conocen dos enteros
ietjtels quej i >1etayo< x < aj . Se considera el elemento de índice k=E(21(i+j)): Está situado (en el mejor de los casos) en
medio de la tabla compuesto por los elementos cuyos índices están comprendidos entre etj. Se compara xetak . Seis < ak , entonces
ayo< x < ak , y se puede iterar el procedimiento (sik i >1). Siak< x, alorsak< x < aj . Siak=x, entonces devolvemosTrue.
Es muy importante entender que se devuelven falsos ya sea al principio seis < a0oux > an 1ya sea cuando se llega a
dos índices que
Escribir una función dito, que dados una lista ordenada y un número x devuelve True si x aparece en a.
Corrige
def dicho(a,x) :
i=0 ; j=len(a)-1
si (x-a[i])*(x-a[j])== 0 : retornar Verdadero
si (x-a[i])*(x-a[j])>0 : retornar False
mientras j-i>1 :
k = (i+j)//2
si a[k] == x : devolver Verdadero
si a[k] > x : j = k
sino : i = k
return False