Daniel Santamaría Álvarez – 201720222
Dalgo - Tarea 1
1. Dado un número natural, encontrar su raiz cuadrada entera, la cual se define
como el mayor número natural que es menor que la raíz cuadrada real del
número
Entrada: Número natural
var n: nat
Salida: Número natural que representa una raíz cuadrada entera
var r: nat
Precondición: No hay ninguna condición previa que se aplique sobre la
entrada. Se utilizará una constante C para asegurar la persistencia del dato
en el programa.
𝑄: 𝑛 = 𝐶
Postcondición: El objetivo en términos de la entrada y salida se
representaría de la siguiente forma tal que
𝑟 ≤ √𝐶 ≤ 𝑟 + 1
La función 𝑥 2 es creciente en los números reales, la postcondición también
se puede expresar de la siguiente forma en que no requiere el uso de raíces
cuadradas:
{R: 𝑟 2 ≤ C ≤ (𝑟 + 1)2 }
2. Dado un número natural, determinar si es un número primo
Entrada: Número natural
var n: nat
Salida: variable booleana que muestra si el número de entrada es primo o no
var b: bool
Daniel Santamaría Álvarez – 201720222
Precondición: Para cualquier número natural se puede determinar si es
primo, no se pide ninguna condición particular sobre la entrada. Se utilizará
una constante C para asegurar la persistencia del dato en el programa.
𝑄: 𝑛 = 𝐶
Postcondición: El valor de b tiene que coincidir al final con el valor de verdad
de un predicado que solo sea cierto si n es primo. Según la definición de
número primo, el predicado debe indicar que el residuo entre n y cualquiera
de estos números debe ser mayor que cero. La postcondición hace entonces
equivalente el valor de b al valor del predicado:
{R: b = (∀ k | 2 ≤ k ≤ C ∶ C mod k > 0)}
3. Dado un número primo. Encontrar el siguiente número primo:
Entrada: Número natural
var n: nat
Salida: Número natural que representa al siguiente número primo
var p: nat
Precondición: Se pide como condición de inicio que el número de entrada n
sea primo. Como este predicado lo vamos a necesitar también en la
postcondición, lo vamos a definir con el nombre PR para cualquier número
natural x:
PR(x) = (∀ k | 2 ≤ k < x ∶ x mod k > 0)
{Q: PR(n)}
Postcondición: Utilizando el mismo predicado, pedimos al final que p sea
mayor que n, que p sea primo y que ningún número entre n y p sean primos
{R: n < p ∧ PR(p) ∧ (∀𝑘 |𝑛 < 𝑘 < 𝑝 ∶ ¬𝑃𝑅(𝑘)}
Daniel Santamaría Álvarez – 201720222
4. Dado un arreglo de números enteros, encontrar el múltiplo de 3 más grande
del arreglo. Si el arreglo no tiene múltiplos de 3, la respuesta debe ser -1
Entrada: Lista de números. Se representarán en un arreglo de tamaño N.
var E[N]: Array of Z
Salida: múltiplo de 3 más grande de la lista.
var s: Z
Precondición: No hay ninguna condición previa que se pida sobre la entrada.
Pero si la lista se encuentra ordenada, se podría empezar de atrás hacia
adelante. Si no se encuentra ordenada no tiene caso ordenarla ya que solo
se realizaría una única consulta sobre esta y eso tiene un complejidad de
O(n)
Postcondición: Se expresa el objetivo que es el mayor numero múltiplo de 3
de la lista
5. Dado un conjunto de estudiantes ordenados por código y el código de un
estudiante, encontrar el estudiante con el código dado o reportar que el
estudiante no existe
Debido a que el enunciado nos indica que trabajaremos con un objeto de tipo
estudiante, este se representará con la variable e de tipo estudiante. Para
saber su código se usará [Link] y su nombre será [Link]
Entrada:
- Lista de estudiantes. Asumiremos que cada estudiante tiene un código
único y saber que es un conjunto. Se representaran en un arreglo
ordenado de tamaño N.
var E[0,N] : array of Estudiante
- Código del estudiante
Var c: string
Daniel Santamaría Álvarez – 201720222
Salida: Estudiante con el código buscado. Este puede ser un valor nulo.
var e: Estudiante
Precondición: Dado que se escogió un arreglo para representar los
estudiantes, se debe validar como precondición que el arreglo no tenga
repetidos. Además se va a pedir que esté ordenado por código. Las dos
condiciones se pueden describir con un solo predicado:
{𝑄: (∀𝑘 |0 ≤ 𝑘 ≤ 𝑁 − 1 ∶ 𝐸[𝑘]. 𝑐𝑜𝑑𝑖𝑔𝑜 < 𝐸[𝑘 + 1]. 𝑐𝑜𝑑𝑖𝑔𝑜)}
Postcondición: Como hay dos posibilidades, que el estudiante esté o que no
esté, se utiliza una disyunción y se expresa cual es el valor de la variable de
salida en cada uno de los dos casos:
{𝑅: (𝑒 =⊥ ∧ (∀k |0 ≤ 𝑘 ≤ 𝑁 ∶ 𝐸[𝑘]. 𝑐𝑜𝑑𝑖𝑔𝑜 ≠ 𝑐)) ∨ (𝑒 ∈ 𝐸 ∧ 𝑒. 𝑐𝑜𝑑𝑖𝑔𝑜 = 𝑐)}
6. Dado un conjunto de n cadenas, encontrar la cadena más corta tal que cada
una de las cadenas de entrada sea una subcadena de la cadena de salida
