SUM PROBLEM

Hoje, falaremos de uma família de problema interessante relacionado com vetores. Primeiramente, vamos começar com o 2SUM PROBLEM:
Seja L um vetor de inteiros. Determine se existe dois  elementos distintos x e y em L, tal que x+y = K.
A ideia mais trivial seria um algoritmo O( n*n ) , mas podemos fazer melhor. Se o vetor L estiver ordenado podemos resolver esse problema com complexidade O(n). Da seguinte maneira:

bool sum2(vector <int> v, int n, int K, int &x, int &y){
  int i,j;
  i = 0;
  j = n-1;
  while(i<j){
    if(v[i]+v[j] > K ) j--;
    if(v[i]+v[j] < K ) i++;
    if(v[i]+v[j] ==K ) {
      x = v[i];
      y = v[j];
      return true;
    }
  }
  return false;
}

Se o vetor L não estiver ordenado, podemos resolver esse problema com complexidade O(nlogn). Primeiramente, ordenando o vetor e depois aplicando a ideia acima.

Problema 2 3SUM PROBLEM
Seja L um vetor de inteiros. Determine se existe três  elementos distintos x, y e z em L, tal que x+y +z= K.
Um algoritmo de força bruta simplesmente enumeraria todas O($n^3$) possiveis escolhas de elementos x,y e z e testaria se x+y+z = K. Considerando o vetor ordenado, uma ideia simples seria  para cada par x,y em L e realizar uma busca binária pelo  valor (K-x-y). Neste caso, o algoritmo teria como  complexidade no pior caso O($n^2$ lg n).

Será que podemos encontrar uma solução melhor? A idéia é reduzir este problema ao problema 2SUM. Para cada valor x em L, determine se existe y,z em L tal que y+z=K-x. Este algoritmo tem complexidade O($n^2$). Considerando que para cada valor x em L executamos um algoritmo com complexidade O(n).

bool sum3(vector<int> v, int n, int K, int & x, int &y, int &z ){
  for(int i=0;i<n;i++){
      x = v[i];
      if( sum2(v,n,K-x,y,z) ){
        return true;
      }
  }
  return false;
}

Em teoria da complexidade, este problema deu origem ao conceito 3SUM-díficil.  Acredita-se que o limite inferior no pior caso para qualquer solução para o  problema 3SUM seria  O($n^2$).Gajentaan e Overmars lista uma séries de  problema em geometria computacional que pode ser reduzidos ao problema de  3SUM. Por exemplo,  

Dado n pontos em linhas horizontais dados por y=0,y=1 e y=2, existe uma linha não-horizontal  que passa por três pontos? 

Este problema pode ser reduzido ao 3SUM.

 Exercício:
1. Desenvolva um algoritmo O( $n^3$ ) para 4SUM.
 2. Desenvolva um algoritmo O( $n^2$ log n) para 4SUM.  

Referências: 
http://www.sciencedirect.com/science/article/pii/0925772195000222
http://en.wikipedia.org/wiki/3SUM

http://www.cs.mcgill.ca/~jking/papers/3sumhard.pdf

http://cs.smith.edu/~orourke/TOPP/P11.html

http://algorithmsetc.wordpress.com/2012/02/20/array-scanning-problems-2-sum/

http://algorithmsetc.wordpress.com/2012/02/24/3sum/

Conjectura de Collatz

A conjectura de Collatz é devida ao matemático alemão Lothar Collatz. A conjectura estabelece uma seqüência de números, ou trajetória, que a partir de um número natural inicial obedece aos seguintes critérios: Pegue qualquer número natural n . Se n é par, divida-o por 2 para obter n  / 2, se n for ímpar multiplicá-lo por 3 e adicionar 1 para obter 3 n  + 1. Repita o processo (que tem sido chamado de "Half Ou Triplo Plus One", ou HOTPO  ) por tempo indeterminado. A conjectura é que não importa o número que você começar, você sempre vai eventualmente chegar a 1. A propriedade também tem sido chamado de unidade .

Outras informações:
http://en.wikipedia.org/wiki/Collatz_conjecture

Considere o seguinte algoritmo:
      

Consider the following algorithm:

1. input n

2. print n

3. if n = 1 then STOP

         4. if n is odd then n = 3n + 1

         5. else n = n / 2

6. GOTO 2

 

Dado o número 22 como entrada, a seguinte sequência de números é impressa até chegar na condição de parada do algoritmo 22 11 34 17 52 26 13 40 20 10 5 16 8 4 2 1       O problema 3n+1 pede para você calcular o tamanho da maior sequência gerada por um número em um dado intervalo.

       A solução direta para esse problema seria assim:

#include <stdio.h>

typedef long long int lli; 

lli cycle(lli n){
 lli cont;
 cont = 1;
 while(n!=1){
  if(n%2==0) n = n/2;
  else n = 3*n+1; 
  cont++;
 }
 return cont;
}
int main(){ 
 lli max;
 lli n,m,a,b,i,cont;
 
 while( scanf("%lld %lld",&n,&m) > 0 ){
  a = n < m ? n: m;
  b = n > m ? n: m;
  max = 0;
  for(i=a;i<=b;i++){
   cont = cycle(i);
   if(cont > max) max = cont;
  }
  printf("%lld %lld %lld\n",n,m,max);
  
 }
 return 0;
}

2012-07-03 16:23:28

The 3n plus 1 problem

accepted

0.29

1.6M

C

Uma maneira de otimizar esse código é aproveitar a sobreposição de subproblemas desse nesse problema utilizando a memorização. Com ela podemos evitar retrabalhos desnecessários.

#include <stdio.h>

typedef long long int lli; 

lli  mem[1000001];

lli cycle(lli n){
  lli t=1;
  lli temp = n;
  
  while(n!=1LL){
    if(n%2==0) n = n/2;
    else n = 3*n+1;
    if(n<=1000000 && mem[n]!=0){
      if(temp <= 1000000){
        mem[temp] = mem[n] + t;
        return mem[temp];
      }else{
        return mem[n]+t;
      }    
    } 
    t++;
  }
  
  if(temp <=1000000) mem[temp] = t;
  return t;
}

int main(){ 
 lli max;
 lli n,m,a,b,i,cont;
 
 while( scanf("%lld %lld",&n,&m) > 0 ){
  a = n < m ? n: m;
  b = n > m ? n: m;
  max = 0;
  for(i=a;i<=b;i++){
   cont = cycle(i);
   if(cont > max) max = cont;
  }
  printf("%lld %lld %lld\n",n,m,max);
  
 }
 return 0;
}

2012-07-03 16:25:58

The 3n plus 1 problem

accepted

0.03

9.3M

C

Outros links interessantes:
http://www.marcioalthmann.net/2011/06/conjectura-de-collatz/
http://timeroot.zxq.net/collatz.html

Se você gostou dessa postagem, deixe um comentário e curta a nossa página no facebook!

Problema das 8 rainhas

Aprender a programar bem é tão importante quanto aprender tecnologias atuais. O leitor poderá estar pensando assim:  mas será que esta história de algoritmos eficientes tem relevância, numa era de computadores cada vez mais velozes? Considere o seguinte exemplo, o popular problema da oitos rainhas, que deseja determinar uma maneira de colocar oitos rainhas em tabuleiro de xadrez de maneira que nenhuma rainha ataque as outras rainhas do tabuleiro. Uma abordagem ingênua examinaria 64!/56! = 178,462,987,637,760 possíveis maneiras de colocar 8 peças nos 64 casas do tabuleiro, e, para cada configuração, checar se nenhuma rainha ataca qualquer outra. Mas podemos restringir ainda mais o espaço de busca considerando apenas como soluções as permutações dos números de 1 até 8 como uma solução para o problema. Note que agora precisamos gerar 8! = 40320 configurações e testar se as rainhas de cada coluna colocadas na linhas dada pela permutação atacam uma as outras.

Essa configuração equivale a permutação [4,2,7,3,6,8,5,1]

  É claro que este algoritmo funciona para tabuleiros de tamanho moderado e poderia ser usado por nós para resolver este problema. Mas o que ocorre com tabuleiros maiores? Vejamos, por exemplo, uma situação em que o tamanho do tabuleiro cresce para 50. Neste caso, o computador deveria examinar 50! permutações potenciais. Tentemos estimar a magnitude deste número.  A forma mais simples é usar a fórmula de Stirling, que fornece a estimativa n! $\equiv \sqrt{2\pi n}(\frac{n}{e})^n$ . Mas, neste caso, podemos usar estimativas mais elementares.  Por exemplo, podemos usar apenas potências de 2. Temos:

50! =    1 × 2 × 3 × 4 × 5 × 6 × 7 × 8 × ... × 15 × 16 × ... × 31 × 32 × … × 49  x 50 >

            1 × 2 × 2 × 4 × 4 × 4 × 4 × 8 × ... ×   8 × 16 × ... × 16 × 32 × …× 32  x 32 = 

            2² x 4⁴ x 8⁸ x 16¹⁶ x 32¹⁹  =  2^2+8+64+95 = 2¹⁶⁹ =(2¹⁰)^16,9. 

Mas 2¹⁰ = 1024 >10³.  Logo 50! > (10³)^16,9=10^50,7.

Ora, um computador moderno pode realizar cerca de 1 bilhão de  operações por segundo. Se em cada operação ele conseguir testar um circuito, ele ainda assim precisará de mais de 10^50,7 / 1. 10⁹ = 5 × 10⁴¹ segundos, o que corresponde a aproximadamente a 1,58 × 10³⁴ anos.  Assim, trata-se claramente de uma missão impossível para o algoritmo de força bruta baseado na análise de cada permutação.

Backtracking

Os computadores modernos podem utilizar força bruta para resolver problemas de maneira efetiva. Em geral, precisamos desenvolver algoritmos para busca exaustiva em todas as permutações e/ou em todos os subconjuntos possíveis. Vamos aprender algoritmos com retrocesso (backtracking) e desenvolver cortes para tornar estes algoritmos mais poderosos.

Como gerar todas as permutações?

#include <stdio.h>
#include <string.h>
#include <stdlib.h>

int marc[4];//vetor marc[x] = 1 se o elemento esta na permutação
int v[4]; //vetor original
int p[4]; //vetor da permutação
int i;
int n=3;
 
int permute(int i){
 int j;
 
 if(i<=n){ //escolhendo o i-ésimo elemento 
  for(j=1;j<=n;j++){
   if(marc[j]==0){ //se um element não foi escolhido
    marc[j]=1; // este elemento é marcado
    p[i]=j;    // o i-ésimo elemento da permutação corresponde
      // ao j-ésimo elemento do vetor  
    permute(i+1); //escolhe-se o próximo elemento
    marc[j]=0;
   }
  }
 }else{ //Imprime a permutação escolhida
  printf("%d",v[p[1]]);
  for(j=2;j<=n;j++){
   printf(" %d",v[p[j]]);
  }
  printf("\n");
 }
}

int main(){
 int i;
 memset(marc,0,sizeof(marc));
 for(i=1;i<=n;i++) v[i]=i;
 permute(1);
  system("PAUSE");
}

C++

#include <vector>
#include <algorithm>
#include <iostream>
#include <stdlib.h>
using namespace std;

int main(){
  int v[] = {1,2,3}; 
 
  //sort(inicio,fim) 
  sort (v,v+3); //ordena o vetor 

  do {
    cout << v[0] << " " << v[1] << " " << v[2] << endl;
  } while ( next_permutation (v,v+3) ); // gera a próxima permutação
  
  system("PAUSE");

}

Saída

1 2 3

1 3 2

2 1 3

2 3 1

3 1 2

3 2 1

Pressione qualquer tecla para continuar. . .

Desafio SPOJ

http://br.spoj.pl/problems/TENTA/

CORTANDO

No problema das oitos rainhas, reduzimos bastante nosso espaço de busca limitando-se a pesquisar apenas as permutações de [1,..,n]. Mas podemos desistir de uma permutação se a permutação tem duas rainhas que se atacam. Então podemos descobrir prematuramente quando uma permutação não é mais válida.

Em tabuleiro 8x8, temos 8 linhas , 15  diagonais principais e 15 diagonais secundárias. As diagonais principais são formadas pelos elementos (i,j) com 2≤i+j≤16 ou 0≤i+j-2≤14. As diagonais secundárias são formadas pelos elementos (i,j) com -7≤i-j≤7 ou 0≤i-j+7≤14.

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int linha[9];
int coluna[9];
int d1[15];
int d2[15];
int cont;

void queen(int i){
 int j;
 
 if(i<=8){
  //escolhendo onde colocar a i-ésima rainha
  for(j=1;j<=8;j++){
   //nao tem nenhuma outra rainha na mesma linha ou diagonal
   if(linha[j]==0 && d1[i+j-2]==0 && d2[i-j+7]==0){
    coluna[i] = j;
    linha[j]=i;
    d1[i+j-2]=1;
    d2[i-j+7]=1;
    queen(i+1);
    linha[j]=0;
    coluna[i] = 0;
    d1[i+j-2]=0;
    d2[i-j+7]=0;
   }
  }
 }else{
  cont++;
  printf("%d. ",cont);
  printf("%d",coluna[1]);
  for(j=2;j<=8;j++){
   printf(" %d",coluna[j]);
  }
  printf("\n");
 }


}

int main(){
 memset(linha,0,sizeof(linha));
 memset(d1,0,sizeof(d1));
 memset(d2,0,sizeof(d2));
 cont = 0;
 queen(1);
  system("PAUSE");
}

O programa foi capaz de gerar todas 92 possibilidades de colocar 8 rainhas em tabuleiro 8x8;

1. 1 5 8 6 3 7 2 4
2. 1 6 8 3 7 4 2 5
3. 1 7 4 6 8 2 5 3
4. 1 7 5 8 2 4 6 3
5. 2 4 6 8 3 1 7 5
6. 2 5 7 1 3 8 6 4
7. 2 5 7 4 1 8 6 3
8. 2 6 1 7 4 8 3 5
9. 2 6 8 3 1 4 7 5
10. 2 7 3 6 8 5 1 4
11. 2 7 5 8 1 4 6 3
12. 2 8 6 1 3 5 7 4
13. 3 1 7 5 8 2 4 6
14. 3 5 2 8 1 7 4 6
15. 3 5 2 8 6 4 7 1
16. 3 5 7 1 4 2 8 6
17. 3 5 8 4 1 7 2 6
18. 3 6 2 5 8 1 7 4
19. 3 6 2 7 1 4 8 5
20. 3 6 2 7 5 1 8 4
21. 3 6 4 1 8 5 7 2
22. 3 6 4 2 8 5 7 1
23. 3 6 8 1 4 7 5 2
24. 3 6 8 1 5 7 2 4
25. 3 6 8 2 4 1 7 5
26. 3 7 2 8 5 1 4 6
27. 3 7 2 8 6 4 1 5
28. 3 8 4 7 1 6 2 5
29. 4 1 5 8 2 7 3 6
30. 4 1 5 8 6 3 7 2
31. 4 2 5 8 6 1 3 7
32. 4 2 7 3 6 8 1 5
33. 4 2 7 3 6 8 5 1
34. 4 2 7 5 1 8 6 3
35. 4 2 8 5 7 1 3 6
36. 4 2 8 6 1 3 5 7
37. 4 6 1 5 2 8 3 7
38. 4 6 8 2 7 1 3 5
39. 4 6 8 3 1 7 5 2
40. 4 7 1 8 5 2 6 3
41. 4 7 3 8 2 5 1 6
42. 4 7 5 2 6 1 3 8
43. 4 7 5 3 1 6 8 2
44. 4 8 1 3 6 2 7 5
45. 4 8 1 5 7 2 6 3
46. 4 8 5 3 1 7 2 6
47. 5 1 4 6 8 2 7 3
48. 5 1 8 4 2 7 3 6
49. 5 1 8 6 3 7 2 4
50. 5 2 4 6 8 3 1 7
51. 5 2 4 7 3 8 6 1
52. 5 2 6 1 7 4 8 3
53. 5 2 8 1 4 7 3 6
54. 5 3 1 6 8 2 4 7
55. 5 3 1 7 2 8 6 4
56. 5 3 8 4 7 1 6 2
57. 5 7 1 3 8 6 4 2
58. 5 7 1 4 2 8 6 3
59. 5 7 2 4 8 1 3 6
60. 5 7 2 6 3 1 4 8
61. 5 7 2 6 3 1 8 4
62. 5 7 4 1 3 8 6 2
63. 5 8 4 1 3 6 2 7
64. 5 8 4 1 7 2 6 3
65. 6 1 5 2 8 3 7 4
66. 6 2 7 1 3 5 8 4
67. 6 2 7 1 4 8 5 3
68. 6 3 1 7 5 8 2 4
69. 6 3 1 8 4 2 7 5
70. 6 3 1 8 5 2 4 7
71. 6 3 5 7 1 4 2 8
72. 6 3 5 8 1 4 2 7
73. 6 3 7 2 4 8 1 5
74. 6 3 7 2 8 5 1 4
75. 6 3 7 4 1 8 2 5
76. 6 4 1 5 8 2 7 3
77. 6 4 2 8 5 7 1 3
78. 6 4 7 1 3 5 2 8
79. 6 4 7 1 8 2 5 3
80. 6 8 2 4 1 7 5 3
81. 7 1 3 8 6 4 2 5
82. 7 2 4 1 8 5 3 6
83. 7 2 6 3 1 4 8 5
84. 7 3 1 6 8 5 2 4
85. 7 3 8 2 5 1 6 4
86. 7 4 2 5 8 1 3 6
87. 7 4 2 8 6 1 3 5
88. 7 5 3 1 6 8 2 4
89. 8 2 4 1 7 5 3 6
90. 8 2 5 3 1 7 4 6
91. 8 3 1 6 2 5 7 4
92. 8 4 1 3 6 2 7 5
Pressione qualquer tecla para continuar. . .

Métodos de Ordenação

Ordenar é uns das atividades mais importantes para  a computação.  Muitos problemas ficam  fáceis quando os dados encontram-se ordenados. Logo, o conhecimento de vários métodos de ordenação e suas particularidades é extremamente importante para o desenvolvimento de algoritmos eficientes.

O algoritmo de ordenação bolha foi analisado 1956 e  librarysort foi publicado em 2004, mostrando que a área ainda está em evolução. Para comparar os diversos algoritmos, vamos gerar entradas para os algoritmos com o seguinte programa em Python:

import random
def entrada( n ):
    x = range(1,n+1)
    random.shuffle(x)
    filename = str(n) + ".in"
    f = open(filename, "w")
    f.write( str(n) + "\n")
    while len(x) > 0 :
        f.write( str( x.pop() ) + "\n") 

Para gerar um arquivo com os números no intervalo de 1..1000 embaralhados.

>>> entrada(1000)

Código para testar o algoritmo de ordenação:

#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include <string>
using namespace std;
char filename[100];
int n,i,j;
int main(){
 
 FILE * fp;
 scanf("%d",&n);
 
 fp = fopen(filename, "rt");
 if(fp==NULL) printf("Erro ao abrir o arquivo!\n");
 int v[n];
 for(i=0;i<n;i++)
  fscanf(fp,"%d",&v[i]);
 clock_t begin = clock();  

 Algoritmo de Ordena��o
 
 double elapsed = ((double) (clock() - begin)) / CLOCKS_PER_SEC;
 printf("EXECUTION TIME(seconds): %8.5g second(s). \n", elapsed);

} 

Ordenação Bolha

for(i=n-1;i>0;i--)

      for(j=0;j

            if( v[j] > v[j+1])

                  swap(v[j], v[j+1]);    

Propriedades:

• Estável (mantém o ordem relativa dos elementos iguais)
• In-Place (requer uma quantidade constante de memória adicional.)

Otimizações:

• Se não acontece nenhuma troca então o vetor já se encontra ordenado.

Ordenação por inserção

for(j=1; j

      chave = v[j];

      i = j-1;

      while(i >= 0 && v[i] > chave){

            v[i+1] = v[i];

            i--;

      }          

      v[i+1] = chave;

}

Propriedades:

• Estável
• In-Place 
• On-line (novos elementos podem ser adicionados durante a ordenação)

Otimizações:  

• Busca binária para encontrar a posição da chave no vetor ordenado 

QuickSort

#include

using namespace std;

int partition(int vec[], int left, int right) {

  int i, j;

  i = left;

  for (j = left + 1; j <= right; ++j) {

    if (vec[j] < vec[left]) {

      ++i;

      swap(vec[i], vec[j]);

    }

  }

  swap(vec[left], vec[i]);

  return i;

}

void quickSort(int vec[], int left, int right) {

  int r;

  if (right > left) {

    r = partition(vec, left, right);

    quickSort(vec, left, r - 1);

    quickSort(vec, r + 1, right);

  }

}

QuickSort da stdlib.h

#include

int compara(const void *pa , const void *pb){

                               int a = *(int *)pa;

                               int b = *(int *)pb;

                               return a-b;

}

qsort(v,n,sizeof(n) , compara);

Propriedades:

• Não estável
• Não in-place

Otimizações:

• Usar a ordenação por inserção em pequenos vetores ~ 10.
• Escolha aleatória do pivô
• Média de três elementos aleatórios

MergeSort

void merge(int A[] , int B[], int p, int q, int r){

     

      int i,j,k;

     

      for(i=p;i<=r;i++)

       B[i] = A[i];

     

      i = p;

      j = q+1;

     

      for(k=p;k<=r;k++){

            if(B[i] <= B[j]){

                  A[k] = B[i];

                  i = i+1;

            }else{

                  A[k] = B[j];

                  j = j+1;

            }

      }

     

}

void mergesort(int vec[] , int vec2[] , int inicio , int fim){

      int meio;

      if( inicio >= fim ) return ;

      else {

            meio = (inicio+fim)/2;

            mergesort(vec, vec2, inicio, meio);

            mergesort(vec, vec2, meio+1, fim );

            merge(vec, vec2 , inicio, meio, fim);

      }

}

Chamada:
int v2[n];
mergesort(v, v2, 0 , n-1);

HeapSort

#include

using namespace std;

priority_queue pq (v,v+n);

i = n-1;

while( !pq.empty() ){

      v[i] = pq.top();

      pq.pop();

      i--;

}

TreeSort

Set são um tipo de container associativo que são implementados como um árvore binária de busca. 

#include

using namespace std;

set myset (v,v+n);

set::iterator it;

for ( i = 0, it=myset.begin() ; it != myset.end(); it++ , i++ )

 v[i] = *it;

Todos os métodos de ordenação estudados acima são baseados em comparação, os algoritmos de ordenação baseados em comparação tem um limite inferior de O(n log n). Veremos um algoritmo que não dependem de comparação.

 

Ordenação por Contagem

int min,max;

int k;

min = 0;

for(i=1;iif( v[i] < v[min]) min = i;

           

max = 0;

for(i=1;iif( v[i] > v[max]) max = i;

           

k = v[max] - v[min] + 1;

           

int c[k];

           

for(i=0;i < k; i++) c[i] = 0;

           

for(i=0; i < n; i++) {

c[v[i]-v[min]]++;

}

           

for(i=1; i< k ; i++) {

c[i] = c[i] + c[i-1];

                 

}

//C[i] contém o número de elementos menores que ou iguais a i

                 

int b[n];

           

for(j=n-1;j>=0;j--){

      c[ v[j]-v[min] ]--;

b[ c[ v[j]-v[min] ] ] = v[j];

}    

 N= 100000

BUBBLE SORT
EXECUTION TIME(seconds):   51.954 second(s).
INSERTION SORT
EXECUTION TIME(seconds):   17.546 second(s).
QUICK SORT
EXECUTION TIME(seconds):    0.028 second(s).
QSORT SORT
EXECUTION TIME(seconds):    0.026 second(s).
MERGE SORT
EXECUTION TIME(seconds):    0.028 second(s).
HEAP SORT
EXECUTION TIME(seconds):    0.127 second(s).
TREE SORT
EXECUTION TIME(seconds):     0.15 second(s).
COUNT SORT
EXECUTION TIME(seconds):    0.008 second(s).