Departamento de Ciência da
Computação - IME - USP
#include <stdio.h> int f1(int *a, int b); int f2(int v[4]); int main() { int nusp, v[4], m[4], a, b, i, j, c, d; printf("Digite o seu no. USP: "); scanf("%d",&nusp); /* use o SEU no. USP */ printf("nusp=%d\n", nusp); d = nusp%10; m[0] = 11; m[1] = 12; m[2] = 21; m[3] = 22; v[0] = 31; v[1] = 32; v[2] = 41; v[3] = 42; if (d == 2 || d == 5 || d == 9) { a = 0; b = 1; c = 2; i = 3; j = 4; a = f1(&i,j); printf("1: a=%d b=%d i=%d j=%d c=%d\n", a, b, i, j, c); a = 0; b = 1; i = 2; j = 3; c = 4; i = f1(&i,i); printf("2: a=%d b=%d i=%d j=%d c=%d\n", a, b, i, j, c); m[0] = f1(&m[1], m[2]); printf("3: m[0]=%d m[1]=%d m[2]=%d m[3]=%d\n", m[0], m[1], m[2], m[3]); m[3] = f2(m); printf("4: m[0]=%d m[1]=%d m[2]=%d m[3]=%d\n", m[0], m[1], m[2], m[3]); printf("5: v[0]=%d v[1]=%d v[2]=%d v[3]=%d\n", v[0], v[1], v[2], v[3]); } else if (d == 0 || d == 3 || d == 6 || d == 8) { a = 4; b = 0; i = 1; j = 2; c = 3; b = f1(&i,j); printf("1: a=%d b=%d i=%d j=%d c=%d\n", a, b, i, j, c); a = 4; b = 0; i = 1; j = 2; c = 3; j = f1(&j,j); printf("2: a=%d b=%d i=%d j=%d c=%d\n", a, b, i, j, c); m[1] = f1(&m[2],m[3]); printf("3: m[0]=%d m[1]=%d m[2]=%d m[3]=%d\n", m[0], m[1], m[2], m[3]); m[0] = f2(m); printf("4: m[0]=%d m[1]=%d m[2]=%d m[3]=%d\n", m[0], m[1], m[2], m[3]); printf("5: v[0]=%d v[1]=%d v[2]=%d v[3]=%d\n", v[0], v[1], v[2], v[3]); } else if (d == 1 || d == 4 || d == 7) { a = 2; b = 3; c = 4; i = 0; j = 1; b = f1(&i,j); printf("1: a=%d b=%d i=%d j=%d c=%d\n", a, b, i, j, c); a = 1; b = 0; i = 4; j = 3; c = 2; i = f1(&i,i); printf("2: a=%d b=%d i=%d j=%d c=%d\n", a, b, i, j, c); m[2] = f1(&m[3],m[0]); printf("3: m[0]=%d m[1]=%d m[2]=%d m[3]=%d\n", m[0], m[1], m[2], m[3]); m[1] = f2(m); printf("4: m[0]=%d m[1]=%d m[2]=%d m[3]=%d\n", m[0], m[1], m[2], m[3]); printf("5: v[0]=%d v[1]=%d v[2]=%d v[3]=%d\n", v[0], v[1], v[2], v[3]); } else printf("Tirei ZERO nesta questao\n"); return 0; } int f1(int *a, int b) { int i, j, c; *a = 9; b = 8; i = 7; j = 6; c = 5; printf("f1: *a=%d b=%d i=%d j=%d c=%d\n", *a, b, i, j, c); return 10; } int f2(int v[4]) { v[0] = 61; v[1] = 62; v[2] = 71; v[3] = 72; printf("f2: v[0]=%d v[1]=%d v[2]=%d v[3]=%d\n", v[0], v[1], v[2], v[3]); return 81; }
A resposta depende do resto da divisão do seu número USP por 10.
Teste com o seu no. USP e compare a resposta.
nusp%10 == 2 ou nusp%10 == 5 ou nusp%10 == 9.
Digite o seu no. USP: 1234562 nusp=1234562 f1: *a=9 b=8 i=7 j=6 c=5 1: a=10 b=1 i=9 j=4 c=2 f1: *a=9 b=8 i=7 j=6 c=5 2: a=0 b=1 i=10 j=3 c=4 f1: *a=9 b=8 i=7 j=6 c=5 3: m[0]=10 m[1]=9 m[2]=21 m[3]=22 f2: v[0]=61 v[1]=62 v[2]=71 v[3]=72 4: m[0]=61 m[1]=62 m[2]=71 m[3]=81 5: v[0]=31 v[1]=32 v[2]=41 v[3]=42 Digite o seu no. USP: 1234565 nusp=1234565 f1: *a=9 b=8 i=7 j=6 c=5 1: a=10 b=1 i=9 j=4 c=2 f1: *a=9 b=8 i=7 j=6 c=5 2: a=0 b=1 i=10 j=3 c=4 f1: *a=9 b=8 i=7 j=6 c=5 3: m[0]=10 m[1]=9 m[2]=21 m[3]=22 f2: v[0]=61 v[1]=62 v[2]=71 v[3]=72 4: m[0]=61 m[1]=62 m[2]=71 m[3]=81 5: v[0]=31 v[1]=32 v[2]=41 v[3]=42 Digite o seu no. USP: 1234569 nusp=1234569 f1: *a=9 b=8 i=7 j=6 c=5 1: a=2 b=10 i=9 j=1 c=4 f1: *a=9 b=8 i=7 j=6 c=5 2: a=1 b=0 i=10 j=3 c=2 f1: *a=9 b=8 i=7 j=6 c=5 3: m[0]=11 m[1]=12 m[2]=10 m[3]=9 f2: v[0]=61 v[1]=62 v[2]=71 v[3]=72 4: m[0]=61 m[1]=81 m[2]=71 m[3]=72 5: v[0]=31 v[1]=32 v[2]=41 v[3]=42
nusp%10 == 0 ou nusp%10 == 3 ou nusp%10 == 6 ou nusp%10 == 8.
Digite o seu no. USP: 1234560 nusp=1234560 f1: *a=9 b=8 i=7 j=6 c=5 1: a=4 b=10 i=9 j=2 c=3 f1: *a=9 b=8 i=7 j=6 c=5 2: a=4 b=0 i=1 j=10 c=3 f1: *a=9 b=8 i=7 j=6 c=5 3: m[0]=11 m[1]=10 m[2]=9 m[3]=22 f2: v[0]=61 v[1]=62 v[2]=71 v[3]=72 4: m[0]=81 m[1]=62 m[2]=71 m[3]=72 5: v[0]=31 v[1]=32 v[2]=41 v[3]=42 Digite o seu no. USP: 1234563 nusp=1234563 f1: *a=9 b=8 i=7 j=6 c=5 1: a=4 b=10 i=9 j=2 c=3 f1: *a=9 b=8 i=7 j=6 c=5 2: a=4 b=0 i=1 j=10 c=3 f1: *a=9 b=8 i=7 j=6 c=5 3: m[0]=11 m[1]=10 m[2]=9 m[3]=22 f2: v[0]=61 v[1]=62 v[2]=71 v[3]=72 4: m[0]=81 m[1]=62 m[2]=71 m[3]=72 5: v[0]=31 v[1]=32 v[2]=41 v[3]=42 Digite o seu no. USP: 1234566 nusp=1234566 f1: *a=9 b=8 i=7 j=6 c=5 1: a=4 b=10 i=9 j=2 c=3 f1: *a=9 b=8 i=7 j=6 c=5 2: a=4 b=0 i=1 j=10 c=3 f1: *a=9 b=8 i=7 j=6 c=5 3: m[0]=11 m[1]=10 m[2]=9 m[3]=22 f2: v[0]=61 v[1]=62 v[2]=71 v[3]=72 4: m[0]=81 m[1]=62 m[2]=71 m[3]=72 5: v[0]=31 v[1]=32 v[2]=41 v[3]=42 Digite o seu no. USP: 1234568 nusp=1234568 f1: *a=9 b=8 i=7 j=6 c=5 1: a=4 b=10 i=9 j=2 c=3 f1: *a=9 b=8 i=7 j=6 c=5 2: a=4 b=0 i=1 j=10 c=3 f1: *a=9 b=8 i=7 j=6 c=5 3: m[0]=11 m[1]=10 m[2]=9 m[3]=22 f2: v[0]=61 v[1]=62 v[2]=71 v[3]=72 4: m[0]=81 m[1]=62 m[2]=71 m[3]=72 5: v[0]=31 v[1]=32 v[2]=41 v[3]=42nusp%10 == 1 ou nusp%10 == 4 ou nusp%10 == 7.
Digite o seu no. USP: 1234561 nusp=1234561 f1: *a=9 b=8 i=7 j=6 c=5 1: a=2 b=10 i=9 j=1 c=4 f1: *a=9 b=8 i=7 j=6 c=5 2: a=1 b=0 i=10 j=3 c=2 f1: *a=9 b=8 i=7 j=6 c=5 3: m[0]=11 m[1]=12 m[2]=10 m[3]=9 f2: v[0]=61 v[1]=62 v[2]=71 v[3]=72 4: m[0]=61 m[1]=81 m[2]=71 m[3]=72 5: v[0]=31 v[1]=32 v[2]=41 v[3]=42 Digite o seu no. USP: 1234564 nusp=1234564 f1: *a=9 b=8 i=7 j=6 c=5 1: a=2 b=10 i=9 j=1 c=4 f1: *a=9 b=8 i=7 j=6 c=5 2: a=1 b=0 i=10 j=3 c=2 f1: *a=9 b=8 i=7 j=6 c=5 3: m[0]=11 m[1]=12 m[2]=10 m[3]=9 f2: v[0]=61 v[1]=62 v[2]=71 v[3]=72 4: m[0]=61 m[1]=81 m[2]=71 m[3]=72 5: v[0]=31 v[1]=32 v[2]=41 v[3]=42 Digite o seu no. USP: 1234567 nusp=1234567 f1: *a=9 b=8 i=7 j=6 c=5 1: a=2 b=10 i=9 j=1 c=4 f1: *a=9 b=8 i=7 j=6 c=5 2: a=1 b=0 i=10 j=3 c=2 f1: *a=9 b=8 i=7 j=6 c=5 3: m[0]=11 m[1]=12 m[2]=10 m[3]=9 f2: v[0]=61 v[1]=62 v[2]=71 v[3]=72 4: m[0]=61 m[1]=81 m[2]=71 m[3]=72 5: v[0]=31 v[1]=32 v[2]=41 v[3]=42
Cada uma das funções a seguir recebe um inteiro n, 0 < n < MAX, um vetor v[MAX] com n números inteiros em ordem crescente e um número inteiro x e prometem devolver um índice k, 0 ≤ k < n, tal que v[k] = x ou devolver -1 se não existir um tal índice k.
Por exemplo, para n=5, MAX=10 e
v | 1 | 3 | 5 | 7 | 9 | ? | ? | ? | ? | ? |
0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 |
Para cada função indique no quadro correspondente se a função está correta ou não. Se você considerar que a função está incorreta, então você deve exibir um valor para o parâmetro x que junto com o vetor v[MAX] e n mostrados acima comprovem que a função está incorreta, bem como deve exibir o valor devolvido (colocar ∞ se julgar que entra em loop infinito) e o valor que deveria ser devolvido.
(a)
int busca(int v[MAX], int n, int x){ int i; v[n] = x; i = 0; while (v[i]<x) i = i+1; if (v[i]==x) return i; else return -1; }
Falha para x=10, pois devolve 5, mas deveria devolver -1.(b)
int busca(int v[MAX], int n, int x){ int i; v[n] = x; i = 0; while (v[i]!=x) i = i+1; if (i<n) return i; else return -1; }
Funciona sempre.(c)
int busca(int v[MAX], int n, int x){ int i, achou; i = n-1; achou = 0; while (i>0 && achou==0) if (v[i]==x) achou = 1; else i = i-1; if (achou==1) return i; else return -1; }
Falha para x=1, pois devolve -1, mas deveria devolver 0.(d)
int busca(int v[MAX], int n, int x){ int inicio,fim,meio; inicio = 0; fim = n-1; while (inicio<fim) { meio = (fim-inicio)/2; if (x<v[meio]) fim = meio-1; if (x>v[meio]) inicio = meio+1; if (x==v[meio]) return meio; } return -1; }
Falha para x=3, pois devolve -1, mas deveria devolver 1. Entra em loop para x > 5.(e)
int busca(int v[MAX], int n, int x){ int inicio,fimaberto,meio; inicio = 0; fimaberto = n; while (fimaberto-inicio>1) { meio = (inicio+fimaberto)/2; if (x>=v[meio]) inicio = meio; else fimaberto = meio; } if (x==v[inicio]) return inicio; else return -1; }
Funciona sempre.(f)
int busca(int v[MAX],int n, int x){ int inicio,fim,meio,achou; inicio = 0; fim = n-1; achou = 0; while (inicio<fim && achou==0) { meio = (inicio+fim)/2; if (v[meio]==x) achou = 1; if (v[meio]>x) fim = meio-1; else inicio = meio+1; } if (achou==1) return meio; else return -1; }
Falha para x=3, pois devolve -1, mas deveria devolver 1. Falha para x=9, pois devolve -1, mas deveria devolver 4.
Esta questão consiste na implementação de três funções. Todas as funções são simplificações muito grandes de alguns trechos de código que você escreveu para o seu EP4. Os nomes das funções são inicialize_tabuleiro,, numero_reversoes e main.
Otelo é um jogo entre dois jogadores, o jogador Xis e o jogador Bola. Ele é jogado em uma tabuleiro de ordem n, ou seja, de dimensão n × n e portanto com n2 casas. Na configuração inicial do tabuleiro cada jogador tem duas marcas na parte central do tabuleiro como mostrado a seguir. A marca do jogador Xis é 'X' e a marca do jogador Bola é 'O'.
1 2 3 4 +---+---+---+---+ 1 | . | . | . | . | +---+---+---+---+ 2 | . | O | X | . | +---+---+---+---+ 3 | . | X | O | . | +---+---+---+---+ 4 | . | . | . | . | +---+---+---+---+ Figura (a) 1 2 3 4 5 6 +---+---+---+---+---+---+ 1 | . | . | . | . | . | . | +---+---+---+---+---+---+ 2 | . | . | . | . | . | . | +---+---+---+---+---+---+ 3 | . | . | O | X | . | . | +---+---+---+---+---+---+ 4 | . | . | X | O | . | . | +---+---+---+---+---+---+ 5 | . | . | . | . | . | . | +---+---+---+---+---+---+ 6 | . | . | . | . | . | . | +---+---+---+---+---+---+ Figura (b)Na figura (a) o tabuleiro tem ordem 4 e na figura (b) tem ordem 6. Nos tabuleiros as posições com um ponto ('.') indicam casas vazias. Na figura (a) as casas das posições (2,3) e (3,2) têm a marca do jogador Xis e as casas das posições (2,2) e (3,3) têm a marca do jogador Bola.
O jogador Xis é sempre o primeiro a fazer um movimento legal, depois os jogadores devem se alternar. Na sua vez, cada jogador deve colocar a sua marca em uma casa vazia adjacente a uma casa que possui a marca do adversário. Além disso, uma ou mais marcas do adversário devem ser cercadas, verticalmente, horizontalmente ou diagonalmente, por essa nova marca e por uma marca sua pré-existente no tabuleiro. Todas as marcas do adversário que estão cercadas são então revertidas em marcas do jogador.
No enunciado desta questão são usadas as declarações a seguir. Como no EP4, o tabuleiro de Otelo de ordem n deverá ocupar as linhas e colunas de índices 1,. . .,n de uma matriz tab.
#define MAXN 8 #define MINN 2 #define MAX (MAXN+2) #define BOLA 'O' #define XIS 'X' #define VAZIA '.' #define MOLDURA '*'
item (a) Escreva uma função de protótipo
void inicialize_tabuleiro(int n, char tab[MAX][MAX]);que recebe e inicializa uma matriz tab com a configuração inicial de um tabuleiro de Otelo de ordem n. É opcional inicializar ou não a moldura, de acordo com a forma que você resolver o item (b).
void inicialize_tabuleiro(int n, char tab[MAX][MAX]) { int i, j; /* preenche o tabuleiro com casas vazias e a moldura */ for (i = 0; i <= n+1; i++) for (j = 0; j <= n+1; j++) if (i==0 || j==0 || i==n+1 || j==n+1) tab[i][j] = MOLDURA; else tab[i][j] = VAZIA; /* preenche a posicao central */ tab[n/2][n/2] = tab[n/2+1][n/2+1] = BOLA; tab[n/2][n/2+1] = tab[n/2+1][n/2] = XIS ; }
item (b) Escreva uma função de protótipo
int numero_reversoes(int n, char tab[MAX][MAX], char jog, int lin, int col)que recebe na matriz tab em que está armazenada a configuração de um tabuleiro de Otelo de ordem n, na variável jog a marca de Xis ou Bola e uma posição (lin,col). A função deve devolver:
1 2 3 4 +---+---+---+---+ 1 | . | . | . | . | +---+---+---+---+ 2 | . | O | O | O | +---+---+---+---+ 3 | . | X | X | X | +---+---+---+---+ 4 | . | . | . | . | +---+---+---+---+e jog='X',
int numero_reversoes(int n, char tab[MAX][MAX], char jog, int lin, int col) { int no_reversoes = 0; int no_rev; int adversario; int i, j; /* para enumerar direcoes */ int l, c; /* posicao auxiliar */ if (lin < 1 || lin > n || col < 1 || col > n) return 0; else if (tab[lin][col] == BOLA || tab[lin][col] == XIS) return 0; else { /* neste ponto sabemos que (lin,col) e' uma posicao vazia do * tabuleiro. */ if (jog == BOLA) adversario = XIS; else adversario = BOLA; for (i = -1; i <= 1; i++) for (j = -1; j <= 1; j++) { no_rev = 0; l = lin+i; c = col+j; while (tab[l][c] == adversario) { no_rev++; l = l + i; c = c + j; } if (tab[l][c] == jog) no_reversoes = no_reversoes + no_rev; } } return no_reversoes; }
Para escrever a função main pedida no item (c) você deve usar as funções a seguir sem escrevê-las. Suponha que lhe é dada uma função de protótipo
void coloque_marca(int n, char tab[MAX][MAX], char jog, int lin, int col);que recebe uma matriz tab em que está armazenada a configuração de um tabuleiro de Otelo de ordem n, uma variável jog que contém a marca de Xis ou de Bola e uma posição (lin,col). Essa função coloca na posição (lin,col) a marca em jog e faz as reversões correspondentes.
Suponha ainda que lhe é dada uma função de protótipo
void escreva_tabuleiro(int n, char tab[MAX][MAX]);que recebe uma matriz tab em que está armazenada a configuração de um tabuleiro de Otelo de ordem n e imprime o tabuleiro.
item (c) Escreva uma função main que, inicialmente,
A sua função main deve usar obrigatoriamente as funções
inicialize_tabuleiro, numero_reversoes, escreva_tabuleiro, e coloque_marca.Você pode usar as funções inicialize_tabuleiro do item (a) e numero_reversoes do item (b), mesmo que não as tenha feito.
A seguir mostramos um exemplo de execução do programa:
Digite a ordem do tabuleiro: 4 1 2 3 4 +---+---+---+---+ 1 | . | . | . | . | +---+---+---+---+ 2 | . | O | X | . | +---+---+---+---+ 3 | . | X | O | . | +---+---+---+---+ 4 | . | . | . | . | +---+---+---+---+ Vez e' do jogador 'X'. Digite o numero de posicoes: 5 Digite uma posicao: 1 1 main: 'X' nao pode jogar em (1,1) Digite uma posicao: 3 4 main: 'X' pode jogar em (3,4) coloque_marca: 1 'O'(s) revertido(s) para 'X'(s). 1 2 3 4 +---+---+---+---+ 1 | . | . | . | . | +---+---+---+---+ 2 | . | O | X | . | +---+---+---+---+ 3 | . | X | X | X | +---+---+---+---+ 4 | . | . | . | . | +---+---+---+---+ Vez e' do jogador 'O'. Digite uma posicao: 2 4 main: 'O' pode jogar em (2,4) coloque_marca: 1 'X'(s) revertido(s) para 'O'(s). 1 2 3 4 +---+---+---+---+ 1 | . | . | . | . | +---+---+---+---+ 2 | . | O | O | O | +---+---+---+---+ 3 | . | X | X | X | +---+---+---+---+ 4 | . | . | . | . | +---+---+---+---+ Vez e' do jogador 'X'. Digite uma posicao: 1 4 main: 'X' pode jogar em (1,4) coloque_marca: 2 'O'(s) revertido(s) para 'X'(s). 1 2 3 4 +---+---+---+---+ 1 | . | . | . | X | +---+---+---+---+ 2 | . | O | X | X | +---+---+---+---+ 3 | . | X | X | X | +---+---+---+---+ 4 | . | . | . | . | +---+---+---+---+ Vez e' do jogador 'O'. Digite uma posicao: 1 4 main: 'O' nao pode jogar em (1,4)
int main() { char tabuleiro[MAX][MAX]; /* tabuleiro de Otelo */ int n; /* ordem do tabuleiro */ char jog_vez; /* indica qual o jogador da vez */ int lin, col; /* linha e coluna de alguma posicao */ int no_reversoes;/* numero de reversoes causados por um movimento */ int m; /* numero de posicoes */ int i; /* contador auxiliar */ printf("Digite a ordem do tabuleiro: "); scanf("%d", &n); inicialize_tabuleiro(n,tabuleiro); jog_vez = XIS; escreva_tabuleiro(n,tabuleiro); printf("Vez e' do jogador '%c'.\n", jog_vez); printf("Digite o numero de posicoes: "); scanf("%d", &m); for (i = 0; i < m; i++) { printf("Digite uma posicao: "); scanf("%d %d", &lin, &col); no_reversoes = numero_reversoes(n,tabuleiro,jog_vez,lin,col); if (no_reversoes > 0) { printf("main: '%c' pode jogar em (%d,%d)\n", jog_vez, lin, col); coloque_marca(n,tabuleiro,jog_vez,lin,col); if (jog_vez == XIS) jog_vez = BOLA; else jog_vez = XIS; escreva_tabuleiro(n,tabuleiro); printf("Vez e' do jogador '%c'.\n", jog_vez); } else printf("main: '%c' nao pode jogar em (%d,%d)\n", jog_vez, lin, col); } return 0; }