2012年3月19日星期一

Re:Re: Re: [PerlChina] 做google code jam 练习出现的问题

先谢谢 :)
然后回头仔细研究研究 ~~ 呵呵


在 2012-03-19 14:54:51，"亮康" <kangliang1982@gmail.com> 写道：

直接用多项式公式展开，
(a+b)^n=C(0,n)*a^n + C(1,n)*a^(n-1)*b + C(2,n)*a^(n-2)*b^2 + ....+ C(n-1,n)*a*b^(n-1) + C(n,n)*b^n

其中a=3,b= √5,
计算每一项的时候，
如果b的幂次为偶数则该项可计算出整数，则该项只需取模1000只保留3位，再和其他项b的偶数像相加，再取模1000，可得整数m
如果b的幂次为奇数，则计算出所有√5的偶数次幂，只保留一个√5，应该可得N*√5，最后合并所有奇数项可得n*√5

最后可得m+n*√5，现在只需计算n*√5并取模1000，加上m即可。   

这种做法只有可能是n最后过大，那么可以在每一步计算N*√5的时候直接计算出浮点数，然后只从小数点前3位开始取数，大数省略，然后直接合并到结果上即可。
 
另外，对于每个项的计算任然可做优化，无需真正计算出结果。

大概应该是这样子的。 
在 2012年3月18日 下午6:08，kevin_li <xiaohuidexinge@163.com>写道：
前面的几个人都是用c++做的，
看不明白。。。 数学没学好呀。。。


在 2012-03-18 13:17:04，snyh <snyh@snyh.org> 写道：

用haskell整型默认就是任意精度的   2**1000000 立马出结果
至于5  ** 1449613541这级别的  跑半天不动，最后直接swap(3G内存)，硬盘不行，不敢继续运行直接kill了
很好奇这么大的数能有快速的计算方式吗？
On Sunday, March 18, 2012, cnhack TNT wrote:
我了个去，这个计算太夸张了，默认情况下 Pari 栈直接溢出了。。。
取巧的做法是，直接拿 perl 去抓 wolframalpha 的结果，哈哈：



2012/3/17 kevin_li <xiaohuidexinge@163.com>
好的 非常感谢 ：）
我试试先，
不过可能还是解决不了这个题目，  我只是拿2 ** 1000000 举例子， 题目里面是 11-12位数的次幂，5.236067 ** 1449613541 这样的。


在 2012-03-17 04:45:45，"cnhack TNT" <cnhacktnt@gmail.com> 写道：

安装 Math::BigInt::Pari 或者 Math::BigInt::GMP 模块，然后指定 bignum 加载两者之一. 如：

    use bignum lib => 'Pari';

我在命令行上试验：

    perl -Mbignum=l,Pari -le 'print 2**1000000'

不到十秒出结果，当然结果对不对，你还得验证一下哈




2012/3/16 kevin_li <xiaohuidexinge@163.com>
这几天发现google 还有个code jam这么个东西， 里面有历年的比赛题目， 就没事儿做做玩儿玩儿， 我都是用perl 做。
做了几个不是很难，直到碰到了这个
里面的large 涉及到 大数 计算。
我用的use bignum; 计算大数。
以前从来没碰到过用 大数 ，刚才试了一下，我的机器 算个 2**1000000, 就要4分钟。。。。

问题是：这个题目用perl 怎么完成？是有更好的计算大数的方式? 还是这个题目就不能用 "算次幂"的方式来解决？


--
您收到此邮件是因为您订阅了 Google 网上论坛的"PerlChina Mongers 讨论组"论坛。
要向此网上论坛发帖，请发送电子邮件至 perlchina@googlegroups.com。
要取消订阅此网上论坛，请发送电子邮件至 perlchina+unsubscribe@googlegroups.com。
若有更多问题，请通过 http://groups.google.com/group/perlchina?hl=zh-CN 访问此网上论坛。

--
您收到此邮件是因为您订阅了 Google 网上论坛的"PerlChina Mongers 讨论组"论坛。
要向此网上论坛发帖，请发送电子邮件至 perlchina@googlegroups.com。
要取消订阅此网上论坛，请发送电子邮件至 perlchina+unsubscribe@googlegroups.com。
若有更多问题，请通过 http://groups.google.com/group/perlchina?hl=zh-CN 访问此网上论坛。


--
您收到此邮件是因为您订阅了 Google 网上论坛的"PerlChina Mongers 讨论组"论坛。
要向此网上论坛发帖，请发送电子邮件至 perlchina@googlegroups.com。
要取消订阅此网上论坛，请发送电子邮件至 perlchina+unsubscribe@googlegroups.com。
若有更多问题，请通过 http://groups.google.com/group/perlchina?hl=zh-CN 访问此网上论坛。

--
您收到此邮件是因为您订阅了 Google 网上论坛的"PerlChina Mongers 讨论组"论坛。
要向此网上论坛发帖，请发送电子邮件至 perlchina@googlegroups.com。
要取消订阅此网上论坛，请发送电子邮件至 perlchina+unsubscribe@googlegroups.com。
若有更多问题，请通过 http://groups.google.com/group/perlchina?hl=zh-CN 访问此网上论坛。

--
您收到此邮件是因为您订阅了 Google 网上论坛的"PerlChina Mongers 讨论组"论坛。
要向此网上论坛发帖，请发送电子邮件至 perlchina@googlegroups.com。
要取消订阅此网上论坛，请发送电子邮件至 perlchina+unsubscribe@googlegroups.com。
若有更多问题，请通过 http://groups.google.com/group/perlchina?hl=zh-CN 访问此网上论坛。


--
您收到此邮件是因为您订阅了 Google 网上论坛的"PerlChina Mongers 讨论组"论坛。
要向此网上论坛发帖，请发送电子邮件至 perlchina@googlegroups.com。
要取消订阅此网上论坛，请发送电子邮件至 perlchina+unsubscribe@googlegroups.com。
若有更多问题，请通过 http://groups.google.com/group/perlchina?hl=zh-CN 访问此网上论坛。

--
您收到此邮件是因为您订阅了 Google 网上论坛的"PerlChina Mongers 讨论组"论坛。
要向此网上论坛发帖，请发送电子邮件至 perlchina@googlegroups.com。
要取消订阅此网上论坛，请发送电子邮件至 perlchina+unsubscribe@googlegroups.com。
若有更多问题，请通过 http://groups.google.com/group/perlchina?hl=zh-CN 访问此网上论坛。


--
您收到此邮件是因为您订阅了 Google 网上论坛的"PerlChina Mongers 讨论组"论坛。
要向此网上论坛发帖，请发送电子邮件至 perlchina@googlegroups.com。
要取消订阅此网上论坛，请发送电子邮件至 perlchina+unsubscribe@googlegroups.com。
若有更多问题，请通过 http://groups.google.com/group/perlchina?hl=zh-CN 访问此网上论坛。
发帖者 时间：

没有评论:

发表评论

订阅： 博文评论 (Atom)