注册 登录  
 加关注
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

Hao的博客

I'm on my way……

 
 
 

日志

 
 
 
 

数据类型的较量  

2009-04-05 15:06:04|  分类: Algorithm discov |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |

      这两天都在埋头做POJ1306这道题,本来题目很简单却不知道为什么能弄出那么多的问题......

      不知道出题的人有意还是无意,把题目中的数据设置的不大不小,用int型必溢出,使用大数运算的话又未免小题大作。因为考虑到最后的数据不会超过表示范围,而且用C(n,m)=C(n-1,m-1)*(n/m)的方法运算时n/m不一定整除,最后还是决定选用double型,但是却WA掉了。

      和队友分析了一下,得出结论:n/m运算过程中会有精度损失,很有可能中间的某些数据因此错了。那就换种方法,在做n的阶乘运算的每一步都去检查是否能够被i(2~m)整除,如果能则将i加1再判断,否则回去接着做阶乘的运算。关键代码如下:

  result=1;    i=2;
  tempN=n;   tempM=m;
  for(;m>0;m-=1,n-=1){
       result=result*n;
       while(i<=tempM){
           if((int)result%(int)i)break;   //浮点数不能进行取余运算
               result/=i;
               i+=1;
        }
  }

      可是依然WA了,在调试的过程中发现当i增到某一值时if的条件恒为真。可能还是因为浮点数的近似表示的原因吧。那就改个数据类型,改为_int64应该够用了吧,通过一番修改还是WA,在VS上试了下C(100,50)的结果,明显溢出,看样子还是不行。

      虽然最后的结果对于double和_int64都足够了,可是中间的运算未知数太多,还是得使用double,老实的先算出分子,然后分母,再除一下。呵呵,好冷的题目~

后记:

1.虽然double和_int64都是8个字节,但是double可以表示的数据范围要大得多。

2.浮点数不能进行取余运算。

  评论这张
 
阅读(150)| 评论(2)
推荐 转载

历史上的今天

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2017