关于确定循环小数的位数的算法?
由之前的帖子的大家想的一个算法题目,由于是另外一个题目,所以开一个新的帖子..关于这个算法,我真的是还没有什么概念
只是想到是否可以有一个数组可以去存每一位的小数,然后比较是否已经构成循环
可是怎么样判断是构成循环了?还有数组要有多大?小数要求多少位才能确定不是循环小数?
这些都不知道怎么去想.
有人说ACM的有关于这个的算法,可不可以给说一下? a=小数(0); b=小数(1); for (i=0; a!=b; i++) b=小数(i); //结果=i 楼上的好像不是很对吧？小数循环部分也有部分数字可以相同呀。 不好意思应该是余数才对:D 很难处理，有科学家发现上千位的循环小数呢 再次说明了数学牛才是真的牛 我们知道任意分数，总可以化为有限小数或者无限循环小数，不会出现不循环的情况！现在任意给定一个分数，将其化为0.12（34）的形式，其中括号里面的是循环节！
numerator=input("Input the numerator(0,3000):")
denominator=input("Input the denominator(0,3000):")
while numerator>=3000 or denominator>=3000 or numerator<0 or denominator<0:
numerator=input("Input the numerator(0,3000):")
denominator=input("Input the denominator(0,3000):")
residue=[]
quotient=[]
if numerator>=denominator:
quotient.append(numerator/denominator)
numerator=numerator%denominator
else:
quotient.append(0)
isCircle=0
circleFlag=0
p=1
while numerator and not isCircle:
residue.append(numerator)
quotient.append(numerator*10/denominator)
numerator=numerator*10-quotient*denominator
p+=1
if numerator:
for circleFlag in range(p-1):
if numerator==residue:
isCircle=1
break
if not isCircle:
print "The result is limited."
print quotient,'.',
for k in range(1,p):
print "%d"%quotient,
else:
print "The result is unlimited."
print quotient,'.',
if circleFlag:
for k in range(1,circleFlag+1):
print "%d"%quotient,
print "(",
for k in range(circleFlag+1,p):
print "%d"%quotient,
print ")"
print "There are %d positions circle!" % (p-circleFlag-1)
这个程序原理很简单，因为所谓循环，实际上就是我们作除法是遇到的余数开始和前面的重复！所以只要找到余数重复，就发现循环节了！ 我曾经以为有一个算法可以优化这个题目，可惜，我查阅了相关资料，发现我是做不到了！
诚然，算法依然有，不过并不简洁。运用了近世代数里面的群论和费尔马小定理！对分母进行相当复杂的判断，可以确定其循环节的位数！通过分解分母因子，可以确定不循环的部分，我想比除商，然后看小数还是要简单一些！但是实在不会简单很多，因为对分母的判断太难了！不过倒是借此复习了一点近世代数，呵呵 优化的话可用高精度的优化原理
可以测试到小数点后10000位以上都没问题
不过代码多拉 不是很看得懂算法,得慢慢再研究一下
页:
[1]