Universidade Federal de Santa Maria
Departamento de Eletrônica e Computação
Disciplina: Preparação para Maratona de Programação I - ELC1096
Prof. Cesar Tadeu Pozzer
18/05/2012
Fundamentos Matemáticos
1. Números primos
O que são números primos? São números divisíveis por 1 e por ele mesmo
Quais são os primos?
[0..100] – 25 primos
[0..1000] – 168 primos
[0..10000] – 1229 primos
Como determinar se um número é primo?
1 – Algoritmo naive – O(n)
Testa a divisão de todos os números inteiros k até n.
2 – Algoritmo naive – O(n/2) = O(n)
Testa a divisão de todos os números inteiros k até n/2, pois se k for maior que n/2, o valor da divisão é
menor que 2
3 – até a √ – O(√)
Testa a divisão de todos os números inteiros k até √. Se N é divisível por p, então N = p x q. Se q for
menor que p, significa que ele já foi testado anteriormente, e a divisão produziu resto zero.
4 – Dividir somente pelos impares – somente o 2 é par e é impar O( ) =O(√)
Somente o número 2 é par.
5 – Sieve (peneira, separador) de Eratosthenes
Cria um vetor de 0 a N indicando se o dado número é primo ou não. Indicado para números não muito
grandes.
6 – Divisão por primos
Se um numero N não for divisível por nenhum primo p < √, entãoeleéumprimo
7 – Fatores Primos
Algoritmo Sieve + Divisão por Primos
#include <bitset>
#include <vector>
#define SIEVE_SIZE 100000 //10 Mi
using namespace std;
vector<int> primes;
bitset<SIEVE_SIZE+1> bs; //se o valor for 0, nao eh primo.
//cria:
// - um vetor com tamanho SIEVE_SIZE com valores bool: primo ou nao primo
// - um vetor com os numeros primos.
void sieve()
{
long long i, j, max = SIEVE_SIZE + 1;
bs.reset();
bs.flip();
bs.set(0, false);
bs.set(1, false);
for( i=2; i <= max; i++ )//poderia ser até raiz(Max) se não tivesse o vetor primes.
{
if( bs.test(i) == true ) // i é primo, e todos os múltiplos de i nao
{
primes.push_back( (int)i );
for( j = i*i; j <= max; j += i )
{
bs.set(j, false);
}
}
}
}
//deve-se garantir que p não é maior que raiz(max(primes[]))
bool isPrime(long long p)
{
if( p < SIEVE_SIZE )
return bs.test(p);
for(int i=0; i < primes.size()-1; i++)
{
if( p % primes[i] == 0 )
return false;
}
return true;
}
Exercícios
1. Programa para contar o número de primos em intervalos de inteiros
2. Determinar até que valor de N o algoritmo Sieve tem vantagem
3. Testar se, caso um número não seja divisível por um primo, também não é divisível por múltiplos desse
primo.
4. Qual algoritmo é mais rápido: O( ), 1ú#$ $%
5. Determinar o tamanho do sieve adequado para cada problema.
Questões de maratonas – UVA 294, 406 (Prime Cuts), 516, 524 (Prime Ring Problem), 543, 583, 686, 897, 914,
993, 10006, 10042, 10140, 10200, 10235, 10311, 10394, etc.
2. Fibonacci
Os números de Fibonacci são definidos por:
Fib(0) = 0, fib (1) = 1, fib(n) = fib(n-1)+fib(n-2) para n > 1
Ou seja, 0, 1, 2, 3, 5, 8, 13, 21, etc.
Teorema de Zeckendorf: Qualquer número inteiro positivo pode ser escrito como a soma de um ou mais
números de Fibonacci distintos e não consecutivos. O fato dos números não serem consecutivos pode ser
facilmente observada a partir da definição de Fibonacci. Se o numero for expresso pela sola de dois
consecutivos, então pode ser expresso pelo próximo número da sequencia.
Problemas: UVA 948 (Fibonaccimal Base), 10183, 10229, 763, 11000, etc.
3. Fatorial
Fatorial de um número n é definido como fat(n) = n x fat(n-1).
Problemas: Uva 324, 160, 884, etc.
4. MMC e MDC
O Maior Divisor Comum (GCD) de dois números (a,b) é expresso como o maior número inteiro que divide a e b
sem gerar resto. Como exemplo, GCD(20,12) = 4, pois os divisores são 1, 2 e 4. Para GCD(24,12)=12, pois os
divisores são 1, 2, 4 e 12. Para GCD(3,7) = 1, pois é o único divisor.
Os seguintes algoritmos calculam o GCD. Ambos são muito rápidos, pois fazem muito poucas iterações, mesmo
que os argumentos sejam números grandes.
//faz uso de operador bitwise ou exclusivo (XOR)
int GCD(int a, int b) {
while (b > 0) {
a = a % b;
a ^= b; b ^= a; a ^= b; //troca valor a por b
//c=a; a = b; b = c;
}
return a;
}
int GCD2(int a, int b)
{
return (b == 0 ? a : GCD2(b, a%b) );
}
Por exemplo, para calcular o GCD(37,1000000) = 1, o algoritmo itera apenas 3 vezes. Para GCD(1000,1000) =
1000 itera apenas 1 vez. Deve-se observar que os argumentos podem ser colocados em qualquer ordem de
valores, ou seja, a > b ou b > a.
Para GCD(20,12) tem-se as seguintes iterações: GCD(20,12) GCD(12,8) GCD(8,4) GCD(4, 0) 4
Para GCD(3,7) tem-se as seguintes iterações: GCD(3,7) GCD(7, 3) GCD(3, 1) GCD(1, 0) 1
Por sua vez, o Mínimo Múltiplo Comum (LCM) de (a,b) é o menor número inteiro que seja múltiplo de a e b. Por
exemplo, lcm(20,12) = 60, pois os múltiplos de 20 são 20, 40, 60, 80, etc. Os múltiplos de 12 são 12, 24, 36, 48,
60, 72, etc. O menor múltiplo comum é então 60. O algoritmo LCM também é muito rápido, pois faz uso do
algoritmo GCD.
int LCM (int a, int b)
{
return (a * (b / GCD(a,b) ) );
}
Problemas: UVA 332, 412, 10193, 11417, etc.
5. Combinatória
Arranjo: Combinação dos elementos de um conjunto sendo que a ordem influencia na solução. (1,2) é diferente
de (2,1). O número de combinações é dado por A =
n!
(n − p )!
Combinação: A ordem dos elementos não influencia, logo (1,2) = (2,1). O número de combinações é dado por
C=
n!
p !( n − p )!
Exercícios: Uva 530 (Binomial Showdown), 326, 991, 11401, 10375, etc.
Comentários Uva 530: Inicialmente deve-se observar como a operação pode ser simplificada. Seguem dois
exemplos de como isso pode ser feito.
C (10,8) = 10! = 10.9.8.7.6.5.4.3.2.1 = 10.9.8.7.6.5.4.3 = 45
2! 8! 2.1 . 8.7.6.5.4.3.2.1 8.7.6.5.4.3.2.1
C (10,8) = 10! = 10.9.8.7.6.5.4.3.2.1 = 10.9 = 45
8! 2! 8.7.6.5.4.3.2.1. 2.1 2.1
Desta forma, a solução para o problema de encontrar C(n,k) pode ser dado por
k = min(k, n-k);
for (int i=0; i<k; i++)
{
calculo....
}
Para o cálculo do processo, a ideia é ir dividindo o numerador e o denominador a cada iteração do processo,
para evitar a geração de números muito grandes. Pode-se adotar duas estratégias:
1 – Calcular o numerador e o denominador e iterativamente dividi-los pelo GCD
2 – Dividir o numerador pelo denominador a cada etapa
6. Java BigInteger
Para diversos problemas, o uso de tipos inteiros primitivos da linguagem C (como o long long) não é suficiente
para comportar a resposta, que pode manipular números muito grandes. Para problemas do tipo, uma solução é
o uso da classe BigInteger, da linguagem Java. Essa classe representa números inteiros como strings, permitindo
desta forma a manipulação de números com número de casas limitado pela memória do computador.
Essa classe tem métodos para realizar somas (fácil de implementar), multiplicação, divisão, potenciação,
comparação, dentre outros.
Exercícios: Uva 343, 424, 10083, etc.