玩一下google编程挑战赛试题
eraera · 2005-12-24
美人她爹
每天总有些想法,不写下来就忘了. - eraera
<< 白色火星 引
|
首 页
|
Mocking Keso and other web 2.0 pioneers >>
2005-12-24
玩一下google编程挑战赛试题
TAG:
Google
Code
JAM
题在这里:
http://blog.donews.com/wysuperfly/archive/2005/12/22/667661.aspx
简单说就是:一个表示为I.F(L)*的有理数,如何转换成分数.
三部分:
1.处理输入字符串,找出循环小数的循环部分和前缀. 1.234(56), 1.23是前缀,(56)是循环部分. I.F(L)*,I.F是前缀,L是循环部分.利用*,+就可以做了.
2.转换成分数.对前缀,分子用前缀串,分母用10的N次方,N是前缀的小数部分.对循环部分,分子是循环串,分母是10的M次方-1,M是循环串长度.用正则表式法会更清楚,不过太长,不写了.其实就是:
IF / (10^(length_of(F))) + L / ((10 ^ (length_of(L)) - 1) * (10^(length_of(F))))
3.用中国最大公约数算法约分,加和.
算法有了,翻译成程序就好了.
Tricks:
有理数是字符表示,处理I, F, L的时候用三个字符指针分别指向I, F, L.而'.'和'(', ')'都被转换成0
,作为三个新字符串的结尾,就避免了重新分配内存.如果要保证输入数据不变,改回来就是了.
约分的时候有一些小trick可以防止溢出,比如说如果有F,那么分母肯定是2和5的倍数,如果有L,那么分母肯定是9的倍数.先把这些从分子里除去.
eraera
@ 00:04:09 |
引用 0
|
编辑
评论
发表评论
姓名:
E-mail:
地址:
原始快照:web.archive.org