2 Prova de MC102 2ºsemestre de 2013

Prévia do material em texto

MC102 – Algoritmos e Programac¸a˜o de Computadores
2o semestre de 2013 – Turmas Coordenadas
2a Prova (19/11/2013)
Nome:
RA: Turma:
Questa˜o Valor Nota
1 2,5
2 2,5
3 2,5
4 2,5
Total 10,0
Instruc¸o˜es
1. A durac¸a˜o da prova e´ de 100 minutos.
2. Na˜o e´ permitida consulta a qualquer material.
3. Somente sera˜o consideradas respostas nos espac¸os indicados.
4. Use o verso das folhas apenas como rascunho.
5. Celulares, pagers, calculadoras e demais dispositivos eletroˆnicos devem permanecer desligados
durante toda a prova.
6. Nenhum aluno sera´ autorizado a deixar a sala de prova antes que tenham decor-
ridos 60 minutos desde o seu in´ıcio.
7. Todo aluno que deixar a sala de prova devera´ entrega´-la em definitivo.
8. Todos os co´digos devem ser escritos em linguagem C.
9. Nas questo˜es que solicitam que seja completada uma func¸a˜o cujo esboc¸o ja´ e´ fornecido, cada
retaˆngulo em branco devera´ conter uma u´nica expressa˜o, ou enta˜o, um u´nico comando
simples em linguagem C, conforme o contexto.
10. Nas questo˜es onde sa˜o solicitados co´digos em C a clareza do programa sera´ um fator bastante
relevante para a avaliac¸a˜o. Considere fortemente tambe´m a possibilidade de adicionar
comenta´rios ao seu co´digo para que ele fique mais leg´ıvel.
Noite
1. Foi visto na disciplina MC102 que a linguagem C admite diferentes formas de passagem de
paraˆmetros para func¸o˜es.
No programa esboc¸ado abaixo, cada um dos s´ımbolos
%
,
U
,
 
e
P
devem ser substitu´ıdos por
expresso˜es, conforme mostrado a seguir:
%
: “a” ou “&a”
U
: “x” ou “?x”
 
: “b” ou “&b”
P
: “y” ou “?y”
Por exemplo, quando
%
= “a”,
U
= “x”,
 
= “&b” e
P
= “?y”, a linha correspondente a`
chamada da func¸a˜o P no programa principal sera´ P(a,&b). Ja´ o cabec¸alho da func¸a˜o torna-se
P(int x, int *y).
Observe atentamente o co´digo e perceba que a e b sa˜o varia´ves globais. Suponha que o valor lido
para a na entrada seja o u´ltimo d´ıgito do seu RA (i.e., o d´ıgito das unidades). Ale´m disso, suponha
que o valor lido para b na entrada seja o penu´ltimo d´ıgito do seu RA (i.e., o d´ıgito das dezenas).
Preencha o quadro abaixo com os valores de a e b lidos na entrada.
a: b:
Agora, indique na tabela a seguir os resultados que seriam impressos conforme os mecanismos de
passagem de paraˆmetros utilizados. Note que cada entrada da tabela deve conter duas respostas
correspondendo aos valores das varia´veis a e b, respectivamente.
/* programa da questao 1 */
#include <stdio.h>
/* declaracao das variaveis globais */
int a, b;
/* procedimento P */
void P ( int
U
, int
P
) {
U
=
P
* a + b;
P
=
U
* b + a;
}
/* inicio do programa principal */
int main() {
/* ler ultimo e penultimo digitos do RA */
scanf(“%d”, &a);
scanf(“%d”, &b);
/* executar o procedimento P */
P(
%
,
 
);
/* imprime os valores de a e b */
printf(“a: %d b: %d\n”, a, b);
return 0;
}
% U P
a: b:
a x b y
&a ?x b y
a x &b ?y
&a ?x &b ?y
2. Deseja-se implementar uma func¸a˜o em C cujo objetivo e´ determinar se em uma matriz bidimen-
sional existe uma linha e uma coluna indexadas pelo mesmo nu´mero e cuja soma dos seus elementos
e´ ideˆntica. Os paraˆmetros de entrada da func¸a˜o sa˜o, na ordem:
1. a: a matriz (dimensa˜o ma´xima 20× 20);
2. m: o nu´mero de linhas da matriz;
3. n: o nu´mero de colunas da matriz;
4. r: uma varia´vel que retornara´ o ı´ndice I tal que a soma dos elementos da linha I e da coluna
I sa˜o ideˆnticas ou, caso na˜o exista uma linha e coluna com essa propriedade, retornara´ o
valor −1. Existindo mais de uma linha e coluna com a propriedade procurada, r devera´ ter
o menor valor poss´ıvel.
O valor de retorno da func¸a˜o sera´ 1 (UM) caso exista a linha e a coluna, com mesmo ı´ndice,
satisfazendo a` propriedade procurada e 0 (ZERO) caso contra´rio.
Note que os ı´ndices das linhas e colunas comec¸am em 0 (ZERO).
A t´ıtulo de exemplo, considere as duas matrizes 3×4 (m = 3, n = 4) abaixo. Na matriz a` esquerda,
o retorno da func¸a˜o sera´ 0 (ZERO) enquanto a varia´vel r retornara´ o valor −1, uma vez que a soma
dos elementos de uma linha e uma coluna de mesmo ı´ndice sempre sa˜o diferentes (note que neste
caso os ı´ndices sa˜o sempre menores que 3 pois o ı´ndice ma´ximo de uma linha e´ 2). Na matriz a`
direita, o valor de retorno sera´ 1 (UM) e a varia´vel r retornara´ 0 (ZERO) uma vez que a soma da
linha e da coluna de ı´ndice I e´ o mesmo tanto para I = 0 quanto para I = 1.
 2 0 1 21 1 3 0
0 5 0 0

 1 0 0 00 2 0 0
0 0 3 1

Agora, seguindo as instruc¸o˜es contidas na folha de rosto, preencha os retaˆngulos em branco de
modo a completar corretamente o co´digo da func¸a˜o.
Fique atento aos comenta´rios e a` indentac¸a˜o do programa para entender a lo´gica do mesmo.
/* N: se existe um indice I tal que a soma dos elementos tanto da linha quanto da coluna I sao iguais,
retorna 1 com o parametro r igual ao indice I. Caso contrario, retorna 0 com o parametro r igual
a −1. */
int N(int a[20][20], int m, int n, int *r) {
/* variaveis locais */
int i, k, mindim=m; /* mindim: menor dimensao da matriz */
int somalin, somacol; /* soma dos elementos na linha e na coluna, respectivamente */
/* encontra a menor dimensao da matriz */
if (mindim > n) mindim = n;
/* verifica se existe linha e coluna de mesmo indice com a mesma soma de elementos */
for (i = 0 ; i < ; i++) {
somalin = 0;
/* calcula soma na linha */
for(k = 0 ; k < m ; k++) ;
somacol = 0;
/* calcula soma na coluna */
for(k = 0 ; k < n ; k++) ;
if ( ) {
;
return 1;
}
} /* fim do for externo */
;
return 0;
} /* fim da funcao N */
3. Suponha que para ter acesso a um determinado sistema, um usua´rio deve cadastrar uma senha.
Por razo˜es de seguranc¸a, para uma senha ser aceita, e´ necessa´rio que ela satisfac¸a a`s seguintes
regras:
1. a senha deve ser uma cadeia de caracteres contendo no mı´nimo 8 e no ma´ximo 10 caracteres.
2. a senha so´ deve conter letras, que podem ser tanto minu´sculas quanto maiu´sculas, e d´ıgitos
de 0 (ZERO) a 9.
3. a quantidade de d´ıgitos presentes na senha deve ser no mı´nimo 3 e no ma´ximo de 5.
4. a senha deve conter pelo menos 3 letras maiu´sculas.
5. as letras maiu´sculas na˜o podem ocorrer todas em posic¸o˜es consecutivas na senha (ou seja,
pelo menos entre duas letras maiu´sculas deve existir um ou mais d´ıgitos ou letras minu´sculas).
O programa mostrado na pro´xima pa´gina ja´ implementa as regras de 1 a 4. Leia atentamente
este co´digo, dando especial atenc¸a˜o aos comenta´rios pois eles ajudam bastante no entendimento da
lo´gica do programa.
Observe que o programa se utiliza das informac¸o˜es da tabela ASCII para a codificac¸a˜o de caracteres.
Caso voceˆ julgue conveniente, fac¸a uso da tabela ASCII mostrada na u´ltima folha da prova. A tabela
esta´ dividida em 4 grupos de 3 colunas. O caracter da coluna char em um deste grupos e´ codificado
pelo decimal correspondente na coluna dec. Por exemplo, a letra “L” (maiu´scula) e´ codificada pelo
decimal 76.
Use o espac¸o da pa´gina que se segue ao programa para escrever um co´digo em C que implemente a
func¸a˜o UltimaRegra que verifica a regra 5 descrita acima.
#include<stdio.h>
int UltimaRegra(char s[],int tam); /* prototipo da funcao a ser codificada */
int main() {
char senha[11]; int tam=0, i;
/* quantidade de digitos, letras maiusculas e minusculas, respectivamente */
int qd=0, qm=0, qM=0;
scanf("%s",senha); /* le a senha com pelo menos um caractere */
while (senha[tam] != ’\0’) tam++; /* calcula tamanho da senha */
if ( (tam < 8) || (tam > 10) ) { /* testa Regra 1 */
printf("tamanho da senha invalido (%d)\n",tam);
return 1;
}
/* conta quantidade de digitos, letras maiusculas e minusculas */
for (i=0; i<tam;i++) {
/* digitos de 0 a 9 ===> 48 <= codigo ASCII <= 57 */
if ( (senha[i]>47) && (senha[i]<58) ) qd++;
/* letra maiuscula ===> 65 <= codigo ASCII <= 90 */
if ( (senha[i]>64) && (senha[i]<91) ) qM++;
/* letra minuscula ===> 97 <= codigo ASCII <= 122 */
if ( (senha[i]>96) && (senha[i]<123) ) qm++;
}
if ( qM+qm+qd < tam ) { /* testa Regra 2 */
printf("senha contem caracteres invalidos (%d)\n",tam-qM-qd-qm);
return 2;
}
if ( (qd<3) || (qd>5) ) { /*testa Regra 3 */
printf("quantidade de numeros invalida (%d)\n",qd);
return 3;
}
if ( qM < 3 ) { /* testa Regra 4 */
printf("quantidade de letras maiusculas invalida (%d)\n",qM);
return 4;
}
if (!UltimaRegra(senha,tam)) { /* testa Ultima Regra */
printf("Ultima Regra nao satisfeita.\n");
return 5;
}
printf("senha valida (%s)\n",senha);
return 0;
}
Escreva abaixo o co´digo da func¸a˜o da questa˜o 3.
int UltimaRegra(char s[],int tam) {
} /* FIM DA FUNCAO */
4. Escreva o co´digo da func¸a˜o QPrimos cujo cabec¸alho e´ dado o qual, recebendo como paraˆmetro
de entrada um nu´mero inteiro n no intervalo (fechado) [0, 2147483647], retorna a quantidade de
d´ıgitos em n que sa˜o nu´meros primos (nota: um nu´mero inteiro d e´ primo se ele for maior ou
igual a 2 e os seus u´nicos divisores sa˜o 1 e o pro´prio d).
Exemplo: se n = 1220305, QPrimos deve retornar 4.
Importante: a sua func¸a˜o deve usar recursividade, caso contra´rio sua resposta sera´ considerada
errada.
int QPrimos(int n) { /* USE RECURSAO ! */
} /* FIM DA FUNCAO QPrimos */