题目40：找出这个无理数的小数部分的第n位

欧拉计划

Champernowne's constant

An irrational decimal fraction is created by concatenating the positive integers:

0.123456789101112131415161718192021...

It can be seen that the 12th digit of the fractional part is 1.

If represents the nth digit of the fractional part, find the value of the following expression.

题目：

将正整数连接起来可以得到一个无理小数：

0.123456789101112131415161718192021...

可以看出小数部分的第 12 位是 1。

如果用 表示这个数小数部分的第 n 位，找出如下表达式的值：

迷雾少年

210。。不知道对否

1. #include <iostream>
   
2. using namespace std;
   
3. //获取一个int类型的位数
   
4. int get(int n)
   
5. {
   
6.         if(n==0) return 1;
   
7.         int m = 0;
   
8.         while (n)
   
9.         {
   
10.                 n/=10;
    
11.                 m++;
    
12.         }
    
13.         return m;
    
14. }
    
15. //获取一个数的第几位
    
16. //从左边开始第几个
    
17. int  getnum(int n,int m)
    
18. {
    
19.         int k = get(n)-m+1; //就是右边的k个
    
20.         int z = 1;
    
21.         while (n)
    
22.         {
    
23.                 if(z==k)
    
24.                         return n%10;
    
25.                 n/=10;
    
26. 
    
27.                 z++;
    
28. 
    
29.         }
    
30. }
    
31. int main(void)
    
32. {
    
33. 
    
34.         int j=0;//第几位
    
35.         int z = 0;
    
36.         int result = 1;
    
37. 
    
38.         for (int i =1;i<1000000;i++)
    
39.         {
    
40.                 z=get(i);
    
41.                 for (int k=j+1;k<=j+z;k++)
    
42.                 {
    
43.                           if(k==10 || 100==k || 1000==k || 10000==k || 100000==k|| 1000000==k)
    
44.                           {
    
45.                                    result*=getnum(i,k-j);
    
46.                           }
    
47.                
    
48.                 }
    
49.                 j+=z;
    
50.                
    
51.        
    
52.         }
    
53.         std::cout<<result;
    
54.         return 0;
    
55. }

复制代码

愤怒的大头菇

1. str_1 = '0'
   
2. for i in range(1,1000000):
   
3.       str_1 += str(i)
   
4. str_2 = '1'
   
5. count = 1
   
6. for i in range(7):
   
7.       count *= int(str_1[int(str_2)])
   
8.       str_2 += '0'
   
9. print(count)

复制代码

结果210

jerryxjr1220

210
[Finished in 0.4s]

1. def getstr(n):
   
2.         strlist = '1'
   
3.         for i in range(2,n+1):
   
4.                 strlist += str(i)
   
5.         return strlist
   
6. strlist = getstr(200000)
   
7. cal = 1
   
8. for j in range(7):
   
9.         cal *= int(strlist[10**j-1])
   
10. print (cal)

复制代码

芒果加黄桃

1. # encoding:utf-8
   
2. # 小数后第N位相乘
   
3. from time import time
   
4. def euler040():
   
5.     s_tmp = '.'
   
6.     result = 1
   
7.     for i in range(1,200000):
   
8.         s_tmp += str(i)
   
9.         if len(s_tmp) > 1000000:
   
10.             break
    
11.     for i in range(0,7):
    
12.         result *= int(s_tmp[10**i])
    
13.     print(result)
    
14. if __name__ == '__main__':
    
15.     start = time()
    
16.     euler040()
    
17.     print('cost %.6f sec' % (time() - start))
    

复制代码

210
cost 0.120103 sec

loadinggg

大神们大部分都是遍历1000000
我觉得先分析了一波ps输出格式抄袭了渡风大神一波，前面很多题也感谢渡风大神给我的灵感

此代码使用matlab编程
该问题所用时间为0.007945秒
该问题的答案为210

1. function Output = champernownesConstant_40(Input)
   
2. tic
   
3. if nargin == 0
   
4.     Input = [100,1000,10000,100000,1000000];
   
5. end
   
6. %想找到各个位置上的数字，不用全部写出来，只需要计算位数就可以
   
7. %个位数1-9，十位数10-99，百位数100-999，千位数1000-9999，万位数10000-99999，十万位数100000-999999
   
8. %上述的数字个数一共是9+90*2+900*3+9000*4+90000*5+100000*6 = 1088889位数
   
9. %先判断出Input中的数是属于哪两个位数之间的，然后根据低位数的第几个判断出来第几个数
   
10. %第一位和第十位都是1
    
11. list = [9,189,2889,38889,488889,1088889];
    
12. Num = 1;
    
13. for ii = 1:length(Input)
    
14.     s = find(list>Input(ii));
    
15.     %s(1) - 1 = [1 2 3 4 5]
    
16.     a = floor((Input(s(1)-1) - list(s(1)-1))/s(1));%低位数的第几个数-1
    
17.     b = mod((Input(s(1)-1) - list(s(1)-1)),s(1));
    
18.     qianshu = a + 10^(ii) - 1;
    
19.     if b == 0
    
20.         res = num2str(qianshu);
    
21.         Num = Num * str2num(res(end));
    
22.     else
    
23.         zhenshu = qianshu + 1;
    
24.         res = num2str(zhenshu);
    
25.         Num = Num * str2num(res(b));
    
26.     end
    
27. end
    
28. Output = Num;
    
29. toc
    
30. disp('此代码使用matlab编程')
    
31. disp(['该问题所用时间为',num2str(toc),'秒'])
    
32. disp(['该问题的答案为',num2str(Output)])

复制代码

渡风

loadinggg 发表于 2017-5-21 22:12
大神们大部分都是遍历1000000
我觉得先分析了一波ps输出格式抄袭了渡风大神一波，前面很多题也感谢渡风大 ...

感觉招式被偷了

渡风

此代码使用matlab编程
Problem40所用时间为0.0063565秒
Problem40的答案为210
编程思路与楼上一致。

1. %% Problem40.m
   
2. %最后编辑时间：2017-06-12 19:11 版本1.0
   
3. %将正整数连接起来可以得到一个无理小数: 0.123456789101112131415161718192021...
   
4. %求第1,10,100,1000,10000,100000,1000000，的乘积
   
5. function Output = Problem40()
   
6. tic
   
7. boundary = [1 2 3 4 5 6].*[9 90 900 9000 90000 900000];
   
8. boundary = cumsum(boundary);              %找出位数的边界
   
9. Set = [10 100 1000 10000 100000 1000000];
   
10. 
    
11. Output = 1;
    
12. for ii = 1:6
    
13.     Temp = Set(ii);
    
14.     for jj = 1:length(Set)
    
15.         if boundary(jj) < Temp && Temp <= boundary(jj+1)   %预测在哪个位置
    
16.             Start = jj;            
    
17.             break
    
18.         end
    
19.     end
    
20.    
    
21.     Distance = Set(ii) - boundary(Start);
    
22.     Num = floor(Distance / (Start + 1));
    
23.     Numset = mod(Distance,Start + 1);
    
24.    
    
25.     All  = 10^Start : 10^(Start + 1);
    
26.    
    
27.     if Numset == 0
    
28.         Exact = num2str(All(Num));
    
29.         Output = Output * str2double(Exact(end));
    
30.     else
    
31.         Exact = num2str(All(Num+1));        
    
32.         Output = Output * str2double(Exact(Numset));
    
33.     end
    
34.         
    
35. end
    
36.    
    
37. toc
    
38. 
    
39. disp('此代码使用matlab编程')
    
40. disp(['Problem40所用时间为',num2str(toc),'秒'])
    
41. disp(['Problem40的答案为',num2str(Output)])
    
42. end

复制代码

k往事如烟k

1. strTemp = ""
   
2. for i in range(1, 200000):
   
3.     strTemp += str(i)
   
4. 
   
5. product = 1
   
6. for n in [1, 10, 100, 1000, 10000, 100000, 1000000]:
   
7.     product *= int(strTemp[n-1])
   
8. 
   
9. print(product)

复制代码

210

王小召

结果是：210
用时：0.2652017 秒

1. import functools
   
2. import time
   
3. 
   
4. def get_str(num):
   
5.     count = 0
   
6.     tmp = 0
   
7.     while count < num:
   
8.             tmp += 1
   
9.             count += len(str(tmp))
   
10.     return str(tmp)[num - count - 1]
    
11. 
    
12. print("结果是：{}\n用时：{} 秒".format(
    
13.     functools.reduce(lambda x, y: x*y, [int(i) for i in map(get_str, [10**i for i in range(7)])]),
    
14.     time.process_time()))

复制代码

永恒的蓝色梦想

1. ZERO_ACSII = ord('0')
   
2. func = lambda x : ord(digits[x]) - ZERO_ACSII
   
3. digits = [None]
   
4. i = 1
   
5. 
   
6. 
   
7. while len(digits) <= 1000000:
   
8.     digits += str(i)
   
9.     i += 1
   
10. 
    
11. 
    
12. print(func(1) * func(10) * func(100) * func(1000) * func(10000) * func(100000) * func(1000000))

复制代码

debuggerzh

210

Process returned 0 (0x0)   execution time : 0.034 s
Press any key to continue.
参考了6#的解法，先确定每个位数所在的自然数区间，再求出偏移量，取余可以确定具体取那一位
位数和通项公式

                               
登录/注册后可看大图

1. #include<iostream>
   
2. #include<cstdio>
   
3. #include<vector>
   
4. using namespace std;
   
5. 
   
6. const int dgt[] = {0,9,189,2889,38889,488889,5888889};//0为占位符
   
7. const int M = 1000000;
   
8. 
   
9. int extract(int x,int digit){
   
10.   vector<int> v;
    
11.   while(x){
    
12.     v.push_back(x % 10);
    
13.     x /= 10;
    
14.   }
    
15.   int n = v.size();
    
16.   return v[n - 1 - digit];
    
17. }
    
18. 
    
19. int main(){
    
20.   int ans = 1;
    
21. 
    
22.   for (int i = 10;i <= M;i*=10){
    
23.     int cur_dgt;
    
24.     for (int j = 1;j < 6;j++)
    
25.       if (i > dgt[j] && i < dgt[j+1]) {cur_dgt = j+1; break;}//落在哪一区间
    
26.     int t = i - dgt[cur_dgt-1] - 1;
    
27.     int cnt = t / cur_dgt;//偏移了cnt个数
    
28.     int resd = t % cur_dgt;//取该数的第几位
    
29.     int tar = i/10 + cnt;//目标数
    
30.     //printf("%d %d %d %d %d\n",t,cur_dgt,cnt,tar,resd);
    
31.     ans *= extract(tar,resd);
    
32. 
    
33.   }
    
34.   cout << ans << endl;
    
35.   return 0;
    
36. }
    

复制代码

4444567

1000005 185186
1 1 5 3 7 2 1
210

1. n = ''
   
2. a = 1
   
3. while len(n) < 1000001:
   
4.     n += str(a)
   
5.     a += 1
   
6.    
   
7. print(len(n),a)
   
8. print(int(n[0]) , int(n[9]) , int(n[99]) , int(n[999]),int(n[9999]) ,int(n[99999]) , int(n[999999]))
   
9. print(int(n[0]) * int(n[9]) * int(n[99]) * int(n[999]) * int(n[9999]) * int(n[99999]) * int(n[999999]))

复制代码

a1351468657

1. #include <stdio.h>
   
2. #include <string.h>
   
3. 
   
4. main()
   
5. {
   
6.         char str[1000010], temp[128];
   
7.         int i = 1, count = 1;
   
8.         str[0] = '1';
   
9.         str[1] = '\0';
   
10. 
    
11.         for (i = 2; i < 1000000; i++)
    
12.         {
    
13.                 if (count >= 1000000)
    
14.                 {
    
15.                         break;
    
16.                 }
    
17.                 sprintf(temp, "%d", i);
    
18.                 count += strlen(temp);
    
19.                 strcat(str, temp);                       
    
20.         }
    
21.         count = 1;
    
22.         for (i = 1; i < 1000001; i *= 10)
    
23.         {
    
24.                 printf("%c ", str[i - 1]);
    
25. 
    
26.                 count *= (str[i - 1] - '0');
    
27.         }
    
28.         printf("\n%d\n", count);
    
29. }

复制代码

210

ft215378

#找出这个无理数的小数部分的第n位
from time import *
#简单计算得出当数字在19万以内 位数超过百万
def d(n):
    str1 = ''
    num = 1
    while True:
        str1 += str(num)
        num += 1
        if num == 190000:
            break
    return  int(str1[n-1])

#计算
start = time()
n = 1
result = 1
while n:
    result *= d(n)
    n *= 10
    if n == 1000000:
        break

end = time()
print(result)
print("用时：%.4f秒" % (end-start))

guosl

1. #include <iostream>
   
2. #include <cstdlib>
   
3. #include <cstring>
   
4. using namespace std;
   
5. 
   
6. int f[] = { 0,9,2 * 90,3 * 900,4 * 9000,5 * 90000,6 * 900000 };//f[i]记录i位数的个数
   
7. int g[] = { 0,1,10,100,1000,10000,100000 };//记录i位数的第一个数
   
8. 
   
9. int getDigit(int k)
   
10. {
    
11.   int nCount = 0, i;
    
12.   for (i = 1; i <= 6; ++i)//找出k是几位数
    
13.   {
    
14.     if (nCount + f[i] >= k)
    
15.       break;
    
16.     nCount += f[i];
    
17.   }
    
18.   k -= nCount;//计算k在i位数中的位置
    
19.   int n = g[i] + k / i - 1, m = k % i;//计算出具体的数
    
20.   //输出具体的数字
    
21.   char str[12];
    
22.   int nL;
    
23.   if (m == 0)
    
24.   {
    
25.     _itoa_s(n, str, 10);
    
26.     nL = strlen(str);
    
27.   }
    
28.   else
    
29.   {
    
30.     _itoa_s(n + 1, str, 10);
    
31.     nL = m;
    
32.   }
    
33.   return int(str[nL - 1] - 48);
    
34. }
    
35. 
    
36. int main(void)
    
37. {
    
38.   int p = getDigit(1);
    
39.   p *= getDigit(10);
    
40.   p *= getDigit(100);
    
41.   p *= getDigit(1000);
    
42.   p *= getDigit(10000);
    
43.   p *= getDigit(100000);
    
44.   p *= getDigit(1000000);
    
45.   cout << p << endl;
    
46.   return 0;
    
47. }

复制代码

B1tetheDust

1. import time as t
   
2. 
   
3. start = t.perf_counter()
   
4. d_n = ''
   
5. for i in range(185186):
   
6.     d_n += str(i)
   
7. 
   
8. product = 1
   
9. for j in range(7):
   
10.     print('d_%d = %s' % (10 ** j, d_n[10 ** j]))
    
11.     product *= int(d_n[10 ** j])
    
12. 
    
13. print(product)
    
14. print("It costs %f s" % (t.perf_counter() - start))
    

复制代码

d_1 = 1
d_10 = 1
d_100 = 5
d_1000 = 3
d_10000 = 7
d_100000 = 2
d_1000000 = 1
210
It costs 0.067895 s

mathtimes

1. $ time ./main
   
2. 210
   
3. 
   
4. real        0m0.001s
   
5. user        0m0.000s
   
6. sys        0m0.001s

复制代码

1. // count bits before 10^l
   
2. fn cb(l: u32) -> u32 {
   
3.     if l == 0 {
   
4.         return 0;
   
5.     }
   
6.     9 * 10u32.pow(l - 1) * l + cb(l - 1)
   
7. }
   
8. 
   
9. // 返回第i位所在的数字以及偏移量
   
10. fn b2n(x: u32) -> (u32, u32) {
    
11.     let mut base_l = 1;
    
12.     while cb(base_l) < x {
    
13.         base_l += 1;
    
14.     }
    
15.     base_l -= 1;
    
16.     (
    
17.         (x - cb(base_l)) / (base_l + 1) + 10u32.pow(base_l) - 1,
    
18.         (x - cb(base_l)) % (base_l + 1),
    
19.     )
    
20. }
    
21. 
    
22. fn d(x: u32) -> u32 {
    
23.     let (b, mut i) = b2n(x);
    
24.     if i == 0 {
    
25.         return b % 10;
    
26.     }
    
27.     let mut y = b + 1;
    
28.     i = y.ilog10() + 2 - i;
    
29.     let mut r = 0;
    
30.     while i > 0 {
    
31.         r = y % 10;
    
32.         y /= 10;
    
33.         i -= 1;
    
34.     }
    
35.     r
    
36. }
    
37. fn main() {
    
38.     println!("{}", (0..=6).map(|x| d(10u32.pow(x))).product::<u32>())
    
39. }

复制代码

测试

1. #[cfg(test)]
   
2. mod tests {
   
3.     use super::*;
   
4.     #[test]
   
5.     fn test_cb() {
   
6.         assert_eq!(cb(1), 9);
   
7.         assert_eq!(cb(2), 189);
   
8.     }
   
9.     #[test]
   
10.     fn test_b2n() {
    
11.         assert_eq!(b2n(8), (8, 0));
    
12.         assert_eq!(b2n(9), (9, 0));
    
13.         assert_eq!(b2n(100), (54, 1));
    
14.         assert_eq!(b2n(189), (99, 0));
    
15.         assert_eq!(b2n(191), (99, 2));
    
16.         assert_eq!(b2n(192), (100, 0));
    
17.     }
    
18.     #[test]
    
19.     fn test_d() {
    
20.         assert_eq!(d(1), 1);
    
21.         assert_eq!(d(12), 1);
    
22.         assert_eq!(d(13), 1);
    
23.         assert_eq!(d(100), 5);
    
24.     }
    
25. }

复制代码