玩一下google编程挑战赛试题

来源: BlogBus 原始链接: http://eraera.blogbus.com:80/logs/2005/12/1742032.html 存档链接: https://web.archive.org/web/20060114034344id_/http://eraera.blogbus.com:80/logs/2005/12/1742032.html

美人她爹 每天总有些想法,不写下来就忘了. - 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： 地址：