Examen Final Junio 2013 (2013)

Examen Español
Universidad Universidad Politécnica de Cataluña (UPC)
Grado Ingeniería de Sistemas de Telecomunicación - 1º curso
Asignatura Fonamentos de Ordenadores
Año del apunte 2013
Páginas 11
Fecha de subida 16/09/2014
Descargas 0
Subido por

Vista previa del texto

Fonaments d’Ordinadors 26 de junio de 2013 Notas provisionales: 30/06/13 a partir de las 15:00 Límite alegaciones: 01/07/13 a partir de las 8:00 hasta Departament d’Arquitectura de Computadors las 16:00 Notas definitivas: 02/07/13 a partir de las 17:00 Profesores: M. Gil, A. Heredero, M. Jiménez, M. Macias, M. Moreto, T. Monreal, J.L. Pérez, B. Otero, X. Valverde.
• • • • Duración del examen: 175 min + 5 min para repartir el examen (3h) Contestar los problemas 1, 2 y 3 en hojas de examen separadas Se puede consultar únicamente la documentación entregada en el examen No se puede utilizar ningún dispositivo electrónico durante la realización del examen Problema 1 (2.5 punts, 40 minuts) Volem escriure un programa en C per calcular la intensitat que proporciona la font d’alimentació d’un circuit format per 2n resistències, com el mostrat a continuació. Per aconseguir-ho, es calcularà la resistència equivalent del circuit i s’aplicarà la llei d’Ohm.
El circuit conté una font de tensió connectada a una cadena de 2n resistències en sèrieparal—lel. Les resistències senars estan connectades en sèrie amb el circuit equivalent que formen les resistències amb un nombre superior (e.g. la resistència 1 està connectada en sèrie amb les resistències 2, 3, 4, ..., 2n). En canvi, les resistències parell estan connectades en paral—lel amb el circuit equivalent que formen les resistències amb un nombre superior (e.g. la resistència 2 està connectada en paral—lel amb les resistències 3, 4, 5, ..., 2n).
a) (0.5 punts) Defineix un tipus estructurat de nom tcircuit que guardi la descripció d’un circuit: Voltatge, Número de resistències, i el valor de les resistències. Has de definir un número màxim de resistències que podrà guardar el circuit (MAX_RESIST).
b) (1.0 punt) Escriu un programa en C que llegeixi de teclat la descripció d’un circuit com l’especificat anteriorment. El programa demanarà primer la tensió del circuit en Volts. A continuació, s’ha d’introduir el número de resistències del circuit que hauria de ser parell. El programa ha de comprovar si aquest número és correcte i, en cas contrari, tornar a demanar el número de resistències del circuit. Finalment, llegirà els valors de les resistències del circuit en Ohms.
Exemples d’execució (En negreta les dades introduïdes per l’usuari): Exemple 1 Exemple 2 Introdueix la tensio del circuit (V): 5.5 Introdueix la tensio del circuit (V): 2.5 Introdueix el numero de resistencies: 4 Introdueix el numero de resistencies: -3 Introdueix la resistencia 1 (Ohms): 125.0 Numero erroni.
Introdueix la resistencia 2 (Ohms): 25.0 Introdueix el numero de resistencies: 3 Introdueix la resistencia 3 (Ohms): 35.0 Numero erroni.
Introdueix la resistencia 4 (Ohms): 125.0 Introdueix el numero de resistencies: 2 Introdueix la resistencia 1 (Ohms): 125.0 Introdueix la resistencia 2 (Ohms): 25.0 1 c) (1.0 punt) A continuació, s’ha de calcular la resistència equivalent d’aquest circuit expressada en Ohms, així com la intensitat de corrent que subministra la font de tensió expressada en mA. Declara les noves variables que es necessiten i, després, escriu el tros de codi que aniria al final del codi anterior. Pots utilitzar les fórmules següents: • Resistència equivalent de dues resistències en sèrie: Req = Ra + Rb • Resistència equivalent de dues resistències en paral—lel: Req = (Ra x Rb) / (Ra + Rb) • Llei d’Ohm: V = R x I Exemple d’execució - Si l’usuari ha introduït el següent circuit: V=5.5V, N=4, R1=125Ω, R2=25Ω, R3= 35Ω, R4=125Ω La resistència equivalent val: 146.6 Ohms La intensitat que proporciona la font de tensió val: 37.51 mA - Si l’usuari ha introduït el següent circuit: V=2.0V, N=6, R1=100.0Ω, R2=200.0Ω, R3= 50.0Ω, R4=300.0Ω, R5=200.0Ω, R6=100.0Ω.
La resistencia equivalent val: 200.0 Ohms La intensitat que proporciona la font de tensio val: 10.00 mA Problema 2 (4.0 puntos, 75 minutos) Dos novios que se casan están organizando su boda y necesitan conocer algunos detalles tales como: la cantidad de dinero que han recaudado con los regalos que han realizado los invitados, quiénes son los invitados que más dinero han aportado, cuántos invitados vendrán finalmente a la boda, y si el dinero recaudado es suficiente para pagar todos los gastos del restaurante. Para determinar todo esto, se quiere realizar un programa informático con los siguientes tipos de datos y variables inicializadas: #include <stdio.h> #define MAX_CAR 25 #define MAX_INV 150 typedef struct { char nomb[MAX_CAR]; int edad; int asiste; float dinero_regalo; /* /* /* /* Nombre del invitado */ Edad del invitado */ 1 si asiste a la boda, 0 si no viene */ 0.0 si no hace regalo, cualquier otro valor >0.0 es el importe del regalo */ } tinvitado; 2 typedef struct { int num; tinvitado comensales[MAX_INV]; } tlista_inv; /* Numero de invitados a la boda */ /* Lista de invitados a la boda */ main() { tlista_inv lis={5,{{"Maria Moreno", 38, 1, 250.0},{"Enrique Garcia", 5, 1, 120.0},{"Daniel Cayer", 42, 0, 100.0},{"Luisa Delgado", 22, 0, 250.0},{"Luis Rojas", 34, 1, 100.0}}}; } El tipo de dato tlista_inv permite almacenar una lista de invitados. El campo num indica cuántos invitados hay almacenados en el campo comensales. Este campo es una lista cuyos elementos son de tipo tinvitado y almacenan la información de cada invitado (nombre, edad, si asiste o no a la boda y el importe del regalo).
Considerando la inicialización de la variable lis en el main, los invitados de la boda son: Maria Moreno, Enrique Garcia, Daniel Cayer, Luisa Delgado y Luis Rojas. El campo comensales de la variable lis contiene la información de cada uno de los 5 invitados.
Utilizando los tipos de datos anteriores y la variable lis se quiere implementar un programa para conocer: -) ¿Quién o quiénes fueron los invitados que más dinero aportaron? -) ¿Cuál es la recaudación total de dinero aportada por todos los invitados? -) ¿Cuántos invitados vendrán a la boda? ¿Cuántos son adultos y cuántos de ellos son menores de edad? -) ¿Cuál es el importe a pagar en el restaurante por los menús de los invitados que asisten a la boda? -) ¿Cuál es la lista final de invitados que asistirán al restaurante? Para hacer el programa anterior suponga que ya se ha implementado la siguiente función (Ud. no debe implementarla de nuevo): (0.0 pto) void mostrar_invitado(tinvitado inv) Esta función muestra por pantalla la información del invitado inv considerando el siguiente formato: nombre: edad : asiste: dinero Ejemplo: Maria Moreno: 38 : 1 : 250.00 Se pide implementar las siguientes funciones y el programa principal: a) (0.25 ptos) void mostrar_lista(tlista_inv lista); Esta función muestra por pantalla la información de todos los invitados de lista.
Nota: Utilice la función void mostrar_invitado(tinvitado inv).
Ejemplo (considerando la inicialización de la variable lis): Maria Moreno: 38 : 1 : 250.00 Enrique Garcia: 5 : 1 : 120.00 Daniel Cayer: 42 : 0 :100.00 Luisa Delgado: 22 : 0 : 250.00 Luis Rojas: 34 : 1 : 100.00 b) (0.75 ptos) float dinero_recaudado_invitado_generoso(tlista_inv lista); Esta función retorna el importe total del dinero aportado en regalos por todos los invitados de la lista (inclusive el de aquellos invitados que no vienen a la boda). Además, la función muestra por pantalla la información de los invitados (puede haber más de uno) que han aportado más dinero al regalo de bodas.
Nota: Utilice la función void mostrar_invitado(tinvitado inv).
Ejemplo (considerando la inicialización de la variable lis): La función mostraría por pantalla la siguiente información: 3 Invitado(s) mas generoso(s) con el regalo de la boda: Maria Moreno: 38 : 1 : 250.00 Luisa Delgado: 22 : 0 : 250.00 Además, la función retorna el valor de 820.00 como dinero recaudado.
c) (0.5 ptos) void eliminar_invitado(int pos, tlista_inv *lista); Esta función elimina de la lista apuntada por el parámetro lista el invitado de la posición pos.
Nota: Suponga que el parámetro pos siempre contiene un valor válido.
Ejemplo (considerando la inicialización de la variable lis anterior y pos = 0): Después de ejecutar esta función la lista apuntada por el parámetro lista tiene 4 invitados, ya que se elimina a Maria Moreno (primer invitado de la lista). El campo comensales del parámetro lista tiene ahora la siguiente información: Enrique Garcia: 5 : 1 : 120.00 Daniel Cayer: 42 : 0 :100.00 Luisa Delgado: 22 : 0 : 250.00 Luis Rojas: 34 : 1 : 100.00 d) (1.0 pto) int eliminar_invitados_no_asisten(int *adultos, tlista_inv *lista); Esta función elimina de la lista apuntada por el parámetro lista todos los invitados que no asisten a la boda. La función retorna la cantidad de invitados que han sido eliminados e indica en el parámetro adultos la cantidad de adultos que asistirán a la boda.
Notas: Suponga que un adulto es aquel que ha cumplido 18 años.
Utilice la función void eliminar_invitado(int pos, tlista_inv *lista).
Ejemplo (considerando la inicialización de la variable lis anterior): Después de ejecutar esta función la lista apuntada por el parámetro lista tiene 3 invitados (los que solo asisten a la boda): Maria Moreno: 38 : 1 : 250.00 Enrique Garcia: 5 : 1 : 120.00 Luis Rojas: 34 : 1 : 100.00 La función retorna el valor 2, ya que se eliminan dos invitados que no asisten a la boda.
Además, la función devuelve a través del parámetro adultos la cantidad de adultos que vienen a la boda, que en este caso también es 2 (Maria Moreno y Luis Rojas).
e) (1.5 ptos) Escriba el programa principal para que dada la lista de invitados muestre por pantalla: • La información de los invitados que más dinero han aportado y el monto total del dinero recaudado.
• La cantidad total de invitados que vienen a la boda, especificando cuántos de ellos son adultos y cuántos de ellos menores de 18 años.
• El monto total del dinero a pagar en el restaurante, suponiendo que el menú de adultos cuesta 120.0€ y el menú para menores de 18 años cuesta 60.0€. No se olvide de incluir a los novios, que también pagan menú. Además, el programa debe indicar si los novios tienen que aportar dinero para pagar los gastos del restaurante. Si es necesario que los novios contribuyan con dinero, el programa deberá indicar el monto de dinero a aportar. Si los novios no tienen que poner dinero el programa debe mostrar un mensaje por pantalla indicándolo junto con el monto del dinero que sobra.
• La lista de invitados que asistirán a la boda.
Nota: Utilice todas las funciones anteriores.
Ejemplo de ejecución: Suponiendo la inicialización anterior de la variable lis, el programa mostrará por pantalla los siguientes mensajes: Invitado(s) mas generoso(s) con el regalo de la boda: Maria Moreno: 38 : 1 : 250.00 Luisa Delgado: 22 : 0 : 250.00 El dinero recaudado en regalos es: 820.00 4 A la boda vendran 3 invitados de un total de 5.
Adultos: 2 y Menores de 18: 1 El restaurante cuesta: 540.00 Los novios no tienen que poner dinero. Sobra 280.00 Invitado(s) que vendra(n) a la boda: Maria Moreno: 38 : 1 : 250.00 Enrique Garcia: 5 : 1 : 120.00 Luis Rojas: 34 : 1 : 100.00 Problema 3 (3.5 puntos, 60 minutos) Tenemos el siguiente código en C que ordena un vector de valores enteros por el algoritmo de la Burbuja. Queremos traducir completamente este código en C a código ensamblador IA32: // bubble.c 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 #define N 10 main() { int v[N]; short i; short j; int aux; // inicializar v[N]={5,235,61,315,134,221,53,145,117,5}; for(i=N-1; i>0; i--) { for(j=0; j<i; j++) { if(v[j] > v[j+1]) { aux=v[j]; v[j]=v[j+1]; v[j+1]=aux; } } } // vector ordenado v[N]={5,5,53,61,117,134,145,221,235,315}; } Responde a las siguientes preguntas. Las líneas del código indicadas en a), b), c), d) y e) se refieren al código de bubble.c: a) (0.2 ptos) Traduce a ensamblador IA32 las líneas del código 1, 5, 6 y 8 (definición de constantes y declaración de variables sin inicializar).
b) (0.3 ptos) Traduce a ensamblador IA32 las líneas del código 12, 13 y 23 (primer bucle for, sin las instrucciones de su cuerpo).
c) (0.3 ptos) Traduce a ensamblador IA32 las líneas del código 14, 15 y 22 (segundo bucle for, sin la instrucción condicional if ni las instrucciones de su cuerpo). Asume aquí y a partir de aquí que la variable j se almacena en el registro %si d) (0.75 ptos) Traduce a ensamblador IA32 las líneas del código 16, 17 y 21 (instrucción condicional if).
e) (0.75 ptos) Traduce a ensamblador IA32 las líneas del código 18, 19 y 20 (cuerpo del if).
Ahora vamos a modificar el código anterior para que una función realice el segundo bucle for, la instrucción condicional if y las instrucciones de su cuerpo. La función recibe i como primer parámetro por valor y la dirección donde comienza el vector v como segundo parámetro por referencia. La función no devuelve nada a través del return. La cabecera de la función es: void mover(short i, int v[]); 5 El nuevo código en C que usa la función mover para ordenar un vector de valores enteros por el algoritmo de la Burbuja es el siguiente: // fbubble.c 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 #define N 10 void mover(short i, int v[]) { short j; int aux; for(j=0; j<i; j++) { if(v[j] > v[j+1]) { aux=v[j]; v[j]=v[j+1]; v[j+1]=aux; } } } main() { int v[N]; short i; for(i=N-1; i>0; i--) { mover(i, &v[0]); } } Responde a las siguientes preguntas. Las líneas del código indicadas en f), g) y h) se refieren ahora al código de fbubble.c: f) (0.2 ptos) Traduce a ensamblador IA32 la línea del código 26. Asume que la declaración de las variables sin inicializar v e i es la de a) (las líneas 21 y 22 de fbubble.c son igual a las líneas 5 y 6 de bubble.c) g) (0.25 ptos) Dibuja el estado de la pila (bloque de activación) durante la ejecución de la subrutina mover. Indica claramente dónde apuntan los registros %esp y %ebp. Suponer que sólo la variable local aux está en la pila. Indica claramente los desplazamientos respecto al %ebp de los parámetros y la variable local aux.
h) Completa el siguiente código en ensamblador IA32 que corresponde al código completo de la subrutina mover (líneas 8-16 de fbubble.c) mover: pushl %ebp movl %esp, %ebp subl $4, %esp # completa aquí lo indicado en h.1, h.2 y h.3 addl $4, %esp popl %ebp ret h.1) (0.3 ptos) Traduce a ensamblador IA32 las líneas del código 8, 9 y 16 (bucle for sin las instrucciones de su cuerpo). Asume aquí y a partir de aquí que la variable local j se almacena en el registro %si h.2) (0.15 ptos) Traduce a ensamblador IA32 las líneas del código 10, 11 y 15 (instrucción condicional if).
h.3) (0.3 ptos) Traduce a ensamblador IA32 las líneas del código 12, 13 y 14 (cuerpo del if).
6 Solución Problema 1 (2.5 punts, 40 minuts) #include <stdio.h> /* Apartat 1.a */ #define MAX_RESIST 50 typedef struct { float v; int num_R; float val_R[MAX_RESIST]; } tcircuit; main() { /* Apartat 1.b */ tcircuit circ; int i; float req=0; printf("Introdueix la tensio del circuit (V): "); scanf("%f",&circ.v); printf("Introdueix el numero de resistencies: "); scanf("%d",&circ.num_R); while (circ.num_R<1 || circ.num_R>MAX_RESIST || circ.num_R%2!=0) { printf("Numero erroni.\n”); printf("Introdueix el numero de resistencies: "); scanf("%d",&circ.num_R); } for (i=0;i<circ.num_R;i++) { printf("Introdueix la resistencia %d: ", i+1); scanf("%f", &circ.val_R[i]); } /* Apartat 1.c */ req=circ.val_R[circ.num_R-1]; for (i=circ.num_R-2;i>0;i-=2) { req=req+circ.val_R[i]; req=req*circ.val_R[i-1]/(req+circ.val_R[i-1]); } req=req+circ.val_R[0]; printf("La resistencia equivalent val: %.1f Ohms\n", req); printf("La intensitat que proporciona la font de tensio val: %.2f mA\n", 1000.0*circ.v/req); } Problema 2 (4.0 puntos, 75 minutos) #include <stdio.h> #define MAX_CAR 25 #define MAX_INV 150 typedef struct { char nomb[MAX_CAR]; int edad; int asiste; float dinero_regalo; /* 1 si asiste, 0 no viene */ /* 0.0 si no hace regalo, cualquier otro valor >0.0 es el importe del regalo */ } tinvitado; 7 typedef struct { int num; tinvitado comensales[MAX_INV]; } tlista_inv; void mostrar_cadena(char cad[MAX_CAR]); void mostrar_invitado(tinvitado inv); void mostrar_lista(tlista_inv lista); float dinero_recaudado_invitado_generoso(tlista_inv lista); void eliminar_invitado(int pos, tlista_inv *lista); int eliminar_invitados_no_asisten(int *adultos, tlista_inv *lista); /* Apartado e */ main() { int menus, eli, adul, pos; float dinero, restaurant, aux; tlista_inv lis={5,{{"Maria Moreno", 38, 1, 250.0},{"Enrique Garcia", 5, 1, 120.0},{"Daniel Cayer", 42, 0, 100.0},{"Luisa Delgado", 22, 0, 250.0},{"Luis Rojas", 34, 1, 100.0}}}; dinero = dinero_recaudado_invitado_generoso(lis); printf("\nEl dinero recaudado en regalos es: %.2f\n", dinero); eli = eliminar_invitados_no_asisten(&adul, &lis); printf("\n\nA la boda vendran %d invitados de un total de %d\n", lis.num,lis.num+eli); printf("\nAdultos: %d y Menores de 18: %d\n\n", adul,(lis.num)-adul); restaurant = (adul+2)*120.0 + (lis.num-adul)*60.0; printf("El restaurante cuesta: %.2f\n", restaurant); aux = dinero-restaurant; if (aux>=0) printf("\nLos novios no tienen que poner dinero. Sobra %.2f\n", aux); else printf("\n Los novios tienen que poner %.2f\n", (-1)*aux); printf("\nInvitado(s) que vendra(n) al restaurante:\n"); mostrar_lista(lis); } void mostrar_cadena(char cad[MAX_CAR]) { int i = 0; while(i < MAX_CAR && cad[i] != '\0' ) { printf ("%c", cad[i]); i++; } } void mostrar_invitado(tinvitado inv) { mostrar_cadena(inv.nomb); printf(": %d : %d : %.2f\n", inv.edad, inv.asiste, inv.dinero_regalo); } 8 /* Apartado a */ void mostrar_lista(tlista_inv lista) { int i; for(i=0; i< lista.num; i++) mostrar_invitado(lista.comensales[i]); } /* Apartado b */ float dinero_recaudado_invitado_generoso(tlista_inv lista) { int i, pos=0; float dinero_regalos, max_reg = 0.0; dinero_regalos = 0.0; for(i=0; i<lista.num;i++) { if (lista.comensales[i].dinero_regalo > max_reg) { max_reg = lista.comensales[i].dinero_regalo; pos = i; } dinero_regalos = dinero_regalos + lista.comensales[i].dinero_regalo; } printf("\nInvitado(s) mas generoso(s) con el regalo de la boda: \n"); for(i=pos; i<lista.num; i++) { /* Donde 0.001 es el ERROR de aproximación al comparar reales */ if((lista.comensales[i].dinero_regalo + 0.001 >= max_reg) && (lista.comensales[i].dinero_regalo - 0.001 <= max_reg)) mostrar_invitado(lista.comensales[i]); } return (dinero_regalos); } /* Apartado c */ void eliminar_invitado(int pos, tlista_inv *lista) { int i; for(i=pos; i<lista->num-1; i++) lista->comensales[i] = lista->comensales[i+1]; lista->num--; } /* Apartado d */ int eliminar_invitados_no_asisten(int *adultos, tlista_inv *lista) { int i, eliminados=0; (*adultos) = 0; for(i=0;i<lista->num;i++) { if((lista->comensales[i].asiste==1) && (lista->comensales[i].edad>=18)) (*adultos)++; else if (lista->comensales[i].asiste==0) { eliminar_invitado(i, lista); eliminados++; i--; } } return (eliminados); } 9 Problema 3 (3.5 puntos, 60 minutos) a) (0.2 ptos) N=10 .comm v,N*4,4 .comm i,2,2 .comm aux,4,4 b) (0.3 ptos) fori: movw $N, i subw $1, i cmpw $0, i jle finfori ...
decw i jmp fori # i=N-1; también: movw $N-1, i # i>0 # líneas: 14-22 # i-- finfori: # aquí es el final del programa c) (0.3 ptos) forj: movw $0, %si cmpw i, %si jge finforj ...
incw %si jmp forj # j=0; # j<i # líneas: 16-21 # j++ finforj: # también finforj: decw i de b) d) (0.75 ptos) if: movl $v, %edi movswl %si, %esi movl (%edi,%esi,4), %ebx cmpl 4(%edi,%esi,4), %ebx jle finif ...
# %edi=&v[0] # j en %esi # %ebx=v[j] # v[j] > v[j+1] # líneas: 18-20 # también finif: finif: incw %si de c) e) (0.75 ptos) movl movl movl movl movl %ebx, aux 4(%edi,%esi,4), %ebx %ebx, (%edi,%esi,4) aux, %edx %edx, 4(%edi,%esi,4) # aux=v[j] # v[j]=v[j+1] # v[j+1]=aux f) (0.2 ptos) pushl $v pushl i call mover addl $8, %esp # paso de parámetros (2) # eliminar parámetros (12) g) (0.25 ptos) %esp, %ebp - 4 aux %ebp %ebp @retorno i %ebp + 8 %ebp + 12 @vector 10 h.1) (0.3 ptos) forj: # # # # # # # movw $0, %si cmpw 8(%ebp), %si jge finforj ...
incw %si jmp forj j en %si igual que en c) i es ahora 8(%ebp) igual que en c) líneas: 10-15 igual que en c) igual que en c) finforj: h.2) (0.15 ptos) if: movl 12(%ebp), %edi movswl %si, %esi movl (%edi,%esi,4), %ebx cmpl 4(%edi,%esi,4), %ebx jle finif ...
# &v[0] es ahora 12(%ebp) # igual que en d) # igual que en d) movl movl movl movl movl # aux es ahora -4(%ebp) # igual que en d) # líneas: 12-14 # igual que en d) finif: h.3) (0.3 ptos) %ebx, -4(%ebp) 4(%edi,%esi,4), %ebx %ebx, (%edi,%esi,4) -4(%ebp), %edx %edx, 4(%edi,%esi,4) # igual que en e) # aux es ahora -4(%ebp) # igual que en e) 11 ...