小练习：20160704 找出小于1000的数字中令1/d拥有最长循环圈的数字d

冬雪雪冬 · 发表于 2016-7-3 21:05:34

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

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

x

本帖最后由冬雪雪冬于 2016-7-11 13:51 编辑

从现在开始我们要开展一批欧拉计划的习题练习。
其实在我们论坛中已有欧拉计划的板块，可能有些鱼油还没注意到。
什么是欧拉计划：http://bbs.fishc.com/thread-60405-1-1.html
我们欧拉板块现已给出了81道题，这批练习将从欧拉计划中选题。其实用python语言完成有很多的优势，可以更简洁更方便的实现。
如果大家有兴趣也可浏览欧拉的英文网站：https://projecteuler.net/archives
这里已经有了500余题，并且你每做对一题，就可以下载到参考答案的pdf文件，看看你的实现方法与参考答案有什么不同，以利于迅速提高自己的水平。

登录/注册后可看大图

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

题目要求：
以python语言完成，如果是python2请注明。
程序以代码文字格式发帖。
题目比较简单，注重程序效率和创意。
答题在一周内完成，即7.11 10：00之前，其后将公开大家的答案，并评比成绩。
另程序和答案可以在网上搜到，希望大家独立完成。

----除列出程序外，请给出输出的结果。----

题目：

分子为1的分数称为单分数。分母是 2 到 10 的单分数用十进制表示如下：

1/2       =       0.5
1/3       =       0.(3)
1/4       =       0.25
1/5       =       0.2
1/6       =       0.1(6)
1/7       =       0.(142857)
1/8       =       0.125
1/9       =       0.(1)
1/10    =       0.1

其中 0.1(6) 表示 0.166666...,因此它又一个长度为 1 的循环圈。可以看出 1/7 拥有一个 6 位的循环圈。

找出小于 1000 的数字 d，1/d 的十进制表示含有最长的循环圈。

附加题：

以下是斐波那契数列的递归定义：

登录/注册后可看大图

那么其 12 项为:

登录/注册后可看大图

因此第 12 项，

登录/注册后可看大图

，是第一个包含三位数字的项。

斐波那契数列中第一个包含 1000 位数字的项是第几项？

奖励：
对所有完成程序并得出正确答案的将给予加分奖励，优秀的将额外加分。
在完成一批题目后，将根据每期的完成情况总评评出最佳，会有神秘大奖。

冬雪雪冬 · 发表于 2016-7-3 21:08:40

我的答案：

maxlen = 0
for i in range(2, 1000):
if i <= 10:
num = 10
elif i <= 100:
num =100
else:
num = 1000
list1 = []
num1 = [1]
length = 0
while True:
list1.append(num // i)
num %= i
if num == 0:
break
if num in num1:
length = len(list1[num1.index(num):])
break
num1.append(num)
num *= 10
if length > maxlen:
maxlen = length
maxn = i
print(maxn)

复制代码

983

复制代码

def fab():
n1, n2 = 1, 1
while True:
n2, n1 = n1 + n2, n2
yield n2
import time
tt = time.time()
i = 3
for n in fab():
if len(str(n)) > 999:
break
i += 1
print(i)
print('%.2f s'%(time.time() - tt))

复制代码

4782
0.14 s

复制代码

caobynk · 发表于 2016-7-4 06:54:18

def getloop(n):
up = [10]
result = [int(10/n)]
down = 10*(10%n)
while (down not in up) and (down > 0):
up.append(down)
result.append(int(down/n))
down = 10*(down%n)
if down > 0:
nLoop = result[up.index(down):]
else:
nLoop = []
return nLoop
if __name__ == '__main__':
result = []
Num = 1
for num in range(1,1000):
num_loop = getloop(num)
if len(num_loop) > len(result):
Num = num
result = num_loop
print('具有最长循环圈的数字为：' + str(Num))
from functools import reduce
print('循环圈为：'+ reduce(lambda x,y: str(x)+str(y), result))
# 附加题
def getIndex(n):
a = b = 1
c = a + b
k = 3
while (len(str(c))) < n:
a, b = b, c
c = a + b
k += 1
return k
if __name__ == '__main__':
n = 1000
print(getIndex(n))

复制代码

Spicebush · 发表于 2016-7-4 13:49:24

本帖最后由 Spicebush 于 2016-7-16 18:57 编辑

#答案为983
num_s = {1}
for num in range(1, 1000):
while num%2 == 0:
num /= 2
while num%5 == 0:
num /= 5
num_s.add(num)
number = 0
length = 0
for n in num_s:
t = 9
while t%n != 0:
t = 10*t+9
l = len(str(t))
if l > length:
length = l
number = n
print(number)

复制代码

附加题：

#答案为4782
known = {0:0, 1:1}
def fib(n):
if n in known:
return known[n]
res = fib(n - 1) + fib(n - 2)
known[n] = res
return res
#以上程序以前看过，这次正好拿来用
n = 1
while n > 0:
num = fib(n)
if len(str(num)) < 1000:
n += 1
else:
print(n)
n = 0

复制代码

THU-CUI · 发表于 2016-7-4 16:37:51

看起来好流弊的样子，可惜不怎么会啊

小剑剑 · 发表于 2016-7-4 20:50:16

def circle(num):
n=10
while n<num:
n*=10
circle1=[]
while 1:
m=n%num
if m==0:
return 0
elif m in circle1:
return len(circle1)-circle1.index(m)
circle1.append(m)
n*=10
from functools import reduce
a=1
b=1
i=2
while b<10**999:
b,a=a+b,b
i+=1
print(reduce(lambda x,y:x if x[1]>y[1]else y,enumerate(map(circle,range(1,1001)),1))[0],i)

复制代码

huomqh · 发表于 2016-7-5 01:43:47

本帖最后由 huomqh 于 2016-7-6 20:55 编辑

import time
tt=time.time()
def l(x):
a=[]
numerator=1000
while 1:
remainder=numerator % x
if remainder==0:
return 0
elif remainder in a:
return len(a)-a.index(remainder)
else:
a.append(remainder)
numerator = remainder *10
while numerator<= x:
a.append(0)
numerator=numerator*10
maxi=0
maxl=0
ll=0
i=3
while i<1000:
ll=l(i)
if maxl<ll:
maxl=ll
maxi=i
i+=2
print ("d=%d,循环体长度=%d"%(maxi,maxl))
print('用时：%.4f s'%(time.time() - tt))

复制代码

d=983,循环体长度=982
用时：0.3900 s

附加题：

import time
tt=time.time()
import sys
sys.setrecursionlimit(1000000)
def fbnq(x,y,i):
if x+y>=n:
print(i)
else:
fbnq(y,x+y,i+1)
n=10**999
fbnq(1,1,3)
print('用时：%.4f s'%(time.time() - tt))

复制代码

4782
用时：0.0468 s

wangzhenas · 发表于 2016-7-5 06:04:45

第一题： 983

import time
def primes_sieve(limit=100):
limitn,not_prime,primes = limit+1,set(),list()
for i in range(2, limitn):
if i in not_prime:
continue
for f in range(i*2, limitn, i):
not_prime.add(f)
primes.append(i)
return primes
t,maxi,prime_l = time.time(),(0,),primes_sieve(1000)[4:]
for prime in prime_l:
summ,i = 9,1
while summ%prime != 0:
summ = summ*10+9
i += 1
if i > maxi[0]:
maxi = i,prime
print(maxi[1],'time:',time.time()-t)

复制代码

第二题：4782

import time
a,b,i,t = 1,1,2,time.time()
while len(str(a)) < 1000:
a,b,i = a+b,a,i+1
print(i,'time:',time.time()-t)

复制代码

老忘 · 发表于 2016-7-5 14:40:45

本帖最后由老忘于 2016-7-5 14:59 编辑

小练习：

# -*- coding:Utf-8 -*-
import time
start= time.clock()
def js(num):
b=1
list_temp=[]
list_rel=[]
while 1:
if (b*10)%num ==0:
list_temp.append([int((b*10)/num),0])
list_rel=[False,len(list_temp)]
break
elif ([int((b*10)/num),(b*10)%num] in list_temp):
list_rel=[True,len(list_temp)-list_temp.index([int((b*10)/num),(b*10)%num])]
break
else:
a=int((b*10)/num)
b=(b*10)%num
list_temp.append([a,b])
return list_rel
list_len=[]
for i in range(1,1000):
if js(i)[0]:
list_len.append([js(i)[1],i])
print(max(list_len)[1])
end = time.clock()
print ("read: %f s" % (end - start))

复制代码

小练习计算结果：983

复制代码

附加题：

int_count=3
a,b=1,1
while len(str(a+b))<1000:
int_count+=1
a,b=b,a+b
print(int_count)

复制代码

附加题计算结果：4782

复制代码

bacon6581 · 发表于 2016-7-6 23:19:41

本帖最后由 bacon6581 于 2016-7-7 15:19 编辑

为什么小数点精度取2003呢？
我先取的500，不够。。。
再取的1000，还是不够用。。。
取到2000，够用了。。。

from time import time
from decimal import *
start=time()
getcontext().prec=2003
#
len_max=0
num=0
for i in range(6,1000):
length=1
zhi_str=str(Decimal(1)/Decimal(i))
if len(zhi_str)<100:
continue
zhi_str=zhi_str[:-3]
while length<=999:
if zhi_str[len(zhi_str)-length:]==zhi_str[len(zhi_str)-length*2:len(zhi_str)-length]:
break
length+=1
if length>len_max:
len_max=length
num=i
print('d is: ',num)
print('len_max is: ',len_max)
print('Used time is: ',time()-start)

复制代码

from time import time
start=time()
lie={1:1,2:1}
n=2
while 1:
n+=1
lie[n]=lie[n-1]+lie[n-2]
if len(str(lie[n]))>=1000:
break
print(n)
print(lie[n])
print(time()-start)

复制代码

原先想用递归的，吃晚饭，睡了一觉，还没算完....
然后用字典
再用列表，还比字典慢一点点

back0893 · 发表于 2016-7-7 12:07:06

import math
#首先计算1000内的的所有素数
def getn(n):
for i in range(3,n+1,2):
      isn=True
      for j in range(3,int(math.sqrt(i)+1)):
         if i%j==0:
            isn=False
            break
      if isn:
         yield i
Max=0
Maxn=0
for i in getn(1000):
length=0
temp1=1
temp2=[]
for j in range(i):
      temp1=(temp1*10)%i#利用余数，求重复长度
      if temp1 not in temp2: #余数没有出现过就，加入list
         temp2.append(temp1)
      else:
         star=temp2.index(temp1)#定位循环开始处
         length=len(temp2)-star
         if length>Max:
            Max=length
            Maxn=i
print(Maxn,Max)

shichaoufo · 发表于 2016-7-7 16:21:54

最长循环的数字是983,长度为982

import time
start = time.time()
num = 0
fenshu = 0
for d in range(2,1000):
c = []
b = 1*pow(10,len(str(d)))
a,b = divmod(b,d)
while b:
if b in c:
if len(c)-c.index(b) > num:
num = len(c)-c.index(b)
fenshu = d
break
if a:
c.append(b)
b *= 10
else:
c.append(None)
b *= 10
a,b = divmod(b,d)
yongshi = time.time()-start
print("最长循环的数字是%d,长度为%d" % (fenshu,num))
print("用时%f秒" % yongshi)

复制代码

附加题
斐波那契数列中第一个包含1000位数字的项是第4782项

import time
start = time.time()
a=1
b=1
num = 1
while not (a // pow(10,999)):
c = b
b = a + b
a = c
num += 1
yongshi = time.time() - start
print("斐波那契数列中第一个包含1000位数字的项是第%d项" % num)
print("用时%f秒" % yongshi)

复制代码

a1104201 · 发表于 2016-7-7 16:44:50

#-*- coding:UTF-8 -*-

def fab(n):
if n==1:
      return 1;
if n==0:
      return 0;
else:
      result = fab(n-1) + fab(n-2);
      return result;

for i in range(1000):
a = fab(i);
if a >= 1000 :
      print("第%s项是第一出现三围数的，数字为%s" % (i,a));
      break;

tengfei8382 · 发表于 2016-7-8 00:47:59

import time
tt = time.time()
def feb():
a = 0
b = 1
while True:
a,b = b,a+b
yield a
lenght = 0
feb_num = ""
f = feb()
count = 0
while lenght < 1000:
feb_num = str(next(f))
lenght = len(feb_num)
count += 1
print("共计用时：%.4f s"%(time.time()-tt))
print(count)

复制代码

附加题，主题有点没看懂。那个循环节是怎么求出来的呢？
答案是4782

DingRan · 发表于 2016-7-8 12:40:53

严重支持

def cycleNum(n):
while n%2 == 0:
n = int(n/2)
while n%5 == 0:
n = int(n/5)
s = 1
while True:
if (10**s-1)%n == 0:
break
s += 1
return s
maxr = 0
for i in range(1, 1000):
r = cycleNum(i)
if r > maxr:
maxr = r
maxi = i
print('1/%s 的十进制表示含有最长的循环圈，长度为 %s'%(maxi,maxr))
###############附加题################
i = 0
f1 = 0
f2 = 1
while True:
i += 1
if len(str(f2)) > 999:
break
f1, f2 = f2, f1+f2
print('附加题：斐波那契数列中第一个包含 1000 位数字的项是第 %s 项' %i)

复制代码

运行结果：

>>>
1/983 的十进制表示含有最长的循环圈，长度为 982
附加题：斐波那契数列中第一个包含 1000 位数字的项是第 4782 项
>>>

复制代码

mather · 发表于 2016-7-10 22:12:03

本帖最后由 mather 于 2016-7-10 22:22 编辑

第一题：

import time
on = time.time()
dics = [0]*1000
the_res = 1
max_len = 0
for i in range(1,1001):
#去掉2，5因数剩下的数和其值求得的循环数一致
while i % 2==0:
i = i//2
while i % 5==0:
i = i//5
if dics[i]:
j = dics[i]
else:
j=1
while (10**j-1)%i != 0:
j+=1
dics[i]=j
if max_len < j:
max_len = j
the_res = i
print("1/%d循环数是：%d" % (the_res,max_len))
print(time.time()-on)

复制代码

结果：1/983循环数是：982
用时：0.15621447563171387

附加题：

import time
on = time.time()
data1 = 1
data2 = 1
data3 = data1 + data2
index = 3
while(len(str(data3))<1000):
data1 = data2
data2 = data3
data3 = data1+data2
index += 1
print(index)
print(time.time()-on)

复制代码

结果：4782
用时：0.06375360488891602

挥舞乾坤 · 发表于 2016-7-11 09:22:04

import time
def long(n):
while True:
m = n
if n % 2 == 0:
n = n // 2
if n % 5 == 0:
n = n // 5
if m == n:
break
i = 1
m = 9
while True:
if m % n == 0:
return i
m += 9 * 10 ** i
i += 1
return i
t = time.time()
r = [i for i in range(1,1001) if i % 2 and i % 5]
print(max(r, key=long))
print(time.time() - t)

复制代码

答案：983
附加题：

import time
t = time.time()
a, b, i= 0, 1, 1
while True:
if 1 < b / (10 ** (1000-1)) < 10:
print(i)
break
a, b = b, a + b
i += 1
print(time.time() - t)

复制代码

附加题答案：4782

leozyre · 发表于 2016-7-16 15:36:50

Spicebush 发表于 2016-7-4 13:49
附加题：

请问为什么可以把1/n转化成10*n+9呢。。

Spicebush · 发表于 2016-7-16 18:59:06

本帖最后由 Spicebush 于 2016-7-18 08:08 编辑

leozyre 发表于 2016-7-16 15:36
请问为什么可以把1/n转化成10*n+9呢。。

   对于大于1的整数d，将其表示为d=(2^p)*(5^q)*d'，其中p、q均为非负整数，d'为不能被2或5整除的整数。
   若d'等于1，则1/d不为循环小数。当d'不等于1时，则从一个9开始，用一连串的9除以d'，当恰好能整除时，9的个数即为1/d的循环圈长度。
   例如，当d=(2^p)*(5^q)*3时，9/3=3，所以此时1/d的循环圈长度为1;当d=(2^p)*(5^q)*7时，9/7=1……2，99/7=14……1，……，999999/7=142857，所以此时1/d的循环圈长度为6。

   PS：每次在答题之前我都会去查一查里面有没有什么数学小知识，然后再去编程。其实有些知识我们在小学或中学的时候都接触过，只不过现在都忘得差不多了。另外，通过回答你的问题我发现我的程序里有一个当初的错误想法，现已修改。

leozyre · 发表于 2016-7-16 19:13:22

Spicebush 发表于 2016-7-16 18:59
对于大于1的整数d，将其表示为d=(2^p)*(5^q)*d'，其中p、q均为非负整数，d'为不能被2或5整除的整 ...

哦哦哦谢了

账号		自动登录	找回密码
密码			立即注册

[技术交流] 小练习：20160704 找出小于1000的数字中令1/d拥有最长循环圈的数字d

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

评分

评分

评分

评分

评分

评分

评分

评分

评分

评分

评分

评分

评分