首页
社区
课程
招聘
[原创][第二阶段◇第二题答案]看雪论坛.腾讯公司2008软件安全竞赛
2008-10-26 11:16 3222

[原创][第二阶段◇第二题答案]看雪论坛.腾讯公司2008软件安全竞赛

2008-10-26 11:16
3222
收藏
点赞0
打赏
分享
最新回复 (4)
雪    币: 503
活跃值: (80)
能力值: (RANK:280 )
在线值:
发帖
回帖
粉丝
mstwugui 6 2008-10-26 11:57
2
0
代码写的很匆忙,没有整理清楚还请见谅

基本上的思路是先递归优化表达式,最里面的括号先计算,如果该层不含除法,则直接计算出结果并更新表达式。如果含除法,则该层优化为a/b的形式。一直到最外一层表达式。分别计算出分子分母后再做一次除法算出所需答案。

具体实现的四则运算都是先做相对应的无符号计算,然后再修正符号

除法的优化包含几个步骤

[*]替换掉不必要的除法,例如"a/b/c"替换成"a/(b*c)", "a/b + c/d + e"替换成"a*d + c*b + e*b*d"
[*]由于要精确到小数点后40位,因此在运算前先将被除数乘以41,除法运算结束后再将商除以41,并将小数点后第41位四舍五入到第40位
[*]如果被除数小于除数,则先放大被除数直到正好比除数大为止,计算完成后再将商缩小同样倍数
[*] 如果除数或被除数含小数,则将除数和被除数放大同样倍数直到除数和被除数都肯定是整数,然后计算两个大数的位差并将除数放大以补足位差。接下来循环计算,如果被除数大于除数,则被除数减去除数,如果被除数小于除数,则除数缩小1位并将位差减1,直到最后位差小于零退出乘法的实现用了快速傅立叶变换(很抱歉傅立叶变换的知识实在记不清,因此乘法运算的部分代码来是google来的)

BigCalc函数写的很简单,先是读文件长度然后分配内存,接着读第一行字符串到内存中,并尝试解析和计算结果

大数是用单字节表示每一个十进制位并且按照倒序的方式保存的,并且用一个32位整形变量nCurrentSize用于保存当前长度,还有一个nMaxSize表示当前缓冲最大长度,如果计算时需要更多字节程序会调用realloc重新分配缓冲。虽然内存使用上略有浪费但计算时还是比较方便。另外所有计算的实现全部是整数计算,不过有一个32位整形变量nDotPos用于保存小数点位置,因此如果需要的话很轻易就可以提高精度
雪    币: 1505
能力值: (RANK:210 )
在线值:
发帖
回帖
粉丝
bithaha 5 2008-11-13 12:51
3
0
带有乘除和括号的运算 程序运行出错 .

只有加减的运算时间:141

60分
雪    币: 1505
能力值: (RANK:210 )
在线值:
发帖
回帖
粉丝
bithaha 5 2008-11-13 13:14
4
0
http://bbs.pediy.com/showthread.php?t=75390
雪    币: 503
活跃值: (80)
能力值: (RANK:280 )
在线值:
发帖
回帖
粉丝
mstwugui 6 2008-11-13 15:09
5
0
解析表达式有个bug, 自己发现了可是提交时间已经过了,所以就懒得改了
游客
登录 | 注册 方可回帖
返回