040. 钱珀努恩数(Champernowne's constant)

十进制下的钱珀努恩数可以通过将所有正整数前后相接来构成:

$$ 0.123456789101112131415161718192021... $$
可以看出来小数点后的第十二位数是一。如果\(d_n\)代表小数点后的第\(n\)位数,求以下表达式的值:
$$ d_1\times d_{10} \times d_{100} \times d_{1000} \times d_{10000} \times d_{100000} \times d_{1000000} $$

分析:由于这道题的问题规模比较小,最大只需要求第一百万位数字,所以可以直接使用暴力破解的方法,先生成一个足够长的满足要求的字符串,再求取相应位置上的数字相乘即可,这种方法在我的电脑上大约耗时4.8秒。但是如果问题规模进一步扩大,这种方法将变得非常缓慢,所以我们可以对问题进一步深入分析,找到更高效的算法。

通过分析钱珀努恩数的规律,我们可以发现它小数点后的构成方法如下:首先是九个一位数、然后是九十个二位数,再是九百个的三位数,依次类推。根据这个规律,我们可以推断出每个位数的从第几位开始,到第几位结束,比如一位数从第一位开始,到第九位结束;二位数的区域共有九十个数,因此需要占180个位置,则应该在第189位结束;三位数区域共有九百个数,需要占2700个位置,则应该在第2889位结束。依次类推,我们可以推算出每个区域开始和结束的位置。

一般的,要求第\(n\)位数\(d_n\),假设其所处区域是\(k\)位数的区域,我们可以求出这个区域的位数范围,设这个范围的上界为\(U\),则:

$$ U(k)=\sum_{i=1}^{k}i\cdot(10^i-10^{i-1})=9\sum_{i=1}^k i\cdot10^{i-1}=10^{k}(k-\frac{1}{9})+\frac{1}{9} $$

根据这个公式,我们可以计算出特定位数的位置区域如下:

img

假设我们要求第一千位的数,因为\(189<1000<2889\),则其应该处在三位数的区域,也就是说\(k=3\)。在确定\(k\)以后,我们可以很方便的确定\(U(k)\)\(U(k-1)\),则第\(n\)位和其所在区域的上一个区域的上界之间共有\(D=(n-U(k-1))\)个数位,假设\(D\)除以\(k\)的商为\(m\)且余\(r\),则所求第\(n\)位数所在的整数\(T=10^{k-1}+m+1\),而\(d_n\)就等于数\(T\)的第\(r\)位数,即为所求。总结一下上面的计算步骤:

通过以上的算法优化,解决题目中的问题在我的电脑上需要花费36微秒,相比于暴力破解的方法,所用时间缩短了约133333倍。

def get_k_pub(n):
    previous_bound = lambda k : 10**k*(k-1/9)+1/9
    k = 1
    while previous_bound(k)<n:
        k += 1
    return k,int(previous_bound(k-1))

def get_digit(n):
    if n < 10:
        return n
    elif n >= 10:
        k,pub = get_k_pub(n)
        m = (n-pub) // k
        r = (n-pub) % k
        t = 10**(k-1) + m + 1
        dn = int(str(t)[r-1])
        return dn

def main():
    n = [10**x for x in range(7)]
    ans = 1
    for i in n:
        ans *= get_digit(i)
    return ans