【讨论】ProjEuler[40]:把数字列为一排……

qibbxxt

来自：http://forum.simwe.com/viewthread.php?tid=911288&extra=page%3D1%26amp%3Bfilter%3Dtype%26amp%3Btypeid%3D508

An irrational decimal fraction is created by concatenating the positive integers:
0.123456789101112131415161718192021...
It can be seen that the 12^(th) digit of the fractional part is 1.
If d_(n) represents the n^(th) digit of the fractional part, find the value of the following expression.
d_(1) × d_(10) × d_(100) × d_(1000) × d_(10000) × d_(100000) × d_(1000000
把数字从1开始按从小到大的顺序排成一列，求出其中第1,10,100,1000,10000,100000,1000000位（从左算起）之积。

我用下面的办法实现，但是觉得有点投机取巧的感觉，希望大家一起讨论，找出高效的做法

1. clear;clc;close all
   
2. tic
   
3. a=1:10^6;
   
4. b=int2str(a);
   
5. b(b==' ')=[];
   
6. c=prod(str2double({b(1),b(10),b(100),b(1000),b(10000),b(100000),b(1000000)}));
   
7. toc
   

复制代码

1. Elapsed time is 3.192799 seconds.
   
2. >> c
   
3. c =
   
4.    210
   
5. 
   

复制代码

lin2009

版主所说的高效的做法，就是运行时间要尽量的短吗？那就必须找出位数和数字的对应的关系式。
不过高效应该是时间、空间（内存）和编程复杂度的综合考虑。
lz的程序，将数字问题化为字符串问题来解决，思路清晰，程序很简单，容易编写，内存需求可能稍大一点，但运行时间很短，算是比较高效的程序了。
若要找对应关系式的话，可能运行时间更短，内容需求更少，但是花在找关系式的时间就变长了。对于个案来说，不划算。
以上为个人见解。

qibbxxt

2# lin2009
恩，非常赞同你的看法，roc的书中也有类似的观点。
就像应用题用算术的方法和方程的方法求解一样，
算术的方法看着是没有用到变量，比较简单，
但是人们需要绞尽脑汁的去思考，
尤其是现在的一些小学生的奥数题，
而如果用方程或者方程组去求解的话，
节省了脑力和时间

lin2009

1. 
   
2. tic
   
3. D_No_Set = 10.^(1:10);
   
4. for k = 1 : length(D_No_Set)
   
5.     D_No = D_No_Set(k);
   
6.     f = @(n) 9*n .* 10.^(n - 1);
   
7.     index = f(1:10);
   
8.     ind = find(D_No >= index);
   
9.     if isempty(ind)
   
10.         D(k) = D_No;
    
11.     end
    
12.     res = D_No - sum(f)(ind));
    
13.     m1 = floor(res/(ind(end) + 1)); % m1 为当前列中的序号
    
14.     n = mod(res, ind(end) + 1); % n 为当前数的第 n 位, 从左算起。
    
15.     m = 10^(ind(end)) + m1 - 1;
    
16.     if n == 0
    
17.         D(k) = mod(m, 10);
    
18.     else
    
19.         m = 10^(ind(end)) + m1 - 1 + 1;
    
20.         D(k) = mod(floor)(m)/10^(ind(end) + 1 - n)), 10);
    
21.     end
    
22. end
    
23. D
    
24. prod(D)
    
25. toc
    

复制代码

ans =
     1     5     3     7     2     1

ans =

   210

Elapsed time is 0.034431 seconds.

程序运行的时间算是缩短了，但是寻找关系式及编程、调试的时间却几十倍的增加。所以在小规模的运算中不划算。

qibbxxt

一个稍高效一点的程序如下：

1. clear;clc;close all
   
2. tic
   
3. n=6;
   
4. a=1:10^n;
   
5. b=cumsum(floor(log10(a))+1);
   
6. c=10.^(0:n);
   
7. g=zeros(size(c));
   
8. for i=1:n+1
   
9.     e=b(find(b>c(i),1)-1);
   
10.     q=a(find(b>c(i),1)-1);
    
11.     d=c(i)-e;
    
12.     if d
    
13.         f=mod(floor((q+1)./10.^(floor(log10(q+1)):-1:0)),10);
    
14.         g(i)=f(d);
    
15.     else
    
16.        f=mod(floor((q)./10.^(floor(log10(q)):-1:0)),10);
    
17.        g(i)=f(end);
    
18.     end
    
19. end
    
20. p=prod(g);
    
21. toc

复制代码

1. Elapsed time is 0.052385 seconds.
   
2. >> p
   
3. 
   
4. p =
   
5. 
   
6.    210
   
7. 
   
8. >>

复制代码

upc1984

引用：

1. 
   
2. In[4]:= Product[t[[10^i]], {i, 0, 6}] /.
   
3.   t -> Flatten@Table[IntegerDigits[m], {m, 1000000}] // Timing
   
4. 
   
5. During evaluation of In[4]:= Part::partd: Part specification t[[1]] is longer than depth of object. >>
   
6. 
   
7. During evaluation of In[4]:= Part::partd: Part specification t[[10]] is longer than depth of object. >>
   
8. 
   
9. During evaluation of In[4]:= Part::partd: Part specification t[[100]] is longer than depth of object. >>
   
10. 
    
11. During evaluation of In[4]:= General::stop: Further output of Part::partd will be suppressed during this calculation. >>
    
12. 
    
13. Out[4]= {3.947, 210}
    

复制代码