Ferramentas de Utilizador
inf05016:2013-2-trabalhos
Diferenças
Esta página mostra as diferenças entre as duas revisões da página.
| Ambos os lados da revisão anterior Revisão anterior Próxima revisão | Revisão anterior | ||
|
inf05016:2013-2-trabalhos [2013/11/11 10:10] marcus [Entregas] |
inf05016:2013-2-trabalhos [2013/12/09 09:36] (Actual) marcus [Entregas] |
||
|---|---|---|---|
| Linha 2: | Linha 2: | ||
| ==== Entregas ==== | ==== Entregas ==== | ||
| - | Atualizado: 11/11/2013 | + | Atualizado: 9/12/2013 |
| - | ^ Cartão ^ T1 ^ T2 ^ T3 ^ T4 ^ T5 ^ | + | ^ Cartão ^ T1 ^ T2 ^ T3 ^ T4 ^ T5 ^ T6 ^ |
| - | | 23333 | P | P | P | R | R | | + | | 23333 | P | P | P | P | P | P | |
| - | | 106962 | P | P | | R | R | | + | | 106962 | P | P | | P | P | | |
| - | | 118775 | | | | | | | + | | 118775 | | | | | | | |
| - | | 136465 | | | | | | | + | | 136465 | | | | | | | |
| - | | 143287 | P | P | P | R | R | | + | | 143287 | P | P | P | P | P | | |
| - | | 145608 | P | P | P | R | R | | + | | 145608 | P | P | P | P | P | | |
| - | | 158921 | P | P | | R | | | + | | 158921 | P | P | | P | P | P | |
| - | | 159033 | P | P | P | R | R | | + | | 159033 | P | P | P | P | P | | |
| - | | 173897 | P | P | P | R | R | | + | | 173897 | P | P | P | P | P | P | |
| - | | 180190 | | | | | | | + | | 180190 | | | | | | | |
| - | | 191935 | P | P | P | R | R | | + | | 191935 | P | P | P | P | P | P | |
| - | | 195836 | P | P | P | R | R | | + | | 195836 | P | P | P | P | P | | |
| - | | 205978 | P | P | P | R | | | + | | 205978 | P | P | P | P | | | |
| - | | 208669 | P | P | P | R | R | | + | | 208669 | P | P | P | P | P | | |
| - | | 236521 | P | P | P | R | R | | + | | 236521 | P | P | P | P | P | P | |
| - | | 237015 | | | | | | | + | | 237015 | | | | | | | |
| R = recebido | R = recebido | ||
| Linha 372: | Linha 372: | ||
| representa uma chave a inserir e m linhas que contém um número inteiro que representa uma consulta. O algoritmo deve imprimir na saida padrão (stdout) m linhas que contém o resultado dos m lookups: 0 para uma chave que não pertence a tabela hash, e 1 caso contrário. | representa uma chave a inserir e m linhas que contém um número inteiro que representa uma consulta. O algoritmo deve imprimir na saida padrão (stdout) m linhas que contém o resultado dos m lookups: 0 para uma chave que não pertence a tabela hash, e 1 caso contrário. | ||
| + | ==== Trabalho 6 (Teste de primalidade) ==== | ||
| + | |||
| + | Entrega: 04/12/2013 | ||
| + | |||
| + | === Objetivos === | ||
| + | * Implementar o teste de primalidade de Miller & Rabin | ||
| + | * Analisar a complexidade do algoritmo em função de log_2(n) experimentalmente. | ||
| + | * Analisar a probabilidade de responder erradamente "sim" experimentalmente. | ||
| + | * Observação: o trabalho é opcional (i.e. só contam os cinco melhores trabalhos entregues). | ||
| + | |||
| + | === Casos de teste === | ||
| + | * Números inteiros positivos aleatórios. | ||
| + | |||
| + | === Convenções === | ||
| + | * As implementações do algoritmo devem ler um número decimal com até 1000 dígitos da entrada padrão e imprimir "s" na saída padrão caso o número é considerado primo e "n" caso contrário. | ||
| + | |||
| + | === Dicas === | ||
| + | * Usa a biblioteca {{http://gmplib.org|GNU MP}} para representar números grandes. Ela tem interfaces para {{http://en.wikipedia.org/wiki/GNU_Multiple_Precision_Arithmetic_Library#Language_bindings|diversas linguagens}} de programação. Um exemplo em C++: | ||
| + | <code c++> | ||
| + | #include <iostream> | ||
| + | using namespace std; | ||
| + | |||
| + | #include <gmpxx.h> | ||
| + | |||
| + | int main(int argc, char *argv[]) { | ||
| + | mpz_class a; | ||
| + | cin >> a; | ||
| + | cout << "O quadrado de " << a << " é " << a*a << endl; | ||
| + | } | ||
| + | </code> | ||
inf05016/2013-2-trabalhos.1384171848.txt.gz · Esta página foi modificada pela última vez em: 2013/11/11 10:10 por marcus
Ferramentas de Página
Excepto menção em contrário, o conteúdo neste wiki está sob a seguinte licença: CC Attribution-Noncommercial-Share Alike 4.0 International
