Download TRABAJO PRÁCTICO N° 3

Departamento de Cs. de la Computación
Resolución de Problemas y Algoritmos
Universidad Nacional del Sur
2001
TRABAJO PRÁCTICO N° 3
ALGORITMOS – PARTE II
Fecha tentativa de terminación: (a confirmar)
Ejercicio 1 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.
Ejercicio 2 Escribir un algoritmo que indique si un número natural n puede expresarse como la
suma de dos números primos.
Ejercicio 3 Elaborar un algoritmo que decida si un número natural n es o no capicúa. Un número
n formado por dígitos “d1 d2 d3 … dk ” es capicúa si el numero “dk dk-1 … d2 d1 ” es igual a n. Por
ejemplo, 1, 7, 212 y 5005 son capicúas.
Ejercicio 4 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.
Ejercicio 5 Un número natural a es espejo de otro número natural b, si los dígitos que forman a
listadas en orden inverso forman el número b. Ej: 123 es espejo de 321; 334667 es espejo de
766433; 345 no es espejo de 541. Escribir un algoritmo que, dados dos números naturales a y b,
indique si a es espejo de b.
Ejercicio 6 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.
Ejercicio 7 Escribir un algoritmo que, dados dos números enteros a y b tal que a ≤ b, indique si
todos los números comprendidos entre a y b pueden expresarse como la suma de dos números
primos. Por ejemplo, si a=5 y b=8 el algoritmo debe responder verdadero, dado que 5=2+3,
6=3+3, 7=2+5 y 8=3+5.
Ejercicio 8 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:
1. Dadas dos fechas d1, m1, a1 y d2, m2, a2, determinar si las fechas son iguales.
Página 1 de 3
Departamento de Cs. de la Computación
Resolución de Problemas y Algoritmos
Universidad Nacional del Sur
2001
2. Dada una fecha d, m, a, determinar cuál será el día siguiente. Por ejemplo, si la fecha es
31/12/1993 el día siguiente será 1/1/1994.
3. Dadas dos fechas d1, m1, a1 y d2, m2, a2, calcular la cantidad de días comprendidos entre
ambas. Observación: es posible utilizar el algoritmo que, dada una fecha, devuelve como
resultado el día siguiente a la misma.
Ejercicio 9 Desarrollar un algoritmo que indique si dos números naturales n y m están
formados por los mismos dígitos. Por ejemplo, 321 y 213; 599 y 995; 45 y 554 están formados por
los mismos dígitos.
Ejercicio 10 Escribir un algoritmo que, dado un número natural n, devuelva un nuevo número
natural m, tal que m esté formado por los dígitos de n ordenados de menor a mayor.
Ejercicio 11 Confeccionar un algoritmo que, dado un número natural n, devuelva el menor
número natural m que puede formarse usando todos sus dígitos impares seguidos de todos sus
dígitos pares. Por ejemplo: para n=96592, este algoritmo debe devolver m=59926.
Ejercicio 12 Escribir algoritmos para calcular la suma de los n primeros términos de las
siguientes sumatorias:
a) 1 + 3 + 5 + 7 + ... + ( 2k + 1)
b) 1 − 3 + 5 − 7 + ... + ( −1) k ( 2k + 1)
c) 2*13 / 1! - 2*23 / 2! + 2*33 / 3! - 2*43 / 4! + … + (-1)n+1 * 2 * n3 / n!
Ejercicio 13 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 elementos de la sucesión de
Fibbonacci son: 1, 1, 2, 3, 5, 8, 13, 21, 34, . . .
a) 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.
b) Elaborar un algoritmo que, dados dos números naturales cualesquiera n y m, determine
si los mismos son miembros consecutivos de la sucesión de Fibbonacci. Ej: para n=5 y
m=8, la respuesta es verdadero; para n=5 y m=21, la respuesta es falso.
Ejercicio 14 Dos números x e y se dicen primos mellizos si tanto x como y son primos, y difieren
entre sí en dos unidades. Por ejemplo, los números 3 y 5 son primos mellizos. Confeccionar un
algoritmo para contar la cantidad de pares de primos mellizos formados por números menores o
iguales a un natural m (dato de entrada de este algoritmo). Ej: para m=15 hay tres pares de primos
mellizos, que son los siguientes: (3,5); (5,7) y (11,13).
Ejercicio 15 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 son impares y el dígito restante es par.
Ej.: 123, 161, etc.
Ejercicio 16 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.
Página 2 de 3
Departamento de Cs. de la Computación
Resolución de Problemas y Algoritmos
Universidad Nacional del Sur
2001
Ejercicio 17 Enunciar un algoritmo que dados dos números naturales n y m, diga si m está
“contenido” en n. Un número m está contenido en otro n si la secuencia de los dígitos de m aparece
consecutivamente dentro de la secuencia de los dígitos de n. Por ejemplo, 12 está contenido en
2123, 12 no está contenido en 2132 , 103 está contenido en 93103, 31 está contenido en 93103.
Importante: el algoritmo debe funcionar correctamente para casos del estilo: N=9872387, M=987.
Ejercicio 18 Dado un valor de X tal que -1 < X ≤ 1, podemos resolver la serie binomial (1+X)-1/2
como se detalla a continuación:
(1 + X )
−1
2
=1× X 0 +
1 × X 1 1× 3 × X 2 1 × 3 × 5 × X 3 1 × 3 × 5 × 7 × X 4
−
+
−
+Λ
2
2 ×4
2 ×4 × 6
2 × 4 ×6 ×8
Suponiendo que se cuenta con la primitiva POTENCIA que dado una base y un exponente devuelve
baseexponente (es decir, es posible llamar a esta primitiva como POTENCIA X,3 para obtener X3 ).
a) Escribir un algoritmo que dado un X tal que -1 < X ≤ 1, y un n perteneciente a los
naturales unidos al cero, devuelva el n-ésimo término de la serie binomial.
b) Realizar un algoritmo que calcule una aproximación de (1+X)1/2 con un error dado.
Ejercicio 19 Elaborar un algoritmo que permita calcular un valor de la serie:
1−
x1 x 2 x 3 x 4 x5
+
−
+
−
+Λ
1!
2! 3! 4! 5!
para un valor de x cualquiera, con una “aproximación” de 0.001 en el resultado (es decir, si Sk es la
suma de los primeros k términos, y SK+1 es la suma de los primeros k+1 términos, la diferencia en
valor absoluto entre SK y SK+1 debe ser menor que 0.001).
Ejercicio 20 Suponiendo que p1 = 2, p2 = 3, p3 = 5, etc. (es decir pi = i-ésimo número primo, pi+1 =
i+1-ésimo número primo), escribir una primitiva SumarSeriePrimos que dado un número natural n
calcule la suma de los primeros n términos de la serie:
p
p
p
p
p
p
1
+ 1 + 2 + 3 + 4 + 5 + Λ + n −1
p1 p 2 p 3 p 4 p 5 p 6
pn
Por ejemplo, si n=3, SumarSeriePrimos debe devolver la suma de 1/p1 +p1 /p2 +p2 /p3 , es decir, la
suma de 1/2+2/3+3/5 = 1.77. Sugerencia: definir una primitiva PróximoPrimo que dado un número
n devuelva el primer primo mayor que n.
Página 3 de 3