Departamento de Ciência da
Computação - IME - USP
Em um jogo da velha temos um jogador Xis, um jogador Bola e
um tabuleiro de dimensão n × n.
Uma configuração do tabuleiro pode ser representada
por uma matriz em que cada posição armazena um string que pode ser um:
'X' que é a marca do jogador Xis;
'O' que é a marca do jogador Bola; ou
' ' que indica um posição vazia.
n5 × 54 \times 4 com e sem vencedor:
+---+---+---+---+---+ +---+---+---+---+---+ +---+---+---+---+---+
| X | | O | | | | X | | O | | | | X | X | O | O | |
+---+---+---+---+---+ +---+---+---+---+---+ +---+---+---+---+---+
| O | O | O | O | X | | O | O | O | O | X | | O | O | O | O | X |
+---+---+---+---+---+ +---+---+---+---+---+ +---+---+---+---+---+
| | | X | | | | O | | X | | | | O | X | X | O | X |
+---+---+---+---+---+ +---+---+---+---+---+ +---+---+---+---+---+
| | | X | X | | | X | X | X | X | X | | X | X | X | O | X |
+---+---+---+---+---+ +---+---+---+---+---+ +---+---+---+---+---+
| | | O | | X | | O | | O | | X | | O | X | O | O | X |
+---+---+---+---+---+ +---+---+---+---+---+ +---+---+---+---+---+
Sem vencedor Xis venceu Bola venceu
+---+---+---+---+---+ +---+---+---+---+---+ +---+---+---+---+
| O | X | O | | X | | O | X | O | O | X | | X | | O | X |
+---+---+---+---+---+ +---+---+---+---+---+ +---+---+---+---+
| O | O | X | O | X | | | O | O | X | X | | O | O | O | O |
+---+---+---+---+---+ +---+---+---+---+---+ +---+---+---+---+
| O | X | O | O | X | | O | X | X | O | | | O | X | X | |
+---+---+---+---+---+ +---+---+---+---+---+ +---+---+---+---+
| X | X | X | O | X | | X | X | X | O | X | | X | X | | |
+---+---+---+---+---+ +---+---+---+---+---+ +---+---+---+---+
| O | X | X | O | O | | X | O | | O | O | Bola venceu
+---+---+---+---+---+ +---+---+---+---+---+
Bola venceu Xis venceu
Escreva um função com cebaçalho:
def verifica_tabuleiro(tab):
que recebe uma configuração tab de um tabuleiro do jogo da velha e retorna:
'O' se o jogador Bola é o vencedor;
'X' se o jogador Xis é o vencedor; ou
'N' se não há vencedor.
#--------------------------------------------------------------------
# SOLUÇÃO 1:
#
#--------------------------------------------------------------------
def verifica_tabuleiro(Tab):
''' (matriz) -> string
Recebe uma confiiguração tab de um tabuleiro do jogo da velha e
retorna:
- 'O' se o jogador Bola é o vencedor;
- 'X' se o jogador Xis é o vencedor; ou
- 'N' se não há vencedor.
'''
n = len(Tab)
# verifique cada linha
for i in range(n):
marca = Tab[i][0]
if marca != " ":
j = 1
while j < n and Tab[i][j] == marca:
j += 1
if j == n:
return marca
# vefifique cada coluna
for j in range(n):
marca = Tab[0][j]
if marca != " ":
i = 1
while i < n and Tab[i][j] == marca:
i += 1
if i == n:
return marca
# verifique diagonal principal
marca = Tab[0][0]
if marca != " ":
i = 1
while i < n and Tab[i][i] == marca:
i += 1
if i == n:
return marca
# verifiuqe diagonal secundária
marca = Tab[0][n-1]
if marca != " ":
i = 1
while i < n and Tab[i][n-i-1] == marca:
i += 1
if i == n:
return marca
return "N"
#--------------------------------------------------------------------
# SOLUÇÃO 2:
#
#--------------------------------------------------------------------
def verifica_tabuleiro(Tab):
''' (matriz) -> string
Recebe uma confiiguração tab de um tabuleiro do jogo da velha e
retorna:
- 'O' se o jogador Bola é o vencedor;
- 'X' se o jogador Xis é o vencedor; ou
- 'N' se não há vencedor.
'''
n = len(Tab)
for marca in "XO":
# verifique cada linha
for i in range(n):
j = 1
while j < n and tab[i][j] == marca:
j += 1
if j == n:
return marca
# vefifique cada coluna
for j in range(n):
i = 1
while i < n and tab[i][j] == marca:
i += 1
if i == n:
return marca
# verifique diagonal principal
marca = tab[0][0]
i = 1
while i < n and tab[i][i] == marca:
i += 1
if i == n:
return marca
# verifique diagonal secundária
marca = tab[0][n-1]
i = 1
while i < n and tab[i][n-i-1] == marca:
i += 1
if i == n:
return marca
return "N"
Esta questão é composta por 3 itens.
item (a)
Escreva uma função de cabeçalho
def ocorre(texto, i, palavra):
que recebe um string texto, um inteiro i e um string
palavra e retorna True se palavra ocorre em
texto começando na posição i e retorna
False em caso contrário.
A seguir estão alguns exemplos.
>>> ocorre('0123456', 1, '012')
False
>>> ocorre('0123456', 0, '012')
True
>>> ocorre('Como é bom estudar MAC2166!', 1, 'omo')
True
>>> ocorre('abcdabcd', 4, 'abc')
True
>>> ocorre('abcdabcd', 6, 'cd')
True
>>> ocorre('abcdabcd', 6, 'cde')
False
def ocorre(texto, i, palavra):
''' (string, int, string) -> bool
Recebe um string ´texto´, um inteiro ´i´ e um string
´palavra´ e retorna True se a palavra ocorre no texto
começando na posição ´i´.
'''
n = len(texto)
m = len(palavra)
j = 0
while i < n and j < m and texto[i] == palavra[j]:
i += 1
j += 1
if j == m:
return True
return False
item (b)
Escreva uma função de cabeçalho
def picota(texto, padrão):
que recebe os strings texto e padrão e
retorna uma lista com os pedaços (strings) que resultariam
se as ocorrências de padrão fossem removidas
e texto fosse cortado nessas ocorrências.
A seguir estão alguns exemplos.
>>> picota('Como é bom estudar MAC2166!', ' ')
['Como', 'é', 'bom', 'estudar', 'MAC2166!']
>>> picota('Como é bom estudar MAC2166!', 'estudar')
['Como é bom ', ' MAC2166!']
>>> picota('Como é bom estudar', 'dar')
['Como é bom estu', '']
>>> picota('ossos', 'os')
['', 's', '']
>>> picota('Como é bom estudar MAC2166!', 'Física')
['Como é bom estudar MAC2166!']
def picota(texto, padrão):
''' (string, string) -> lista
Recebe strings ´texto´ e ´padrão´ e retorna uma lista com os strings
que resultariam se as ocorrências de ´padrão´ fossem removidas e
o texto fosse cortado nessas ocorrências.
'''
n = len(texto)
m = len(padrão)
lista = []
palavra = ""
i = 0
while i < n:
# há uma ocorrência do padrão começando na posição i
if ocorre(texto,i,padrão):
lista.append(palavra)
palavra = ""
i = i + m
else:
# concatena o caractere no fim da palavra
palavra = palavra + texto[i]
i = i + 1
lista.append(palavra)
return lista
item (c)
Nesse item você pode utilizar a função do item anterior mesmo que não
a tenha feito. Você não precisa reescrever a função.
Escreva um programa que leia três strings: frase,
velho e novo, e imprima um string
onde todas as ocorrências de velho foram
substituidas por novo.
A seguir estão alguns exemplos.
>>> Digite uma frase: Como é bom estudar PCC! Digite o velho: PCC Digite o novo: MAC2166 Como é bom estudar MAC2166! >>> Digite uma frase: as rugas das tartarugas ninjas. Digite o velho: rugas ninj Digite o novo: ninjas rug as rugas das tartaninjas rugas. >>> Digite uma frase: palavras são palavras nada mais do que palavras Digite o velho: palavras Digite o novo: coisas coisas são coisas nada mais do que coisas
def main():
'''
Programa que recebe três strings: ´frase´, ´velho´ e ´novo´, e imprime um string
onde todas as ocorrências de ´velho´ foram substituídas por ´novo´.
'''
frase = input("Digite um frase: ")
velho = input("Digite o texto velho: ")
novo = input("Digite o texto novo: ")
lista_palavras = picota(frase, velho)
n = len(lista_palavras)
nova_frase = ""
for i in range(n-1):
nova_frase = nova_frase + lista_palavras[i] + novo
nova_frase += lista_palavras[n-1]
print(nova_frase)
Essa questão é baseada no exercício programa 4.
Dada uma matriz tdorm que representa uma configuração de um
turtledorm diremos que uma matriz tap é uma solução de
tdorm
se o guardião dando tapinhas nas turtles das posições em que a matriz
tap tem um 1 coloca todas as turtles para dormir.
Escreva um programa que inicialmente leia o nome de dois arquivos.
Os dois arquivos contêm matrizes no mesmo formato utilizado no EP4
(ou seja, matrizes quadradas n × n).
O primeiro arquivo contém uma matriz tdorm que representa um
turtledorm.
O segundo arquivo contém uma matriz tap que é uma
candidata a solução de tdorm.
O programa deve imprimir 'SIM' se a matriz tap é
solução de tdorm e imprimir 'NÃO' em caso contrário.
Por exemplo, considere o conteúdo dos seguintes 3 arquivos com
matrizes 3 × 3:
1 1 0 1 0 0 0 0 0
1 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 1
tdorm.txt tap1.txt tap2.txt
A matriz em tap1.txt é solução para o turtledorm em tdorm.txt.
Já a matriz em tap2.txt não é solução para o
turtledorm em tdorm.txt.
Para resolver essa questão você pode utilizar, sem escrevê-la a função
def leia_turtledorm(nome_do_arquivo):
que recebe o nome de um arquivo e retorna a matriz que está no arquivo e representa
um turtledorm ou uma candidata solução.
Caso ache conveniente, escreva e use outras funções adicionais.
def main():
'''
Programa que lê um matriz tdorm representando um turtledorm e uma matriz
tap candidata a solução do tdorm e imprime "SIM" se a matriz tap é solução
de tdorm e imprime "NÃO" em caso contrário.
'''
# leia o matriz com o turtledorm
nome_do_arquivo = input("Digite o nome do arquivo: ")
tdorm = leia_turtledorm(nome_do_arquivo)
# leia a matriz de candidata a solução
nome_do_arquivo = input("Digite a matriz do tapinhas: ")
tapinhas = leia_turtledorm(nome_do_arquivo)
n = len(tdorm)
for lin in range(n):
for col in range(n):
if tapinhas[lin][col] == 1:
atualize_turtledorm(tdorm,lin,col)
if todos_dormindo_no(tdorm):
print("SIM")
else:
print("NAO")
#--------------------------------------------------------------------------
def todos_dormindo_no(tdorm):
''' (matriz) -> bool
Verifica se todos os turtles no turtledorm tdorm estão dormindo.
Retorna True em caso afirmativo e False em caso contrário.
'''
n = len(tdorm)
for i in range(n):
for j in range(n):
if tdorm[i][j] == 1:
return False
return True
#-----------------------------------------------------------------------
def atualize_turtledorm(tdorm, lin, col):
''' (matriz, int, int) -> None
Atualiza a configuração do turtledorm de forma a refletir a mudança de
estados provocado por um tapinha no turtle no cubículo de coordenada (lin,col).
Pré-condição: a função supõe que lin e col são posições validas do tdorm.
'''
# dimensão do tdorm: n x n
n = len(tdorm)
tdorm[lin][col] = 1 - tdorm[lin][col]
# norte
if lin+1 < n: # equivalente a 0 <= lin+1 and lin+1 < n:
tdorm[lin+1][col] = 1 - tdorm[lin+1][col]
# sul
if 0 <= lin-1: # equivalente a 0 <= lin-1 and lin-1 < n:
tdorm[lin-1][col] = 1 - tdorm[lin-1][col]
# leste
if col+1 < n: # equivalente a 0 <= col+1 and col+1 < n:
tdorm[lin][col+1] = 1 - tdorm[lin][col+1]
# oeste
if 0 <= col-1: # equivalente a 0 <= col-1 and col-1 < n:
tdorm[lin][col-1] = 1 - tdorm[lin][col-1]
#-----------------------------------------------------------------------
main()