fun_ver
(em vários formatos) neste diretório. Este programa simula este jogo entre
dois jogadores (o programa usa o módulo gb_flip
para simular os lances da moeda).
fun_ver_modif.c
, gb_flip.c
e gb_flip.h
e gere um executável
fun_ver_modif
. Veja aqui
como você pode fazer isto. Em particular, você pode usar este Makefile.
fun_ver_modif.c
automaticamente, após ter
escrito o programa fun_ver.w
em CWEB
.
Você deve estudar o programa fun_ver
; use os arquivos fun_ver.dvi
(que pode ser
visualizado com o programa xdvi
no X
), fun_ver.ps
, ou fun_ver.pdf
. Você pode obter o
CWEB
na página acima, juntamente com o manual etc. Para ler
programas em CWEB
, você não precisa saber nada sobre este
sistema, já que a apresentação é bastante intuitiva. De qualquer forma,
você pode consultar um capítulo de umas poucas páginas no livro sobre o Stanford
GraphBase (este é um livro de Knuth de programas
escritos em CWEB
).
fun_ver
estão além do escopo
desta disciplina, mas você deve ser capaz de entender como executá-lo (veja
compila.txt). Só para mencionar, neste
programa usamos um algoritmo famoso de Knuth, Morris e Pratt para
busca de padrões. Se você estiver curioso sobre este problema clássico de
busca de padrões, você pode consultar http://www.dir.univ-rouen.fr/~charras/string/string.html.
fun_ver
para fazer uma
série de experimentos com o jogo Penney-Ante. Observação. Você
não deve se basear muito no programa fun_ver_modif.c
!
Este programa está sendo fornecido apenas como algo com que você pode
experimentar. Os seus programas devem ser escritos `a partir do zero'. Em
princípio, eu poderia ter fornecido apenas executáveis de
fun_ver
.
fun_ver
. Para tanto, você deve observar em
fun_ver
que (a) o gerador de números aleatórios deve ser
inicializado com gb_init_rand(seed)
, onde seed
é a
semente dada, e (b) para gerar 0
ou 1
com
probabilidade 1/2
cada, você deve executar a chamada
gb_unif_rand(2)
. Em fun_ver
, 0
é
identificado com `cara' (H
) e 1
com
`coroa' (T
).
gb_flip
se comporte de forma idêntica em todas as situações.
Para ver se a máquina/ambiente/compilador que você está usando é compatível
com o gb_flip
, você pode executar um pequeno teste, compilando
e rodando o programa test_flip.c
. Veja aqui
o teste que executei na rede Pró-aLinux do IME. (O Makefile deste
diretório é o mesmo que o Makefile usado para gerar o
fun_ver_modif
.)
HTHH
, um inteiro positivo n
e uma semente seed
(para o gerador de números aleatórios).
No caso n = 1
, o seu programa ep3a
deve simular uma
seqüência de lances de uma moeda honesta (i.e., com probabilidade
1/2
de dar tanto cara como coroa) até que o padrão dado ocorra.
O seu programa deve imprimir o comprimento da seqüência de caras e coroas
gerada, isto é, o número de vezes que a moeda foi lançada, até o padrão dado
ocorrer. Veja aqui como o
fun_ver_modif
pode ser usado.
Quando n > 1
, o seu programa ep3a
deve executar
n
experimentos e registrar o resultado (i.e., o número de lances
da moeda) em cada caso. Ele deve imprimir a média destes valores. Por
exemplo, para a entrada HTHH
, seed = 31415
e n
= 10
, o resultado deve ser 32.4
(os resultados dos
10
experimentos são, respectivamente, 48 61 9 46 13 24 66
15 23 19
. Veja aqui). Para a
entrada HTHH
, seed = 31415
e n =
100000
, o resultado deve ser 17.9264
.
p1
e p2
, uma semente
seed
, e um inteiro positivo n
. O seu
programa ep3b
deve simular o jogo Penney-Ante com os dois
padrões dados, usando seed
para inicializar o gerador de
números aleatórios gb_flip
. O programa deve, na verdade,
simular n
jogos com estes padrões (com
gb_flip
inicializado uma única vez, naturalmente).
Ao término destas n
simulações, o programa deve dizer quantas
vezes cada um dos padrões venceu. O programa também deve imprimir a razão
entre o número de vitórias do padrão p1
e n
. Note
que esta razão é uma estimativa para a probabilidade do padrão
p1
ser `melhor' que o padrão p2
neste jogo
(isto é, para a probabilidade de p1
ocorrer antes de
p2
em uma seqüência aleatória).
Escrevamos P(p1, p2)
para a probabilidade do parágrafo anterior.
Existe uma fórmula para esta probabilidade; você pode ver, por exemplo, o
programa fun_ver
. Esta fórmula, devida a J.H. Conway, está além
do escopo desta disciplina, e portanto nós nos contentaremos com as
estimativas que obteremos usando o ep3b
para valores grandes de
n
.
O programa fun_ver_modif
pode ser usado para ver como tais
estimativas se comparam com o resultado teórico. Veja nestes arquivos como
usar este programa: exemplo3b1.txt, exemplo3b2.txt.
O seu programa ep3b
deve ser capaz de obter boas
estimativas experimentais para os valores de P(p1, p2)
para padrões p1
e p2
de comprimento
razoável. Note que, para tanto, o seu programa deve ser o mais
eficiente possível, já que suas estimativas vão ser melhores para
n
maiores.
Executando seu ep3b
para várias entradas, você poderá
classificar padrões de acordo com a sua `eficácia' neste jogo. De
fato, o padrão p1
é `melhor' que o padrão p2
se
P(p1, p2) > 1/2.
Por comodidade, se este for o caso, vamos escrever p1 > p2
.
ep3c
deve receber como entrada inteiros
positivos n
e L
. Aqui, L
será
o comprimento dos padrões que consideraremos. O comprimento de um
padrão é, naturalmente, o número total de H
s e
T
s no padrão; por exemplo, HTHH
tem
comprimento 4. O inteiro n
é o número de vezes que você
deve simular o jogo entre dois padrões para estimar a probabilidade de
vitória de um deles sobre o outro.
A saída de ep3c
deve ser uma lista de triplas (p1,
p2, p3)
de padrões de comprimento L
. Estas
triplas devem satisfazer a seguinte propriedade:
p1 > p2 > p3 > p1
(Veja a definição de >
acima.) O seu programa
ep3c
deve encontrar o maior número possível de tais triplas.
Pode ser útil para o usuário de ep3c
a possibilidade de
pedir apenas o número de tais triplas que ele encontrou, ao invés de
imprimir todas as triplas encontras. Implemente esta opção em seu
ep3c
.
Note que, em particular, uma hipótese subjacente a este enunciado para
ep3c
é que, um tanto surpreendentemente, a relação
>
não é transitiva (se fosse, triplas como
acima não existiriam).
Observação. Para verificar sua saída, veja o arquivo saidaEP3c.txt. O programa que usei para gerar esta
saída é baseado na fórmula de Conway (veja o programa fun_ver
).
ep3d
que procura seqüências longas de
padrões p1, p2, p3,...
satisfazendo
p1 > p2 > p3 > ... > p1.
Tais seqüências de comprimento L
existem, com padrões de
comprimento L
. Será que existem tais seqüências com
muito mais do que L
elementos? Note que o número de
padrões de comprimento L
é 2^L
, que é muito
maior que L
(para valores grandes de L
).
/*********************************************************************** * * Nome do Aluno ... Numero USP ... * * Curso ... Data ... * * Nome do Professor ... * * Exercicio Programa Numero ... * * Compilador usado ... * **********************************************************************/
Last modified: Tue Jun 22 14:29:34 EST 1999