0votos

Sucesion Aritmetica en C

por josejuan hace 4 años

Problema directamente relacionado con SubSetSum (NP-completo) o con Table-k-SUM (fastidiosamente polinomial). Afortunadamente el problema indicado puede resolverse fácilmente en (al menos) tiempo O(n^2 log n) y espacio O(n) usando la misma estrategia que para Table-k-SUM. En mi máquina 0,66 segundos pero puede paralelizarse.

Determinar cuantos números de un Conjunto están en sucesión aritmética.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
#include <stdio.h> 
#include <stdlib.h> 
#include <time.h> 
#include <sys/time.h> 
 
int cmpfunc(const void * a, const void * b) { 
   return ( *(int*)a - *(int*)b ); 
 
int main(int argc, char **argv) { 
 
  srand((unsigned) time(NULL)); 
 
  int n = atoi(argv[1]); // nº de nºs 
  int h = atoi(argv[2]); // homogeneidad (dominio nºs) 
 
  int *m = (int *) malloc(sizeof(int) * n); 
 
    int i; 
    for(i = 0; i < n; i++) 
      m[i] = rand() % h; 
 
  // ordenamos O(n log n) 
  qsort(m, n, sizeof(int), cmpfunc); 
 
  struct timespec t1, t2; 
  clock_gettime(CLOCK_MONOTONIC,  &t1); 
 
  { // para cada par búsqueda dicotómica candidato O(n^2 log n) 
    int a, b, counter = 0; 
    for(a = 0; a < n - 3; a++) { 
      for(b = a + 1; b < n - 2; b++) { 
        int ba = m[b] + m[a]; 
        int u = b + 1, v = n - 1; 
        while(u <= v) { 
          int w = (u + v) >> 1; 
          if(m[w] == ba) break; 
          if(m[w] <  ba) u = w + 1; 
          if(m[w] >  ba) v = w - 1; 
        if(u <= v) 
          counter++; 
    printf("%i tripletes\n", counter); 
 
  clock_gettime(CLOCK_MONOTONIC,  &t2); 
  double t = (t2.tv_sec - t1.tv_sec) + (double) (t2.tv_nsec - t1.tv_nsec) * 1e-9; 
  fprintf(stderr, "Seconds: %f\n", t); 
 
  return 0; 
 
/* 
[josejuan@centella Solveet]$ gcc -O3 3arit.c && ./a.out 7000 10000000 
9815 tripletes 
Seconds: 0.659949 
*/ 

Comenta la solución

Tienes que identificarte para poder publicar tu comentario.