Buscar

lista 04 Principios de contagem

Faça como milhares de estudantes: teste grátis o Passei Direto

Esse e outros conteúdos desbloqueados

16 milhões de materiais de várias disciplinas

Impressão de materiais

Agora você pode testar o

Passei Direto grátis

Faça como milhares de estudantes: teste grátis o Passei Direto

Esse e outros conteúdos desbloqueados

16 milhões de materiais de várias disciplinas

Impressão de materiais

Agora você pode testar o

Passei Direto grátis

Faça como milhares de estudantes: teste grátis o Passei Direto

Esse e outros conteúdos desbloqueados

16 milhões de materiais de várias disciplinas

Impressão de materiais

Agora você pode testar o

Passei Direto grátis

Você viu 3, do total de 6 páginas

Faça como milhares de estudantes: teste grátis o Passei Direto

Esse e outros conteúdos desbloqueados

16 milhões de materiais de várias disciplinas

Impressão de materiais

Agora você pode testar o

Passei Direto grátis

Faça como milhares de estudantes: teste grátis o Passei Direto

Esse e outros conteúdos desbloqueados

16 milhões de materiais de várias disciplinas

Impressão de materiais

Agora você pode testar o

Passei Direto grátis

Faça como milhares de estudantes: teste grátis o Passei Direto

Esse e outros conteúdos desbloqueados

16 milhões de materiais de várias disciplinas

Impressão de materiais

Agora você pode testar o

Passei Direto grátis

Você viu 6, do total de 6 páginas

Prévia do material em texto

FACULDADE ESTACIO DO RECIFE. 
CURSO SISTEMAS DE INFORMAÇÃO/ADS 
MATEMATICA APLICADA A COMPUTAÇÃO 
LISTA 04: PRINCÍPIOS DE CONTAGEM: como contar? 
 
 A Combinatória é a parte da matemática que tem como objetivo o estudo de problemas de 
contagem do número de agrupamentos que podem ser obtidos com os elementos de um dado conjunto. Fazer 
contagem é uma tarefa que temos em diversas situações. Por exemplo, quando queremos dimensionar 
quantos espaços um banco de dados consome, quantos usuários a configuração de um computador suporta, 
quantos cálculos certo algoritmo resolve, quantas linhas tem a tabela-verdade de uma proposição composta 
por n proposições simples, quantas senhas de acesso a um caixa eletrônico podem ser formadas, com quatro 
algarismos, entre outros casos. 
 
 Inicialmente, o que é uma lista? 
 
7.1 LISTAS – Uma lista é uma seqüência ordenada de objetos. Para escrevermos uma lista, escrevemos 
os seus elementos entre parênteses. Por exemplo, (2, a ,3, X ) é uma lista cujo primeiro elemento é 2, o 
segundo é a, o terceiro é 3 e o quarto elemento é X. Isso significa que a ordem em que os elementos figuram 
na lista é relevante: a lista (a, c, h) é diferente da lista (c, a, h). Além disso, uma lista pode conter elementos 
repetidos: (1, a , 2, 2 ). 
 
O número de elementos de uma lista é dito comprimento da lista. A lista (1, a, 2, 2 ) tem comprimento 4. 
Uma lista de comprimento 2 é chamada de par ordenado, como por exemplo, (1,2). Claro que ( ) é uma 
lista vazia, de comprimento 0. 
 
Dizemos que duas listas são iguais se tem o mesmo comprimento e se os elementos nas posições 
correspondentes são iguais. 
 
Exemplo 7.1. 1 
a) Senha numérica com quatro algarismos é uma lista de comprimento 4. 
b) CPF é uma lista de comprimento 11. 
c) Matricula de aluno de uma faculdade: 2015 2 169 034 é uma lista de comprimento 11. 
d) O Código de Endereçamento Postal – CEP é uma lista de comprimento 8 (Veja exercício 15). 
 
Como se calcula o número de listas? 
O cálculo é feito por meio de princípios de contagem. Estudaremos dois deles. 
 
7.2. PRINCÍPIO MULTIPLICATIVO: contagem de listas de comprimento dois. 
 
Considere as listas de dois elementos em que o primeiro pode ser escolhido de n maneiras e, para 
cada uma dessas escolhas, há m escolhas do segundo elemento da lista. Então, o número de listas 
de comprimento dois é n.m. 
 
Exemplo 7.2.1. Com os números 1, 2, 3, 4 e 5 podemos formar quantas dezenas? 
Uma dezena é uma lista de comprimento dois, constituída por dois algarismos, escolhidos dentre 1, 2, 3, 4 
e 5. Assim, queremos formar listas do tipo (x, y). Temos 5 escolhas para o primeiro elemento x e, para cada 
escolha do primeiro, existem, 5 escolhas para o segundo elemento. Logo, podemos formar 5 x 5 = 25 
dezenas. 
 
Exemplo 7. 2. 2. Suponha agora que queremos formar dezenas de dois algarismos diferentes com os 
algarismos 1, 2, 3, 4 e 5. A escolha do primeiro elemento do par pode ser feita de 5 maneiras. Escolhido o 
primeiro, restam 4 escolhas para o segundo elemento da lista. De modo que, podemos formar 5 x 4 = 20 
listas de comprimento 2 , com elementos distintos. 
 
Exemplo 7. 2. 3. Uma seqüência de dois bits é uma lista de comprimento dois formada por ZERO (0) e UM 
(1) de comprimento dois. Podemos formar 2 x 2 = 4 listas: 00, 01, 10 e 11. 
 
 E quando as listas têm comprimento maior do que dois? Como é feito o cálculo delas? 
7.3 LISTAS DE COMPRIMENTO MAIOR DO QUE DOIS. 
 
Suponhamos que temos n elementos e queremos formar listas de comprimento k. O primeiro elemento da 
lista pode ser escolhido de n formas diferentes, o segundo também de n maneiras diferentes e, assim, até o k-
ésimo elemento que pode ser escolhido de n maneiras. Logo, a quantidade de listas será 
 
 
  
Fatoresk 
........n n.n n ..n
= n
k
 
 
 
Exemplo 7.3.1. Um número binário é uma lista de ZERO e UM. Um número binário com 8 dígitos é 
chamado “byte”. 
a) Quantos “bytes” podem-se formar? 
 Como um byte é uma lista de comprimento 8 tal que cada posição pode ser ocupada por zero (0) ou um 
(1), podemos formar 2 x 2 x 2 x 2 x 2 x 2 x 2 x 2 = 2
8
 =256 bytes. 
 
b) Quantos bytes começam por 10 e terminam por 01? 
 As duas primeiras posições e as duas últimas são ocupadas cada uma delas por um único determinado bit, 
então podemos formar 1x1x 2 x 2x 2 x 2 x 1x1= 16 bytes 
c) Quantos bytes começam por 10 e não terminam por 01? 
 Existe apenas uma maneira de preencher as duas primeiras posições e três maneiras de preencher as duas 
últimas: 00,10 e 11. De modo que podemos formar 1x2x2x2x2x3 = 48 bytes. 
 
Exemplo 7.3.2. Os aeroportos, embora tendo nomes diferentes, têm códigos de três letras. Por exemplo, o 
aeroporto que serve Recife é REC, o aeroporto que serve São Paulo (Guarulhos) é GRU e o que serve 
Brasília é BSB. Com as 26 letras do nosso alfabeto podemos formar 26.26.26 = 26
3
 códigos diferentes. 
 
Quando as listas têm repetição de elementos, como se processa o seu cálculo? 
 
7.4 LISTAS DE COMPRIMENTO K SEM REPETIÇÀO DE ELEMENTOS. 
 
Agora, dispondo de n elementos, se queremos formar listas de k elementos (k  n ) , sem repetições, 
procedemos assim: temos n escolhas para o 1º elemento da lista, n-1 escolhas para o 2º elemento da lista, n-2 
escolhas para o 3º, e finalmente n- (k-1) escolhas para o k
o
 elemento da lista. De modo que podemos formar 
 
n x (n-1) x (n-2) x .... x (n – (k-1) ) listas de comprimento k. 
 
 
Exemplo 7.4.1. As placas de licença de carros em 
certo estado dos Estados Unidos consistem em sete elementos: os três primeiros são letras maiúsculas (A-Z) 
e os quatro últimos são algarismos (0-9). Podemos formar 26
3
x10
4
 placas distintas, das quais 
26x25x24x10x9x8x7 são placas em que nenhum elemento é repetido. 
 
7.5. PRINCÍPIO ADITIVO – Se dois eventos A e B disjuntos (não ocorrem simultaneamente) tem n e 
m possibilidades, respectivamente, então, o número total de possibilidades para o evento A ou B é m + n. 
Exemplo 7.5.1. Se A é o evento de escolher um número primo entre 10 e 20 inclusive e B escolher um 
número par entre 10 e 20 inclusive, de quantas maneiras podemos escolher um número primo ou um número 
par entre 10 e 20, inclusive? 
Bom, A = {11, 13, 17, 19} e B = {10, 12, 14, 16, 18, 20}, então (AB) = A + B = 4 + 6 = 10. 
 
O Princípio Aditivo pode ser usado apenas quando os eventos são 
disjuntos, isto é, quando não houver possibilidade em comum. 
 
Os dois princípios podem ser usados simultaneamente num problema? Sim, veja o seguinte exemplo. 
 
Exemplo 7.5.2. Uma rede de computadores é constituída por quatro nodos (ou nós): 1, 2, 3 e 4. Existem dois 
caminhos entre 1 e 3, dois entre 2 e 4, três entre 1 e 2 e quatro entre 3 e 4. Uma mensagem pode ser enviada 
do nodo 1 para o nodo 4 por meio 3.2 + 2.4 = 6 + 8 = 14 caminhos distintos. Observe que os caminhos do 
nó 1 até o nó 4, indo pelo nó 2 ou nó 3, são eventos disjuntos. 
 
 
 
Exemplo 7.5.3. As variáveis A, i, j e k no programa seguinte são variáveis inteiras. Qual o valor de A após 
o seguinte código ter sido executado? 
 A: = 0for i: = 1 to 10 do 
 A: = A + 1; 
 for j: = 1 to 9 do 
 A: = A + 1; 
 for: = 1 to 8 do 
 A: = A + 1; 
 No primeiro for a variável A recebe o acréscimo +1 no total de 10 vezes, no segundo for, 9 
vezes e no terceiro for, 8 vezes. De modo que ao final, da execução do programa o valor da variável A será 
A = 0 + (10+9+8).1 = 0 + 27 = 27 
 
Exemplo 7.5.4. Qual o valor de A após o seguinte código ter sido executado? As variáveis A, i, j, e k são 
inteiras. 
 A : = 100 
 for i : = 1 to 10 do 
 for j: = 1 to 9 do 
 for k : = 1 to 8 do 
 A: = A + 1; 
 end; 
 end; 
 end; 
 Em cada for, a variável A é incrementada de 1 unidade, de modo que ao final da execução dos três for, 
teremos 10.9.8 incrementos de 1 unidade ao valor de A. Assim, teremos A = 100 + (10.9.8).1 = 100 + 720 = 
820 
 
APRENDA PRATICANDO: EXERCÍCIO PROPOSTO 7.1 
 
 Bem, agora é a sua vez! Verifique se você entendeu os assuntos desse capítulo, resolvendo os 
exercícios propostos. As respostas dos exercícios de número par serão apresentadas logo a seguir. Se tiver 
dúvidas, tente esclarecê-las com os seus colegas. 
 
1. O número de telefone no país X é composto de dez algarismos, onde o primeiro não pode ser nem ZERO 
nem UM. Quantos telefones são possíveis? 
 
2. Um número de inscrição no Seguro Social de um país X é composto de nove algarismos (0-9). 
a) Quantos números de Seguro Social são possíveis? 
b) Quantos deles são números pares? 
c) Quantos têm todos os algarismos números pares ? 
d) Quantos podem ser lidos igualmente para trás e para frente (por exemplo, 122070221)? 
e) Quantos não têm nenhum dos seus algarismos igual a 8 ? 
f) Quantos têm exatamente um algarismo igual a 8 ? 
g) Quantos têm ao menos um algarismo igual a 8 ? 
 
3. Um sistema de computador permite atribuir nomes aos arquivos utilizando qualquer combinação de 
letras maiúsculas (A-Z) e de algarismos (0-9), mas o número de caracteres no nome deve ser no máximo 
oito (e deve haver ao menos um caractere no nome do arquivo). Por exemplo, A423, WJ, 4AA e 
CDEF4321 são nomes de arquivo válidos, mas J-31 e TURBINADA não são válidos. Quantos nomes de 
arquivo diferentes podem ser formados nesse sistema? 
 
4. Uma prateleira contém 20 livros. De quantas maneiras diferentes esses livros podem ser dispostos na 
prateleira? 
 
5. Um compact disc player tem espaço para 5 CDs; há cinco bandejas numeradas de 1 a 5 em que se 
colocam os CDs. Possuo 50 CDs. 
a) De quantas maneiras o CD player pode ser carregado, se todas as bandejas são ocupadas por CDs ? 
b) De quantas maneiras o CD player pode ser carregado se eu coloco apenas um CD no 
 aparelho? 
 
6. Uma prova de múltipla-escolha tem 15 perguntas, cada qual com quatro respostas possíveis, e 15 
perguntas adicionais, cada uma das quais com cinco respostas possíveis. Quantas folhas de respostas 
diferentes são possíveis ? 
 
 
7. Uma senha de um usuário em um computador de grande porte consiste em três letras seguidas de dois 
dígitos. Quantas senhas diferentes são possíveis (considere o alfabeto com 26 letras)? 
 
8. Quantas senhas são possíveis, na questão anterior, se diferenciarmos as letras maiúsculas das 
minúsculas? 
 
 
9. Quantos números de CPF são possíveis? 
 
 
 
10. Uma pessoa pode viajar no trecho Recife/Natal/Recife de ônibus, automóvel, avião, navio ou trem. Se o 
meio de transporte da ida não é o mesmo da volta, de quantas maneiras essa pessoa pode realizar a 
viagem? 
 
11. Um alfabeto consiste em três letras: A, B, C. Nessa língua, uma palavra é uma seqüência arbitrária de no 
máximo três letras. Quantas palavras existem nessa língua? 
 
 
12. Qual o valor de A após o seguinte código ter sido executado? As variáveis A, i, j e k são inteiras. 
 A: = 1 
 for i: = 1 to 10 do 
 for j: = 1 to 9 do 
 for k: = 1 to 8 do 
 A:= A + 2; 
 end; 
 end; 
 end; 
 
 
 
13. Qual o valor de A após o seguinte código ter sido executado? 
A: = 100 
for i: = 1 to 10 do 
 A := A - 1; 
for j: = 1 to 20 do 
 A: = A - 1 
for k : = 1 to 30 do 
 A= A - 1; 
 end; 
 
14. Qual o valor de A após o seguinte código ter sido executado? 
 A: = 1 
 for i : = 2 to 12 do 
 for j: = 3 to 11 do 
 for k : = 10 downto 1 do 
 A: = A + 2; 
 end; 
 end; 
 end; 
 
15. O Código de Endereçamento Postal ( CEP:      -    ) usado no Brasil tem como objetivo 
principal orientar e acelerar o tratamento e distribuição de objetos de correspondência. É constituído de 8 
dígitos, cada um variando de 0 a 9, de modo que o 1º dígito representa a Região do Brasil, o 2º a Sub-região, 
o 3º o Setor, o 4º o Sub-setor, o 5º o Divisor de Sub-setor e os três últimos, recebem o nome de Sufixo e 
destinam-se à identificação individual de localidades, Caixas Postais Comunitárias, Logradouros, códigos 
especiais., etc. 
 
 Região  Sub-Região Setor Sub-setor Div de Setor  Sufixo Sufixo Sufixo 
 
 a) Quantos são os CEP’s possíveis ? 
 b) Quantos são os CEP’s são possíveis para atender à região 3 (Sede em Salvador) 
 c) Quantos são os CEP’s são possíveis para atender à região 5 (Sede em Recife) ? 
 
16. Um cofre tem três discos, cada um com as mesmas 26 letras e só pode ser aberto quando se colocar uma 
determinada letra de cada um dos discos numa determinada posição. Supondo que se ignora o segredo do 
cofre, de quantas maneiras diferentes se podem colocar as letras dos discos nas referidas posições ?17. Quantos números diferentes de 3 algarismos podemos formar com os algarismos 1, 3 e 9 no sistema 
decimal. ? 
 
18. Quantos números de quatro algarismos podemos formar com os algarismos 0, 2, 4, 6 e 8 no sistema 
decimal? Resp 
19. Com cinco pedaços de tecidos nas cores amarela, azul, verde, vermelho e branco, quantas 
bandeiras tricolores podemos formar supondo que os tecidos são colocados só em tiras verticais? 
 
20. Uma senha de computador é constituída por seis caracteres: três letras (de 26 letras) seguidas de três 
dígitos (de 0-9). Determinar o número de senhas possíveis, nos seguintes casos: 
a) tanto as letras como os dígitos podem ser repetidos; 
b) os dígitos não podem ser repetidos; 
c) as letras não podem ser repetidos; 
d) nem as letras nem os dígitos podem ser repetidos. 
21. Quantas senhas são possíveis no exercício anterior se elas apresentam as três letras e os três dígitos de 
forma alternada: LDLDLD ou DLDLDL? 
22. Com os dígitos 0, 1, 2, 5 e 8, quantos números de quatro algarismos diferentes podemos formar? 
Quantos são múltiplos de 5 ? Quantos são múltiplos de 10? 
23. Os clientes de uma livraria virtual são todos cadastrados ao criarem uma senha de quatro ou cinco 
dígitos, seguindo as seguintes instruções: a senha deve conter apenas vogais ou os algarismos 1, 2, 3; o 
primeiro e o último dígitos devem ser vogais; os caracteres não podem ser repetidos. Quantos clientes 
podem ser cadastrados com senha, segundo este procedimento, sabendo que a cada cliente corresponde uma 
senha e a cada senha corresponde um único cliente? Resp 3.000 
 
24. Um pacote de dados tramita de um ponto A a um ponto B passando por 2 roteadores R1 e R2, nessa 
ordem. Sabe-se que existem 3 rotas de A até R1, 3 rotas de R1 a R2 e 4 rotas de R2 a B. 
Quantos caminhos distintos esse pacote pode percorrer de A até B? Resp 36 
 
 
25. Pretendo colocar um roteador wireless em cada uma das 4 salas do meu escritório. O site da empresa 
onde será feita a compra, oferece 8 modelos distintos. De quantas maneiras distintas pode ser feita essa 
compra? Resp. 70 
 
 
RESPOSTA DO EXERCÍCIO 7.1 
 
2) a) 109 b) 5x108 c) 59 d) 105 e) 9.98=99 f) 99 g) 109 – 99 
4) 20x19x18x17x....x2x1 = 20! 
6) 420x 510 8) 523x102 10) 20 12) 1441 
14) 902 
16) 263 
18) 4.53=500 
20) a) 263x 103 b) 263x10x9x8 c) 26x25x24x103 d) 26x25x24x10x9x8 
22) a) 96 b) 42 c) 24

Outros materiais