关于确定循环小数的位数的算法?

jinry

由之前的帖子的大家想的一个算法题目,由于是另外一个题目,所以开一个新的帖子..

关于这个算法,我真的是还没有什么概念
只是想到是否可以有一个数组可以去存每一位的小数,然后比较是否已经构成循环
可是怎么样判断是构成循环了?还有数组要有多大?小数要求多少位才能确定不是循环小数?
这些都不知道怎么去想.

有人说ACM的有关于这个的算法,可不可以给说一下?[em021]

不会游泳鱼

a=小数(0); b=小数(1); for (i=0; a!=b; i++) b=小数(i); //结果=i

gyCai

楼上的好像不是很对吧？小数循环部分也有部分数字可以相同呀。

不会游泳鱼

不好意思应该是余数才对:D

漂流瓶

很难处理，有科学家发现上千位的循环小数呢

Leon001

再次说明了数学牛才是真的牛

cdy20

我们知道任意分数，总可以化为有限小数或者无限循环小数，不会出现不循环的情况！现在任意给定一个分数，将其化为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[p]*denominator
    p+=1
    if numerator:
        for circleFlag in range(p-1):
            if numerator==residue[circleFlag]:
                isCircle=1
                break
if not isCircle:
    print "The result is limited."
    print quotient[0],'.',
    for k in range(1,p):
        print "%d"%quotient[k],
else:
    print "The result is unlimited."
    print quotient[0],'.',
    if circleFlag:
        for k in range(1,circleFlag+1):
            print "%d"%quotient[k],
    print "(",
    for k in range(circleFlag+1,p):
      print "%d"%quotient[k],
    print ")"
    print "There are %d positions circle!" % (p-circleFlag-1)  

        这个程序原理很简单，因为所谓循环，实际上就是我们作除法是遇到的余数开始和前面的重复！所以只要找到余数重复，就发现循环节了！        我曾经以为有一个算法可以优化这个题目，可惜，我查阅了相关资料，发现我是做不到了！
        诚然，算法依然有，不过并不简洁。运用了近世代数里面的群论和费尔马小定理！对分母进行相当复杂的判断，可以确定其循环节的位数！通过分解分母因子，可以确定不循环的部分，我想比除商，然后看小数还是要简单一些！但是实在不会简单很多，因为对分母的判断太难了！不过倒是借此复习了一点近世代数，呵呵

cdy20

优化的话可用高精度的优化原理
可以测试到小数点后10000位以上都没问题
不过代码多拉

jinry

不是很看得懂算法,得慢慢再研究一下