90
edits
Changes
→Exemplos extras da seção 4.1
(a) Se voce escolher um código de entrada que consiste de uma sequencia de 4 digitos, com números repetidos permitidos, quantos códigos de entrada são possíveis?
(b) Se voce escolher um código de entrada que consiste de uma sequencia de 4 digitos, sem repetir os números, quantos códigos de entrada são possíveis?
'''Solução: ''' Precisa-se preencher os espaços em branco,mas cada espaço deve ser preenchido com inteiros diferentes de 1 a 5.Usando a regra do produto pode ser aplicado 5! = 5x4x3x2x1 = 120 maneiras.
'''EXAMPLE (E3, page 302)'''
Conte os numeros de instruções de impressão nesse algoritmo:
<nowiki>
de i=1 até n
inicio
de k=1 ate n
print hello
fim </nowiki>
'''Solução: ''' Para cada valor de i,tanto o laço do 'j' como o do 'k' sao executados. Assim a cada i, o número de declarações de impressão executado é 2Xn .Portanto o numero total de instruções de impressao executados é 2xn² .
'''EXEMPLO (E4, page 302)'''
Conte os numeros de instruções de impressão nesse algoritmo:
<nowiki>
de i=1 até n
inicio
de k=i+1 ate n
print hello
fim </nowiki>
'''Solução: ''' Para cada valor de i,tanto o laço do 'j' como o do 'k' sao executados. Assim a cada laço do i, o número de declarações de impressão executado é i no primeiro laço mais n-i no segundo laço. Portanto para cada i, o numero de impressoes é i + (n-i) = n.
'''EXEMPLO (E5, pag 306)'''
Encontre o numero de palavras com 10 letras sem repeti-las:
(a) que não tenha vogais.
(b) que começam com uma vogal.
(Cc) que tenha C e V nas extremidades (em qualquer ordem).
(d) que tenha vogais nas duas primeiras posições.
'''Solução: para '''Para resolver o problema é ter em mente uma fila de dez espaços em branco :
a) Cada um dos 10 espaços em branco da cadeia deve conter 1 das 21 consoantes,sem repeti-las.Pela regra do produto: 21 X 20 X 19 X 18 X ... X 12.
c)Primeiramente contamos o número de maneiras de preencher os 10 espaços começando com C e terminando com V,o numero de manerias de preencher as oito letras restantes é 24 x 23 x ... x 18 x 17;
V _ _ _ _ _ _ _ _ C
Logo,pela regra da soma :
d) Primeiramente vamos contar o número de maneiras de colocar as vogais nos dois primeiros espaços em branco.Podemos escolher qualquer uma das 5 vogais para a primeiro espaço e das 4 vogais restantes para o 2 espaço : 5 x 4=20 maneiras de colocar duas vogais nas duas primeiras posições.
Portanto, o número de maneiras de colocar vogais nois dois primeiros espaços e oito letras nos restantes dos espaços é: 5 x 25 x 24 x 23 x ... x 18 x 17
'''EXAMPLE (E6, page 306)'''
10 homens e 10 mulheres estão em uma fila:
(a) encontre quantas possibilidades pode ser formada a fila.
(b) encontre quantas possibilidades pode ser formada a fila se duas pessoas do mesmo sexo não podem ficar lado a lado;
(c) encontre quantas possibilidades pode ser formada a fila se Beryl, Carol, e Darryl querem ficar juntas nesta sequencia (Carol, Beryl, and Darryl; ou Darryl, Beryl, e Carol).
'''Solução:'''
a)Há 20 pessoas;Portanto eles podem ser colocados em uma fila: 20 x 19 x 18 x....x 1 = 20!
b)se duas pessoas do mesmo sexo não podem ficar lado a lado;Entao há dois padroes possiveis, usando M para Masulino e F para Feminino:
Se contar o numero de maneiras de se obter a primeira possibilidade, dobramos ela para chegarmos ao resultado final.O Primeiro homem pode ser escolhido em 10 maneiras, a Primeira mulher pode ser escolhida de 10 Maneiras, o homem Segundo pode ser escolhido de 9 maneiras, etc.Assim,pela regra do produto temos :
10 x 10 x 9 x 9 x ... x 2 x 2 x 1 x 1 ou (10!)² maneiras.
c)Considerando primeiro os arranjos onde Beryl,Carol e Darryl ficam um ao lado do outro,nessa ordem.Colocando as outras 17 pessoas na fileira.o que pode ser feito em 17! Maneiras.Nao importa como as 17 pessoas sao colocadas na fila,Beryl,Carol e Darryl,pode ser inserido,nessa ordem,entre duas das 17, ou então colocado em uma das duas extremidades.
'''EXEMPLO (E7, página 308)'''
Encontre o número de palavras 10 letras :
(a) não contenha vogais.
(b) começar com uma vogal.
(c) ter vogais nas duas primeiras posições.
(d) começar com C e terminam com V.
(e) começar com C ou terminar com V.
a) Cada um dos 10 espaços em branco da cadeia deve conter 1 das 21 consoantes,como podemos repeti-las.Pela regra do produto: 21 X 21 X 21 X 21 X ... X 21 = 21^10 ;
b)Há cinco opções para uma vogal ser colocada na primeira posição, e não há restrições sobre os outros nove letras,por isso : 5 x 26^9
c)Se essas vogais devem estar nas duas primeiras posições e as letras podem ser repetidas, obtém-se o produto: 5² x 26^8
d)Se a palavra tem a forma : C....V existem 26 maneiras para preencher cada uma dos oito espaços. Portanto, há 26^8 palavras desta forma.
e)Precisa-se usar o princípio da inclusão-exclusão para evitar a dupla contagem.Sendo A¹ o conjunto de todas as palavras com 10 letras que começam com C e A² o conjunto de todas as palavras com 10 letras que terminam com V: A¹ U A² = |A¹|+|A²| - |A¹ n A²| = 26^9 + 26^9 - (26^8);