开发工具:
文件大小: 932kb
下载次数: 0
上传时间: 2015-06-13
详细说明: tc C程序最好的编程工具 阶乘的推导(郭先强) 下面以精确计算 1000! 为例,阐述该算法: 记 F1(n) = n*(n-1)*...*1; F2(n) = n*(n-2)*...*(2 or 1); Pow2(r) = 2^r; 有 F1(2k+1) = F2(2k+1) * F2(2k) = Pow2(k) * F2(2k+1) * F1(k), F1(2k) = Pow2(k) * F2(2k-1) * F1(k), 及 Pow2(u) * Pow2(v) = Pow2(u+v), ∴ 1000! = F1(1000) = Pow2(500)*F2(999)*F1(500) = Pow2(750)*F2(999)*F2(499)*F1(250) = Pow2(875)*F2(999)*F2(499)*F2(249)*F1(125) = Pow2(937)*F2(999)*F2(499)*F2(249)*F2(125)*F1(62) = P ow2(968)*F2(999)*F2(499)*F2(249)*F2(125)*F2(61)*F1(31) = Pow2(983)*F2(999)*F2(499)*F2(249)*F2(125)*F2(61)*F2(31)*F1(15) = ... 如果你预存了某些小整数阶乘(比如这里的“F1(15)”),则可提前终止分解,否则直至右边最后一项为“F1(1)”为止;这样,我们将阶乘转化为2的整数次幂与一些连续奇数的积(或再乘以一个小整数的阶乘); 再定义:F2(e,f) = e*(e-2)*...*(f+2),这里仍用“F2”,就当是“函数重载”好了:), 则 F2(e) = F2(e,-1) = F2(e,f)*F2(f,-1) (e、f为奇数,0≤f≤e) ∴ F2(999) = F2(999,499)*F2(499,249)*F2(249,125)*F2(125,61)*F2(61,31)*F2(31), F2(499) = ____________F2(499,249)*F2(249,125)*F2(125,61)*F2(61,31)*F2(31), F2(249) = ________________________F2(249,125)*F2(125,61)*F2(61,31)*F2(31), F2(125) = ____________________________________F2(125,61)*F2(61,31)*F2(31), F2( 61) = _______________________________________________F2(61,31)*F2(31), F2( 31) = _________________________________________________________F2(31), ∴ F1(1000) = F1(15) * Pow2(983) * F2(999,499) \ * [F2(499,249)^2] * [F2(249,125)^3] \ * [F2(61,31)^4] * [F2(31)^5] 这样,我们又将阶乘转化为了乘方运算。 上式实际上是个形如 a * b^2 * c^3 * d^4 * e^5 的式子;我们再将指数转化为二进制,可得到如下公式: a * b^2 * c^3 * d^4 * e^5 = (a*c*e)*[(b*c)^2]*[(d*e)^4] = (((e*d)^2)*(c*b))^2*(e*c*a), 即可转化成了可充分利用高效的平方算法。 ...展开收缩
(系统自动生成,下载前可以参看下载内容)
下载文件列表
相关说明
- 本站资源为会员上传分享交流与学习,如有侵犯您的权益,请联系我们删除.
- 本站是交换下载平台,提供交流渠道,下载内容来自于网络,除下载问题外,其它问题请自行百度。
- 本站已设置防盗链,请勿用迅雷、QQ旋风等多线程下载软件下载资源,下载后用WinRAR最新版进行解压.
- 如果您发现内容无法下载,请稍后再次尝试;或者到消费记录里找到下载记录反馈给我们.
- 下载后发现下载的内容跟说明不相乎,请到消费记录里找到下载记录反馈给我们,经确认后退回积分.
- 如下载前有疑问,可以通过点击"提供者"的名字,查看对方的联系方式,联系对方咨询.