MAC110 - Introdução à Computação

BCC - 1o. Semestre de 1999

Exercício-Programa 1

Nim

Aqueles que assistiram à palestra de divulgação do professor Imre aprenderam um pouco sobre o jogo Nim. Este exercício-programa é sobre este jogo bem conhecido.

As regras deste jogo são bem simples. Podemos definir um jogo para cada inteiro positivo k. Fixe um k positivo. Chamaremos o jogo Nim correspondente de k-Nim.

As possíveis posições do jogo k-Nim são as k-uplas de inteiros não-negativos (n_1, n_2,..., n_k). Temos dois jogadores, chamados, digamos, L e R, que alternam seus lances. Um lance consiste em

escolher um índice i entre 1 e k e
reduzir n_i de pelo menos 1.

Claramente, a soma n_1+n_2+...+n_k diminui de pelo menos 1 a cada lance, e portanto chegamos, em algum momento, à configuração (0,0,...,0). Naturalmente, o jogador que tiver de jogar neste instante, não tem nenhum lance legal a seu dispor. Convencionamos que este jogador perde o jogo. Em outras palavras, o jogador que levar o jogo à situação (0,0,...,0) vence o jogo.

Os seus programas

Você deverá escrever 3 programas, ep1a.c, ep1b.c ep1c.c. Para todos estes programas, você deve assumir que k = 5.

1. ep1a

Este programa deve servir para dois jogadores humanos jogarem o jogo. O programa deve mostrar a situação do jogo a cada instante e deve receber os lances dos jogadores alternadamente. Inicialmente, o programa deve perguntar qual é a configuração inicial (assim como faz o capenguinha) e qual dos dois jogadores será o primeiro jogador. A seguir, o programa deve ler os lances dos dois jogadores alternadamente, verificando a legalidade de cada lance fornecido. Naturalmente, quando um jogador vencer, o programa deve indicar este fato, parabenizar o vitorioso, e terminar sua execução.

Procure escrever este programa de forma que seu uso seja conveniente para os dois jogadores humanos.

2. ep1b

Este programa deve servir para o professor Teoria mostrar suas habilidades nimísticas. Isto é, este programa deve servir para um jogador humano (por exemplo, você) jogar contra o professor Teoria. Para tanto, veja os seguintes arquivos para ver como você pode incorporar em seu programa as funções de protótipo


int lance_prof_Teoria(int n1, int n2, int n3, int n4, int n5, int f);
string mens_prof_Teoria(int n1, int n2, int n3, int n4, int n5);

do professor Teoria.

prof_Teoria.h
prof_Teoria.o (GNU/Linux, 1604 bytes), prof_Teoria.obj (DOGS, 3347 bytes)
prof_Teoria2.o (GNU/Linux, 12200 bytes, versão mais divertida), prof_Teoria2.obj (DOGS, 12703 bytes, versao mais divertida).
Para Borland C++: PT.h (134 bytes) e PT.obj (3945 bytes).
Para Turbo C++: PT.h (134 bytes) e PT.obj (4125 bytes).
ep1exemplo.c
Como compilar na rede do IME; como compilar no djgpp.

Note que, basicamente, este programa ep1b é o mesmo que o programa capenguinha (uma diferença é que o capenguinha não faz verificações sobre a validade dos lances).

3. ep1c

Para este programa, você deve escrever uma função de protótipo


int lance_aluno_brilhante(int n1, int n2, int n3, int n4, int n5, int f);

que jogará contra o professor Teoria. Isto é, o programa ep1c deve receber como entrada os valores dos n_i (como no ep1a e ep1b), deve perguntar qual dos jogadores será o primeiro jogador, e então deve deixar o professor Teoria e a sua função jogarem entre si, até que o jogo termine.

Será que sua função será capaz de derrotar o professor Teoria?

Observações importantes

Data de Entrega: você deve entregar o seu programa até as 18:00 do dia 10 de maio de 1999, na secretaria do Departamento de Ciência da Computação, Sala 256, Bloco A. Se por algum acaso a secretaria fechar antes deste horário, você deve me procurar. Caso não me encontre (e isto é necessário somente neste caso), você deve enviar o seu programa por correio eletrônico para mim, até as 18 horas daquele dia.
Programas entregues com atraso valerão muito pouco.
O EP é estritamente individual. Exercícios semelhantes receberão nota 0.
Exercícios com erros de sintaxe receberão nota 0.
Endente o seu programa sistematicamente. Uma má apresentação do código resultará em nota menor.
Coloque comentários apropriados em seu programa. Programas sem documentação receberão nota baixa.

Coloque um cabeçalho bem informativo, como o seguinte

  /***********************************************************************
   *
   * Nome do Aluno ...            Numero USP ...
   *
   * Curso ...                    Data ...
   *
   * Nome do Professor ...
   *
   * Exercicio Programa Numero ...
   *
   * Compilador usado ...
   *
   **********************************************************************/

Entregue em um envelope (preferencialmente de plástico transparente):
- Um disquete com o código do seu programa. Identifique o disquete com uma etiqueta. Observação. Note que o monitor vai compilar o seu programa, de forma que não é necessário incluir um executável. Se voce tiver familiaridade com estas coisas e o seu programa envolver a compilação separada de vários módulos, você pode incluir um Makefile para facilitar o processo de compilação.
- Uma listagem do programa.
- Quaisquer saídas que você achar importantes (com as respectivas entradas, em forma eletrônica, quando cabível). A abrangência dos seus testes também será considerada na nota. Saber testar bem um programa é também muito importante.
Uma regra básica é a seguinte: do ponto de vista do monitor, quanto mais convenientemente apresentado estiver o seu programa, melhor será a disposição dele para dar uma nota generosa.
Guarde uma cópia de seu material até o fim do semestre!

Página de principal de MAC110 (BCC - 1o. semestre de 1999).

Y. Kohayakawa <yoshi@ime.usp.br>

Last modified: Wed May 5 08:54:39 EST 1999