Download TP3 - TEM

Document related concepts

Algoritmo de Karatsuba wikipedia, lookup

Cálculo de la raíz cuadrada wikipedia, lookup

Algoritmo wikipedia, lookup

Test de primalidad AKS wikipedia, lookup

Algoritmo de Luhn wikipedia, lookup

Transcript
Tecnologías en la Educación Matemática
Dpto. de Cs. e Ing. de la Computación, UNS
Trabajo Práctico N° 3
Problemas y Algoritmos con repetición
1. Indicar en cada caso cuál será el valor de los datos a, b y c después de ejecutar los siguientes
trozos de algoritmos.
(1)
a0
b 1
repetir mientras a < 100
b  b*2
(2)
c  100
repetir
cc–1
hasta c = 0
(3)
a9
repetir mientras a < 10
aa+1
(4)
a0
repetir
a  a +1
hasta a = 0
(5)
b5
repetir mientras b = 0
bb-1
2. Trazas:
a) Determinar cuál será el valor de los datos a, b y c después de ejecutar el siguiente trozo de
algoritmo, suponiendo que al comienzo a = 3 y b = 2. ¿Qué relación hay entre el valor final de c
y los valores iniciales de a y b?
ca
repetir mientras b > 0
cc+1
b b - 1
b) ¿Qué ocurre si ejecuta el mismo trozo de código para un valor negativo de b?
c) Realizar una traza de los siguientes trozos de algoritmos para los mismos valores usados en el
inciso a y b respectivamente. ¿Qué conclusiones puede sacar?
a)
ca
repetir
cc+1
bb-1
hasta b = 0
3.
a)
b)
c)
d)
b)
ca
si b>0
entonces
repetir
cc+1
bb-1
hasta b = 0
Escribir algoritmos para:
Hallar la suma de los primeros 1000 números naturales.
Sumar los primeros n números naturales.
Calcular el producto de los primeros n naturales pares.
Dado un número entero x, contar la cantidad C de dígitos que lo forman. Ej: si x=343, entonces
c=3; si x = -20, entonces c=2.
e) Dado un número entero x, calcular la suma S de todos los dígitos que lo forman. Ej: si x=12,
entonces S=1+2=3.
f) Determinar si un dígito d está presente en un número entero x. Ej: el dígito 5 está presente en
el entero 345; el dígito 3 no está presente en el entero -122.
g) Indicar si un entero positivo n es o no un número primo. Recordar que un entero n es primo si
y sólo si es divisible por sí mismo y por la unidad
Tecnologías en la Educación Matemática
Dpto. de Cs. e Ing. de la Computación, UNS
4. Dado el siguiente algoritmo:
Algoritmo ¿Qué?
Datos de Entrada: x, y {números naturales}
Datos de Salida: a
Datos Auxiliares: z
ax
repetir
za+x
yy-1
az
hasta y = 1
Fin Algoritmo
a) Realizar las trazas necesarias para determinar qué operación matemática realiza, usando
valores de y mayores que 1.
b) ¿Qué inconveniente presenta para y =1?. Justificar.
c) Escribir una nueva versión de este algoritmo que resuelva el problema encontrado. En esta
nueva versión, es importante utilizar nombres significativos para los datos.
5. Considerando el siguiente algoritmo:
Algoritmo Sorpresa
Datos de Entrada: a {número natural}
Datos de Salida: b {número natural}
Datos Auxiliares: dig
ba
repetir
dig  a//10
a  a /e 10
b  b * 10 + dig
hasta a = 0
Fin Algoritmo
a) ¿Qué operación realiza el algoritmo SORPRESA?. Confeccionar una traza para a=4834 y a=4830.
b) ¿Qué ocurre si se cambia la primera asignación, es decir, b  a por b  0?
6. Dado el siguiente algoritmo:
Algoritmo Desconocido
Datos de Entrada: x {número natural}
Datos de Salida: a
ax
repetir
xx-1
aa*x
hasta x = 1
Fin Algoritmo
a) Confeccionar las trazas necesarias para determinar qué operación matemática realiza el
algoritmo Desconocido usando valores de x mayores o iguales que 2.
b) ¿Qué inconveniente presenta para x=1? Justificar.
Tecnologías en la Educación Matemática
Dpto. de Cs. e Ing. de la Computación, UNS
c) Escribir una nueva versión del mismo que resuelva el problema encontrado. En esta versión,
es importante utilizar nombres significativos para los datos.
7. Escribir algoritmos para cada uno de los siguientes incisos. Es recomendable utilizar como
primitivas los algoritmos realizados en el práctico anterior.
a) Sumar los números primos menores a un número natural n dado. Ej. si n =18, el algoritmo
deberá sumar 2+3+5+7+11+13+17.
b) Dado un número natural primo p, escribir un algoritmo que calcule el primo ps inmediato
siguiente. Ej.: si p = 5 entonces ps deberá ser 7. Si p = 13 entonces ps deberá ser 17
c) Dados dos números a y b, determinar si la suma de los divisores de a es igual a b.
d) Dados dos números a y b, y un dígito d, decidir si d está presente tanto en a como en b.
e) Dados dos números a y b, devolver si la suma de los dígitos de a es igual a la suma de los
dígitos de b.
8. Escribir algoritmos que teniendo como dato de entrada n, calculen los n primeros elementos
de las siguientes sumatorias:
a) 1+3+5+7+…+(2k+1)
b) 1-3+5-7+…+(-1)k(2k+1)
9. La sucesión de Fibbonacci comienza con los números 1 y 1. Luego, cada uno de los términos se
calcula como la suma de los dos anteriores. Los primeros términos de la sucesión de
Fibbonacci son: 1, 1, 2, 3, 5, 8, 13, 21, 34, . . .
Escribir un algoritmo que, dado un número natural n, devuelva el n-ésimo término de la
sucesión de Fibbonacci. Ej: para n=7, debe devolverse 13.
10. Escribir un algoritmo que genere y cuente todos los números naturales de 3 cifras en los
cuales el dígito más significativo y menos significativo sean impares y el dígito restante par.
Ej.: 123, 161, etc.
11. Desarrollar un algoritmo que genere y cuente todos los números naturales de 4 dígitos tal que
la suma del dígito perteneciente a la unidad y el dígito perteneciente a la centena sea mayor
que la suma de los restantes dígitos. Por ejemplo, 1237 y 7989 son números que deberían
contarse pero 5321 y 9821 no.
12. Una fecha puede representarse mediante tres números naturales Día, Mes y Año,
correspondientes a número de día, número de mes y número de año, respectivamente.
Escribir algoritmos para, dadas dos fechas d1, m1, a1 y d2, m2 y a2 determinar si son iguales.
13. Dos números se dicen amigos si la suma de los divisores de cada uno de ellos (incluida la
unidad, y exceptuando el número mismo) es igual al otro número dado. Ej: 220 y 284 son
números amigos. Escribir un algoritmo para determinar si dos números enteros x e y son
amigos.
14. Un número natural n se dice perfecto si la suma de todos sus divisores positivos (incluyendo la
unidad) es igual a n. Ej: 28 = 1+2+4+7+14 es un número perfecto; otros números perfectos son
el 6 y el 496. El número 12  1+2+3+4+6, luego 12 no es perfecto. Confeccionar un algoritmo
para determinar si un número natural n es perfecto.