Champernowne定数（整数のシリーズ）C

Question

何とかChampernowne定数のシリーズを印刷するコードを入力するよう求められます。 （実際にそれに取り組む！） ので、我々はこのような一連のn番目の桁見つけたい：ここ 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; 
} 

しかし、それが通過するのを失敗したので、それは、私が思うのギャップを持っていますそれが提供された7つのテストケースのうちの1つ！誰でも助けてくれますか？

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がChampernowne秒の最初の10000桁が含まれていることを確認等価。

また、次のプログラムでいくつかの検証を行うことができます。

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