Introdução à Programação - Poli - P1 - em C - 2005

Prévia do material em texto

Departamento de Ciência da Computação - IME - USP
MAC2166 Introdução à Computação
Prova 1
QUESTÃO 1
 Simule a execução do programa abaixo, destacando a saída do programa. A saída do programa é tudo que
aparece na tela durante a execução do programa.
#include <stdio.h>
int main(){
 int nusp, n, i, j, soma, cont;
 printf ("Entre com seu no. USP: ");
 scanf ("%d", &nusp); /* nesta linha use o seu numero USP */
 printf ("nusp = %d\n", nusp);
 n = 3 + nusp%3;
 printf("0: n = %d\n", n);
 if (n < 3)
 n = n + 3;
 if (n%2 == 0)
 i = (2*n + 1)/2; 
 else 
 if (n%3 == 0)
 i = (3*n)/2;
 else 
 i = (n + 4)/2;
 printf("1: i = %d\n", i);
 if (i > 5)
 i = i - 2;
 j = 2*i + n;
 printf("2: n = %d, i = %d, j = %d\n", n, i, j);
 
 cont = i;
 while (cont > 1 && j > 0) {
 soma = n;
 if (j > 8 || i%2 == 0) {
 soma = soma + i;
 j = j - 5;
 i = i + 1;
 printf("3: i = %d, j = %d, soma = %d\n", i, j, soma);
 }
 else {
 soma = soma + j;
 i = i - 1;
 j = j + 2;
 printf("4: i = %d, j = %d, soma = %d\n", i, j, soma);
 }
 cont = cont - 1;
 }
 /* O ultimo valor a ser impresso e' o da variavel cont */
 printf("5: i = %d, j = %d, cont = %d\n", i, j, cont);
 return 0;
}
SOLUÇÃO
A resposta depende do resto da divisão do seu número USP por 3. Teste com o seu no. USP e compare a
resposta.
(0) nusp%3 == 0. Veja os 2 exemplos abaixo.
 Entre com seu no. USP: 1234560
 nusp = 1234560
 0: n = 3
 1: i = 4
 2: n = 3, i = 4, j = 11
 3: i = 5, j = 6, soma = 7
 4: i = 4, j = 8, soma = 9
 3: i = 5, j = 3, soma = 7
 5: i = 5, j = 3, cont = 1
 Entre com seu no. USP: 0
 nusp = 0
 0: n = 3
 1: i = 4
 2: n = 3, i = 4, j = 11
 3: i = 5, j = 6, soma = 7
 4: i = 4, j = 8, soma = 9
 3: i = 5, j = 3, soma = 7
 5: i = 5, j = 3, cont = 1
(1) nusp%3 == 1. Veja os 2 exemplos abaixo.
 Entre com seu no. USP: 1234561
 nusp = 1234561
 0: n = 4
 1: i = 4
 2: n = 4, i = 4, j = 12
 3: i = 5, j = 7, soma = 8
 4: i = 4, j = 9, soma = 11
 3: i = 5, j = 4, soma = 8
 5: i = 5, j = 4, cont = 1
 Entre com seu no. USP: 1
 nusp = 1
 0: n = 4
 1: i = 4
 2: n = 4, i = 4, j = 12
 3: i = 5, j = 7, soma = 8
 4: i = 4, j = 9, soma = 11
 3: i = 5, j = 4, soma = 8
 5: i = 5, j = 4, cont = 1
(2) nusp%3 == 2. Veja os 2 exemplos abaixo.
 Entre com seu no. USP: 1234562
 nusp = 1234562
 0: n = 5
 1: i = 4
 2: n = 5, i = 4, j = 13
 3: i = 5, j = 8, soma = 9
 4: i = 4, j = 10, soma = 13
 3: i = 5, j = 5, soma = 9
 5: i = 5, j = 5, cont = 1
 Entre com seu no. USP: 2
 nusp = 2
 0: n = 5
 1: i = 4
 2: n = 5, i = 4, j = 13
 3: i = 5, j = 8, soma = 9
 4: i = 4, j = 10, soma = 13
 3: i = 5, j = 5, soma = 9
 5: i = 5, j = 5, cont = 1
QUESTÃO 2
 Escreva um programa em C que lê dois números inteiros p e q, p > 0 e q > 0, e imprime se p é um subnúmero
de q.
[Um número
p = pn*10n + pn-1*10n-1 + . . . + p1*101 + p0,
onde, para cada i, 0 <= i < n, vale que 0 < pi < 9, é subnúmero de um número
q = qm*10m+ qm-1*10m-1 + . . . + q1*101 + q0,
onde, para cada i, 0 <= i <= m, vale que 0 <= qi <= 9, se existe um número inteiro j, 0 <= j <= m-n, tal que qj+i = pi para i=0,1,
. . . ,n.]
Por exemplo:
se p = 5, q = 5, então p é subnúmero de q;
se p = 23, q = 1453157238, então p é subnúmero de q;
se p = 253, q = 258347543, então p não é subnúmero de q;
se p = 50, q = 5, então p não é subnúmero de q;
se p = 11, q = 10101, então p não é subnúmero de q.
Exemplos de 6 execuções do programa:
 Digite p e q: 5 5 Digite p e q: 23 258347
 5 e' subnumero de 5 23 nao e' subnumero de 258347
 Digite p e q: 23 1453157238 Digite p e q: 50 5
 23 e' subnumero de 1453157238 50 nao e' subnumero de 5
 Digite p e q: 253 258347543 Digite p e q: 11 10101 
 253 nao e' subnumero de 258347543 11 nao e' subnumero de 10101
SOLUÇÃO
/*
 * Solucao 1: Solucao curta e simples.
 */
#include <stdio.h>
#define TRUE 1
#define FALSE 0
int main() 
{
 int p, q; /* dados do problema */
 int pot10; /* guardara a menor potencia de 10 maior que p */
 int qaux; /* variavel auxiliar; usada para `descascar' q */
 int subnumero; /* guarda um subnumero de q */
 int achou; /* indica se achou em q um subnumero igual a p */
 /* 0. leia os dados */
 printf("Digite p e q: ");
 scanf("%d %d", &p, &q);
 /* 1. determine a menor potencia de 10 maior que p */
 pot10 = 1;
 while (pot10 <= p) 
 {
 pot10 = pot10 * 10;
 }
 /* 2. verifique se algum subnumero de q e igual a p */
 achou = FALSE;
 qaux = q;
 while (qaux >= p && achou == FALSE) 
 {
 subnumero = qaux%pot10;
 qaux = qaux/10;
 if (subnumero == p)
 {
 achou = TRUE;
 }
 }
 
 if (achou == TRUE)
 { 
 printf("%d e' subnumero de %d\n", p, q);
 }
 else 
 {
 printf("%d nao e' subnumero de %d\n", p, q);
 }
 return 0;
}
/*
 * Solucao 2: identica a solucao 1 sem chaves superfluas.
 */
#include <stdio.h>
#define TRUE 1
#define FALSE 0
int main() 
{
 int p, q; /* dados do problema */
 int pot10; /* guardara a menor potencia de 10 maior que p */
 int qaux; /* variavel auxiliar; usada para `descascar' q */
 int subnumero; /* guarda um subnumero de q */
 int achou; /* indica se achou em q um subnumero igual a p */
 /* 0. leia os dados */
 printf("Digite p e q: ");
 scanf("%d %d", &p, &q);
 /* 1. determine a menor potencia de 10 maior que p */
 pot10 = 1;
 while (pot10 <= p)
 pot10 = pot10 * 10;
 /* 2. verifique se algum subnumero de q e igual a p */
 achou = FALSE;
 qaux = q;
 while (qaux >= p && achou == FALSE) 
 {
 subnumero = qaux%pot10;
 qaux = qaux/10;
 if (subnumero == p)
 achou = TRUE;
 }
 
 if (achou == TRUE)
 printf("%d e' subnumero de %d\n", p, q);
 else 
 printf("%d nao e' subnumero de %d\n", p, q);
 return 0;
}
/*
 * Solucao 3: esta solucao tem dois while's enacaixado
 * 
 */
#include <stdio.h>
#define TRUE 1
#define FALSE 0
int main()
{
 int p; /* valor dado */ 
 int q; /* valor dado */
 int p_seg; /* segmento (prefixo) de p */ 
 int q_seg; /* segmento (prefixo) de q */
 int q_seg2; /* segmento (prefixo) de q_seg */
 int dig_p; /* digito menos significativo de p_seg */
 int dig_q; /* digito menos significativo de q_seg2 */
 int subnumero; /* indica se p e subnumero de q */
 /* 0. leia os dados */
 printf("Digite p e q: ");
 scanf("%d %d", &p, &q);
 
 /* 1. verifique se p e subnumero de q */
 subnumero = FALSE;
 q_seg = q;
 while (q_seg >= p && subnumero == FALSE) 
 { 
 /* 1.1 verifique se p e subnumero (sulfixo) de q_seg */
 subnumero = TRUE;
 p_seg = p;
 q_seg2 = q_seg;
 while (p_seg > 0 && subnumero == TRUE)
 {
 dig_p = p_seg%10;
 p_seg = p_seg/10;
 dig_q = q_seg2%10;
 q_seg2 = q_seg2/10;
 if (dig_p != dig_q) 
 {
 subnumero = FALSE;
 }
 }
 
 /* 1.2 `remova' o digito menos significativo de q_seg */
 q_seg = q_seg/10;
 }
 /* 2. escreva resposta */
 if (subnumero == TRUE) 
 printf("%d e subnumero de %d\n", p, q);
 else
 printf("%d nao e subnumero de %d\n", p, q);
 
 return 0;
}
/*
 * Solucao 4: colocaremos aqui qualquer solução que virmos e que 
 * seja essencialmente diferente das anteriores.
 */
QUESTÃO 3
 Escreva um programa em C que lê um número inteiro n, n > 0, e lê uma seqüência de n números inteirose
imprime o maior comprimento de um segmento crescente.
[Um segmento de uma seqüência
a1, a2, . . . , an-1,an
é qualquer subseqüência da forma
ai, ai+1, ai+2, . . . , ai+k-1, ai+k.
Um segmento
ai, ai+1, ai+2, . . . , ai+k-1, ai+k
é crescente se
ai < ai+1 < ai+2 < . . . < ai+k-1 < ai+k.
O comprimento de um segmento é o número de elementos no segmento.]
Exemplos:
1. para n=4 e a seqüência 3 1 7 9 a resposta é 3;
2. para n=11 e a seqüência 4 6 -1 3 13 21 27 0 2 5 98 a resposta é 5;
3. para n=1 e a seqüência 45 a resposta é 1;
4. para n=6 e a seqüência 20 20 19 11 4 -5 a resposta é 1;
SOLUÇÃO
/*
 * Solucao 1: Solucao curta e simples.
 *
 */
#include <stdio.h>
int main()
{
 int n; /* tamanho da sequencia */
 int atual; /* usado para aleitura da sequencia */
 int anterior; /* elemento da sequencia lido antes de atual */
 int compmax; /* maior comprimento de um segmento crescente da 
 subsequencia lida */
 int comp; /* comprimento do segmento crescente sendo examinado */
 int i; /* contador de numeros ja lidos */
 /* 0. leia o tamanho da sequencia */
 printf("Digite o numero de elemento da sequencia: ");
 scanf("%d", &n);
 /* 1. leia o 1o. numero da sequencia */
 printf("Digite o 1o. numero: ");
 scanf("%d", &anterior);
 /* 2. leia e examine o 2o., 3o.,... numero da sequencia */ 
 compmax = 1;
 comp = 1;
 i = 1; 
 while (i < n) 
 {
 /* 2.1 leia o proximo numero da sequencia */
 printf("Digite o %do. numero: ", i+1);
 scanf("%d", &atual); 
 i = i + 1;
 /* 2.2 atualize o comprimento da seq crescente corrente */
 if (anterior < atual)
 {
 comp = comp + 1;
 if (comp > compmax)
 {
 compmax = comp;
 }
 }
 else
 {
 comp = 1;
 }
 
 anterior = atual;
 }
 printf("Maior comprimento de um segmento crescente = %d\n", compmax);
 return 0;
}
/*
 * Solucao 2: identica a solucao 1, com for no lugar de 
 * while.
 */
#include <stdio.h>
int main()
{
 int n; /* tamanho da sequencia */
 int atual; /* usado para aleitura da sequencia */
 int anterior; /* elemento da sequencia lido antes de atual */
 int compmax; /* maior comprimento de um segmento crescente da 
 subsequencia lida */
 int comp; /* comprimento do segmento crescente sendo examinado */
 int i; /* contador de numeros ja lidos */
 /* 0. leia o tamanho da sequencia */
 printf("Digite o numero de elemento da sequencia: ");
 scanf("%d", &n);
 /* 1. leia o 1o. numero da sequencia */
 printf("Digite o 1o. numero: ");
 scanf("%d", &anterior);
 /* 2. leia e examine o 2o., 3o.,... numero da sequencia */ 
 compmax = 1;
 comp = 1;
 for (i = 1; i < n; i++) 
 {
 /* 2.1 leia o proximo numero da sequencia */
 printf("Digite o %do. numero: ", i+1);
 scanf("%d", &atual); 
 /* 2.2 atualize o comprimento da seq crescente corrente */
 if (anterior < atual)
 {
 comp = comp + 1;
 if (comp > compmax)
 {
 compmax = comp;
 }
 }
 else
 {
 comp = 1;
 }
 
 anterior = atual;
 }
 printf("Maior comprimento de um segmento crescente = %d\n", compmax);
 return 0;
}
/*
 * Solucao 3: identica a solucao 2 sem chaves superfluas.
 * 
 */
#include <stdio.h>
int main()
{
 int n; /* tamanho da sequencia */
 int atual; /* usado para aleitura da sequencia */
 int anterior; /* elemento da sequencia lido antes de atual */
 int compmax; /* maior comprimento de um segmento crescente da 
 subsequencia lida */
 int comp; /* comprimento do segmento crescente sendo examinado */
 int i; /* contador de numeros ja lidos */
 /* 0. leia o tamanho da sequencia */
 printf("Digite o numero de elemento da sequencia: ");
 scanf("%d", &n);
 /* 1. leia o 1o. numero da sequencia */
 printf("Digite o 1o. numero: ");
 scanf("%d", &anterior);
 /* 2. leia e examine o 2o., 3o.,... numero da sequencia */ 
 compmax = 1;
 comp = 1;
 for (i = 1; i < n; i++) 
 {
 /* 2.1 leia o proximo numero da sequencia */
 printf("Digite o %do. numero: ", i+1);
 scanf("%d", &atual); 
 /* 2.2 atualize o comprimento da seq crescente corrente */
 if (anterior < atual)
 {
 comp = comp + 1;
 if (comp > compmax) compmax = comp;
 }
 else comp = 1;
 
 anterior = atual;
 }
 printf("Maior comprimento de um segmento crescente = %d\n", compmax);
 return 0;
}
/*
 * Solucao 4: identica a solucao 1; usa n como quantidade
 * de numeros a serem lidos
 */
#include <stdio.h>
int main()
{
 int n; /* quantida de numero da seq a serem lidos */
 int atual; /* usado para aleitura da sequencia */
 int anterior; /* elemento da sequencia lido antes de atual */
 int compmax; /* maior comprimento de um segmento crescente da 
 subsequencia lida */
 int comp; /* comprimento do segmento crescente sendo examinado */
 /* 0. leia o tamanho da sequencia */
 printf("Digite o numero de elemento da sequencia: ");
 scanf("%d", &n);
 /* 1. leia o 1o. numero da sequencia */
 printf("Digite o 1o. numero: ");
 scanf("%d", &anterior);
 n = n - 1;
 /* 2. leia e examine o 2o., 3o.,... numero da sequencia */ 
 compmax = 1;
 comp = 1;
 while (n > 0)
 {
 /* 2.1 leia o proximo numero da sequencia */
 printf("Digite o proximo numero: ");
 scanf("%d", &atual); 
 n = n - 1;
 /* 2.2 atualize o comprimento da seq crescente corrente */
 if (anterior < atual)
 {
 comp = comp + 1;
 if (comp > compmax) compmax = comp;
 }
 else comp = 1;
 
 anterior = atual;
 }
 printf("Maior comprimento de um segmento crescente = %d\n", compmax);
 return 0;
}
/*
 * Solucao 5: colocaremos aqui qualquer solução que virmos e que 
 * seja essencialmente diferente das anteriores.
 */
 
 
 
Last modified: Mon May 16 11:39:18 BRT 2005
	MAC2166 Introdução à Computação
	Prova 1
	QUESTÃO 1
	QUESTÃO 2
	QUESTÃO 3