31
edits
Changes
Técnicas Avançadas de Contagem (view source)
Revision as of 11:36, 8 December 2015
, 11:36, 8 December 2015no edit summary
===='''3. Inclusão – Exclusão'''===
Nós vamos começar a ver, nesta seção, a segunda das duas principais técnicas de contagem abrangida no Capítulo 5 desse texto – O princípio de inclusão e exclusão. Vamos ver como usar Maple para resolver problemas com essa técnica. No cerne do princípio de inclusão e exclusão está a fórmula
==='''4. Funções geradoras'''===
Funções geradoras são ferramentas poderosas para modelar conjuntos de objetos e suas construções. Por exemplo, se um conjunto de objetos é construído a partir de dois outros através da realização de um produto cartesiano de dois conjuntos subjacentes, em seguida, a função geradora para o novo conjunto é muitas vezes apenas o produto das funções geradoras pelos dois conjuntos subjacentes. Assim, saber como um conjunto é construído pode nos ajudar a construir a sua função geradora.
==='''5. Cálculos e como explorá-los'''===
Esta seção apresentará algumas soluções em Maple para alguns dos problemas. Nós nem sempre deve apresentado aqui uma solução completa; em alguns casos, nós apenas sugerimos uma ou duas coisas para você experimentar, e deixar a implementação detalhado para você.
Implementar o crivo de Eratóstenes é um exercício não-trivial em qualquer linguagem de programação, mas Maple torna isso mais fácil do que a maioria.
O crivo produz uma lista de todos os números primos que não excedam um dado número inteiro positivo n. Vamos modelar a lista de números inteiros de 1 a n por um booleano com valores em uma matriz obtida um vetor obtido com o ISPrime. A i-ésima entrada do ISPrime terá o valor verdadeiro se i é um número primo, e false de outra forma. No início do algoritmo, todas as entradas são inicializados como false. Isto corresponde a ter escrito a lista de números de 1 a n, mas não ter tirado nenhum para fora. Para tirar um número, definimos seu valor na matriz o vetor ISPrime para false. Progredindo através do algoritmo detecta a não-primaridade, e entradas serão marcadas como falsas à medida que são descobertos a ser múltiplos. Nosso programa consiste principalmente de três para loops. O primeiro simplesmente inicializa o vetor ISPrime, enquanto o terceiro loop for imprime os resultados. O crivo em si é o meio para o laço. Usamos três novas funções no código. A função do vetor simplesmente cria um vetor não inicializado. A função '''isqrt''' produz uma aproximação inteira da raiz quadrada do seu argumento. O novo recurso mais interessante é a chamada pdo tipo, que testa se seu primeiro argumento tem o tipo de seu segundo argumento. Aqui, está sendo utilizado para testar se o resultado da divisão é um número inteiro, o que determina se eficazmente um número inteiro divide outro. Outra maneira de fazer isso seria usar a função de '''irem''', que resulta no resto depois de dividir seu primeiro argumento pelo seu segundo argumento. irem(5,2); irem(6,2);