Константа Champernowne (серия целых чисел) для C

Question

Мне предлагается код, чтобы каким-то образом напечатать серию констант Champernowne. (На самом деле работать с ним!) поэтому мы хотим, чтобы найти п-й разряд таких серий: 1234567891011121314... Вот мой код:

#include <stdio.h> 

long long int num(long long int a); 
long long int f(long long int n); 
long long int power(long long int a, long long int b); 
long long int dig(long long int a, long long int b); 

/*MAIN*/ 

int main(void) { 
    long long int n = 0, k = 0, r = 0, m = 0; 
    /* n , num(n) , primary  result , range specifier */ 
    scanf("%lld", &n); 

    k = num(n); 
    if (k <= 1) { 
     printf("%lld\n", n); 
    } else { 
     for (m = 0; n > f(power(10, m) - 1); m++) { 
     } 

     r = n - f(power(10, m - 1) - 1); 

     if (r % m == 0) { 
      printf("%lld\n", dig(power(10, m - 1) - 1 + r/m, 1)); 
     } else { 
      printf("%lld\n", 
        dig(power(10, m - 1) - 1 + (int)r/m + 1, m + 1 - (r % m))); 
     } 
    } 
    return 0; 
} 

/*How many digits do we have ? */ 

long long int num(long long int a) { 
    long long int b = a; 
    long long int c = 0; 
    while (b != 0) { 
     b /= 10; 
     ++c; 
    } 
    return c; 
} 

/* Power */ 
long long int power(long long int a, long long int b) { 
    if (b == 0) { 
     return 1L; 
    } 
    long long int c = 1; 
    long long int d; 
    d = a; 
    for (c = 1; c < b; c = c + 1) { a = a * d; } 
    return a; 
} 

/* Lets solve it! */ 
long long int f(long long int n) { 
    int k = num(n); 
    if (k == 1) { return n; } 
    return f(power(10, (k - 1)) - 1) + k * (n - (power(10, (k - 1)) - 1)); 
} 

/*Digit */ 
long long int dig(long long int a, long long int b) { 
    long long int x = 0, z = 0, t = 0; 
    x = a % power(10, (b)); 
    z = power(10, (b - 1)); 
    t = x/z; 
    return t; 
} 

Но есть разрыв, я полагаю, потому что он не проходит 1 из 7 тестовых случаев, предусмотренных для этого! Может кто-нибудь мне помочь?

Answer 1

Ваш код является слишком сложным, я не нашел проблему, но я подозреваю, что вы должны уменьшить n на f(power(10, m) - 1) в своем начальном цикле.

Вот более простая программа, которая может быть настроена для различных баз и из командной строки или стандартного ввода:

champernowne.c:

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

int digit(long long int pos, int base) { 
    int n = 1;   /* number of digits of the block numbers */ 
    long long power = 1; /* power of base at the start of the block */ 

    if (pos <= 0) 
     return 0; 

    pos--; /* adjust position such that 1st digit is 1 */ 
    for (;;) { 
     /* length of the block of n-digit numbers */ 
     long long int block = power * (base - 1) * n; 
     if (pos < block) 
      break; 
     pos -= block; 
     power *= base; 
     n++; 
    } 
    long long num = power + pos/n; 
    for (pos %= n; pos < n - 1; pos++) { 
     num /= base; 
    } 
    return (int)(num % base); 
} 

int main(int argc, char *argv[]) { 
    long long int n; 
    if (argc > 1) { 
     for (int i = 1; i < argc; i++) { 
      printf("%d\n", digit(strtoll(argv[i], NULL, 0), 10)); 
     } 
    } else { 
     while (scanf("%lld", &n) == 1) { 
      printf("%d\n", digit(n, 10)); 
     } 
    } 
    return 0; 
} 

Вы можете использовать простой тест:

chqrlie@mac ~/dev/stackoverflow > ./champernowne {1..10000} | tr -d '\n' > c10000 

И убедитесь, что c10000 содержит первые 10000 цифр Champernowne s equence.

Вы также можете выполнить некоторые проверки со следующими программами:

generator.c:

#include <stdio.h> 

int main(void) { 
    for (long long n = 1;; n++) 
     printf("%lld", n); 
} 

extractor.c:

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

int main(int argc, char *argv[]) { 
    if (argc > 1) { 
     long long i = 0, n = strtoll(argv[1], NULL, 0); 
     int c; 
     while ((c = getchar()) != EOF) { 
      if (++i == n) { 
       printf("%c\n", c); 
       break; 
      } 
     } 
    } 
    return 0; 
} 

Например:

chqrlie@mac ~/dev/stackoverflow > time ./generator | ./extractor 1000000000 
1 

real 0m46.741s 
user 1m6.978s 
sys  0m0.759s 

chqrlie@mac ~/dev/stackoverflow > time ./champernowne 1000000000 
1 

real 0m0.018s 
user 0m0.003s 
sys  0m0.004s