鱼C论坛

 找回密码
 立即注册
查看: 4157|回复: 16

[技术交流] 小练习:20161010 找出这个无理数的小数部分的第n位

[复制链接]
发表于 2016-10-10 09:11:19 | 显示全部楼层 |阅读模式

马上注册,结交更多好友,享用更多功能^_^

您需要 登录 才可以下载或查看,没有账号?立即注册

x
本帖最后由 冬雪雪冬 于 2016-10-17 10:30 编辑

从现在开始我们要开展一批欧拉计划的习题练习。
其实在我们论坛中已有欧拉计划的板块,可能有些鱼油还没注意到。
什么是欧拉计划:http://bbs.fishc.com/thread-60405-1-1.html
我们欧拉板块现已给出了81道题,这批练习将从欧拉计划中选题。其实用python语言完成有很多的优势,可以更简洁更方便的实现。
如果大家有兴趣也可浏览欧拉的英文网站:https://projecteuler.net/archives
这里已经有了500余题。


                               
登录/注册后可看大图

好了言归正传,我们开始做小练习。




题目要求:
以python语言完成,如果是python2请注明。
程序以代码文字格式发帖。
注重程序效率和创意。
答题在一周内完成,即10.17 10:00之前,其后将公开大家的答案,并评比成绩。

另程序和答案可以在网上搜到,希望大家独立完成。

----回帖需写明解题思路,鼓励在程序中加上注释-----
----除列出程序外,请给出输出的结果。----


题目:

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

0.123456789101112131415161718192021...

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

如果用

                               
登录/注册后可看大图
表示这个数小数部分的第 n 位,找出如下表达式的值:


                               
登录/注册后可看大图

评分

参与人数 1鱼币 +5 收起 理由
bacon6581 + 5 阿姨,你又走光了!

查看全部评分

本帖被以下淘专辑推荐:

想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复

使用道具 举报

发表于 2016-10-10 11:48:34 | 显示全部楼层
  1. import time

  2. i,result=1,1  #正整数、结果初始化
  3. s=''          #字符串初始化
  4. t1=time.time()

  5. while True:  
  6.     s+=str(i)   #将所有正整数以字符串的形式连接起来
  7.     i+=1
  8.     if len(s)>=1000000:    #判断总位数是否达到1000000位
  9.         result=int(s[0])*int(s[9])*int(s[99])*int(s[999])*int(s[9999])*int(s[99999])*int(s[999999])
  10.         t=time.time()-t1
  11.         print(result,t)
  12.         break
复制代码


结果:
>>>
210 0.25

评分

参与人数 1荣誉 +10 鱼币 +10 收起 理由
冬雪雪冬 + 10 + 10 热爱鱼C^_^

查看全部评分

想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

发表于 2016-10-10 11:55:04 | 显示全部楼层
本帖最后由 玄天宗 于 2016-10-10 11:59 编辑

1.用的python3
2.代码如下:
  1. s=''  #用一个空的字符串存储小数点的数字
  2. for i in range(1,1000000):
  3.     s +=str(i)
  4.     if len(s)>1000000: #当小数点后有1000000位时,字符串长度已经满足题目要求
  5.         break
  6.    
  7. d1=int(s[0])#取出我需要的部分转化为int型
  8. d10=int(s[9])
  9. d100=int(s[99])
  10. d1000=int(s[999])
  11. d10000=int(s[9999])
  12. d100000=int(s[99999])
  13. d1000000=int(s[999999])

  14. print(d1*d10*d100*d1000*d10000*d100000*d1000000)
复制代码

3.结果:210
4.解题思路:把小数点后面部分的数字利用for循环保存为一个字符串,利用切片取出我需要的部分,转化为int型
新人,估计没有什么创意了,肯定也不是最简单的、、、
暂时就想到这个方法,想学习学习更简单的方法、、、

评分

参与人数 1荣誉 +10 鱼币 +10 收起 理由
冬雪雪冬 + 10 + 10 热爱鱼C^_^

查看全部评分

想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

发表于 2016-10-10 20:59:59 | 显示全部楼层
本帖最后由 bacon6581 于 2016-10-10 21:06 编辑

思路:其实和一楼、二楼差不多。不过我是写完代码了,再去看他们写的代码。
1、造个字符串不少于100万位,用i++往上垒。
2、取出第10、100……1000000位。(小数点后第一位是i[0]哦 )
3、把取出来的这几位全部乘法

  1. from time import time
  2. start = time()

  3. st=''
  4. i=0
  5. result=1
  6. while  len(st)<1000001:
  7.     i=i+1
  8.     st=st+str(i)

  9. i=1
  10. while i<1000000:
  11. #反正小数点后第一位是1,乘不乘无所谓的啦!
  12.     i=i*10
  13.     result=result*int(st[i-1])

  14. print(result)
  15. print(time()-start)
复制代码

  1. >>> ================================ RESTART ================================
  2. >>>
  3. 210
  4. 1.7878320217132568
  5. >>>
复制代码

评分

参与人数 1荣誉 +10 鱼币 +10 收起 理由
冬雪雪冬 + 10 + 10 热爱鱼C^_^

查看全部评分

想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

发表于 2016-10-10 22:45:04 | 显示全部楼层
  1. from time import time
  2. start = time()
  3. i=1
  4. str1=''
  5. while 1:
  6.     str1+=str(i)
  7.     i+=1
  8.     if (len(str1)) >=1000000:
  9.         break;
  10. def countnum(strx,x):
  11.     a=int(strx[x-1])
  12.     return a
  13. j=1;d=countnum(str1,1)
  14. while j<=6:
  15.     d*=countnum(str1,10**j)
  16.     j+=1
  17. print(d)
  18. print(time()-start)
复制代码


结果
  1. 210
  2. 0.10933828353881836
复制代码

评分

参与人数 1荣誉 +7 鱼币 +7 收起 理由
冬雪雪冬 + 7 + 7 热爱鱼C^_^

查看全部评分

想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

发表于 2016-10-11 09:18:44 | 显示全部楼层
这题比较简单,思路就是先取得列表,然后按位置取值再计算。(穷举法)
但是应该有更好的算法不用穷举。
210
[Finished in 0.2s]

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

评分

参与人数 1荣誉 +10 鱼币 +10 收起 理由
冬雪雪冬 + 10 + 10 热爱鱼C^_^

查看全部评分

想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

发表于 2016-10-11 12:49:17 | 显示全部楼层
本帖最后由 hvagab 于 2016-10-17 11:21 编辑

import time
start=time.time()
s='0'
for i in range(1,200000):
    s=s+str(i)

def d(n,x):
    return int(n[x])

f=d(s,1)*d(s,10)*d(s,10**2)*d(s,10**3)*d(s,10**4)*d(s,10**5)*d(s,10**6)
print(f)
print(time.time()-start)

输出结果:
210
0.375

把乘号想成加号了 重新改了一下 思路没有变

评分

参与人数 1荣誉 +7 鱼币 +7 收起 理由
冬雪雪冬 + 7 + 7 热爱鱼C^_^

查看全部评分

想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

发表于 2016-10-11 15:37:30 | 显示全部楼层
#! usr/bin/python
# -*- coding:utf-8 -*-
#python 2.7
str_=reduce(lambda x,y:str(x)+str(y),xrange(1,185400))
print int(str_[0])*int(str_[9])*int(str_[99])*int(str_[999])*int(str_[9999])*int(str_[999999])

评分

参与人数 1荣誉 +7 鱼币 +7 收起 理由
冬雪雪冬 + 7 + 7 热爱鱼C^_^

查看全部评分

想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

发表于 2016-10-11 16:03:37 | 显示全部楼层
  1. import time
  2. time1=time.time()
  3. s=''
  4. i=1
  5. while len(s)<1000000:
  6.        s=s+str(i)
  7.        i+=1
  8. print(int(s[0])*int(s[9])*int(s[99])*int(s[999])*int(s[9999])*int(s[99999])*int(s[999999]),time.time()-time1)
复制代码

210

评分

参与人数 1荣誉 +7 鱼币 +7 收起 理由
冬雪雪冬 + 7 + 7 热爱鱼C^_^

查看全部评分

想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

发表于 2016-10-11 16:39:38 | 显示全部楼层
先看看这个联系,尝试一下总是好的
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

发表于 2016-10-14 20:09:16 | 显示全部楼层
  1. s, n = "", 1
  2. for i in range(1,200000): # 生成无理小数
  3.     s += str(i)
  4. for i in range(7): # 乘
  5.     n *= int(s[10**i-1])
  6. print(n)
复制代码


答案:210

评分

参与人数 1荣誉 +7 鱼币 +7 收起 理由
冬雪雪冬 + 7 + 7 热爱鱼C^_^

查看全部评分

想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

发表于 2016-10-16 09:52:38 | 显示全部楼层
基本思路就是:
把小数点后的数字转换为字符串,然后再从字符串中提取所需要的位数,乘起来即可。

  1. s = ''

  2. for i in range(1,1000000):
  3.     s = s + str(i)
  4.     if len(s) >= 1000000:
  5.         result = int(s[0])*int(s[9])*int(s[99])*int(s[999])*int(s[9999])*int(s[99999])*int(s[999999])
  6.         print(result)
  7.         break
  8. print(s[0])
  9. print(s[9])
  10. print(s[99])
  11. print(s[999])
  12. print(s[9999])
  13. print(s[99999])
  14. print(s[999999])
复制代码


输出结果是:
210
1
1
5
3
7
2
1

评分

参与人数 1荣誉 +10 鱼币 +10 收起 理由
冬雪雪冬 + 10 + 10 热爱鱼C^_^

查看全部评分

想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

发表于 2016-10-16 20:30:37 | 显示全部楼层
本帖最后由 wangzhenas 于 2016-10-16 20:44 编辑

答案: 210
思路: 列表中储存每位数的个数乘位数,比如两位数有90个(10 - 99)列表中储存2*90即180,三位数900个(100-999)储存900*3即2700
find_num函数找到具体每位数字,i表示目标数位数,rest表示减去i<目标位数后剩余的rest位数字,digit表示一个多位数从左到右中的第几位,this_num即当前数字,this_digit表示目标位数

比如100,rest是90,digit=0,即第45个两位数的第0位,就是55的第0位5,以此类推即可


  1. from time import time
  2. from functools import reduce
  3.    
  4. def find_digit(l,num):
  5.     s = 0
  6.     for i in range(1,len(l)):
  7.         s += l[i]
  8.         if s > num:   
  9.             rest = num - (s - l[i]) - 1
  10.             break        

  11.     digit,this_num = rest % i, rest//i + 10**(i-1)
  12.     this_digit = (this_num//(10**(i-digit-1)))%10
  13.    
  14.     print(digit,this_num,this_digit)   
  15.     return this_digit
  16.    

  17. #main   
  18. t = time()

  19. #maximum: 10 ** 6
  20. input_num = 6

  21. #parameter,list init
  22. i,l,maxi = 1,[1],10**input_num  
  23. while sum(l) <= maxi:   
  24.     l.append((10**i - 10**(i-1))*i)
  25.     i += 1
  26.    
  27. #find number (10,100,1000,10000,1000000)
  28. print(reduce(lambda x,y: x*y, (find_digit(l,10**i) for i in range(1,input_num+1))), time()-t)
  29. #end   
复制代码

评分

参与人数 1荣誉 +15 鱼币 +15 收起 理由
冬雪雪冬 + 15 + 15 热爱鱼C^_^

查看全部评分

想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

发表于 2016-10-17 09:50:49 | 显示全部楼层
  1. for i in range(0,1000000):
  2.     a=a+str(i)
  3. b=list(a)
  4. for j in range(0,1000000):
  5. print('d'+str(i)+':'+' 'b[j])
复制代码
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

发表于 2016-11-1 21:29:19 | 显示全部楼层
虽然已经结束了,不过我也来凑一下热闹
想法是:
1)用一个列表存每位数的最大数所占的小数点位号,比如1位数最大数所占的位号是9,2位数占最大数所占的位号是(9+2*90)=189,。。。的列表[0, 9, 189, 2889, 38889, 488889, 5888889]
2)当前位比较列表数,来断定当前位数是属于几位数,比如位号为100的是2位数中的一个
3) 用Position//Count来知道该位号属于哪个Count位数,比如100是2位数45中的一个
4)用Position%Count来知道该位号属于那个Count位数,比如100是2位数45中的5

想法有点蠢···不过,我会继续努力的,每日一题,这是第二题,昨天那题没有做出来
向各位厉害的鱼油,学习,看齐!
  1. Power = 0
  2. NumberLong = [0]
  3. for i in range(1,7):
  4.     Power = 9*i*pow(10,i-1) + Power
  5.     NumberLong.append(Power)
  6. Answer = 1
  7. for i in range(0,8):
  8.     Count = 0
  9.     Position = pow(10,i)
  10.     for Each in NumberLong:
  11.         if Position - Each > 0:
  12.             Count += 1
  13.         else:
  14.             Position = Position - NumberLong[Count-1]
  15.             if Count == 1:
  16.                 Temp = list(range(10))
  17.             else:
  18.                 Temp = list(range(pow(10,Count-1),pow(10,Count)))
  19.             Temp = str(Temp[Position//Count])
  20.             Answer *= int(Temp[Position%Count-1])
  21.             break
  22. print(Answer)
复制代码
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

发表于 2017-10-31 19:11:19 | 显示全部楼层
多谢,学习了
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

发表于 2017-11-1 13:50:09 From FishC Mobile | 显示全部楼层
  1. import math
  2. c,l,i,ti,s=1,1,1,0,1
  3. t=(10,100,1000,10000,100000,1000000)
  4. while c<1000001:
  5.   i+=1
  6.   l=int(math.log10(i))+1
  7.   if c+l>=t[ti]:
  8.     s*=int(str(i)[t[ti]-c-1])
  9.     ti+=1
  10.   c+=l
  11. print s
复制代码

不用一次性生成100万长度的字符串
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

您需要登录后才可以回帖 登录 | 立即注册

本版积分规则

小黑屋|手机版|Archiver|鱼C工作室 ( 粤ICP备18085999号-1 | 粤公网安备 44051102000585号)

GMT+8, 2024-3-29 23:13

Powered by Discuz! X3.4

© 2001-2023 Discuz! Team.

快速回复 返回顶部 返回列表