Boletín de Problemas de Metodología y Tecnología de la Programación

Bolet´ ın de Problemas de Metodolog´ ıa y Tecnolog´ ıa de la Programaci´ on, IS04 Curso 2006/2007 16 de octubre de 2006 1 Cap´ ıtulo 2: Conceptos B´ asicos 1. Se dispone de dos variables, xey. No importa de qu´ e tipo son. Hay que escribir un algoritmo que permita que intercambien sus valores. 2. Sabiendo que x,yyzson variables del mismo tipo, con valores distintos dos a dos, analizar la siguientes secuencias de instrucciones e indicar en cu´ ales var´ ıa el resultado si se invierte el orden de ejecuci´ on. Por ejemplo, si var´ ıa o no el resultado si se ejecuta la secuencia x=y z=xo la inversa z=x x=y (a)x=y z=y (b)x=y y=x (c)x=x+y z=x+y (d)y=x+y z=x+z 3. Escribir un algoritmo que, dados tres valores de tipo real, permita calcular su media aritm´ etica. 4. Dise˜ nar un algoritmo que permita pasar una cantidad de tiempo expresada en segundos al formato horas, minutos y segundos. 5. Sabiendo que el precio de venta al p´ ublico de un art´ ıculo engloba su precio de coste y las siguientes repercusiones, Gastos de comercializaci´ on, estimados en un 20 % sobre el precio de coste, Gastos Generales, personal, publicidad ... estimados en un 75 % sobre el precio de coste, Impuestos, que repercuten un 1.5 % sobre el precio de coste, Y al resultado del precio obtenido, a˜ nadirle un 0.7 % sobre el precio resultante como aportaciones a ONGs, escribir un algoritmo que, conociendo el precio de coste, permita determinar el precio de venta al p´ ublico final. 6. Escribir un algoritmo que permita determinar la soluci´ on de una ecuaci´ on de primer grado, ax + b = c. 7. Escribir un algoritmo que, dado un valor de tipo real, permita calcular el ´ area del cuadrado cuyo lado tiene esa medida. 8. Escribir un algoritmo que, dado un valor de tipo real que representa el ´ area de un c´ ırculo, permita calcular el per´ ımetro de su circunferencia. Cap´ ıtulo 3: Programaci´ on Estructurada 1. Sean a y b dos variables enteras con valores 3 y 5, respectivamente. Indicar si las siguientes condiciones son ciertas o falsas: a + b < 10 !((a + b) <= 10) a >= 2 && b >= 5 a < 10 || (a > 0 && b < 0) a > 0 && (b < 2 || !(b > 5)) a < 5 && b < 8 !(a >= 5 || b >= 8) 2. Sean A, B, C y D variables enteras. Se considera la secuencia if (((A >0) || (B >C)) && ((D >A) || (D <5))) { A=0; D=B+C; } else { C=A-B; if (C <0){ D = -D ; } B = 0 ; } Determinar los valores finales para las variables, sabiendo las siguientes posibilidades de valores iniciales: a) A = 5, B = 3, C = 4, D = 6 b) A = -1, B = 3, C = 4, D = 3 c) A = -1, B = -2, C = 4, D = 3 3. Sean X, Y y S variables enteras. Dada la secuencia if (X < 0) S=1; else if (Y > 0) S = 1 ; else S=0; escribir una secuencia equivalente, sin anidamiento de condicionales y sin repetir la instrucci´ on S = 1. 4. Dada la secuencia if (p && q) a ; else s ; 3 donde pyqson predicados elementales y aysson acciones, escribir una secuencia equivalente, en la que s´ olo se eval´ ue cada vez un predicado elemental. 5. ¿Son equivalentes las tres secuencias siguientes? s=0; if (p) { s=3; } else { if (!q) { s=3; } } s=0; if (!(!p&&q)) { s=3; } s=0; if (p || !(q)) { s=3; } 6. A, B y C son tres variables enteras. Escribir una secuencia de instrucciones que determine cu´ al es la variable de mayor valor y devuelva el resultado en una variable MAX. 7. Dados tres valores enteros A, B y C, escribir una secuencia de instrucciones que los ordene en orden creciente. 8. Las siguientes secuencias hacen lo mismo, pero ¿cu´ al es mejor y por qu´ e? (nota: los valores de a, b y c son distintos dos a dos.) if ((a>b) && (a>c)) { max = a; } if ((b>a) && (b>c)) { max = b; } if ((c>a) && (c>b)) { max = c; } if ((a>b) && (a>c)) { max = a; } else { if ((b>a) && (b>c)) { max = b; } else { if ((c>a) && (c>b)) { max = c; } } } 9. Dado el siguiente fragmento de c´ odigo, reescribirlo utilizando un ´ unico condicional, que adem´ as est´ e simplificado al m´ aximo: if (b < 10) { if (b >= 5) a=a*2; if (b < 5) { if (b >= 0) a = a*2; } } 10. Escribir una secuencia de instrucciones que determine a cu´ anto asciende la factura de la luz de un abonado. Para ello, se conoce AI, antiguo ´ ındice y NI, nuevo ´ ındice, que representan los valores le´ ıdos en el contador de la luz. El resultado se quiere sobre la variable IMPORTE, que se calcula sabiendo que un abonado a) Paga 5 euros por gastos fijos de contrato, b) El consumo se determina por tramos: los primeros 100 Kws, a 5 c´ entimos el Kw; los 150 Kws siguientes, a 3 c´ entimos el Kw; si el consumo excede de 250 Kws, esa fracci´ on se cobra a 2 c´ entimos el Kw. 4 11. Reescribir la siguiente secuencia en forma de un ´ unico condicional regido por un predicado compuesto, tan simple como sea posible. Justificar todos los cambios realizados. if (a > b) if (b-a > 0) a=a+1; else if (x > a) if (x > b) if ((2*x) > (a+b)) x = 0; else if (x < 100) x = 1; 12. Simplificar al m´ aximo las siguientes secuencias, justificando las acciones realizadas, sabiendo que las variables X, Y, I y K, son enteras: if (X>0) { I=I+2; K=0; Y=2*X; } else { I=I+2; K=0; Y=0; } if (X==3) { X=Y; Y=0; I=X+Y; } else { X=Y; Y=K*2; I=X+Y; } 13. Las secuencias siguientes ¿hacen lo mismo? s=0; x=a; s=b; if (x>=c) { x=x%c; } else { x=x+1; } s=b; if (x>=c) { x=a; x=x%c; } else { x=a; x=x+1; } 14. ¿Verdadero o Falso (justificar)?: La ejecuci´ on de cada una de las dos secuencias siguientes es exactamente igual. if (v<V1) { <inst 1>; } else { if (v>V2) { <inst 2>; } } if (v<V1) { <inst 1>; } if (v>V2) { <inst 2>; } 15. Antes de ejecutarse el siguiente fragmento de c´ odigo se cumple el predicado /* j <Nand acum == 0 */. Analizar el fragmento e indicar que ocurrir´ ıa al ejecutarlo: 5 i=j; while (i<=N) { if (j<i) { i=i-1; } else { i=i+1; } acum=acum+i*i; } 16. Simplificar al m´ aximo la secuencia siguiente, justificando adecuadamente todos los cambios realizados: /*x e y son variables reales */ /*n, entero, n=N>1 */ y = x; for (i=1; i<=n; i=i+1){ if (i<n) { y=i*x; } else { y=2*x; } } 17. Dado el siguiente esquema condicional: if (<cond1>){ if (<cond2>){ <inst1>; } else { if (<cond3>){ <inst2>; <inst3>; } } } else { if (<cond3>){ <inst2>; <inst3>; } } ¿Es posible substituirlo por un ´ unico condicional? ¿Por qu´ e? Dar una versi´ on equivalente con el menor n´ umero posible de condicionales anidados. 18. Simplificar al m´ aximo el siguiente condicional, sabiendo que a,b,cydson enteros: 6 a = 3; if (a < 3) { b=2*a; } else { if (b > c) { a=a+b; b=b+c; c=c+d; } else { a=a+b; b=b+c; c=2*c; c=c+d; } } 19. ¿Verdadero o Falso (justificar)?: “Los dos condicionales siguientes siempre producir´ an los mismos resultados”, if (p) { <inst 1>; } else { <inst 2>; } if (p) { <inst 1>; } if (!p) { <inst 2>; } 20. ¿Verdadero o Falso (justificar)?: “Los dos condicionales siguientes son equivalentes”, if (p) { for(j=k;j<=q;j++) { b[i]=a[j]; i++; } } else { for(k=j;k<=m;k++) { b[i]=a[k]; i++; } } if (p) { for(j=k;j<=q;j++) { b[i]=a[j]; } } else { for(k=j;k<=m;k++) { b[i]=a[k]; } } i++; 21. Simplificar al m´ aximo el siguiente condicional: if (a>=b) { a=a/2; if (a>=c) { a=a/2; } else { a=a/2; } } else { a=a/2; } 22. Dado el siguiente bucle, en el que iytson enteros, 7 /*n es un entero, n>1 */ t=1; i=0; while (t<n) { t=t*2; i=i+1; } indicar para cada uno de los predicados siguientes si puede ser o no un invariante y por qu´ e: a){2i<=n&& n>0} b){n>0&& i<=log2n} 23. Simplificar al m´ aximo la siguiente secuencia de c´ odigo: /*Pre: j==V1, V1 > 0 */ int aux, i; aux=0; i=0; while (i<=j) { if (i>=j) { aux=aux+(i*j); i=i+1; } else { aux=i*j; i=j; } } printf(" %d\n", aux); } 24. Dada la variable entera NUM, que contiene un valor n ≥1, elaborar una secuencia de instrucciones que determine la suma de los nprimeros n´ umeros naturales. 25. Dado un entero i, i >0, escribir una secuencia de instrucciones que nos devuelva el menor entero n, tal que 2n> i . 26. Escribir una secuencia de instrucciones que determine el cociente y el resto de la divisi´ on entera de dos n´ umeros enteros A y B. (Nota: mediante restas y sumas). 27. Escribir una secuencia de instrucciones para calcular xn, siendo n un n´ umero entero. 28. Dado un valor n≥1, elaborar una secuencia de instrucciones que calcule n!. 29. Escribir un programa que haga lo siguiente: Se ir´ an leyendo valores reales por teclado y el objetivo es detectar secuencias. Una secuencia es una serie de n´ umeros consecutivos iguales. Por ejemplo, en la siguiente serie hay 6 secuencias: 0.25, 0.5, 0.5, 1.75, 0.1, 0.1, 0.1, 0.1, 0.15, 0.8, 0.8, 0.0 Cuando se lea el valor 0.0 finaliza la introducci´ on de n´ umeros y se deber´ a escribir cu´ antas secuencias se han detectado. 30. La sucesi´ on de Fibonacci se obtiene de acuerdo a fibonacci(n) =    1si n = 1, 1si n = 2, fibonacci(n−1) + fibonacci(n−2) si n > 2 . 8 Escribir una secuencia de instrucciones que calcule el n´ umero de Fibonacci asociado a un entero n. 31. Escribir una secuencia de instrucciones que permita calcular el t´ ermino n de la sucesi´ on s0= 1 s1= 1 s2= 1 sn=sn−2+sn−3, n ≥3. Es decir, los tres primeros t´ erminos son 1, 1, 1; el siguiente se calcula sumando los t´ erminos pen´ ultimo y antepen´ ultimo. Si, por ejemplo, n=12, los t´ erminos a calcular ser´ ıan: 1, 1, 1, 2, 2, 3, 4, 5, 7, 9, 12, 16, 21,... y habr´ ıa que devolver el valor 21. 32. Escribir una secuencia de instrucciones que calcule el t´ ermino k-´ esimo de la sucesi´ on T(0) = 1 T(1) = 1 T(n) = T(n−1) + (n−1) ∗T(n−2), n ≥2. 33. Escribir una secuencia de instrucciones que convierta una variable entera en otra, tambi´ en entera, en la que el entero original aparezca del rev´ es. Por ejemplo, el entero 357 se debe convertir en el 753. 34. Escribir una secuencia de instrucciones que dado un n´ umero entero lo reduzca a la suma de sus d´ ıgitos, de forma que el resultado sea un n´ umero de un s´ olo d´ ıgito. Por ejemplo, dado el n´ umero 13674891, 13674891 →1 + 3 + 6 + 7 + 4 + 8 + 9 + 1 = 39 →3 + 9 = 12 →1 + 2 = 3 el resultado pedido es 3. 35. Escribir una secuencia de instrucciones que calcule la exponencial de un n´ umero real a, de acuerdo a la serie, ea= ∞ $ n=0 an n!= 1 + a+a2 2+a3 3! +a4 4! +. . . +an n!+. . . Aproximar el resultado hasta que para alg´ un kse cumpla que ak/k!≤10−5. 36. Escribir una secuencia de instrucciones que calcule la exponencial de aseg´ un la serie del problema 35, pero aproximando hasta que k=20. 37. La funci´ on seno se puede calcular de acuerdo a la serie sin x= ∞ $ n=0 (−1)nx2n+1 (2n+ 1)! =x−x3 3! +x5 5! −x7 7! +. . . mientras que para calcular la funci´ on coseno se utiliza la serie, cos x= ∞ $ n=0 (−1)nx2n (2n)! = 1 −x2 2! +x4 4! −x6 6! +. . . Dado un real, x, escribir una secuencia de instrucciones que calcule el seno y el coseno de x simult´ aneamente utilizando estas series y de la forma m´ as eficiente posible. Se considerar´ a una aproximaci´ on v´ alida que |sin2x+ cos2x−1|sea menor que 10−6. 9 b) Escribir un programa que use la funci´ on del apartado anterior para determinar cu´ antos n´ umeros curiosos pares y cu´ antos n´ umeros curiosos impares hay entre 1 y un valor entero K, que se leer´ a de teclado. 13. Diremos que dos n´ umeros enteros positivos nymest´ an liados si al pasarlos a binario la cantidad de 1’s de nes igual a la cantidad de 0’s significativos de my la cantidad de 0’s significativos de nes igual a la cantidad de 1’s de m. Por ejemplo, el n´ umero 50 (110010) est´ a liado con: el 35 (100011), el 37 (100101), el 38 (100110), el 41 (101001), el 42 (101010), el 44 (101100), el 49 (110001), el 52 (110100) y el 56 (111000). a) Escribir una funci´ on que determine si dos n´ umeros est´ an o no liados, indicando su precondici´ on y su postcondici´ on. La cabecera debe ser: boole liados (int n, int m) b) Escribir un programa que use la funci´ on del apartado anterior para determinar cu´ ales son los n´ umeros liados con uno dado, que se leer´ a de teclado. Nota: Dado n¿cu´ al es el rango de los posibles candidatos a estar liados con ´ el? 14. ¿Cu´ al es el dominio de definici´ on del siguiente algoritmo? Justifica la respuesta. char mayuscula(char c) { return c-32; /*Post:devuelve c en may´ usculas*/ } NOTA: Para transformar ’z’ (c´ odigo ASCII 122) en ’Z’ (c´ odigo ASCII 90), por ejemplo, basta con restarle 32. Los c´ odigos ASCII de las letras may´ usculas van de 65 a 90. 15. El siguiente algoritmo determina si en un n´ umero aparece o no un determinado d´ ıgito ¿Cu´ al es su dominio de definici´ on? Justificar la respuesta. boole contieneDigito (int num, int digito) { int n; n = num; while ((n>9) && (n %10!=digito)) { n=n/10; } return (n %10==digito); } 16. Simplificar al m´ aximo la siguiente funci´ on y especificarla: int simplFuncion(int y, int z, int v) { int i, w, x; x = 0; if (x > 1) { x = 2; 16 } else { x = 1; } if (x == 1) { x = y; x = (x+z)/2; w=x; for (i=1;i<=((w)/1)+1);i++) { v=v*x+v; } v = v/w; } else { x = z; x = (x+z)/2; w = x; } return w; } 17. Simplificar al m´ aximo este procedimiento, comentando brevemente todas las simplificaciones realizadas (Nota: N >i>0). void simplProcedimiento(int N, float b, int *i, float *a) { int j,k; float w,v; j = *i; while (j <= N) { v = j; *a = b + (j-i); w = sqrt(((*a)*(*a) + b*b)/2); while ((*a < b) || (j == *i)) { v=w-b; *a = w; *i = *i + 1; } if (v >= 0) { for (k=i; k<=j+1; k++) { a=a+k; *i = j; } } else { for (k=i; k<=j+1; k++) { v=w+b; } } j=j+1; }/*fin del while (j <= N) */ } 17 18. Dado el siguiente algoritmo, que calcula el resto de la divisi´ on entera, ¿cu´ al es su dominio de definici´ on? int resto (int numer, int denom) { /*Pre: ..... */ while (numer >= denom) numer = numer - denom; return numer; /*Post: devuelve el resto de la divisi´ on entera entre numer y denom */ } 19. Se pretende escribir una funci´ on que resuelva la conjetura de los capic´ uas: dado un entero positivo, hay que indicar cu´ antas veces se debe repetir el proceso de sumarlo al valor obtenido al invertir sus d´ ıgitos, antes de obtener un resultado capic´ ua. Indicar cu´ ales son los 4 errores (no sint´ acticos) cometidos al desarrollar la siguiente funci´ on, justificando para cada error el porqu´ e: int conjetura (int num) { /*Pre: num contiene un valor positivo */ int veces,aux,suma=0; veces=0; aux=num; do { /*... hasta llegar a un capicua */ while ((aux/10) > 9) { suma=(suma*10)+(aux %10); aux=aux/10; } suma=(suma*10)+aux; /*suma vale num invertido */ /*si el n´ umero no es capic´ ua, repito */ if (num!=suma) { veces=veces+1; num=num+suma; } }while (num!=suma); /*Post: devuelve el n´ umero de veces que se */ /*repite el proceso */ } 18 Cap´ ıtulo 5: Estructuras de Datos Est´ aticas 1. Definidos int i, aux, n; int v[10]; realizar una traza del siguiente fragmento de c´ odigo: for (i=0; i<n; i=i+2) { aux=v[i]; v[i]=v[i+1]; v[i+1]=aux; } sabiendo que n=10 yv=(6, 2, 5, 1, 4, 5, 6, 3, 7, 6). 2. Definidos int i, n; float v[10]; realizar una traza del siguiente fragmento de c´ odigo: for (i=0; i<(n/2); i=i + 1) { v[i]=v[n-(i+1)]; v[n-(i+1)]=v[i+1]; } sabiendo que n=10 yv=(6.5,2.0,5.1,4.1,7.5,5.0,6.25,3.1,7.8,6.0). 3. Dada la siguiente secuencia de instrucciones: cont=0; suma=0; for (i=0; i<n; i=i+1){ if (v[i]>n1){ if (v[i]<n2){ cont=cont+1; suma=suma+v[i]; } } } se pide lo siguiente: a) Convertir la secuencia anterior en una funci´ on o procedimiento, es decir, darle una cabecera, indicando cu´ al o cu´ ales son los par´ ametros de entrada e indicando cu´ al o cu´ ales son los resultados que devuelve. b) Establecer la precondici´ on, es decir, describir bajo qu´ e condiciones dicha secuencia ser´ a correcta (funciona correctamente y produce alg´ un resultado). c) Establecer la postcondici´ on, es decir, indicar qu´ e calcula. 4. Dado el siguiente fragmento de c´ odigo: 19 blancos = 0; varios = 0; contLetra = 0; i=0; while (cad[i] != ’\0’){ if ((cad[i] == car)||(cad[i] == car-32)){ contLetra = contLetra + 1; } else if (cad[i] == ’ ’){ blancos = blancos + 1; } else { varios = varios + 1; } i = i+1; } porcentaje=contLetra/i; a) Convertir la secuencia anterior en una funci´ on o procedimiento, es decir, indicando qu´ e objetos deber´ ıan ser datos, cu´ ales resultados y cu´ ales variables propias del proceso, darle una cabecera, hacer la declaraci´ on de variables y reescribir el c´ odigo para asegurar que el resultado o resultados se devolver´ an adecuadamente. b) Establecer la postcondici´ on, es decir, indicar qu´ e calcula. c) Establecer la precondici´ on, es decir, describir bajo qu´ e condiciones dicha secuencia ser´ a correcta (funciona correctamente y produce resultados correctos). 5. ¿Verdadero o Falso (justificar)?: “El predicado (i==0 || i==N || v[i]==c) es un invariante del siguiente bucle:” int buscar (float v[], int N, float c) { /*Pre: v=vector d tama˜ no N, c=elem. a buscar*/ int i=0; while (v[i]!=c && i<N) i++; return i; } /*Post: devuelve ´ ındice [0..N-1] de la posi-*/ /*ci´ on de c en v si lo encuentra, o N si no */ 6. Escribe todo lo que se podr´ ıa leer en la pantalla del ordenador al ejecutar el siguiente fragmento de programa, sabiendo que: se han definido estos dos tipos typedef struct { char nombre[N]; float s1, s2, s3; }tSaltador; typedef struct { char nombre[N]; float marca; }tClasificado; Es posible que el siguiente procedimiento tenga instrucciones in´ utiles. Elimina cualquier cosa que te parezca que sobra, justificando cada cambio, de forma que quede una versi´ on lo m´ as simple posible del procedimiento. Y, por supuesto, que siga produciendo el mismo efecto: 20 void chungoChungo(int a[], int n) { /*Pre: n > 0 */ /*Se supone definido el tipo boole */ int i,j,k; boole chivato; i=0; while (i<n){ chivato=falso; j=i+1; while ((j<n)&& !(chivato)){ chivato=chivato&&(a[i]==a[j]); j=j+1; } if (j==n){ a[i]=0; } else { for(k=j;k<n;k=k+1){ a[k]=a[j]+a[i]; a[k]=2*a[i]; } if (a[n]<a[i]){ a[n]=0; } else{ a[i]=i; } } i=i+1; } } el vector ves un vector de TAM=6 elementos de tipo tSaltador, cuyos valores son: nombre “J.Lino” “Fiona” “Yago” “Niurka” “Concha” “Iv´ an” s1 6.75 0 0 6.38 6.69 6.05 s2 7.1 0 7.06 0 0 6.23 s3 7.32 6.37 7.01 0 6.17 7.08 0 1 2 3 4 5 que v2 es un vector, tambi´ en de TAM=6, y con elementos del tipo tClasificado. #include <string.h> #define N 10 #define TAM 6 #define TOPE 6.5 ... /*Las definiciones de tipo */ int main() { int indice,i; float max; tSaltador v[TAM]; tClasificado v2[TAM]; ... /*Se asignan los valores de v */ indice=0; for (i=0; i<TAM; i=i+1) { if ((v[i].s1>=TOPE) || (v[i].s2>=TOPE) || (v[i].s3>=TOPE)) { 21 printf("\n %s se clasifica,", v[i].nombre); strcpy(v2[indice].nombre,v[i].nombre); max=v[i].s1; if (v[i].s2 > max) { max=v[i].s2; printf(" no por el primer salto,"); } if (v[i].s3 > max) { max=v[i].s3; printf(" ni por el segundo."); } v2[indice].marca=max; indice=indice+1; } } printf ("\n\nClasificados: \n"); for (i=0; i<indice; i=i+1) { printf("\t>> %s, con un mejor salto de %5.2f m.\n", v2[i].nombre, v2[i].marca); } } 7. Escribe todo lo que se podr´ ıa leer en la pantalla del ordenador al ejecutar el siguiente fragmento de programa, sabiendo que el vector ves un vector de TAM=6 elementos de tipo tHalterofilia, typedef struct { char nombre[N]; int peso; }tHalterofilia; y que los valores que se asignar´ an a los elementos de vson: nombre “Paco” “Pedro” “Ana” “Alicia” “Pepe” “Luis” peso 40 80 45 70 90 42 0 1 2 3 4 5 int main() { int indice,i; tHalterofilia v[TAM]; ... /*Se asignan los valores de v */ indice=0; printf("\nEl valor de indice es %d",indice); for (i=1; i<TAM; i++) { if (v[i].peso > v[indice].peso) { indice = i; printf("\nEl valor de indice es %d",indice); } } 22 printf("\nGana %s con una marca de %d kilos.\n", v[indice].nombre, v[indice].peso); printf ("\nDiferencias entre participantes: \n"); for (i=0; i<TAM; i++) { if (i!=indice) { printf("\t>> Entre %s y %s, de %d kilos.\n", v[indice].nombre, v[i].nombre, (v[indice].peso-v[i].peso)); } } } 8. Escribir un algoritmo que permita sumar dos vectores de Nelementos. 9. Escribir un algoritmo que calcule la media de los elementos de un vector real de Nelementos. 10. Escribir un algoritmo que permita obtener el producto escalar de dos vectores. 11. Dado un vector de Ncomponentes reales, dise˜ nar un algoritmo que permita obtener su elemento m´ aximo y otro algoritmo que permita obtener su elemento m´ ınimo. 12. Obtener los algoritmos que, para un vector a de Ncomponentes, determinen: a) El recorrido, r = max(a[i]) - min(a[i]), i=1.. N, b) El valor medio de los componentes de a, ˜a, c) La desviaci´ on t´ ıpica, σ=&%n i=1(ai−˜a)2 n d) El coeficiente de variaci´ on, σ ˜a. 13. Alguien ha definido la funci´ on amigos cuyo prototipo es: boole amigos(int n1, int n2); /*pre: n1=N1, n2=N2, enteros positivos */ /*post: devuelve cierto si N1 y N2 son amigos, */ /*falso en caso contrario */ Teniendo en cuenta esta definici´ on (adem´ as de la habitual para el tipo boole), indicar cu´ ales son los 5 errores (no sint´ acticos) cometidos al desarrollar el siguiente procedimiento, justificando para cada error el porqu´ e: void vectorAmigos (int M, int v[]) { /*pre: v es un vector de enteros, de tama˜ no M */ int suma,i,j; for (i=0; i<N; i=i+1) { /*Se calcula en suma el valor */ /*de la suma de divisores de i */ for (j=1; j<(i/2); j=j+1) { if (i %j==0) { suma=suma+i; } 23 } /*El valor almacenado en suma es */ /*el unico candidato a amigo de i */ /*Si lo es, se guarda en v[i] y, */ /*si no, se guarda un cero */ v[i]=(amigos(i,suma))?0:suma; } /*post: v es un vector en el que v[i] es amigo */ /*de i, si i tiene amigos, 0 en caso contrario */ } 14. Dado el siguiente bucle, que trabaja con un vector de Nreales vy un valor real x, .... boole iguales=cierto; int i=0; while ((i<N) && iguales) if (v[i]==x) iguales=falso; else i=i+1; .... ¿es un invariante del bucle el predicado “v[k]=x, para todos los valores de k tales que 0<=k < i”? 15. Dado un vector A de caracteres, escribir un algoritmo que indique si la frase almacenada en dicho vector es o no capic´ ua. Nota: Se considera que los vectores de caracteres poseen un centinela (’\0’) que indica el final de los caracteres v´ alidos del vector. 16. ¿Verdadero o falso? Hay que justificar las respuestas. a) Las siguientes secuencias hacen exactamente lo mismo. /*Secuencia num. 1*/ i=0; enc=falso; while((i<n)&&!(enc)){ enc=(v[i]==x); i=i+1; } /*Secuencia num. 2*/ i=0; enc=falso; while((i<n){ if(!(enc)){ enc=(v[i]==x); } i=i+1; } b) El alumno que escribi´ o la secuencia n´ umero 2, obtuvo mejor nota en ese problema que el alumno que escribi´ o la secuencia n´ umero 1. c) La siguiente versi´ on es mucho mejor que las anteriores. 24 /*Secuencia num. 3*/ i=0; enc=falso; while((i<n){ if(!(enc)){ enc=(v[i]==x); i=i+1; } } 17. Dado un vector Ade tipo base car´ acter y dados dos caracteres car1 ycar2, escribir un algoritmo que busque las ocurrencias de car1 en Ay las sustituya por car2. 18. Dado un vector Ade tipo base car´ acter y dado un car´ acter c, escribir un algoritmo que busque las ocurrencias de cen Ay las elimine. 19. Necesitamos una funci´ on o procedimiento (justificar la elecci´ on) para corregir las may´ usculas de un p´ arrafo, de modo que tanto la letra inicial como todas las primeras letras que aparezcan despu´ es de un punto est´ en en may´ usculas (independientemente de los espacios en blanco que pueda haber entre el punto y la letra). Por ejemplo, la correcci´ on de la siguiente cadena ‘‘El perro ladra. mi madre canta... quisiera verla. Oigo. no veo nada" producir´ ıa ‘‘El perro ladra. Mi madre canta... Quisiera verla. Oigo. No veo nada" a) Implementa una funci´ on o procedimiento auxiliar pasarAMayusculas. Si se le pasa una letra min´ uscula, debe devolver su conversi´ on a may´ uscula. En otro caso, debe devolver el car´ acter sin modificar. Recuerda que puedes pasar un car´ acter cde min´ uscula a may´ uscula con la expresi´ on c-32. b) Utilizando pasarAMayusculas, implementa la funci´ on o procedimiento corrigeMayusculas, que obtenga una versi´ on corregida de una cadena dada. c) Escribir un programa que use corrigeMayusculas para ir corrigiendo cadenas que se ir´ an leyendo de teclado, finalizando el proceso cuando el usuario teclee una cadena vac´ ıa. No olvid´ eis indicar precondiciones y postcondiciones en todos los apartados. 20. Uno de los m´ etodos m´ as simples para comprimir archivos de m´ usica consiste en ir calculando la media aritm´ etica de R valores consecutivos y almacenar el resultado obtenido en otro fichero, tambi´ en de forma consecutiva. As´ ı, se consigue dividir el tama˜ no del fichero original entre R. La idea del problema que os proponemos es similar, pero con vectores. Se dispone de un vector vde Nn´ umeros reales, siendo Nm´ ultiplo de R, ambas constantes. Y se quiere obtener otro vector wde n´ umeros reales, de tama˜ no M=N/R. Por ejemplo, si R=15 y N=150, entonces Mser´ ıa 10. #define R 15 /*Reducci´ on del tama˜ no */ #define N 150 /*Tama˜ no del vector v, m´ ultiplo de R */ #define M 10 /*Tama˜ no del vector w, N/R */ Se pide escribir una funci´ on o procedimiento (hay que justificar la elecci´ on) que, dado el vector v, obtenga el vector w, de modo que cada elemento de wsea la media de 15 elementos consecutivos de v, tal y como muestra el siguiente esquema: 25 El m´ etodo a utilizar para asignar esca˜ nos a los partidos es el siguiente (ley de D’Hont simplificada): Se construye una tabla de NE columnas y NP filas. La primera columna coincide con los resultados en votos obtenidos por cada partido; las sucesivas, columna j con j=1...NE-1, se construyen dividiendo los valores de la primera columna entre (j+1) (divisi´ on entera). Los esca˜ nos se reparten atendiendo a las valores m´ aximos de la tabla: el primer esca˜ no al valor m´ as grande, el segundo al siguiente m´ as grande y as´ ı sucesivamente hasta repartir los NE esca˜ nos. 32