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.
n
5 × 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 venceuEscreva 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.txtA 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()