一个小算法...

jinry

算法:求1/7的第100位的小数是什么?
那天去华为面试的时候那个一面的人在和我聊很多之后突然又给这样一个算法的题目

chen284470

是循环小数   0.142857循环        8

jinry

OK, 如果是循环小数,你如何确定循环的位数,并且判断要求的位数的数字?

如果是另外一个除数,不是循环小数,又该如何去考虑这个算法?

不会游泳鱼

参照微机原理…把除法变成加减法…[016]不过太死板了,估计没戏

不会游泳鱼

不是循环小数的应该好办一点,叫他给出那个小数的定义让他精确到小数点后100位即可…

jieshao733

小弟我初试牛刀，结果大伤脑筋 期待各位高手解决

Ja5oN

原帖由 jinry 于 2007-8-7 01:34 发表
OK, 如果是循环小数,你如何确定循环的位数,并且判断要求的位数的数字?

如果是另外一个除数,不是循环小数,又该如何去考虑这个算法?

是有理除法的话就一定是循环小数
至于怎样确定循环位数就不知道了
有高手现身说教一下么

iptton

本题的话，先笔算出循环位数为8，如果2F没算错的话



确定循环位数的算法MS见过有ACM题目是要用到的，不过我也不会...

iptton

想到一个思路（其实就是判断循环小数的数学方法 ）
把每次的余数保存下来，并与之前保存的相比，如果有相同，就是到了循环

在被除数位数小时，这个方法应该可以

jinry

我当时想了两个方面,一个是放大被乘数,明显不行,而且是算法,肯定不能这样依赖他的大小了.然后第二个就是循环小数,但是发现这个循环小数的位数的确认也是件麻烦事.所以我用了这个方法
temp= 1
for(i=0;i<99;i++)
{
   temp = (temp*10)%7;
}
reslut = temp/7
这个result就是结果....
只要是个数的除数那么算法就是一定成立,如果除数是2位,3位更多位就是要判断余数和除数的比较了..

jieshao733

为什么余上100次就出结果了？？

jinry

LS没有看题目...
而且不是余一百次....
是99次....

jieshao733

师兄能不能详细点说明一下算法让师弟学习学习···

渣咋

jinry漏了少少野。。。应该系
temp= 1
for(i=0;i<99;i++)
{
   temp = (temp*10)%7;
}
reslut = (temp*10)/7

渣咋

受了jinry的启发，改写一下，应该能应付所有整型的除数吧，欢迎拍砖

temp = 被除数;
for(i = 0;i < 要求的小数位-1;i++)
{
   if((temp = temp*10) < 除数) continue;
   temp = temp%除数;
}
result = (temp*10) / 除数 ;


[ 本帖最后由 渣咋 于 2007-8-8 14:31 编辑 ]

以为晴天

理论上可以是1/7的结果乘以10的100次方，然后%10，但是如此庞大的数不合实际应用，LS的是很好的方法，每次循环剩下的余数不停地除以7，数位越来越小，然后得到结果

jinry

谢谢14F的.....
是少了一个*10.....

不过15的,在第一个循环出来之后应该就可以得到这个结果,不用再循环了吧,只是求那个小数上的数字,如果(temp*10<除数)的话应该是0...

jinry

原帖由 jieshao733 于 2007-8-8 11:40 发表
师兄能不能详细点说明一下算法让师弟学习学习···

在纸上做一下这个1/7的除法运算吧..

渣咋

原帖由 jinry 于 2007-8-8 14:09 发表
谢谢14F的.....
是少了一个*10.....

不过15的,在第一个循环出来之后应该就可以得到这个结果,不用再循环了吧,只是求那个小数上的数字,如果(temp*10<除数)的话应该是0...

对哦，改了

jinry

发现对帖子加错分了,呵呵,不过都是给这个ID加分了,只能最多加5分了.不好意思,,