魔方吧·中文魔方俱乐部

标题: 关于1000的阶乘的问题 [打印本页]

作者: lulijie 时间: 2009-8-30 20:19:32 标题: 关于1000的阶乘的问题

关于1000的阶乘：
1. 末尾有几个0？
2. 去掉末尾所有的0后最后一位是什么数字？
3. 写成质因数的幂的乘积的形式又是什么？比如 360=2^3 * 3^2 * 5^1

------------------------------
由于1000以内的素数太多，第3题计算起来比较繁琐。
第3题就改为
求100!的质因数的幂的乘积的形式。

[ 本帖最后由 lulijie 于 2009-8-31 00:10 编辑 ]

作者: Osullivan 时间: 2009-8-30 20:52:40

这个问题计算机和数学可解？

~~~~~~~~~~

作者: lulijie 时间: 2009-8-30 20:55:51

不要用计算机来解。

作者: lulijie 时间: 2009-8-30 22:41:59

算第三题，要用到1000以内的所有素数，提供如下：
   2 3 5 7 11 13 17 19 23 29 31 37 41 43 47  53 59 61 67 71 73 79 83 89 97
101 103 107 109 113 127 131 137 139 149 151 157 163 167 173 179 181 191 193 197 199
211 223 227 229 233 239 241 251 257 263 269 271 277 281  283 293
307 311 313 317 331 337 347 349 353 359 367 373 379 383 389 397
   401 409 419 421 431 433 439 443 449 457 461 463 467 479 487 491 499
503 509 521 523 541 547 557 563 569 571 577 587 593 599
601 607 613 617 619 631 641 643 647 653 659 661 673 677 683 691
   701 709 719 727 733 739 743 751 757 761 769 773 787 797
   809 811 821 823 827 829 839 853 857 859 863 877 881 883 887
   907 911 919 929 937 941 947 953 967 971 977  983 991 997

作者: stonesmith322 时间: 2009-8-30 22:49:52

第一个最后有多少零很简单啊只要考虑5就好了有一个5就有一个零有两个就有两个零比如25就是在末尾添上两个零

作者: 骰迷 时间: 2009-8-30 23:02:57

理解題目有點困難，原來是１０００！
第一題是不是249?
第二題是不是6?

作者: lulijie 时间: 2009-8-30 23:09:50

第一题=[1000/5]+[1000/25]+[1000/125]+[1000/625]=200+40+8+1=249
所以楼上正确。
不过第2题不对。

作者: oyyq99999 时间: 2009-8-30 23:21:30

貌似拿計算機來解也沒什麽問題，就計算1000次嘛，正好我有個高精度計算器，待我改一下來算他一算

作者: oyyq99999 时间: 2009-8-31 00:14:32

402387260077093773543702433923003985719374864210714632543799910429938512398629020592044208486969404800479988610197196058631666872994808558901323829669944590997424504087073759918823627727188732519779505950995276120874975462497043601418278094646496291056393887437886487337119181045825783647849977012476632889835955735432513185323958463075557409114262417474349347553428646576611667797396668820291207379143853719588249808126867838374559731746136085379534524221586593201928090878297308431392844403281231558611036976801357304216168747609675871348312025478589320767169132448426236131412508780208000261683151027341827977704784635868170164365024153691398281264810213092761244896359928705114964975419909342221566832572080821333186116811553615836546984046708975602900950537616475847728421889679646244945160765353408198901385442487984959953319101723355556602139450399736280750137837615307127761926849034352625200015888535147331611702103968175921510907788019393178114194545257223865541461062892187960223838971476088506276862967146674697562911234082439208160153780889893964518263243671616762179168909779911903754031274622289988005195444414282012187361745992642956581746628302955570299024324153181617210465832036786906117260158783520751516284225540265170483304226143974286933061690897968482590125458327168226458066526769958652682272807075781391858178889652208164348344825993266043367660176999612831860788386150279465955131156552036093988180612138558600301435694527224206344631797460594682573103790084024432438465657245014402821885252470935190620929023136493273497565513958720559654228749774011413346962715422845862377387538230483865688976461927383814900140767310446640259899490222221765904339901886018566526485061799702356193897017860040811889729918311021171229845901641921068884387121855646124960798722908519296819372388642614839657382291123125024186649353143970137428531926649875337218940694281434118520158014123344828015051399694290153483077644569099073152433278288269864602789864321139083506217095002597389863554277196742822248757586765752344220207573630569498825087968928162753848863396909959826280956121450994871701244516461260379029309120889086942028510640182154399457156805941872748998094254742173582401063677404595741785160829230135358081840096996372524230560855903700624271243416909004153690105933983835777939410970027753472000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000

作者: oyyq99999 时间: 2009-8-31 00:16:05

第一個問題，最後有249個零
第二個問題，最後一位是2
至於第三個問題，解決思路應該是通過對2到1000這999個數分別進行質因數分解，然後再統計，我可以試一下。。。

第三個問題最後結果在12樓

[ 本帖最后由 oyyq99999 于 2009-8-31 00:57 编辑 ]

作者: lulijie 时间: 2009-8-31 00:19:14

不要强算，有没有办法可以算出最后一位非0数字是2？

作者: oyyq99999 时间: 2009-8-31 00:56:39

1000!=2^994*3^498*5^249*7^164*11^98*13^81*17^61*19^54*23^44*29^35*31^33*37^27*41^24*43^23*47^21*53^18*59^16*61^16*67^14*71^14*73^13*79^12*83^12*89^11*97^10*101^9*103^9*107^9*109^9*113^8*127^7*131^7*137^7*139^7*149^6*151^6*157^6*163^6*167^5*173^5*179^5*181^5*191^5*193^5*197^5*199^5*211^4*223^4*227^4*229^4*233^4*239^4*241^4*251^3*257^3*263^3*269^3*271^3*277^3*281^3*283^3*293^3*307^3*311^3*313^3*317^3*331^3*337^2*347^2*349^2*353^2*359^2*367^2*373^2*379^2*383^2*389^2*397^2*401^2*409^2*419^2*421^2*431^2*433^2*439^2*443^2*449^2*457^2*461^2*463^2*467^2*479^2*487^2*491^2*499^2*503^1*509^1*521^1*523^1*541^1*547^1*557^1*563^1*569^1*571^1*577^1*587^1*593^1*599^1*601^1*607^1*613^1*617^1*619^1*631^1*641^1*643^1*647^1*653^1*659^1*661^1*673^1*677^1*683^1*691^1*701^1*709^1*719^1*727^1*733^1*739^1*743^1*751^1*757^1*761^1*769^1*773^1*787^1*797^1*809^1*811^1*821^1*823^1*827^1*829^1*839^1*853^1*857^1*859^1*863^1*877^1*881^1*883^1*887^1*907^1*911^1*919^1*929^1*937^1*941^1*947^1*953^1*967^1*971^1*977^1*983^1*991^1*997^1

作者: oyyq99999 时间: 2009-8-31 01:13:06

關於最後一位的計算，應該可以用每一個數的最後一位非零數字(把末尾的零全去掉)相乘得到，在計算過程中只截取結果的最後一位非零數字進行下一次計算

作者: zxl0714 时间: 2009-8-31 19:24:43

第二题做过。。。先不考虑含有5因数的数，这样n!只需考虑个位即可，所以n!可以分为[ n / 10 ]个10!和( n mod 10 )!，而不含5因数的10!的尾数都是6，所以只需考虑( n mod 10 )!的尾数。
列一个表t( n ) = { 1, 1, 2, 6, 4, 4, 4, 8, 4, 6 } ( 0 <= n < 10 )
要提出因数5，一次可提出[ n / 5 ]个，这样要找[ n / 5 ]个2与之配对，就是将计算出的不含5的尾数除以2 ^ [ n / 5 ]，注意由于除了0!和1!外所有阶乘的最后一位都为偶数，所以2 / 2 = 6，6 / 2 = 8，注意到除以２以后的变化是４个以循环，所以只需除以[ n / 5 ] mod 4个２即可。由于被提出因数5的那些数还没有计算完，所以要继续计算它的尾数，即[ n / 5 ]!的尾数，然后和原来的相乘就是n!的尾数。这样有一个递推关系
f( n ) = f( [ n / 5 ] ) * t( n mod 10 ) * 6 / 2 ^ ( [ n / 5 ] mod 4 )
不知道我讲清楚没有。

f( n ) = { 1, 1, 2, 6, 4, 2, 2, 4, 2, 8 } ( 0 <= n < 10 )

[ 本帖最后由 zxl0714 于 2009-8-31 21:36 编辑 ]

作者: lulijie 时间: 2009-8-31 19:34:10

14楼：可以用你的方法检验一下n取较小值时，答案正确不正确。

作者: lulijie 时间: 2009-8-31 19:42:46

比如n=11 11!=39916800
f(11)=f(2)*f(1)*6/2^2=2*1*6/4=12/4=?
=8? =3?

作者: zxl0714 时间: 2009-8-31 19:54:19

12也是取尾数的，就是2，2 / 2 = 6，6 / 2 = 8

作者: lulijie 时间: 2009-8-31 19:58:56

是这样么：
2/2=6
6/2=8
8/2=4
4/2=2

作者: zxl0714 时间: 2009-8-31 20:01:19

对，就是这样.....

作者: lulijie 时间: 2009-8-31 20:09:18

f(49)=f(9)*f(9)*6/2^1=6*6*6/2=6/2=8
而49!=608281864034267560872252163321295376887552831379210240000000000

作者: zxl0714 时间: 2009-8-31 21:34:34

郁闷。。。我写错了，现在改好了。。

作者: lulijie 时间: 2009-8-31 21:57:11

很好！
不错！
不过可以把公式写的规范一些，像2/2=6，6/2=8之类的毕竟不太正规。

作者: ukyo502 时间: 2009-9-10 09:21:56

用强大的计算机CPU把结果算出来就是了~~推荐用python语言，嘿嘿

作者: zxl0714 时间: 2009-9-11 12:39:11

楼上太搞笑了。。。。这题给的数据是小了点，如果再大一点，比如１００００００，朴素算法就不好用了，复杂度要O( n^2 )（普通高精度乘法），再往上就要用快速傅里叶变换了，但是复杂度也只能到O( nlogn )。这题只需计算最后有多少０，不用计算具体数，所以我们可以用人脑列出一个递推公式，使得算法复杂度降到O( n )，所以不能依赖CPU。
还有为什么要用python，python在效率上比起c要差的远，虽然比较好编。

作者: 网罟双星 时间: 2009-9-17 09:08:08

汗...出现个用穷举法的...不过这是我的最爱！哈哈

欢迎光临魔方吧·中文魔方俱乐部 (http://bbs.mf8-china.com/)