Download TRABAJO PRÁCTICO N° 3
Document related concepts
Transcript
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