Geraç˜ao de números pseudo-aleatórios

Geracao de numeros pseudo-aleatorios[ePD94, Cap. 5.9-10]

Utilizacao para simulacao e jogos.

Funcao rand()i = rand();

gera um inteiro entre 0 e RAND MAX, com igual probabilidade de ocorrer...

O valor da constante simbolica RAND MAX e o prototipo da funcao encontram-seem <stdlib.h>.

#include <stdlib.h>#include <stdio.h>main() {int i;for(i = 1; i <= 100; i++) printf("%d\n",rand());

}

Usualmente pretendem-se valores noutros intervalos...Se for entre 0 e a-1:

srand() % a

Departamento de Ciencia de Computadores da FCUP — PI — Aula 6 1

Simulacao do lancamento duma moeda:cara 0 e coroa 1

#include <stdlib.h>#include <stdio.h>

main() {int i;for(i=1; i<=10; i++) {if (rand() % 2) printf("Cara\n");else printf("Coroa\n");}

}

Execucao:% moedaCaraCoroaCaraCaraCaraCaraCoroaCoroaCaraCara

A medida que o numero de lancamentos aumenta, o numero de coroas deve serigual ao numero de caras.


Alice e Bob atiram a moeda ao ar

Lancando uma moeda ao ar repetidamente, a Alice ganha o jogo se aparecerprimeiro uma determinada sequencia de tres valores consecutivos e o Bob ganhase aparecer primeiro outra dessas sequencias.

1. A Alice escolhe a sequencia 000 (cara, cara, cara) e o Bob a sequencia 111

2. A Alice escolhe a sequencia 001 (cara, cara, cara) e o Bob a sequencia 011

Quem tem mais probabilidade de ganhar? Isto e, em varios jogos quem ganhamais vezes? Para cada uma das escolhas, serao as sequencias da Alice e do Bobequiprovaveis?

Vamos simular N lancamentos e para cada jogador contabilizar os jogos ganhos equal a sua frequencia (numero de jogos ganhos/ numero de jogos total).


Algoritmo para um jogo

Tem de haver pelo menos 3 lancamentos...

ant2 = rand()% 2ant = rand()% 2Enquanto (1) fazer

t = rand() % 2se saiu a sequencia da Alice (p.e ant2==0 && ant==0 &&t==1)

entao Escreve ‘‘Alice ganha’’ e pararse saiu a sequencia do Bob (p.e ant2==0 && ant==1 &&t==1)

entao Escreve ‘‘Bob ganha’’ e pararant2 = antant = t


Programa em C para MAXJ jogos#include <stdlib.h>#include <stdio.h>#define MAXJ 1000main() {int i, a = 0, b = 0, t, ant, ant2;printf("Alice Bob\n"); printf("---------------\n");for(i=1; i<MAXJ; i++) {ant2 = rand()%2; ant = rand()%2;while (1) {t = rand()%2;if (ant2 == 0 & ant == 0 & t == 1) {a++; break;}else if (ant2 == 0 & ant == 1 & t == 1) {b++; break;}else { ant2 = ant; ant = t;}

}}printf("%2d %2.1f %2d %2.1f\n",a,((float) a / MAXJ), b, ((float) b / MAXJ));

}


Execucao

Alice ganha se aparecer primeiro 000, Bob se aparecer primeiro 111

% aliceAlice Bob---------------516 0.5 483 0.5

Conclusao: Como era de esperar, tem a mesma probabilidade de ganhar!

Alice ganha se aparecer primeiro 001, Bob se aparecer primeiro 011

% aliceAlice Bob---------------655 0.7 344 0.3

Conclusao: Alice tem maior probabilidade de ganhar! Porque? A prova analıticae complicada mas o metodo probabilıstico (de Monte Carlo) permite uma aproxi-macao...


Sementes da geracao de pseudo-aleatoriosSe executarmos varias vezes o programa anterior, a sequencia de valores gerada esempre a mesma! Nao e muito aleatorio!

% alice1Alice Bob---------------655 0.7 344 0.3% alice1Alice Bob---------------655 0.7 344 0.3% alice1Alice Bob---------------655 0.7 344 0.3

Nao foi ”cut&paste”!


Funcao srand()

A funcao rand() gera uma sequencia de valores que se repete igual a si propriasempre que o programa e executado.

Isto, porque, a semente da sequencia e sempre a mesma (1)!

Para que produza-se uma sequencia diferente e necessario, mudar a semente usandoa funcao srand(), cujo argumento inteiro (sem sinal) e a nova semente e que naoretorna nenhum valor.

srand(41);

Se se pretender uma sequencia diferente, sempre que o programa e executado, e outilizador nao seja obrigado a introduzir a semente, podemos usar uma funcao queretorna o valor do relogio do computador em segundos (e cujo prototipo esta emtime.h):

srand(time(NULL));


Numeros aleatorios num intervalo

[ePD94, Cap. 5.9-10]

Para gerar inteiros entre a e a+b-1:

i=a + rand() % b;

Simulacao de lancamentos de um dado

Valores entre 1 e 6: 1 + rand() % 6#include <stdlib.h>#include <stdio.h>main() {int i;for(i = 1; i <= 20; i++) {printf("%3d",1 + (rand() % 6));if (i % 5 == 0) printf("\n");

}}

%cc dado1.c -o dado1% dado1

2 5 4 2 62 5 1 4 23 2 3 2 65 1 1 5 5

%


Determinar a frequencia absoluta de cadanumero de 1 a 6, em 6000 lancamentos

Algoritmo1. Definir um contador para cada um dos valores: f1, f2, f3, f4, f5 e f6.

2. Para cada valor gerado (entre 1 e 6), incrementar o contador correspondente.

main() {int vez, face, f1 = 0, f2 = 0, f3 = 0, f4 = 0, f5 = 0, f6 = 0;for(vez = 1; vez <= 6000; vez++) {face = 1 + (rand() % 6);if (face == 1) ++f1; else if (face == 2) ++f2; else if (face == 3) ++f3;else if (face == 4) ++f4; else if (face == 5) ++f5; else ++f6;}

}printf("1 \t2 \t3 \t4 \t5 \t6 \n\n");printf ("%4d\t%4d\t%4d\t%4d\t%4d\t%4d\t\n",f1,f2,f3,f4,f5,f6);

}


E preferıvel usar uma nova instrucao...main() {int vez, face, f1 = 0, f2 = 0, f3 = 0, f4 = 0, f5 = 0, f6 =0;for(vez=1; vez<=6000; vez++) {face = 1 + (rand() % 6);switch(face) {case 1: ++f1; break;case 2: ++f2; break;case 3: ++f3; break;case 4: ++f4; break;case 5: ++f5; break;default: ++f6}

}printf("1 \t2 \t3 \t4 \t5 \t6 \n\n");printf ("%4d\t%4d\t%4d\t%4d\t%4d\t%4d\t\n",f1,f2,f3,f4,f5,f6);

}


Execucao

Cada um devia ocorrer 1000 vezes...

% cc dados1.c -o dados1% dados11 2 3 4 5 6

980 993 1030 1009 1002 986%


Instrucao de escolha switch[ePD94, Cap. 4.7]

Permite a seleccao de uma de varias alternativas.

switch(Expr){case Exp1: Insts1case Exp2: Insts2...default: Instsd

}

Funcionamento: A Expr e calculada. Se for igual a Exp1, a instrucao Insts1 eexecutada,. . . , etc.Se nao for igual a nenhuma, e executada Instsd.• As expressoes Exp1, Exp2,. . . tem de ser constantes.

• Cada grupo de instrucoes Insts1, Insts2 e normalmente terminado com ainstrucao break. Se nao for, a execucao continua com as instrucoes a frente(nas outras alternativas).

• A parte de default e opcional.




Tipos de inteiros em C

Os inteiros em C podem ser com sinal ou sem sinal:

int i;unsigned int u;

E cada um pode ter varios tamanhos: short ou long

short int i; long int l;unsigned int u; unsigned long g; unsigned short int s;

Os intervalo de numeros que representam tem haver com o numero de bits usadospara representar um int:16, 32 ou 64...


Tipo Valor menor Valor Maior16-bits

short int -32768 32767 (215 − 1)unsigned short int 0 65535 (216 − 1)int -32768 32767unsigned int 0 65535long int -2147483648 2147483647unsigned long int 0 4294967295

32-bitsshort int -32768 32767unsigned short int 0 65535int -2147483648 2147483647 (231 − 1)unsigned int 0 4294967295 (232 − 1)long int -2147483648 2147483647unsigned long int 0 4294967295

Para saber quais os valores do teu sistema, ver em limits.h...


Caracteres e Codigo ASCII(American Standard Code for Information Interchange)

0: ................................16: ................................32: ! " # $ % & ’ ( ) * + , - . /48: 0 1 2 3 4 5 6 7 8 9 : ; < = > ?64: @ A B C D E F G H I J K L M N O80: P Q R S T U V W X Y Z [ \ ] ^ _96: ‘ a b c d e f g h i j k l m n o112: p q r s t u v w x y z { | } ~128: ...............................144: ...............................160: ...............................176: ...............................192: A A A ~A A A Æ C E E E E I I I I208: --D ~N O O O ~O O × Ø U U U U Y lb ß224: a a a ~a a a æ c e e e e ı ı ı ı240: ∂ ~n o o o ~o o ÷ ø u u u u y lb y

Programa que obteve a tabela anterior:


#include <stdio.h>#define LINE 16main() {int c;for(c = 0;c < 256;c++) {if (c % LINE == 0) printf ("\n %3d: ",c);if(c < 32 || (c > 127 && c < 192)) printf(". ");else printf("%c ",c);

}printf("\n\n");

}

O tipo char representa o codigo (ASCII) de um caracter e corresponde a um byte(inteiro de 8-bits).

Pode ser signed (-128 a 127) ou unsigned (0 a 256)...

Na duvida pode-se usar int... apenas se gasta mais memoria...


Uma constante do tipo char e um caracter entre plicas.

Ex: ’a’, ’A’, ’!’, ’0’.

Um caracter tambem pode ser especificado por \nnn onde nnn e representacao emoctal do seu codigo.

#include<stdio.h>main(){int x = 99, y = ’\120’;printf("%c tem o codigo ASCII %d\n",x,x);printf("O codigo ASCII %d (octal %o)

corresponde a %c\n",y,y,y);}

Exercıcio 6.1. Escreva uma tabela dos codigos ASCII de caracteres (superioresa 32) em 4 colunas uma com o caracter e as outras com o seu valor em decimal,hexadecimal e octal, respectivamente. �


Ler e escrever caracteres

O conversor %c permite o scanf e o printf ler e escrever caracteres:

int ch;scanf("%c", &ch);printf("%c",ch);

Por exemplo pode-se ler ate ao fim da linha:

do{scanf("%c", &ch);} while( ch != ’\n’);

Mas ha maneiras mais simples e rapidas de ler e escrever caracteres...


Funcao getchar()

A funcao getchar() le um caracter e retorna um inteiro que e:

• o codigo do caracter, ou

• o valor -1 que corresponde a fim de ficheiro (ou a constante simbolica EOF)

int ch;ch = getchar();while ( getchar() != ’\n’);

Problema 1. Contar a’s

#include<stdio.h>main() {int c, i = 0;while ((c = getchar()) != -1) if (c == ’a’) i++;printf("Foram lidos %d a\’s",i); }


Execucao:

% cc aa.c -o aa% aasagHAGHGHGGAHGghshah y1ty21wjhaajakajkaForam lidos 7 a’s

Problema 2. Contar o numero de vogais de uma sequencia de caracteres

Algoritmo

1. Definir um contador para cada vogal: na, ne, ni, no e nu

2. Para cada caracter lido determinar se e uma vogal e, se for, incrementar ocontador correspondente. Notar que nao vale muito a pena ter uma funcao quedetermine se um caracter e vogal...

3. As vogais minusculas e maiusculas tem codigos diferentes e devem ser ambasconsideradas e tambem se podem contar os restantes caracteres...


Programa

main() {int c, na = 0, ne = 0, ni = 0, no = 0, nu = 0,nc = 0;while((c = getchar()) != EOF) {

switch (c) {case ’a’: case ’A’: ++na; break;case ’e’: case ’E’: ++ne; break;case ’i’: case ’I’: ++ni; break;case ’o’: case ’O’: ++no ;break;case ’u’: case ’U’: ++nu; break;default: ++nc;}

}printf("\n A\t E\t I\t O\t U\t Outros\n\n");printf ("%d\t%d\t%d\t%d\t%d\t\n",na,ne,ni,no,nu,nc);

}% vogais < vogais.cA E I O U Outros25 26 14 10 9 405


Funcao putchar()

A funcao putchar(c) tem como argumento um inteiro (entre 0 e 255) e escreveo caracter cujo codigo e esse inteiro.

Problema 3. Substituir letras maiusculas por minusculas.

int maiuscula(int c) {return (c >= ’A’ && c <= ’Z’); }main(){int c;while((c=getchar())!=-1)if(maiuscula(c))putchar(c+(’a’-’A’)); /* ’a’-’A’ = 32 */

else putchar(c);}

$ cc minus.c -o minus$ minussakU8QWWUINMSA SDHH HDH SJSJKjjjk90986$%%^fqtsaku8qwwuinmsa sdhh hdh sjsjkjjjk90986$%%^fqt


Funcoes para manipular caracteres

Acessiveis incluindo o cabecalho ctype.h.

Funcao Descricao Exemploisalpha(c) Retorna 0 se c nao e uma letra ispalpha(’a’) e 6= 0islower(c) Retorna 0 se c nao e uma letra minuscula ispalpha(’A’) e 0isupper(c) Retorna 0 se c nao e uma letra maiuscula ispalpha(’A’) e 6= 0isdigit(c) Retorna 0 se c nao e um algarismo ispalpha(’5’) e 6= 0isalnum(c) Retorna 0 se c nao e uma letra nem um

algarismoispalnum(’?’) e 0

isspace(c) Retorna 0 se c nao e um dos caracteresbrancos ((’ ’,\n,\t,\r,\f))

isspace(’ ’) e 6= 0

tolower(c) Se c e uma letra maiuscula, retorna aminuscula correspondente, sao retorna oproprio caracter

tolower(’A’) e ’a’

toupper(c) Se c e uma letra minuscula, retorna amaiuscula correspondente, sao retorna oproprio caracter

toupper(’a’) e ’A’


A minha versao do Word Count (wc)

Exercıcio 6.2. Contar o numero de caracteres, linhas e palavras dum ficheiro�Para o algoritmo:

1. contador de caracteres, nc: para cada caracter lido e incrementado;

2. cada linha termina com um caracter \n: contar a ocorrencia desses caracteres(nl).

3. Uma palavra e uma sequencia de caracteres entre brancos. Vamos usar a funcaoisspace().

Como contar palavras?Considerar dois estados: FORA e DENTRO duma palavra.Quando se esta FORA e aparece um caracter que nao e um branco, passa-se aDENTRO e incrementa-se o contador.Se se esta DENTRO, passa-se a FORAquando se encontra um branco. Dois ou mais brancos consecutivos nao definempalavras. Contador: np


Algoritmo:Para cada caracter lido (diferente de -1), incrementar nc, se o caracterfor \n, incrementar nl; se for um separador, o estado e FORA, senao se o estadofosse FORA passa a DENTRO e incrementa np.

#include <stdio.h>#include<ctype.h>#define DENTRO 0#define FORA 1main() {char c;int nc = 0, np = 0 ,nl = 0 , estado = FORA;while((c=getchar()) != -1) {++nc;if (c ==’\n’) ++nl;if (isspace(c)) estado = FORA;else if (estado == FORA) { estado = DENTRO; ++np; }

}printf("\n Caracteres: %d\n Palavras: %d \n Linhas: %d \n",nc,np,nl);

}


Execucao e comparacao com o comando wc do UNIX:

%cc contapal.c -o contapal% contapal < contapal.c

Caracteres: 519Palavras: 76Linhas: 25% wc < contapal.c

25 76 519%

Exercıcio 6.3. Reescreve o programa anterior sem usar as variaveis de estadoe, usando eventualmente um outro ciclo interior. �


Leituras

[ePD94, Cap. 4.7,5.9-10]


Referencias

[ePD94] H.M. Deitel e P.J. Deitel. C:How to Program. Prentice Hall InternationalEditions, 2 edition, 1994.


Documents

Geraç˜ao de números pseudo-aleatórios