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:

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 inteiros e 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