C 的 Champerowne 常数(整数系列)

Question

系统提示我输入代码以某种方式打印 Champerowne 常量系列。 (实际使用它!)所以我们想找到这个系列的第 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) 在你的初始循环中。

这是一个更简单的程序，可以针对不同的基础进行定制，并从命令行或标准输入中使用:

champerowne.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 包含 Champerowne 序列的前 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