0votos

numero repetidos en C

por josejuan hace 5 años

Posiblemente la más eficiente consiste en indexar los 9e10 números, para ello lo mejor sería disponer de 84 gigas de RAM. Una alternativa "menos eficiente" es indexar al bit, que sólo requiere 1 giga de RAM. Ésto permite reducir un tiempo de 132 segundos a tan sólo 8 segundos.

programa en c que determine si un numero tiene digitos repetidos

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
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
#include <stdio.h> 
#include <stdlib.h> 
#include <limits.h> 
#include <strings.h> 
#include <time.h> 
 
#define ulong unsigned long long 
 
int nonNegativeRepeatedDigits(ulong n) { 
 
    int bits = 0; 
    while(n) { 
        int msk = 1 << (n % 10); 
        if(msk & bits) 
            return 1; 
        n /= 10; 
        bits |= msk; 
 
    return 0; 
 
 
unsigned char *bits; 
#define setBit(n) (bits[n>>3]|=1<<(n&7)) 
#define getBit(n) (bits[n>>3]&(1<<(n&7))) 
 
int fastNonNegativeRepeatedDigits(ulong n) { 
 
    return getBit(n) ? 0 : 1; 
 
 
void nonRepeatingCombinations(int visited, int level, ulong n) { 
  if(level > 0) { 
    setBit(n); 
    int i, b, l = level - 1; 
    ulong nn = 10 * n; 
    for(i = 0, b = 1; i < 10; i++, b <<= 1) 
      if((b & visited) == 0) 
        nonRepeatingCombinations(visited | b, l, nn + i); 
 
void initializeBits() { 
    bits = (unsigned char*) malloc(1250000000); 
    memset(bits, 0, 1250000000); 
    setBit(0); 
    int i; 
    for(i = 1; i < 10; i++) 
        nonRepeatingCombinations(1 << i, 10, i); 
 
void main(int argc, char **argv) { 
    struct timespec ti, tf; 
#define TI clock_gettime(CLOCK_PROCESS_CPUTIME_ID, &ti) 
#define TF clock_gettime(CLOCK_PROCESS_CPUTIME_ID, &tf); \ 
           printf(" (%f seg)\n", ((int64_t) tf.tv_sec * 1000000000 + \ 
                                  (int64_t) tf.tv_nsec - \ 
                                  (int64_t) ti.tv_sec * 1000000000 + \ 
                                  (int64_t) ti.tv_nsec) * 1e-9f) 
    printf("Max. supported number: %llu\n", LLONG_MAX); 
    printf("Min. supported number: -%llu\n", LLONG_MIN); 
 
    printf("Initializing..."); TI; initializeBits(); TF; 
     
    printf("A: %i\n", nonNegativeRepeatedDigits(atoi(argv[1]))); 
    printf("B: %i\n", fastNonNegativeRepeatedDigits(atoi(argv[1]))); 
     
    int i; 
     
    int A = 0, B = 0; 
     
    printf("Counting (normal) first billion..."); TI; 
    for(i = 0; i < 1000000000; i++) 
        if(nonNegativeRepeatedDigits(i)) 
          A++; 
    TF; 
 
    printf("Counting (fastest) first billion..."); TI; 
    for(i = 0; i < 1000000000; i++) 
        if(fastNonNegativeRepeatedDigits(i)) 
          B++; 
    TF; 
     
    printf("nonNegativeRepeatedDigits     sum %i\n", A); 
    printf("fastNonNegativeRepeatedDigits sum %i\n", B); 
 
 
/* 
 
solveet$ ./repdig 12134 
Max. supported number: 9223372036854775807 
Min. supported number: -9223372036854775808 
Initializing... (2.514709 seg) 
A: 1 
B: 1 
Counting (normal) first billion... (132.873611 seg) 
Counting (fastest) first billion... (7.966312 seg) 
nonNegativeRepeatedDigits     sum 994388229 
fastNonNegativeRepeatedDigits sum 994388229 
 
*/ 

Comenta la solución

Tienes que identificarte para poder publicar tu comentario.