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

[Warrior]

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

    * http://www.cs.ubc.ca/spider/harrison/Java/sorting-demo.html

    * http://linux.wku.edu/~lamonml/algor/sort/sort.html

    * http://en.wikipedia.org/wiki/Sort_algorithm

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

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.

[theproject]

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 []

[vbmaster]

Eu o bublesort até percebo.....

agora o resto..... 😉

[deathseeker25]

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! 😁

[Tiago Salgado]

Eu o bublesort até percebo.....

agora o resto..... 😉

Ve isto aqui http://www.portugal-a-programar.pt/index.php?showtopic=1467

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

[vbmaster]

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ê?

[Warrior]

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.

Enunciado.

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;
    }

  /* nao foi encontrado */
  return (-1);
}

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

Referências

    * http://en.wikipedia.org/wiki/Binary_search

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

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

[vbmaster]

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.

Enunciado.

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[80];
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.... 😕

[Warrior]

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

No teu programa dá errado, na calculadora do windows dá certo.

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

Problema EResolução

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?

[vbmaster]

pode... verifica as condições nos threads sobre o centro de downloads.

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... 😛

[Warrior]

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.

Pesquisei pelo centro de downloads e não encontrei nenhum thread. Onde anda ele?

[deathseeker25]

http://www.portugal-a-programar.pt/index.php?showtopic=281

😕

[Warrior]

Vou mandar para lá então, têm é que ser vários ficheiros porque nem compactado vai lá..

Testes primalidade

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] = 0;
 prime[1] = 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;
}

Referência: http://www.olympus.net/personal/7seas/primes.html

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

[saramgsilva]

que programas interessantes...ja os tive que faz a todos!!  😕   mto fixe...tv venha aki buscar ideias para projectos futuros!!  😁

bom trab...

[vbmaster]

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....?

[saramgsilva]

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... )

[Warrior]

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.

[saramgsilva]

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

cuidado com off-topic

[vbmaster]

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? 😕

[_kossak_]

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.  🙂