 # Preparação para Concursos (algoritmia nível médio + resoluções)

## Recommended Posts Visto isto ser do interesse de muita gente (e pelo facto de neste forum existir pouco material de nivel mais elevado, as perguntas e explicações não saem do simples) resolvi partilhar parte do material fornecido no "Estágio de preparação para as IOI'2005" (Internacional Olympiad in Informatics)

Tentarei abordar um tema por dia, e não tenho qualquer problema em responder a questões ou ver os meus tópicos organizados/editados pelos moderadores.

Tentarei seguir uma lógica pelo grau de dificuldade, de forma a ser possível toda a gente acompanhar.

Em cada caso, darei os exemplos em C/C++, mas se precisarem de uma adaptação para Pascal não exitem em pedir.

Ordenações (ps: a função inicial de cada método é sempre a última)

Provavelmente o básico da algoritmia, e toda a gente sabe que existem vários métodos para se ordenar um vector. Conhecem todos?

Bubble Sort

O bubble sort, funciona comparando elementos adjacentes, trocando-os se estiverem fora de ordem. Levando de cada vez o elemento maior para o fim do vector. É um algoritmo O(n^2).

```int bubble_sort (int p[], int n)  //recebe como parametros o próprio vector e o seu tamanho
{
int i, j, tmp;
for (i = 0; i < n; i ++)
for (j = 1; j < n; j ++)
if (p[j] < p[j-1])
{
tmp = p[j];
p[j] = p[j-1];
p[j-1] = tmp;
}
}
```

Mas este algoritmo pode ser melhorado! Já que consigamos detectar quando o vector fica ordenado, pois não faremos nenhuma troca neste caso.

```int bubble_sort (int p[], int n)
{
int sorted,i;

sorted = 0;
while (sorted == 0)
{
sorted = 1;
for (i = 1; i < n; i ++)
if (p[i-1] > p[i])
{
swap (p, i-1, i); //trocar no vector p a posição i-1 e a posição i (podem usar o esquema da variável auxiliar do exercício de sima)
sorted = 0;
}
}
}
```

Quicksort

Um algoritmo muito melhor que o bubble sort é o quicksort, pois tem uma complexidade média de O(n log n) (Na maioria dos inputs é n log n, mas pode ser n^2 caso tenhamos mesmo azar)

A ideia principal do algoritmo é partir recursivamente o vector em dois, arranjando para isso um pivot. Separando os números que são menores ou iguais ao pivot dos maiores.

```do_qsort (int p[], int low, int high)
{
if (low < high)
{
location = partition (p, low, high);
do_qsort (p, low, location-1);
do_qsort (p, location+1, high);
}
}

int partition (int p[], int low, int high)
{
int i, pivot, leftwall;

swap (p, low, random (low, high));
pivot = p[low];

leftwall = low;
for (i = low+1; i <= high; i ++)
if (p[i] < pivot)
{
leftwall = leftwall + 1;
swap (p, i, leftwall);
}

swap (p, low, leftwall);

return (leftwall);
}

qsort (int p[], int n)
{
do_qsort (p, 0, n-1);
}
```

Mergesort

Um método de ordenação O(n log n) no pior caso (ao contrário do quicksort). Funciona partindo o vector ao meio (recursivamente, ou seja, cada uma das metades do vector, ficarão ordenadas), juntando-as logo de seguida para formar o vector original ordenado.

A grande desvantagem deste método é que precisa de um vector temporário do tamanho do vector que queremos ordenar.

```merge (int p[], int aux[], int L1, int R1, int L2, int R2)
{
int i, j;

i = 0;
while ((L1 <= R1) || (L2 <= R2))
{
if ((L1 <= R1) && ((L2 > R2) || (p[L1] < p[L2])))
{
aux[i] = p[L1];
L1 = L1 + 1;
i = i + 1;
}
else
{
aux[i] = p[L2];
L2 = L2 + 1;
i = i + 1;
}
}

/* copia o vector aux para p */
for (j = 0; j < i; j ++)
p[j] = p[i];
}

do_merge_sort (int p[], int aux[], int left, int right)
{
int middle;
if (right - left <= 1)
return; /* já está ordenado (só tem 0 ou 1 elementos) */

middle = (left+right)/2; /* divisao inteira */

do_merge_sort (p, aux, left, middle);
do_merge_sort (p, aux, middle+1, right);

merge (p, aux, left, middle, middle+1, right);
}

int merge_sort (int p[], int aux[], int n)
{
do_merge_sort (p, aux, 0, n-1);
}
```

-----------------------------------------------------------------------------------

Referências

-----------------------------------------------------------------------------------

Ficam então cobertos 3 métodos de ordenação de vectores. Espero que vos sejam úteis.

Amanhã usarei as ordenações para fazer pesquisas em vectores (binária, etc)

Critiquem o meu primeiro trabalho.

##### Share on other sites Boas, tá bakano. Mas acho que devias falar da estabilidade dos algoritmos visto que estás a fazer uma análise aos mesmos e que a estabilidade é uma propriedade importante dos algoritmos de ordenação.

Tirando isso penso que está bom. Abraço []

##### Share on other sites Eu o bublesort até percebo.....

agora o resto..... ##### Share on other sites Eu o bublesort até percebo.....

agora o resto..... O Bubblesorte é fácil. Se experimentares implementar qualquer um destes algoritmos num caso prático, vais ficar a perceber exactamente qual o seu funcionamento e como o adaptar ás tuas necessidades.

Experimenta criar uma lista em C++ co vários elementos (números por exemplo), todos aleatórios (podes utilizar funções com rand() , etc) e depois propõe-te a ordená-los automaticamente por ordem decrescente (o mais pequeno no início de uma lista). Para os ordenadores implementas o BubbleSort e tenho a certeza que ficas a compreendê-lo perfeitamente. Faz o mesmo para os outros e usa a tua criatividade, que vais ver que não são assim tão difíceis (tenho mais dificuldades é no MergeSort....).

Warrior, keep going! ##### Share on other sites Eu o bublesort até percebo.....

agora o resto..... Acredita que me ajudou bastante na implementaçao de alguns dos algoritmos que estão aí ...

##### Share on other sites Eu o bublesort até percebo.....

agora o resto..... Acredita que me ajudou bastante na implementaçao de alguns dos algoritmos que estão aí ...

wow, isso ajudou mesmo!

Havia alguns que tenho a certeza que pelo código não os ia perceber....

e agora uma pergunta para o Warrior, isto tem a ver com as olímpiadas no quê?

##### Share on other sites O mais importante nos concursos é a parte de algoritmia, e não a da linguagem em si, como já deviam desconfiar.

Este género de exercícios ajudam a desenvolver o raciocínio.

No fundo, ajudam-vos a simplificar os problemas que vos são propostos e a ver várias maneiras de o resolver.

Mas de qualquer forma estava a pensar entrar com uma segunda vertente deste tópico, a das resoluções.

Este é o exercício A do "Concurso inter-escolas de programação" (CIEP) deste ano.

e a minha resolução

Um pequeno pormenor: os casos de teste incluem um binário de 32 digitos (ou seja, não pensem ler como inteiro) e o 0. Verifiquem se o vosso passa.

Continuando.

Pesquisas

Tal como ordenar, pesquisar um dado elemento num vector é sempre importante.

Existem várias maneiras de o fazer:

```int pesquisa(int vec[],int n,int k) { //recebe o vector (vec), o numero de elementos (n) e o numero a pesquisar (k)
int i=0;
while ((vec[i]!=k) && (i<n)) i++;
if (i==n) return -1; // retorna -1 caso não tenha sido encontrado
else return i; //ou a sua posicao caso tenha
}
```

Podemos, contudo, aperfeiçoa-la.

```int pesquisa(int vec[],int n,int k) {
int i=0;
vec[n]=k;
while (vec[i]!=k) i++;
if (i==n) return -1;
else return i;
}
```

Desta forma, não necessitamos de verificar se i<n sempre que o ciclo é usado.

Pesquisa binária

Permite procurar um valor num vector de uma forma muito eficiente - O(log n).

Requere contudo que o vector esteja ordenado.

A ideia principal do algoritmo é olhar para o elemento do meio (do vector) e decidir se devemos procurar à esquerda desse elemento ou à sua direita, caso seja maior ou menor (respectivamente) do que elemento que estamos a procurar.

```int bsearch (int p[], int n, int value)
{
int left, right, middle;

left = 0;
right = n-1;

while (left <= right)
{
middle = (left+right)/2;
if (p[middle] == value)
return (middle);
else if (p[middle] > value) /* o valor é alto demais,
tem que estar para a esquerda */
right = middle-1;
else                        /* valor baixo demais, ver direita */
left = middle+1;
}

return (-1);
}
```

-----------------------------------------------------------------------------------

Referências

-----------------------------------------------------------------------------------

Pesquisas é menos informação do que esperava para um post, mas visto ter perdido tempo a arranjar enunciados de concursos, e respectiva resolução..

Next -> Testes de primalidade, geração de números primos, máximos divisores comuns e minimos multiplos comuns

##### Share on other sites O mais importante nos concursos é a parte de algoritmia, e não a da linguagem em si, como já deviam desconfiar.

Este género de exercícios ajudam a desenvolver o raciocínio.

No fundo, ajudam-vos a simplificar os problemas que vos são propostos e a ver várias maneiras de o resolver.

Mas de qualquer forma estava a pensar entrar com uma segunda vertente deste tópico, a das resoluções.

Este é o exercício A do "Concurso inter-escolas de programação" (CIEP) deste ano.

e a minha resolução

Um pequeno pormenor: os casos de teste incluem um binário de 32 digitos (ou seja, não pensem ler como inteiro) e o 0. Verifiquem se o vosso passa.

Aqui está o meu código, dá feedback (é c++):

```#include <iostream>
using namespace std;

int main () {
char input;
int n, i, j, aux, valor2;
cout << "Insira os numeros a testar:" << endl;
for (n = 0; (input[n] = cin.get ()) != ' '; ++n); cin >> valor2;
for (i = n - 1, j = 1; i >= 0; --i) {
aux +=  ((((int) input[i]) - 48) * j);
j *= 2;
}
(aux == valor2) ? cout << "Certo" << endl : cout << "Errado" << endl;
return 0;}
```

E então?

P.S.: estive uma horinha renhida a fazer este código agora.... ##### Share on other sites Falha para valores grandes.

Por acaso foi uma das coisas que não gostei deste concurso. Em vez de se concentrarem no importante (o algoritmo, o que fizeste)  preocupam-se com porcarias como ser necessário resolver numeros de 32bits.

11111111111111111111111111111111 4294967295

Lembro-m que quando lá estava tive que o resolver duas vezes porque primeiro tinha feito só com inteiros..Esquece isso.

Arranjei os problemas das IOIs desde 1989 a 2004 (47MBs em exercícios). Sãp é MUITO dificeis.

Estava a pensar po-los online, o alojamento da P@P pode recebe-los?

##### Share on other sites Falha para valores grandes.

Por acaso foi uma das coisas que não gostei deste concurso. Em vez de se concentrarem no importante (o algoritmo, o que fizeste)  preocupam-se com porcarias como ser necessário resolver numeros de 32bits.

11111111111111111111111111111111 4294967295

Lembro-m que quando lá estava tive que o resolver duas vezes porque primeiro tinha feito só com inteiros..Esquece isso.

Arranjei os problemas das IOIs desde 1989 a 2004 (47MBs em exercícios). Sãp é MUITO dificeis.

Estava a pensar po-los online, o alojamento da P@P pode recebe-los?

Quanto ao meu algoritmo...epah... a primeira coisa a mudar seria por o valor2 como long e por mais tamanho na array.

Mas se eles vão por aí, qualquer algoritmo falha pois a memoria de um computador é limitada. Pois é... eu acho que até dava fixe para essas provas... então quando vejo problemas desse tipo passo-me mesmo (como hoje, que já devia estar a dormir pois amanhã é dia de visita de estudo) e só paro quando os resolvo.

Mete mais provas... que assim sempre vou metendo o meu c++ em dia... ##### Share on other sites Um binário de 32 bits é um decimal de 10 digitos, logo tinhas que declarar o valor 2 como "unsigned int", e é aí que está o segredo para resolver o problema.

##### Share on other sites Um binário de 32 bits é um decimal de 10 digitos, logo tinhas que declarar o valor 2 como "unsigned int", e é aí que está o segredo para resolver o problema. ##### Share on other sites Vou mandar para lá então, têm é que ser vários ficheiros porque nem compactado vai lá..

Por definição, um número é primo, se os seus únicos divisores são o 1 e o próprio número (excepto o um, que não é primo).

Pela definição podemos arranjar muito rapidamente um algoritmo: testar se algum dos números entre 2 e n-1 dividem n, se algum deles dividir então o número não é primo. Caso contrário o número é primo.

```bool prime (int n)
{
int i;
for (i = 2; i <= n - 1; i ++)
if (n % i == 0) /* se o resto da divisão inteira entre n e i
é zero, então i divide n */
return (false);
return (true);
}```

Mas podemos fazer melhor. Pois se um número não for primo então podemos arranjar dois números, a e b tal que n = a * b.

Se considerarmos que a <= b (algum deles tem que ser menor (ou igual)), então vemos que a é menor ou igual a sqrt(n)!

Desta forma basta testar os números entre 2 e sqrt(n) (inclusive).

```bool prime (int n)
{
int i, max;
max = sqrt (n);
for (i = 2; i <= max; i ++)
if (n % i == 0)
return (false);
return (true);
}```

Crivo de Eratóstenes

O crivo permite gerar os primos entre 0 e n de uma forma muito mais eficiente do que testar se cada um deles é primo.

Funciona eliminando os múltiplos de cada primo.

```int sieve ()
{
int i, j, size=100;
double max;
max = sqrt (size);
prime = 0;
prime = 0;
for (i = 2; i < size; i ++)
prime[i] = 1;
for (i = 2; i < max; i ++)
{
if (prime[i] == 1)
for (j = i + i; j < size; j += i) /* começa no próximo multiplo de i
saltando de i em i */
prime[j] = 0;
}
for (i=0;i<size;i++) if (prime[i]==1) printf("%d %d\n",i,prime[i]);
return 0;
}```

Congruências

Isto são simplesmente algumas relações matemáticas, uteis em programação, inuteis no dia-a-dia.

(a * b) mod c = ((a mod c) * (b mod c)) mod c

(a + b) mod c = ((a mod c) + (b mod c)) mod c

(a - b) mod c = ((a mod c) - (b mod c)) mod c

Nota: Não funciona para a divisão!

Referência: http://mathworld.wolfram.com/Congruence.html

Máximo divisor comum e mínimo múltiplo comum

O máximo divisor comum gcd(a,b) de dois inteiros positivos a e b, é maior divisor comum a a e a b.

Por exemplo, gcd(3,5)=1, gcd(60,12)=12, gcd(12,90)=6.

O maior divisor comum gcd(a,b,c,...) pode ser também definido para três ou mais inteiros positivos como sendo o maior divisor comum a todos eles.

Para o calcular, podemos fazer a factorização do número nos seus primos, e depois usar a regra que todos aprendemos no 8º ano.. os primos comuns de maior expoente.

Contudo, existe uma forma muito rápida de o achar.

```int gcd (int u, int v)
{
if (v == 0)
return (u);
else
return (gcd (v, u % v));
}```

Como podem ver, este método usa recursividade (o facto de uma função se chamar a si própria), pelo que quando os dois números são bastante grandes, torna o programa ligeiramente mais lento (visto ter que armazenar a informação de chamadas anteriores antes de as resolver) do que seria aconselhável.

Portanto, segue uma versão mais rápida, e mais simples de se compreender.

```int mdc1(int a,int b)
{
int r;
while((r=a%b)!=0)
{
a=b;
b=r;
}
return b;
}```

O mínimo múltiplo comum de dois números a e b [lcm(a,b)], é o menor número m para o qual existem inteiros positivos na e nb tais que

na * a = nb * b = m

É possível calcular o mínimo múltiplo comum, usando o máximo divisor comum da seguinte forma:

lcm(a,b) = (a*b) / gcd(a,b)

int lcm (int u, int v)

{

return ((u / gcd (u, v)) * v);

}

A implementação anterior, evita overflows, quando o resultado final cabe num inteiro.

Referências:

http://mathworld.wolfram.com/GreatestCommonDivisor.html

http://mathworld.wolfram.com/LeastCommonMultiple.html

Comparação de números de vírgula flutuante

Os números de virgula flutuante nunca devem ser comparados directamente (i.e. u == v). Deve-se usar sim uma tolerância da seguinte forma:

|u - v| <= epsilon. Um bom valor para epsilon é 10^-6.

Exemplo em C:

```#define EPSILON 1E-6

bool equal (double u, double v)
{
if (fabs (u - v) <= EPSILON)
return (true);
else
return (false);
}```

Aplicação prática de números primos e divisores

Aplicação prática de congruências

##### Share on other sites que programas interessantes...ja os tive que faz a todos!! mto fixe...tv venha aki buscar ideias para projectos futuros!! bom trab...

##### Share on other sites Esse sistema de crivo de eratóstenes, torna-se mais eficiente a determinar números primos do que a usual comparação?

Supera o problema que na comparação existe, de quanto maior for o número a ser testado, mais tempo ele demora a saber se de facto é primo ou não....?

##### Share on other sites Esse sistema de crivo de eratóstenes, torna-se mais eficiente a determinar números primos do que a usual comparação?

Supera o problema que na comparação existe, de quanto maior for o número a ser testado, mais tempo ele demora a saber se de facto é primo ou não....?

sim, quando tens 1 conjunto grande de numeros os crivo é mais fixe...eu usei isso nakele projecto de paralela...k ainda nao apresentei aki no forum... ( nao tenho tido tempo para nada... )

##### Share on other sites O crivo não serve para determinar se um número é primo ou não, mas sim para gerar todos os números primos num dado intervalo.

Tenta usar o crivo para encontrar o primos nos 1024 primeiros numeros, e depois tenta encontrá-los pelo outro métodos (divisões por todos os numeros de 2 a sqrt(n)) e compara.

Prepara-te para um ctrl+c porque o pc certamente vai crashar da segunda vez.

Desculpem hoje não colocar nada, mas acabei de chegar a casa.

Vou tentar enviar o mail para o centro de downloads pelo menos.

##### Share on other sites O crivo não serve para determinar se um número é primo ou não, mas sim para gerar todos os números primos num dado intervalo.

Tenta usar o crivo para encontrar o primos nos 1024 primeiros numeros, e depois tenta encontrá-los pelo outro métodos (divisões por todos os numeros de 2 a sqrt(n)) e compara.

Prepara-te para um ctrl+c porque o pc certamente vai crashar da segunda vez.

Desculpem hoje não colocar nada, mas acabei de chegar a casa.

Vou tentar enviar o mail para o centro de downloads pelo menos.

ainda falas de 1 relativamente pequeno ( fiz 1 programa usando MPI, programa paralelizado) consegui obter ate k primo< 209 000

##### Share on other sites Oh.... o meu pc não crashou quando eu tive umas boas 3 horas a obter primos sem limite máximo (só o da variável int) no meu programa determinador de números primos...

porque haveria de crashar? ##### Share on other sites Exemplo em C:

```bool equal (double u, double v)
{
if (fabs (u - v) <= EPSILON)
return (true);
else
return (false);
}```

Apenas um aparte - não tem a ver com os problemas colocados mas sim com boas práticas de programação. No código acima temos um if do tipo if (exp) then true else false. Está correcto mas é algo que se deve evitar em vez daquilo deveria ter-se:

```bool equal (double u, double v)
{
return (fabs (u - v) <= EPSILON)
}
```

o resultado da comparação <= é um boolean (true ou false), logo o resultado pode ser retornado imediatamente.

Não levem a mal a correcção - eu já passei pelo mesmo e fui corrigido pelos meus profs. ## Create an account

Register a new account

×

• #### Revista PROGRAMAR

• Wiki
• IRC
×
• Create New...