Harvard CS50: Tarefas da Semana 3 (Aulas 7 e 8), Parte 2

Palestras sobre fundamentos de programação de Harvard CS50 Materiais adicionais: notação assintótica, algoritmos de classificação e pesquisa Tarefas da semana 3, parte 1. Classificação e pesquisa.

O jogo começa!

É hora de jogar! A maioria das pessoas está familiarizada com o jogo de quebra-cabeça "Tag". Para formalizá-lo, “Tag” é um campo bidimensional 4x4, neste campo não existem 16, mas 15 quadrados, ou seja, um slot permanece vazio. Cada um dos quadrados é numerado e pode mover-se horizontalmente ou verticalmente dentro do campo (se, claro, houver espaço para se mover). O objetivo é colocar os números em ordem, de 1 a 15, da esquerda para a direita, de cima para baixo. Então o espaço vazio ficará no canto inferior direito. O movimento de qualquer peça (ou de várias) é um “passo” neste espaço de jogo. A combinação mostrada na imagem acima já está empilhada, mas observe que 12 ou 15 peças podem ser colocadas no espaço vazio. As regras estabelecem que uma peça não pode ser movida diagonalmente ou removida do tabuleiro de jogo. Na verdade, existem muitas configurações para iniciar o jogo (você pode contar quantas exatamente), mas para simplificar, vamos organizar as peças em ordem, da maior para a menor, e deixar um espaço vazio no canto inferior direito do tabuleiro. . A única coisa é que vamos trocar 1 e 2 para que o quebra-cabeça possa ser resolvido. Agora vá para o diretório ~/ do seu ambiente de trabalho , depois /pset3/fifteen e abra quinze.c . Ele contém o código do mecanismo de jogo. A tarefa é adicionar código ao jogo. Mas primeiro vamos compilar nosso “motor” (você provavelmente já sabe como fazer isso). Apesar do jogo não ter terminado, você pode iniciar o aplicativo. Será mais conveniente executá-lo em uma janela de terminal maior que o normal, que pode ser aberta clicando no sinal de mais (+) verde ao lado de uma das guias de código e selecionando Novo Terminal . Ou você pode abrir a janela do terminal em tela inteira clicando no ícone Maximizar no canto superior direito do console. Você vê que algumas coisas funcionam de alguma forma. Mas, na verdade, a maior parte do jogo ainda não foi escrita. E aqui - prepare-se - está a sua saída!

Estudar

Estude o código e os comentários de quinze.ce responda às questões abaixo:

1. Além de uma placa 4x4, que tamanho de campo nosso motor permite?
2. Qual estrutura de dados é o campo do jogo?
3. Qual função é chamada para cumprimentar o jogador no início do jogo?
4. Quais recursos você precisa implementar?
5. Nota: Se você deseja que a verificação automática diga se você respondeu às perguntas corretamente, próximo ao arquivo quinze.c, encontre o arquivo quinze.txt e anote nele as respostas a essas perguntas.

Implementação

Bem, vamos começar a implementar o jogo. Lembre-se, estamos avançando em pequenos passos, não tente fazer tudo de uma vez. Em vez disso, vamos implementar os recursos um de cada vez e garantir que funcionem antes de prosseguir. Em particular, sugerimos que você implemente as funções do jogo na seguinte ordem: init (inicialização), draw (desenhar), mover (dar um passo), ganhar (ganhar). As decisões de design (como quanto espaço inserir entre nossos blocos numéricos) são suas. O campo de jogo deve ser mais ou menos assim: 15 14 13 12 11 10 9 8 7 6 5 4 3 1 2 _ Mais uma vez, observe que na posição inicial, 1 e 2 estão localizados na ordem inversa (isso se aplica ao campo clássico 4x4 se o número de peças for ímpar). Se o número de peças for par e o campo for 3x3, não há necessidade de trocar as duas peças “mais baixas”. 8 7 6 5 4 3 2 1 _ Para testar sua implementação de “Tag”, você precisa tentar reproduzi-los (não se esqueça, você pode sair do programa antes de sua conclusão natural pressionando a combinação de teclas crtl+c). Certifique-se de que o programa funcionará se números incorretos forem inseridos. E lembre-se de que, assim como você automatizou a entrada no find, você pode automatizar o “passo a passo” do jogo. Na verdade, na pasta ~cs50/pset3 existem os arquivos 3x3.txt e 4x4.txt , que contêm todas as sequências de passos para vencer nos campos 3x3 e 4x4. Para testar o programa, por exemplo, usando o primeiro dos arquivos, execute o seguinte comando: ./fifteen 3 < ~cs50/pset3/3x3.txt Configure o argumento necessário para acelerar a animação. E em geral, se quiser, você sempre pode mudar o jogo. Para se divertir com "sequências de escape ANSI", incluindo cores. Dê uma olhada em nossa implementação de clear e confira http://isthe.com/chongo/tech/comp/ansi_escapes.html para aprender novos truques. Se desejar, escreva suas próprias funções ou altere os protótipos das funções que escrevemos. A única limitação é que você não altera a lógica da função principal, caso contrário não poderemos aplicar alguns testes automáticos para confirmar se seu programa está funcionando corretamente. Em particular, main deve retornar 0 se e somente se o usuário resolveu o quebra-cabeça. Valores diferentes de zero devem ser retornados para todas as opções de erro. Se ocorrer algum erro, escreva para nós. Pois bem, se você quiser brincar com a implementação do aplicativo preparado pelos assistentes do CS50, execute o seguinte comando: ~cs50/pset3/fifteen Caso tenha interesse em ver uma implementação mais bacana, com resolução automática de quebra-cabeças, confira a versão “Hacker” do programa: ~cs50/hacker3/fifteen Em vez de inserir um número na janela do jogo, digite a palavra DEUS. Ótimo, não é? Se você quiser verificar oficialmente a exatidão do seu programa com check50, observe que check50 assume que o espaço vazio do campo de jogo é preenchido com 0; se você escolheu um valor diferente, substitua-o por zero para verificação correta. Além disso, check50 pressupõe que você está indexando os campos do quadro na ordem [linha] [coluna], e não no quadro [coluna] [linha]. check50 2015.fall.pset3.fifteen fifteen.c

Saiba mais sobre a implementação das funções do jogo Quinze

• init (inicialização)
• empate
• mover (dar um passo)
• ganhou (ganhou)

iniciar

Nesta função apresentamos o campo de jogo. Para fazer isso, usamos uma matriz bidimensional de inteiros. A dimensão da matriz é MAX x MAX, onde MAX é uma constante que indica o número máximo de blocos que podem caber em uma linha ou coluna de um campo. Assim, precisamos definir a variável int board[MAX][MAX] Porém, lembre-se que o tamanho do campo de jogo é determinado pelo usuário. Portanto, precisamos definir uma variável que indique o tamanho do tabuleiro que o usuário deve inserir. Isso é int d . onde d é a dimensão da placa, d <= MAX. No entanto, em C você não pode alterar o tamanho de um array, então você deve se contentar com o tamanho máximo. No init você precisa colocar os valores no quadro. Leia mais sobre matrizes bidimensionais se ainda não trabalhou com elas. Resumindo, eles possuem dois índices, o primeiro denota o número da linha, o segundo o número da coluna. Para o nosso problema, começamos com o número máximo e terminamos no caso de d = 3 (“Oitos”) com um e um canto vazio. Se ainda tivermos “Tag”, trocamos 1 e 2. O que fazer com o espaço vazio? Nosso array consiste em números inteiros, então o vazio deve ser preenchido com algum número inteiro. Portanto, você deve escolher algum número inteiro para inicializar a peça vazia (ou, no caso de um jogo físico, a ausência de peça). Loops podem ser usados ​​para inicializar o tabuleiro de jogo e preenchê-lo com um conjunto inicial de peças. Fazemos um loop pelos índices i e j, onde board[i][j] é um bloco localizado na linha i e na coluna j. Preenchemos o quadro em ordem decrescente. Se o número de peças (sem as vazias) for ímpar, troque 1 por 2.

empate

Esta função deve imprimir o estado atual do campo de jogo. Lembre-se que podemos ter valores com um ou dois dígitos, portanto para uma formatação bonita após os números de 1 a 9 a função deverá imprimir um espaço ( #s ). Isso pode ser feito usando o espaço reservado %2d . printf (“%2d”, board[i][j]); Também não se esqueça da célula vazia. Selecione o caractere que irá representá-lo (no nosso exemplo, é um sublinhado). A função draw deve desenhar esse caractere assim que você atingir uma célula vazia. Portanto, nosso loop seria mais ou menos assim: for каждой строки for каждого element строки print meaning и пробел print новую строку Lembre-se de que a ordem em que a função draw desenha os blocos na tela deve refletir a ordem em que eles estão no array definido na função init .

mover

Depois de inicializar o campo de jogo e desenhar as posições iniciais das peças, você precisa permitir que o usuário edite a posição das peças, ou seja, faça movimentos. Assim, em Fifteen.c , o programa obtém a saída do usuário, constrói o tabuleiro do jogo e, em seguida, chama a função move e informa qual peça ele deseja mover. Tenha cuidado: você está aplicando a função especificamente ao número na peça, e não à sua posição no tabuleiro (na matriz). Então você precisa encontrar a posição real do ladrilho. Além disso, você só deve permitir que o usuário mova o bloco quando possível. Na imagem acima, só podemos mover as peças de número 2, 5 e 8. Como determinar isso? Pelo valor de uma peça vazia. Portanto, a função move funciona mais ou menos assim:

• Aceita o número do bloco que o usuário deseja mover
• Procura a posição na matriz (no campo de jogo) desta peça
• Lembra a posição de uma peça vazia
• Se um bloco vazio for adjacente a outro que o usuário deseja mover, eles serão trocados na matriz.

ganho

Esta função verifica se o jogo terminou após cada etapa do usuário. Ele retorna verdadeiro se as peças estiverem na ordem correta (incluindo a posição da peça vazia no canto inferior direito). Neste caso, o programa pode ser encerrado. Se as peças ainda estiverem espalhadas, a função retorna false e passa as rédeas para a função move . Como organizar uma inspeção? Como no caso de inicializar e desenhar o quadro - usando dois loops for aninhados. Por exemplo, você pode definir a condição de que cada número subsequente na matriz seja maior que o anterior. Observe qual valor está escrito no bloco vazio. Ou de outra forma - use um contador para ter certeza de que todas as peças estão no lugar, se você puder manuseá-lo e escreva a fórmula para obtê-lo. Desejamos-lhe boa sorte em suas experiências!

Como validar seu código e obter notas

Atenção! Se for importante verificar apenas a exatidão das tarefas, use cs50check. Se você deseja obter notas na plataforma edx, siga o procedimento descrito a seguir. Lembre-se de que este procedimento usa o mesmo cs50check para verificar tarefas. A única diferença é que ele lembra os resultados e calcula a pontuação geral.

1. Faça login no CS50 IDE
2. Perto do canto superior esquerdo do IDE CS50 , onde seu navegador de arquivos está localizado (não na janela do terminal), clique com o botão direito no diretório pset3 e clique em Download . Você deverá ver que o navegador baixou o arquivo pset3.tar.gz .
3. Em uma janela ou guia separada, faça login no CS50 Submit
4. Clique no ícone Enviar no canto superior esquerdo da tela
5. Na lista de pastas à esquerda, clique no diretório Conjunto de problemas 3 e , em seguida, clique no botão Carregar novo envio. É à direita.
6. Na tela que aparece, clique no botão Adicionar arquivos .... Uma janela para selecionar arquivos do seu computador será aberta.
7. Navegue até a pasta onde você salvou pset3.tar.gz. Provavelmente está localizado na pasta Downloads ou onde quer que seu navegador coloque os arquivos por padrão. Ao encontrar pset3.tar.gz , clique nele uma vez para selecioná-lo e clique em Abrir .
8. Clique em Iniciar upload . Seus arquivos serão enviados para servidores CS50 .
9. Na tela que aparece, você deverá ver a janela Nenhum arquivo selecionado . Se você mover o cursor do mouse para a esquerda, verá uma lista de arquivos baixados. Para confirmar, clique em cada um deles. Se não tiver certeza sobre algo, você pode reenviar os arquivos repetindo as mesmas etapas. Você pode fazer isso quantas vezes quiser até o final de 2016.