討論區快速選單
知識庫快速選單
網路投保旅行平安險 討論區最近新進100則主題 傑米的攝影旅遊筆記
[ 回上頁 ] [ 討論區發言規則 ]
請教一下999999999階層
更改我的閱讀文章字型大小
作者 : promiseway(promiseway)
[ 貼文 124 | 人氣 3991 | 評價 30 | 評價/貼文 0.24 | 送出評價 8 次 ] 
[ 給個讚 ]  [ 給個讚 ]  [ 回應本文 ]  [ 發表新文 ]  [ 回上頁 ] [ 回討論區列表 ] [ 回知識入口 ]
2003/10/16 上午 10:49:01
請問一下9億9千9百9十9萬9千9百9十9階層(999999999!)
如何在30秒內求出從尾端開始往前找ㄉ第一個非零數
字是什麼?
例:
4!=24 第一個非零數字是1
5!=120 第一個非零數字是2
作者 : neville(福寶)
[ 貼文 111 | 人氣 1806 | 評價 310 | 評價/貼文 2.79 | 送出評價 1 次 ] 
[ 給個讚 ]  [ 給個讚 ]  [ 回應本文 ]  [ 發表新文 ]  [ 回上頁 ] [ 回討論區列表 ] [ 回知識入口 ]
2003/10/16 下午 12:10:02

>請問一下9億9千9百9十9萬9千9百9十9階層(999999999!)
>如何在30秒內求出從尾端開始往前找ㄉ第一個非零數
>字是什麼?
>例:
>4!=24 第一個非零數字是1
>5!=120 第一個非零數字是2

看不懂,為什麼 4! = 24 第一個非零數字是 1?
不是應該是 4! = 24
     ^ ------這個值嗎?
作者 : promiseway(promiseway)
[ 貼文 124 | 人氣 3991 | 評價 30 | 評價/貼文 0.24 | 送出評價 8 次 ] 
[ 給個讚 ]  [ 給個讚 ]  [ 回應本文 ]  [ 發表新文 ]  [ 回上頁 ] [ 回討論區列表 ] [ 回知識入口 ]
2003/10/16 下午 08:20:39
阿..對不起
我打錯了
我順便打清楚一點^^
假設你必需寫一個程式

若給你4,你就要輸出4,因為
4!=4*3*2*1也就是24,從後往面推第一個非零數是4

若給你8,你就要輸出2,因為
8!=8*7*6*5*4*3*2*1也就是40320,從後往面推第一個非零數是2

若給你10,你就要輸出8,因為
10!=10*9*8*7*6*5*4*3*2*1也就是3628800,從後往面推第一個非零數是8

若給你999999999,你ㄉ程式必需在30秒內計算
出,從尾端往前算ㄉ第一個非零數字是啥麼?

作者 : xavier(Xavier)
[ 貼文 38 | 人氣 757 | 評價 200 | 評價/貼文 5.26 | 送出評價 2 次 ] 
[ 給個讚 ]  [ 給個讚 ]  [ 回應本文 ]  [ 發表新文 ]  [ 回上頁 ] [ 回討論區列表 ] [ 回知識入口 ]
2003/10/17 下午 12:40:07
以下是我自己的測試結果不保證正確
有錯請指正

1. 記算每個數字(僅計算尾數且0,1不算)出現的次數
  12345 -> 每個數字出現(12345 / 10)次,0 ~ (12345 % 10)多一次

2. 計算(2的出現次數 % 4) = a2
  (3的出現次數 % 4) = a3
  (4的出現次數 % 2) = a4
  (5的出現次數 % 1) = a5
  (6的出現次數 % 1) = a6
  (7的出現次數 % 4) = a7
  (8的出現次數 % 4) = a8
  (9的出現次數 % 2) = a9
  這是代表x^n尾數每a次一循環

3. 因為5 * 偶數(尾數0)與 3 * 7 = 21(尾數1)
  所以再減去這些東西成為新的a2 ~ a9

4. 計算(2^a2) * (3^a3) * (4^a4) * (5^a5) * (6^a6) * (7^a7) * (8^a8) * (9^a9)

5. 取得剛剛的尾數即為結果
作者 : promiseway(promiseway)
[ 貼文 124 | 人氣 3991 | 評價 30 | 評價/貼文 0.24 | 送出評價 8 次 ] 
[ 給個讚 ]  [ 給個讚 ]  [ 回應本文 ]  [ 發表新文 ]  [ 回上頁 ] [ 回討論區列表 ] [ 回知識入口 ]
2003/10/17 下午 01:58:15
謝謝你^^,寫得真好~給你ㄍ好評
不過這ㄍ問題我曾在許多討論版
問過都還沒有人回答ㄉ出來
不介意我把這ㄍ解法轉貼出去吧^^
作者 : xavier(Xavier)
[ 貼文 38 | 人氣 757 | 評價 200 | 評價/貼文 5.26 | 送出評價 2 次 ] 
[ 給個讚 ]  [ 給個讚 ]  [ 回應本文 ]  [ 發表新文 ]  [ 回上頁 ] [ 回討論區列表 ] [ 回知識入口 ]
2003/10/17 下午 02:50:10
轉貼出去是沒問題
不過你真的確定他對?
我可沒真的驗證過.....
作者 : xavier(Xavier)
[ 貼文 38 | 人氣 757 | 評價 200 | 評價/貼文 5.26 | 送出評價 2 次 ] 
[ 給個讚 ]  [ 給個讚 ]  [ 回應本文 ]  [ 發表新文 ]  [ 回上頁 ] [ 回討論區列表 ] [ 回知識入口 ]
2003/10/17 下午 03:20:09
剛剛看了一下
第三步要小小的修改一下
當(x的出現次數 % a) = 0 時請把0當作a來看


還有即使我剛剛的方法正確但是還是有一個問題
(2^4) * (3^4) * (4^2) * (5^1) * (6^1) * (7^4) * (8^4) * (9^2)
太大了,超出long可表示的範圍
所以可以在計算前稍做修改
因為3^4 = 81, 7^4 = 2401, 9^2 = 81
所以當a3 = 4時,就把a3變成0;a7與a9也一樣處理
2, 4, 8也可以變成2的次方數處理
這樣就不會有溢位的問題了


當然還有另一個方法
把(2^a2) ~ (9^a9)的尾數取出再從頭來算一次也行啦
作者 : neville(福寶)
[ 貼文 111 | 人氣 1806 | 評價 310 | 評價/貼文 2.79 | 送出評價 1 次 ] 
[ 給個讚 ]  [ 給個讚 ]  [ 回應本文 ]  [ 發表新文 ]  [ 回上頁 ] [ 回討論區列表 ] [ 回知識入口 ]
2003/10/17 下午 05:41:03
>1. 記算每個數字(僅計算尾數且0,1不算)出現的次數
>  12345 -> 每個數字出現(12345 / 10)次,0 ~ (12345 % 10)多一次
    請問這是什麼意思?

>3. 因為5 * 偶數(尾數0)與 3 * 7 = 21(尾數1)
    不是應該還有 9*9=81?

剛才寫了一個直覺式的程式來試試看,用的是尾數相乘,結果 99999999! 要24秒...
那 999999999 至少要240秒以上...果然不行...><
作者 : xavier(Xavier)
[ 貼文 38 | 人氣 757 | 評價 200 | 評價/貼文 5.26 | 送出評價 2 次 ] 
[ 給個讚 ]  [ 給個讚 ]  [ 回應本文 ]  [ 發表新文 ]  [ 回上頁 ] [ 回討論區列表 ] [ 回知識入口 ]
2003/10/17 下午 09:55:07

>>1. 記算每個數字(僅計算尾數且0,1不算)出現的次數
>>  12345 -> 每個數字出現(12345 / 10)次,0 ~ (12345 % 10)多一次
> 請問這是什麼意思?
    這個是我手誤少打了一個驚嘆號!
    這是說把12345!化成1 * 2 * 3 * ... * 12344 * 12345
    如果只計算尾數的話那麼每個數字最少會出現(12345 / 10)次
    然後0 ~ ((12345 % 10) = 5)會多出現一次
作者 : promiseway(promiseway)
[ 貼文 124 | 人氣 3991 | 評價 30 | 評價/貼文 0.24 | 送出評價 8 次 ] 
[ 給個讚 ]  [ 給個讚 ]  [ 回應本文 ]  [ 發表新文 ]  [ 回上頁 ] [ 回討論區列表 ] [ 回知識入口 ]
2003/10/18 上午 12:19:41
嗯..我也照著你ㄉ說明將程式完成了
而且我加了一些自已ㄉ想法
不過執行時間...還是過長了^^"
有沒有辦法再簡化呢?
作者 : xavier(Xavier)
[ 貼文 38 | 人氣 757 | 評價 200 | 評價/貼文 5.26 | 送出評價 2 次 ] 
[ 給個讚 ]  [ 給個讚 ]  [ 回應本文 ]  [ 發表新文 ]  [ 回上頁 ] [ 回討論區列表 ] [ 回知識入口 ]
2003/10/18 上午 07:51:45
抱歉我在家沒法寫程式
寫了也不知道怎麼讓他動.......

不過這是直接計算的結果
並不需要去跑一個超級大的迴圈
理論上應該是不會超過時限才對
作者 : promiseway(promiseway)
[ 貼文 124 | 人氣 3991 | 評價 30 | 評價/貼文 0.24 | 送出評價 8 次 ] 
[ 給個讚 ]  [ 給個讚 ]  [ 回應本文 ]  [ 發表新文 ]  [ 回上頁 ] [ 回討論區列表 ] [ 回知識入口 ]
2003/10/18 下午 06:17:44
喔!
因為我計算數字ㄉ出現次數ㄉ時後
有用到迴圈,看來是我誤解你ㄉ意思了^^"!
作者 : gmmark12(MM)
[ 貼文 17 | 人氣 72 | 評價 100 | 評價/貼文 5.88 | 送出評價 0 次 ] 
[ 給個讚 ]  [ 給個讚 ]  [ 回應本文 ]  [ 發表新文 ]  [ 回上頁 ] [ 回討論區列表 ] [ 回知識入口 ]
2003/10/19 下午 05:37:46
我寫了寫,好像找出了規律:
10!的末尾取(9!)^1.....有一個9!在裡面
100!的末尾取(9!)^(10+1)......有11個9!在裡面
1000!ㄉ末尾取(9!)^(100+10+1).....有111個9!在裡面
.........


所以輸入1985就計算:(^(111+9*11+8*1)+5!+8!+9!+1!)%10
假設輸入800,則看成8個100,所以就(9!)^(10+1)*8
另外要計算100*200*300*.....800,所以加上8!
以上都可以邊乘邊取末尾,而且(9!)=362880末尾是8
直接換成8^n算比較快,尤其又會以8、4、2、6循環。
所以我程式寫完999999999好像跑不到2秒,只是不知這想法有沒有錯。
作者 : gmmark12(MM)
[ 貼文 17 | 人氣 72 | 評價 100 | 評價/貼文 5.88 | 送出評價 0 次 ] 
[ 給個讚 ]  [ 給個讚 ]  [ 回應本文 ]  [ 發表新文 ]  [ 回上頁 ] [ 回討論區列表 ] [ 回知識入口 ]
2003/10/19 下午 05:49:48
我的方法是錯的...僅供參考....因為好像有進位的問題。
以上的規律在如12*15=180就被破壞掉了...
作者 : gmmark12(MM)
[ 貼文 17 | 人氣 72 | 評價 100 | 評價/貼文 5.88 | 送出評價 0 次 ] 
[ 給個讚 ]  [ 給個讚 ]  [ 回應本文 ]  [ 發表新文 ]  [ 回上頁 ] [ 回討論區列表 ] [ 回知識入口 ]
2003/10/19 下午 06:44:58
寫個我寫這程式失敗的心得:只用尾數相乘來計算的話結果會錯。
因為如15*16=240(取4)和5*6=30(取3)的結果是不一樣的....
作者 : neville(福寶)
[ 貼文 111 | 人氣 1806 | 評價 310 | 評價/貼文 2.79 | 送出評價 1 次 ] 
[ 給個讚 ]  [ 給個讚 ]  [ 回應本文 ]  [ 發表新文 ]  [ 回上頁 ] [ 回討論區列表 ] [ 回知識入口 ]
2003/10/19 下午 10:20:47
改用 Xavier 大大的方式,果然快速正確的算出解答.
用50組亂數測試的結果,興尾數相乘的方式答案相符

請問 Xavier ,2-9 數字的次方關係式,是如何想到的呢?
的確是一種相當快速有效的方法

附帶一提,單就這題目的話,有個特性 9!,99!,999!.......999999999!
的非零尾數都相同,似乎還有更單純的方式?

作者 : sunyear(coco) VC++卓越專家C++頂尖高手貼文超過2000則
[ 貼文 2421 | 人氣 1485 | 評價 6060 | 評價/貼文 2.5 | 送出評價 5 次 ] 
[ 給個讚 ]  [ 給個讚 ]  [ 回應本文 ]  [ 發表新文 ]  [ 回上頁 ] [ 回討論區列表 ] [ 回知識入口 ]
2003/10/20 下午 06:12:27
本來是不去想這個題目的,原因是離開學校太久了,數學對我來說是個苦刑...
但看到大家討論熱烈,好奇也來參一腳 ^^
30 秒內?那要看是那種機器,和作業平台,甚至編譯器都會影響時間。
我想應是在相同的環境下跑不同的程式來比較才公平吧!

re: 福寶
>改用 Xavier 大大的方式,果然快速正確的算出解答.
>用50組亂數測試的結果,興尾數相乘的方式答案相符
你確定嗎? Xavier 老實說我有點看不太懂^^,但去
計算乘數個位數,應該是不行的(因為尾數會移位)。
你的測試程式可以貼上來看看嗎?

>附帶一提,單就這題目的話,有個特性 9!,99!,999!.......999999999!
>的非零尾數都相同,似乎還有更單純的方式?
真的嗎?那表示所求的尾數是會循環的...
但還是懷疑你的驗證答案 ^^

我想了一個方法,和Xavier一樣不保證方法是對的 ^^
在我的nb(P3-550)上跑,要2.5分鐘,好爛 ^^
希望有人能用更高速的PC來提昇我的成績(這算不算作幣?)
無論如何,我把方法和程式貼在下面,也載在E-Home論壇,以便在本議題被淹沒後,
大家還可在E-Home找到它來討論。
    
由於當運算的中途出現10的倍數值時其非零的尾數將不是在個位數的
位置,所以直接計算個位數相乘的結果是不行的。
想法是先把把乘數中10的因子先移除,再將2,5可能導至乘積為10倍數
的因子先抽離(最後再加入運算),這樣就可以只計算個位數來求尾數了。
舉個例子:求10!第一個非零的尾數
原乘數 10因子    2因子 5因子 餘乘數
10  1       0   0   1
9   0       0   0   9
8   0       3   0   1
7   0       0   0   7
6   0       1   0   3
5   0       0   1   1
4   0       2   0   1
3   0       0   0   3
2   0       1   0   1
-----------------------------
 (10因子直接刪除)七個2 一個5 637(餘乘數相乘)
一個5因子和2因子配對生成10後刪除,所以只剩六個2:
1. 2的6次方為 64 -->只取尾數 4
2. 餘乘數相乘得637-->只取尾數 7
3. 由1.和2.的尾數相乘 4X7 得28-->得尾數 8
尾數8既是10!第一個非零的尾數

#include <iostream>
using namespace std;

void main()
{
unsigned long Result,tmp;
unsigned long num,max,Cnt2,Cnt5;
loop:
cout<<endl<<"Enter a number 1~999999999:";
cin>>max;
for (Result=num=1, Cnt2=Cnt5=0; (tmp=num)<=max; ++num){
while ((tmp%10)==0) tmp/=10;//10的因子直接移除
while ((tmp&1)==0)tmp>>=1,++Cnt2;//抽出2的因子
while ((tmp%5)==0)tmp/=5,++Cnt5;//抽出5的因子
Result=Result*(tmp%10)%10;//2,5,10的因子已移出,尾數不會有零,所已只取尾數
}
if (Cnt5>Cnt2)
cout<<"Rear nonzero digit="<<5<<endl;//因為Result必為奇數,所以Result*5結果尾數必為5
else if(Cnt2>Cnt5){
for(Cnt2=(Cnt2-Cnt5)%4,tmp=6; Cnt2--tmp=tmp*2%10;//求2的(Cnt2-Cnt5)次方的尾數(2的n次方尾數是2,4,8,6的循環)
cout<<"Rear nonzero digit="<<Result*tmp%10<<endl;
}
else//Cnt2=Cnt5
cout<<"Rear nonzero digit="<<Result<<endl;//Result就是最後的尾數
goto loop;
}
作者 : sunyear(coco) VC++卓越專家C++頂尖高手貼文超過2000則
[ 貼文 2421 | 人氣 1485 | 評價 6060 | 評價/貼文 2.5 | 送出評價 5 次 ] 
[ 給個讚 ]  [ 給個讚 ]  [ 回應本文 ]  [ 發表新文 ]  [ 回上頁 ] [ 回討論區列表 ] [ 回知識入口 ]
2003/10/20 下午 06:23:35
本議題轉載在此
http://ehome.hifly.to/showthread.php?postid=3682#post3682
原文已作整理, promiseway若有意見,請提出,我會儘速處理。
作者 : milx(Milx) Java Script優秀好手貼文超過200則
[ 貼文 463 | 人氣 7517 | 評價 1150 | 評價/貼文 2.48 | 送出評價 14 次 ] 
[ 給個讚 ]  [ 給個讚 ]  [ 回應本文 ]  [ 發表新文 ]  [ 回上頁 ] [ 回討論區列表 ] [ 回知識入口 ]
2003/10/20 下午 07:03:57

>4. 計算(2^a2) * (3^a3) * (4^a4) * (5^a5) * (6^a6) * (7^a7) * (8^a8) * (9^a9)
>
>5. 取得剛剛的尾數即為結果

我覺得不用真的計算這麼大的數...(應該會溢位吧)
只要看總共有幾個 2 ,3 ,5 ,7 相乘
然後
2 尾數是 4次一循環
3 尾數是 4次一循環
7 尾數是 4次一循環

就可以算比較小的數了
作者 : sunyear(coco) VC++卓越專家C++頂尖高手貼文超過2000則
[ 貼文 2421 | 人氣 1485 | 評價 6060 | 評價/貼文 2.5 | 送出評價 5 次 ] 
[ 給個讚 ]  [ 給個讚 ]  [ 回應本文 ]  [ 發表新文 ]  [ 回上頁 ] [ 回討論區列表 ] [ 回知識入口 ]
2003/10/20 下午 07:16:22
更正這行為:
for(Cnt2=(Cnt2-Cnt5)%4,tmp=6; Cnt2--;)tmp=tmp*2%10;//求2的(Cnt2-Cnt5)次方的尾數(2的n次方尾數是2,4,8,6的循環)
作者 : neville(福寶)
[ 貼文 111 | 人氣 1806 | 評價 310 | 評價/貼文 2.79 | 送出評價 1 次 ] 
[ 給個讚 ]  [ 給個讚 ]  [ 回應本文 ]  [ 發表新文 ]  [ 回上頁 ] [ 回討論區列表 ] [ 回知識入口 ]
2003/10/20 下午 10:14:10
汗...原來還有2次方尾數的關係,這測試的方法果然是不正確的...
9-99999999也看不出有明顯的依存關係...><
而 coco 的程式,在 20!=4,50!=2!,99!=4,200!=2,500!=4,999!=2.
都與數學軟體 Maple 相符
作者 : sunyear(coco) VC++卓越專家C++頂尖高手貼文超過2000則
[ 貼文 2421 | 人氣 1485 | 評價 6060 | 評價/貼文 2.5 | 送出評價 5 次 ] 
[ 給個讚 ]  [ 給個讚 ]  [ 回應本文 ]  [ 發表新文 ]  [ 回上頁 ] [ 回討論區列表 ] [ 回知識入口 ]
2003/10/21 上午 08:56:04
>而 coco 的程式,在 20!=4,50!=2!,99!=4,200!=2,500!=4,999!=2.
>都與數學軟體 Maple 相符
Maple 可以算非零的尾數啊!?
是否可以自動驗證 1~99999 階乘的非零的尾數?

剛看了一下我寫的,發現對階乘數來說2的因子永遠比5多,所以程式可以改
簡潔一點:
void main()
{
unsigned long Result,tmp;
unsigned long num,max,Cnt2;
loop:
cout<<endl<<"Enter a number 1~999999999:";
cin>>max;
if (!max) exit(0);//input 0 to end the program
for (Result=num=1, Cnt2=0; (tmp=num++)<=max;){
while ((tmp%10)==0) tmp/=10;//10的因子直接移除
while ((tmp%5)==0)tmp/=5,--Cnt2;//抽出5的因子(5的因子永遠比2的因子少,所以可以這樣做)
while ((tmp&1)==0)tmp>>=1,++Cnt2;//抽出2的因子
Result=Result*(tmp%10)%10;//2,5,10的因子已移出,尾數不會有零,所已只取尾數
}
if(Cnt2){
for(Cnt2=Cnt2%4,tmp=6; Cnt2--;)tmp=tmp*2%10;//求2的Cnt2次方的尾數(2的n次方尾數是2,4,8,6的循環)
cout<<"Rear nonzero digit="<<Result*tmp%10<<endl;
}
else
cout<<"Rear nonzero digit="<<Result<<endl;//Result就是最後的尾數
goto loop;

}

可惜只是讓程式看來簡潔一點而已,對執行時間並無幫助 >"<
注意到這個程式跑999999999!比上個快約7秒,但那是這行
for (Result=num=1, Cnt2=0; (tmp=num)<=max; ++num){
改成
for (Result=num=1, Cnt2=0; (tmp=num++)<=max;){
所節省的時間,不是少掉了Cnt5計值的功勞。
作者 : lcwdl(混世魔王) 貼文超過500則人氣指數超過10000點
[ 貼文 951 | 人氣 10894 | 評價 1100 | 評價/貼文 1.16 | 送出評價 10 次 ] 
[ 給個讚 ]  [ 給個讚 ]  [ 回應本文 ]  [ 發表新文 ]  [ 回上頁 ] [ 回討論區列表 ] [ 回知識入口 ]
2003/10/21 下午 12:56:52

>>而 coco 的程式,在 20!=4,50!=2!,99!=4,200!=2,500!=4,999!=2.
>>都與數學軟體 Maple 相符
>Maple 可以算非零的尾數啊!?

Maple是一個非常強大的數學軟體,基本的繪圖...什麼都有
你甚至可以在上面寫程式,這個例子我相信也是可以在Maple上面寫出來的
作者 : lcwdl(混世魔王) 貼文超過500則人氣指數超過10000點
[ 貼文 951 | 人氣 10894 | 評價 1100 | 評價/貼文 1.16 | 送出評價 10 次 ] 
[ 給個讚 ]  [ 給個讚 ]  [ 回應本文 ]  [ 發表新文 ]  [ 回上頁 ] [ 回討論區列表 ] [ 回知識入口 ]
2003/10/21 下午 02:21:28

>只要看總共有幾個 2 ,3 ,5 ,7 相乘

因為乘2的個數一定會比乘5多,兩個消去後就只剩2, 3, 7囉!

接著照:

>2 尾數是 4次一循環

2^(4n+k)的個位數:
在k=1時是2
在k=2時是4
在k=3時是8
在k=0時是6

>3 尾數是 4次一循環

3^(4n+k)的個位數:
在k=1時是3
在k=2時是9
在k=3時是7
在k=0時是1

>7 尾數是 4次一循環

7^(4n+k)的個位數:
在k=1時是7
在k=2時是9
在k=3時是3
在k=0時是1

查到後相乘,相信碼表都還沒按答案就出來了 :)
作者 : sunyear(coco) VC++卓越專家C++頂尖高手貼文超過2000則
[ 貼文 2421 | 人氣 1485 | 評價 6060 | 評價/貼文 2.5 | 送出評價 5 次 ] 
[ 給個讚 ]  [ 給個讚 ]  [ 回應本文 ]  [ 發表新文 ]  [ 回上頁 ] [ 回討論區列表 ] [ 回知識入口 ]
2003/10/21 下午 03:13:39
>查到後相乘,相信碼表都還沒按答案就出來了 :)
是嗎?
基本上因為尾數會移位,所以不能只看所有乘數的尾數。
先確認方法是對的,用”手工”模擬”碼表都還沒按答案就出來了”的方法,算一下
10!, 20!看對是不對!
作者 : milx(Milx) Java Script優秀好手貼文超過200則
[ 貼文 463 | 人氣 7517 | 評價 1150 | 評價/貼文 2.48 | 送出評價 14 次 ] 
[ 給個讚 ]  [ 給個讚 ]  [ 回應本文 ]  [ 發表新文 ]  [ 回上頁 ] [ 回討論區列表 ] [ 回知識入口 ]
2003/10/21 下午 07:17:24

>>查到後相乘,相信碼表都還沒按答案就出來了 :)
>是嗎?


對呀....^^
這是基本的數學問題
尾數是零代表有10這個因數
既然已經化簡成因數只有2,3,7
那麼尾數就不會有零了...
這我國中就算過了...好像是國一吧
只是要寫成程式讓大家看我就沒辦法了...我是初學者
我昨天寫了超久還是沒寫出來(想哭)...==
作者 : sunyear(coco) VC++卓越專家C++頂尖高手貼文超過2000則
[ 貼文 2421 | 人氣 1485 | 評價 6060 | 評價/貼文 2.5 | 送出評價 5 次 ] 
[ 給個讚 ]  [ 給個讚 ]  [ 回應本文 ]  [ 發表新文 ]  [ 回上頁 ] [ 回討論區列表 ] [ 回知識入口 ]
2003/10/21 下午 09:44:11
>>>查到後相乘,相信碼表都還沒按答案就出來了 :)
>>是嗎?
>對呀....^^
>這是基本的數學問題
>尾數是零代表有10這個因數
>既然已經化簡成因數只有2,3,7
>那麼尾數就不會有零了...
好像還在 Xavier的方法上面繞 >~<
先用19!這個數來驗證好了:

尾數 出現值   出現次數
2  2,12  2
3  3,13  2
4  4,14  2
5  5,15  2
6  6,16  2
7  7,17  2
8  8,18  2
9  9,19  2
-------------------------------
5和2各出現2次(合成10),刪去
3和7各出現2次(合成21),刪去
其餘的相乘:
4x4x6x6x8x8x9x9=2985984
所以尾數是 4,我不知道,但如果是用20!
這個數來驗證,其尾數統計會是和上面的一樣的,對吧!?
(因為20的尾數是0所以不計),但20*19!會令19!的尾數改變
,假設上面看出的19!尾數是4是正確的,那麼19!的數應是
???...???4 對吧!這個l數乘以20會是:
???...???80 呵呵,非零尾數變成8了。所以事實上19!和20!
的非零尾數是不一樣的!
正確的19!=121645100408832000--->非零尾數為2
   20!=2432902008176640000-->非零尾數為4
這個驗證指出Xavier統計尾數的一個漏洞:
10  不計尾數,Fine!
20  不計尾數?不行!!它會影響非零尾數,怎可不計,正確應計尾數 2
30  應計為尾數3
250 應計為尾數5
1400應計為尾數4
:::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::
那麼加入上面這些遺漏的尾數再計算可以嗎?
也許可以吧...如果沒有別的漏洞的話 ^^
我去辦點事,回來若有時間寫一個看看,或有人有興趣試試。

作者 : gmmark12(MM)
[ 貼文 17 | 人氣 72 | 評價 100 | 評價/貼文 5.88 | 送出評價 0 次 ] 
[ 給個讚 ]  [ 給個讚 ]  [ 回應本文 ]  [ 發表新文 ]  [ 回上頁 ] [ 回討論區列表 ] [ 回知識入口 ]
2003/10/21 下午 11:03:29
我自己寫的程式碼如下:習慣不好,寫得頗亂!請哪位寫出的高手幫我Run一下好嗎?自己測試了一下初步覺得沒有問題。輸入的數值只要不超過long的範圍即可。

#include <stdio.h>
#include <conio.h>
long main()
{
long n,i,j,m=1,k;
long fiv=0,t[4]={6,8,4,2};
clrscr();
fiv=0; m=1;
scanf("%ld",&n);
k=n;
for(i=1;i<=n%10;i++)
{
if(i%5) m=(m*i)%10;
}
while(k>5)
{
k=k/5;
for(i=1;i<=k%10;i++)
{
if(i%5) m=(m*i)%10;
}
fiv=(fiv+k)%4;
}
/* 6,8,4,2 */
printf("The Number is %ld\n",t[fiv]*m%10);
getch();
return 0;
}
作者 : xavier(Xavier)
[ 貼文 38 | 人氣 757 | 評價 200 | 評價/貼文 5.26 | 送出評價 2 次 ] 
[ 給個讚 ]  [ 給個讚 ]  [ 回應本文 ]  [ 發表新文 ]  [ 回上頁 ] [ 回討論區列表 ] [ 回知識入口 ]
2003/10/21 下午 11:31:49
嗯 果然被發現了
我之後就是有再算過(小算盤+紙筆)
算來算去就是不對(中間還有自己稍微修修改改)
即使是加上漏掉的那幾個數也不對

或許是我的計算錯誤
或許是我的方法還需要修改
最慘的可能是我的方法根本不對...

希望coco大這次可以改好它.....
作者 : sunyear(coco) VC++卓越專家C++頂尖高手貼文超過2000則
[ 貼文 2421 | 人氣 1485 | 評價 6060 | 評價/貼文 2.5 | 送出評價 5 次 ] 
[ 給個讚 ]  [ 給個讚 ]  [ 回應本文 ]  [ 發表新文 ]  [ 回上頁 ] [ 回討論區列表 ] [ 回知識入口 ]
2003/10/22 上午 12:49:35
>嗯 果然被發現了
>我之後就是有再算過(小算盤+紙筆)
>算來算去就是不對(中間還有自己稍微修修改改)
>即使是加上漏掉的那幾個數也不對
回來做了個小測試(有補上面的漏洞),發現程式跑到15!就不對了 ^^
程式貼在下面,有興趣的人可以研究看看
(NonZeroRear就是在計算階乘的非零尾數,程式很短但不容易看懂^^)
unsigned long NonZeroRear(unsigned long max){
    //尾數2~9的次方循環表
    const unsigned long CyclRear[][4]={
    {6,2,4,8},{1,3,9,7},{6,4,6,4},
    {5,5,5,5},{6,6,6,6},{1,7,9,3},
    {6,8,4,2},{1,9,1,9}};
    unsigned long RearCnt[10]={0};//count of rear 0~9
    unsigned long TmpMax, curRear, Result=1;
for (curRear=2; curRear<10; ++curRear){
     for (TmpMax=max; TmpMax; TmpMax/=10){
     RearCnt[curRear]+=(curRear>TmpMax%10)?TmpMax/10:TmpMax/10+1;
     }
Result *= (RearCnt[curRear]==0)?1:CyclRear[curRear-2][RearCnt[curRear]%4];
if (!(Result%10)) Result/=10;//尾數0要去掉
}
return Result%10;
}

void main()
{
unsigned long Result,max;
unsigned _int64 FactN,Check;
for (max=1; max<=40;++max){
Check= FactN= fac(max);
while(!(Check%10)) Check/=10;
Check%=10;
Result= NonZeroRear(max);
if (Check!=Result){
cout<<"Wrong at "<<max<<"!= "<<FactN<<endl;
cout<<"Nonzero rear number is solved as=" <<Result<<endl;
break;
}
}
cout<<"*** The End ***"<<endl;
}

為什麼補了漏洞還是不對?
因為直接取得的尾數個數,並不是因子個數,所以還是有進位的問題,例如最後得到了
一個2和一個5,乘積得10是不能拋棄的,個位數的0可以丟掉,但1要進位後得到一個
新的尾數,問題在於此方法一開始就拋棄了10位數一上的資料,所以無法計算進位以得
到新的尾數,所以 Xavier 的方法大概是死巷了吧 :(

上面 NonZeroRear 函式計算階乘乘數2~9尾數個數的程式,有點短但應是對的,若有
疑問我可解釋,但誠如前述,這是條死巷。除非你想研究"計算階乘乘數2~9尾數個數",
否則大可不必傷腦筋了。
作者 : sunyear(coco) VC++卓越專家C++頂尖高手貼文超過2000則
[ 貼文 2421 | 人氣 1485 | 評價 6060 | 評價/貼文 2.5 | 送出評價 5 次 ] 
[ 給個讚 ]  [ 給個讚 ]  [ 回應本文 ]  [ 發表新文 ]  [ 回上頁 ] [ 回討論區列表 ] [ 回知識入口 ]
2003/10/22 上午 12:53:47
漏了階乘函式:
_int64 fac(int i){
return (i<=1)?i:i*fac(i-1);
}
作者 : milx(Milx) Java Script優秀好手貼文超過200則
[ 貼文 463 | 人氣 7517 | 評價 1150 | 評價/貼文 2.48 | 送出評價 14 次 ] 
[ 給個讚 ]  [ 給個讚 ]  [ 回應本文 ]  [ 發表新文 ]  [ 回上頁 ] [ 回討論區列表 ] [ 回知識入口 ]
2003/10/22 上午 03:06:49
ㄏㄏ...我想錯了...
不過..我有了個比較簡單的想法...一樣是拿尾數相乘(10,20,30,...沒有略掉)
9!的尾數是8


譬如
24!
=(1*2*3*4*5*6*7*8*9*10)*(11*12*13*14*15*16*17*18*19*20)*(21*22*23*24)
=(1*2*3*4*5*6*7*8*9)*(11*12*13*14*15*16*17*18*19)*(21*22*23*24)*(10*20)

尾數=
9!*9!*4!*2!的尾數

54!的尾數就等於8^5 * 4! * 5!的尾數
996!的尾數就等於8^99 * 6! * 99!的尾數
999999!的尾數就等於8^99999 * 9! * 99999!的尾數
ab!的尾數就等於8^a的尾數 * b!第一位非0的尾數 * a!的尾數
(b是個位的那個數字 a是去掉個位數剩下的數字)

8^a的尾數有循環...很容易算
b!的尾數有可能為0...處理一下就可以了
a!好像是原本的問題....用遞迴處理

這樣就解決了吧(我會不會說不清楚呀)

哪為大大可以寫一下程式去跑呀...
我不會寫...ㄏㄏ(我是初學者)
作者 : milx(Milx) Java Script優秀好手貼文超過200則
[ 貼文 463 | 人氣 7517 | 評價 1150 | 評價/貼文 2.48 | 送出評價 14 次 ] 
[ 給個讚 ]  [ 給個讚 ]  [ 回應本文 ]  [ 發表新文 ]  [ 回上頁 ] [ 回討論區列表 ] [ 回知識入口 ]
2003/10/22 上午 03:18:23
抱歉...筆誤
>9!的尾數是8
9!的第一個非0尾數是8

>尾數=
>9!*9!*4!*2!的尾數

>尾數=
>9!*9!*4!*2!的第一個非0尾數

作者 : lcwdl(混世魔王) 貼文超過500則人氣指數超過10000點
[ 貼文 951 | 人氣 10894 | 評價 1100 | 評價/貼文 1.16 | 送出評價 10 次 ] 
[ 給個讚 ]  [ 給個讚 ]  [ 回應本文 ]  [ 發表新文 ]  [ 回上頁 ] [ 回討論區列表 ] [ 回知識入口 ]
2003/10/22 上午 06:58:38

>這個驗證指出Xavier統計尾數的一個漏洞:
>10  不計尾數,Fine!
>20  不計尾數?不行!!它會影響非零尾數,怎可不計,正確應計尾數 2
>30  應計為尾數3
>250 應計為尾數5
>1400應計為尾數4
>:::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::
>那麼加入上面這些遺漏的尾數再計算可以嗎?
>也許可以吧...如果沒有別的漏洞的話 ^^

我之前隨便想想就貼了上來,沒想到真的就鬧了笑話 :P
這樣做的確有漏洞!!
 COCO真的是寶刀未老 :-) 佩服 佩服!
作者 : sunyear(coco) VC++卓越專家C++頂尖高手貼文超過2000則
[ 貼文 2421 | 人氣 1485 | 評價 6060 | 評價/貼文 2.5 | 送出評價 5 次 ] 
[ 給個讚 ]  [ 給個讚 ]  [ 回應本文 ]  [ 發表新文 ]  [ 回上頁 ] [ 回討論區列表 ] [ 回知識入口 ]
2003/10/22 上午 08:47:09
>不過..我有了個比較簡單的想法...一樣是拿尾數相乘(10,20,30,...沒有略掉)
>9!的尾數是8
>譬如
>24!
>=(1*2*3*4*5*6*7*8*9*10)*(11*12*13*14*15*16*17*18*19*20)*
>(21*22*23*24)
>=(1*2*3*4*5*6*7*8*9)*(11*12*13*14*15*16*17*18*19)*(21*22*23*24)*
>(10*20)

>尾數=
>9!*9!*4!*2!的尾數
>54!的尾數就等於8^5 * 4! * 5!的尾數
一樣有尾數進位問題!
9!的非零尾數是8不表示11*12...*19的非零尾數也是8。
作者 : xavier(Xavier)
[ 貼文 38 | 人氣 757 | 評價 200 | 評價/貼文 5.26 | 送出評價 2 次 ] 
[ 給個讚 ]  [ 給個讚 ]  [ 回應本文 ]  [ 發表新文 ]  [ 回上頁 ] [ 回討論區列表 ] [ 回知識入口 ]
2003/10/22 上午 09:29:29
我有一個想法
既然10個數一個區間不行
而惱人的進位問題又只發生在???2 * ???5上(這是因為階層才滿足這條件)
那如果我以100個數一個區間呢?

這時3,4,6,7,8,9次數計算如上(當然不可以漏掉30,40,60...)
然後計算2,5,12,15,22,25,.....,82,85,92,95的個數
(也不要漏掉20和50啊.......)
12以上的數可以使用coco的抽取因數法加入前面的計數中
(或許可以先算出100!中各數的數值來增加速度)

這樣的話至少我用紙筆+小算盤計算20!,30!,40!是正確的
速度上也應該是可以落在限定範圍內

只是.... 希望這次不要又落到死巷了.......
作者 : sunyear(coco) VC++卓越專家C++頂尖高手貼文超過2000則
[ 貼文 2421 | 人氣 1485 | 評價 6060 | 評價/貼文 2.5 | 送出評價 5 次 ] 
[ 給個讚 ]  [ 給個讚 ]  [ 回應本文 ]  [ 發表新文 ]  [ 回上頁 ] [ 回討論區列表 ] [ 回知識入口 ]
2003/10/22 下午 12:11:48
>既然10個數一個區間不行
>而惱人的進位問題又只發生在???2 * ???5上(這是因為階層才滿足這條件)
>那如果我以100個數一個區間呢?

進位的問題不是只發生在???2 * ???5,也不是都只進一位,例如
125*8,8既非2也不是5,但乘上125後非零尾數會進三位^^
重點在有2和5的因子就會造成非零尾數的進位,不是看光看尾數就知
會不會進位或進幾位。

>只是.... 希望這次不要又落到死巷了.......
好像還在巷子裡沒有迴轉 ^_@
作者 : xavier(Xavier)
[ 貼文 38 | 人氣 757 | 評價 200 | 評價/貼文 5.26 | 送出評價 2 次 ] 
[ 給個讚 ]  [ 給個讚 ]  [ 回應本文 ]  [ 發表新文 ]  [ 回上頁 ] [ 回討論區列表 ] [ 回知識入口 ]
2003/10/22 下午 12:26:03
>進位的問題不是只發生在???2 * ???5,也不是都只進一位,例如
>125*8,8既非2也不是5,但乘上125後非零尾數會進三位^^
>重點在有2和5的因子就會造成非零尾數的進位,不是看光看尾數就知
>會不會進位或進幾位。
>
>好像還在巷子裡沒有迴轉 ^_@

至少這巷子寬多了咩...
而且應該是不會發生125*8的情形
因為照階層的計算方式如果出現了125,在他之前也一定會出現122
122 * 125 = 15250, 22 * 25 = 550
兩組的第一個非0尾數是一樣的,所以我才想這樣改寫試試

只不過再往下算數字太大了,小算盤好像也不夠力了
不知道我是不是真的一頭撞在牆上不知道迴轉了
作者 : milx(Milx) Java Script優秀好手貼文超過200則
[ 貼文 463 | 人氣 7517 | 評價 1150 | 評價/貼文 2.48 | 送出評價 14 次 ] 
[ 給個讚 ]  [ 給個讚 ]  [ 回應本文 ]  [ 發表新文 ]  [ 回上頁 ] [ 回討論區列表 ] [ 回知識入口 ]
2003/10/22 下午 12:40:33
ㄏㄏ...
抱歉....我又錯了
真不甘心...
我一定要想出一個連碼錶都還沒按答案就出來的方法
作者 : sunyear(coco) VC++卓越專家C++頂尖高手貼文超過2000則
[ 貼文 2421 | 人氣 1485 | 評價 6060 | 評價/貼文 2.5 | 送出評價 5 次 ] 
[ 給個讚 ]  [ 給個讚 ]  [ 回應本文 ]  [ 發表新文 ]  [ 回上頁 ] [ 回討論區列表 ] [ 回知識入口 ]
2003/10/22 下午 01:26:14
>而且應該是不會發生125*8的情形
>因為照階層的計算方式如果出現了125,在他之前也一定會出現122
>122 * 125 = 15250, 22 * 25 = 550
>兩組的第一個非0尾數是一樣的,所以我才想這樣改寫試試
只要有5的因子(不管幾個)的數乘上有2,4,6,8尾數的數就都會有進位的情況。
這樣的case一定會有吧!^^

>只不過再往下算數字太大了,小算盤好像也不夠力了
>不知道我是不是真的一頭撞在牆上不知道迴轉了
我解釋前面寫的那個程式,若我能說服你它是對的,那不仿拿它來
比對你的新方法。一群數相乘(如階乘就是):
X1*X2*X3....*Xn
抽出X1~Xn的2,5,10因子(10^a*2^b*5^c)後,X1~Xn變成x1~xn
(注意到10^a 意即10的a次方)
那麼
X1*X2*X3....*Xn
=x1*x2*x3...*xn * (10^a*2^b*5^c)
理論上沒有2,5因子的數相乘是不會出現零的尾數的,所以
x1*x2*x3...*xn 的個位數相乘的尾數即非零尾數,假設得 Y
那麼求非零尾數的式子就成了
Y*(10^a*2^b*5^c)
由於10^a因子不會影非零尾數,所以直接刪除得
Y*(2^b*5^c)
再來是,2和5的因子可配對得10也可刪除(事實上前面刪除的10的因子就2和5的配對)
假設 c>b (5的因子較多),尾數式子成了
Y*(5^(c-b))而我們知道的 5的自乘結果尾數還是5,因此尾數式子變成
Y*5
注意到Y中沒有2的因子,所以Y必為奇數,而5乘上奇數,尾數必然是5,所以最後的非
零尾數就是5了。
但在階乘裡,2的因子永遠多於5的因子的,所以2和5因子配對後應是
Y*(2^(b-c))
而幸運的是2的自乘也不會有尾數進位的問題,所以只要求得2^(b-c)的尾數Z再和
Y相乘,取其結果的個位尾數既所求的非零尾數。

說了一堆,是為了取信於你(雖然我自己也沒把握^^),你可以"暫時"拿這個程式去驗證
你的新點子,就不用小算盤或筆紙了。

作者 : sunyear(coco) VC++卓越專家C++頂尖高手貼文超過2000則
[ 貼文 2421 | 人氣 1485 | 評價 6060 | 評價/貼文 2.5 | 送出評價 5 次 ] 
[ 給個讚 ]  [ 給個讚 ]  [ 回應本文 ]  [ 發表新文 ]  [ 回上頁 ] [ 回討論區列表 ] [ 回知識入口 ]
2003/10/22 下午 01:49:42
剛試了一下,把下面這行拿掉:
while ((tmp%10)==0) tmp/=10;//10的因子直接移除
結果在我的 PIII-550在1分50秒完成999999999!的非零尾數計算。
相信拿一台 PIV-2G 的機器應可在30秒內完成的。
這行:while ((tmp%10)==0) tmp/=10;本來是要加快運算的,沒想到反成了絆腳石^^

void main()
{
unsigned long Result,tmp;
unsigned long num,max,Cnt2;
loop:
cout<<endl<<"Enter a number 1~999999999:";
cin>>max;
if (!max) exit(0);//input 0 to end the program
for (Result=num=1, Cnt2=0; (tmp=num++)<=max;){
//while ((tmp%10)==0) tmp/=10;//10的因子直接移除
while ((tmp%5)==0)tmp/=5,--Cnt2;//抽出5的因子(5的因子永遠比2的因子少,所以可以這樣做)
while ((tmp&1)==0)tmp>>=1,++Cnt2;//抽出2的因子
Result=Result*(tmp%10)%10;//2,5,10的因子已移出,尾數不會有零,所已只取尾數
}
if(Cnt2){
for(Cnt2=Cnt2%4,tmp=6; Cnt2--;)tmp=tmp*2%10;//求2的Cnt2次方的尾數(2的n次方尾數是2,4,8,6的循環)
cout<<"Rear nonzero digit="<<Result*tmp%10<<endl;
}
else
cout<<"Rear nonzero digit="<<Result<<endl;//Result就是最後的尾數
goto loop;
}


作者 : neville(福寶)
[ 貼文 111 | 人氣 1806 | 評價 310 | 評價/貼文 2.79 | 送出評價 1 次 ] 
[ 給個讚 ]  [ 給個讚 ]  [ 回應本文 ]  [ 發表新文 ]  [ 回上頁 ] [ 回討論區列表 ] [ 回知識入口 ]
2003/10/22 下午 05:04:38
Maple 可以算非零的尾數啊!?
不行..>< 小弟的方法是,把maple 算出來的 1-n! 的結果,存成一個文字檔.
然後用程式,把答案取非零尾數,再轉存成另一個檔案.
然後修改 coco 的程式,把檔案讀起來和程式的計算結果比對.
因為檔案大小的限制,只算到1-1000!(這樣超過 1MB)
在這個範圍內是完全正確的.
作者 : sunyear(coco) VC++卓越專家C++頂尖高手貼文超過2000則
[ 貼文 2421 | 人氣 1485 | 評價 6060 | 評價/貼文 2.5 | 送出評價 5 次 ] 
[ 給個讚 ]  [ 給個讚 ]  [ 回應本文 ]  [ 發表新文 ]  [ 回上頁 ] [ 回討論區列表 ] [ 回知識入口 ]
2003/10/22 下午 05:35:57
>小弟的方法是,把maple 算出來的 1-n! 的結果,存成一個文字檔.
>然後用程式,把答案取非零尾數,再轉存成另一個檔案.
>然後修改 coco 的程式,把檔案讀起來和程式的計算結果比對.
>因為檔案大小的限制,只算到1-1000!(這樣超過 1MB)
>在這個範圍內是完全正確的.
能算到1000!是正確的,應可合理相信到999999999!也是對的吧!
雖然我的程式速度不令人滿意,但應可用來檢驗別的快速方法是否正確。
作者 : gmmark12(MM)
[ 貼文 17 | 人氣 72 | 評價 100 | 評價/貼文 5.88 | 送出評價 0 次 ] 
[ 給個讚 ]  [ 給個讚 ]  [ 回應本文 ]  [ 發表新文 ]  [ 回上頁 ] [ 回討論區列表 ] [ 回知識入口 ]
2003/10/22 下午 07:09:31
麻煩幫我測試!!我的程式只要1秒就可以算出999999999,輸入範圍在long值。
粗略說一下我的演算法:我先計算有幾個5的乘積在N!裡面,
從1乘到N只用尾數相乘,但不算5的倍數,更重要的一點是,由於我只把5剔除,所以乘末尾時把15當成3來算,20當成4來算,1000當成8來算...等。

所以舉例而言:26!的末尾:先看成(1*2*3*4*6*7*8*9)*(1*2*3*4*6*7*8*9)*(1*2*3*4*6)。>>這裡的尾數是4....

(1*2*3*4*6*7*8*9)末尾是6,怎麼自乘都是6。凡偶數乘6都會是本身。
前述1*2*3*4*6*7*8*9....都略去,只要算1*2*3*4*6

用短除法(迴圈)做到不含5為止:(5*10*15*20)改為(1*2*3*4)。(25)改成1。
這裡又得到一個末尾是4...乘上剛才個位數相乘的值。目前的末尾得到6。
並由此計算出5的乘積個數有6個。

所以26!被除以了6個5和6個2。
不含5時,已得末尾是6。利用循環除以六次的2:6>>8>>4>>2>>6>>8>>4,所以末尾是4。

上次公布的程式碼有誤,此次更正。希望大家幫我抓錯,甚至挑戰,在long的範圍內,我的程式幾乎可以不按馬表。


#include <stdio.h>
#include <conio.h>
long main()
{
long n,i,j,m=1,k,q;
long fiv=0,t[4]={6,8,4,2};
clrscr();
fiv=0; m=1;
scanf("%ld",&n);
k=n;
for(i=1;i<=n%10;i++)
{
if(i%5) m=(m*i)%10;
}
while(k>=5)
{
k=k/5;
for(i=1;i<=k%10;i++)
{
if(i%5) m=(m*i)%10;
}
fiv=(fiv+k)%4;
}
/* 6,8,4,2 */
if(k==1)
{
printf("The Number is 1\n");
  }
else
{
printf("The Number is %ld\n",t[fiv]*m%10);
}
getch();
return 0;
}
作者 : neville(福寶)
[ 貼文 111 | 人氣 1806 | 評價 310 | 評價/貼文 2.79 | 送出評價 1 次 ] 
[ 給個讚 ]  [ 給個讚 ]  [ 回應本文 ]  [ 發表新文 ]  [ 回上頁 ] [ 回討論區列表 ] [ 回知識入口 ]
2003/10/22 下午 07:53:47
實在缺乏正確的方向,請問一下 promiseway ,這倒底是 ACM 中的第幾題呀?
ACM的題目大多都有一些提示的方向,去看看提示也好...:Q
作者 : milx(Milx) Java Script優秀好手貼文超過200則
[ 貼文 463 | 人氣 7517 | 評價 1150 | 評價/貼文 2.48 | 送出評價 14 次 ] 
[ 給個讚 ]  [ 給個讚 ]  [ 回應本文 ]  [ 發表新文 ]  [ 回上頁 ] [ 回討論區列表 ] [ 回知識入口 ]
2003/10/22 下午 08:06:34
什麼是ACM呀
作者 : bugmans(尋找夏天的甲蟲)
[ 貼文 3 | 人氣 5 | 評價 0 | 評價/貼文 0 | 送出評價 0 次 ] 
[ 給個讚 ]  [ 給個讚 ]  [ 回應本文 ]  [ 發表新文 ]  [ 回上頁 ] [ 回討論區列表 ] [ 回知識入口 ]
2003/10/22 下午 08:34:37
http://infoserv.com.tw/phorum/read.php?f=1&i=20084&t=20084
作者 : promiseway(promiseway)
[ 貼文 124 | 人氣 3991 | 評價 30 | 評價/貼文 0.24 | 送出評價 8 次 ] 
[ 給個讚 ]  [ 給個讚 ]  [ 回應本文 ]  [ 發表新文 ]  [ 回上頁 ] [ 回討論區列表 ] [ 回知識入口 ]
2003/10/22 下午 08:55:54
謝謝大家出了不少力^^

給福寶
我是看npscㄉ題目ㄉ= ="
不過似乎acm568題跟這題差不多

給Milx
http://acm.uva.es/problemset/
你到這ㄍ網址看看,或許你就知道囉
作者 : sunyear(coco) VC++卓越專家C++頂尖高手貼文超過2000則
[ 貼文 2421 | 人氣 1485 | 評價 6060 | 評價/貼文 2.5 | 送出評價 5 次 ] 
[ 給個讚 ]  [ 給個讚 ]  [ 回應本文 ]  [ 發表新文 ]  [ 回上頁 ] [ 回討論區列表 ] [ 回知識入口 ]
2003/10/23 上午 02:34:46
re:尋找夏天的甲蟲
可否貼出你的程式碼?
求質因式法,可行!但其實只要抽取2,5因子就可以了。
求到質因式,我想反而變慢了。是否和我的程式比較過?孰快?
提到答案在28126會循環,是真確的嗎?你是如何驗證的?
另外你提到的查表法,若是這樣解題合法,其實不用建28126 個records的
表格的!只要每百萬建一個record,內容為該數階乘的非零尾數和2因子
數量(要扣掉5因子數量)就可以了。這樣的表格若要求到999999999!只要
999筆records就可以了。例如要求12345678!的非零尾數,只要查表得到
12000000!這個數的非零尾數和2因子數量,再以此為基礎求到12345678!
的非零尾數。在我上面貼的程式中求一百萬的尾數(PIII-550)不到1/5秒。所
建999筆的表格就可以在1/5秒內求到999999999!內的非零尾數。
但查表節省的時間會被承認嗎?
作者 : neville(福寶)
[ 貼文 111 | 人氣 1806 | 評價 310 | 評價/貼文 2.79 | 送出評價 1 次 ] 
[ 給個讚 ]  [ 給個讚 ]  [ 回應本文 ]  [ 發表新文 ]  [ 回上頁 ] [ 回討論區列表 ] [ 回知識入口 ]
2003/10/23 下午 02:21:29
附議..:Q
本來也想用這方法的,但是在 n=999999999
質因式分解光在求質數的部份,就有 (n-2)*(log(2,n)) 的複雜度了.
 把質數相乘,在這麼大的 n 下,又是一個很花時間的問題.
還有尾數 50000!-50009!=8868266264,21874!-21883!=2242844846
作者 : bugmans(尋找夏天的甲蟲)
[ 貼文 3 | 人氣 5 | 評價 0 | 評價/貼文 0 | 送出評價 0 次 ] 
[ 給個讚 ]  [ 給個讚 ]  [ 回應本文 ]  [ 發表新文 ]  [ 回上頁 ] [ 回討論區列表 ] [ 回知識入口 ]
2003/10/23 下午 05:41:11
coco的方法也是對的,整題的關鍵是去掉10的因數,至於剩下的數字該怎麼乘每個人做法不同
至於我說的28126會循環一次是用文字編輯器的搜尋功能找出來的,需要大家再驗證
#include<stdio.h>
#include<math.h>
long FindFactor(int n,int prime)
{//對於prime這個質因數,求1~n共有幾個
long count=0;
do{n/=prime;
   count+=n;
  }
while(n!=0);
return count;
}
/****************************************/
void main()
{
freopen("568.cpp","w",stdout);
long n,i,j,k,factor[4],Prime[2500],TotalPrime=0;
int number[11000]={0};
for(i=2;i<11000;i++)//利用Eratosthenes篩法,建質數表
  {if(number[i]==0)
     {Prime[TotalPrime++]=i;
     for(j=2;(k=i*j)<11000;j++)
number[k]=1;
     }
  }
long count=7;
printf("char result[100][100]={\n");
printf("\"126422");
for(n=7;n<=10000;n++)
  {factor[0]=FindFactor(n,2);
   factor[1]=0;//3
   factor[2]=FindFactor(n,5);
   factor[3]=0;//7
   for(i=1;Prime[i]<=n;i++)
     {switch(Prime[i]%10)
{case 1://尾數是1的質因數不影響結果
break;
case 3:
factor[1]+=FindFactor(n,Prime[i]);
break;
case 7:
factor[3]+=FindFactor(n,Prime[i]);
break;
case 9://尾數是9的質因數可代表兩個3相乘,所以乘兩倍
factor[1]+=2*FindFactor(n,Prime[i]);
break;
}
     }
   factor[0]=(factor[0]-factor[2])%4;//先扣掉質因數5的個數再取4循環
   factor[1]%=4;
   factor[2]=0;//質因數5的個數為0
   factor[3]%=4;
   if(factor[0]==0)
     factor[0]=4;
   printf("%ld",((long)(pow(2,factor[0])*pow(3,factor[1])*pow(7,factor[3])))%10);
   if((count++)==100)//每輸出100個換行一次
     {printf("\",\n\"");
     count=1;}
  }
}
作者 : gmmark12(MM)
[ 貼文 17 | 人氣 72 | 評價 100 | 評價/貼文 5.88 | 送出評價 0 次 ] 
[ 給個讚 ]  [ 給個讚 ]  [ 回應本文 ]  [ 發表新文 ]  [ 回上頁 ] [ 回討論區列表 ] [ 回知識入口 ]
2003/10/23 下午 07:34:50
寫給Milx,我這個程式也寫了許多次,也想過你之前的(9!)末尾是8,
所以24!只要8*8*4!求末尾即可。但後來才發現這個寫法有瑕疵。

1 2 3 4 5 6 7 8 9 10
11 12 13 14 15 16 17 18 19 20
21 22 23 24

刪去四個5的次方....

1 2 3 4 1 6 7 8 9 2
11 12 13 14 3 16 17 18 19 4

此時,就可看出端倪:因為所求應該為(1*2*3*4*6*7*8*9)^2 * 4! * (1*2*3*4)
前面5,10,15,20=5*1, 5*2, 5*3, 5*4刪去5以後,必須保留1,2,3,4,然後就可以使用末尾相乘。
最後刪去四個2的次方,因為先前刪去四個5,所以要再刪去四個2。
作者 : lcwdl(混世魔王) 貼文超過500則人氣指數超過10000點
[ 貼文 951 | 人氣 10894 | 評價 1100 | 評價/貼文 1.16 | 送出評價 10 次 ] 
[ 給個讚 ]  [ 給個讚 ]  [ 回應本文 ]  [ 發表新文 ]  [ 回上頁 ] [ 回討論區列表 ] [ 回知識入口 ]
2003/10/24 上午 06:53:26

大略的幫你測試一下:
999! => 2 (你的程式出現的是 1)
200! => 2 (你的程式出現的是 1)

>麻煩幫我測試!!
>#include <stdio.h>
>#include <conio.h>
>long main()
>{
> long n,i,j,m=1,k,q;
> long fiv=0,t[4]={6,8,4,2};
> clrscr();
> fiv=0; m=1;
> scanf('%ld',&n);
> k=n;
> for(i=1;i<=n%10;i++)
> {
> if(i%5) m=(m*i)%10;
> }
> while(k>=5)
> {
> k=k/5;
> for(i=1;i<=k%10;i++)
> {
> if(i%5) m=(m*i)%10;
> }
> fiv=(fiv+k)%4;
> }
> /* 6,8,4,2 */
> if(k==1)
> {
> printf('The Number is 1
');
> }
> else
> {
> printf('The Number is %ld
',t[fiv]*m%10);
> }
> getch();
> return 0;
>}
作者 : sunyear(coco) VC++卓越專家C++頂尖高手貼文超過2000則
[ 貼文 2421 | 人氣 1485 | 評價 6060 | 評價/貼文 2.5 | 送出評價 5 次 ] 
[ 給個讚 ]  [ 給個讚 ]  [ 回應本文 ]  [ 發表新文 ]  [ 回上頁 ] [ 回討論區列表 ] [ 回知識入口 ]
2003/10/24 下午 03:27:34
re:MM
>麻煩幫我測試!!我的程式只要1秒就可以算出999999999,輸入範圍在long值。
>粗略說一下我的演算法:我先計算有幾個5的乘積在N!裡面,
>::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::
看不懂你說明,但
(11*12*13....19)-->簡化成1*2*3...9
就又一樣有進位的問題了!
至少寫完和程式也要自己測到20!吧!?
你的程式在5!答案就不對了,也許是程式的bug不是方法的問題,但自己要先抓bug。

>上次公布的程式碼有誤,此次更正。希望大家幫我抓錯,甚至挑戰,
>在long的範圍內,我的程式幾乎可以不按馬表。
先求能正確再看碼表吧。
作者 : duncan_macleod(洋將) Java卓越專家貼文超過1000則
[ 貼文 1121 | 人氣 921 | 評價 2490 | 評價/貼文 2.22 | 送出評價 3 次 ] 
[ 給個讚 ]  [ 給個讚 ]  [ 回應本文 ]  [ 發表新文 ]  [ 回上頁 ] [ 回討論區列表 ] [ 回知識入口 ]
2003/10/24 下午 03:45:20
我用 Python 稍微檢查了 999999! 的結果,我想 coco 的演算法是正確的。
Base on coco's algorithm,稍微作點修改,我以 Dev-cpp 編譯(Best-Optimization),計算 999999999! 需要 94.926 seconds,如果調高 process priority 到 high,則最快的紀錄約 92.143 seconds,配備 AMD Althlon K7 550 MHz + PC133 sdram on Windows2000 pro。

我有試著以 VC7 來作 optimize,可能是不熟悉吧,怎麼調快不過用 Dev-cpp IDE 設定的 optimization。有沒有願意以 VC6 校調試試?

#include <iostream>
#include <cmath>
#include <ctime>
#include <stdlib.h>

inline
int TailOfFactorial(unsigned long N)
{
    int loan = static_cast<int>(log(N) / log(5.0));
    int twos = 0;
    int tof = 1;
    for (unsigned long i = 1; i <= N; ++i) {
     int x = i;
     while (!(x % 10)) // x 為 10 的倍數
     x /= 10;

     while (!(x % 5)) // x 為 5 的倍數
     {
     --twos;
     x /= 5;
     }
    
     // x 是 2 的倍數,而且借貸的 2s 還不夠
     while ((twos < loan) && !(x & 0x1))
     {
     ++twos;
     x = x >> 1;
     }
     x %= 10; // 取個位數
     tof = (tof * x) % 10;
    }
    
    if (twos)
     tof = static_cast<int>(pow(2.0, twos) * tof) % 10;
    
    return tof;
}

using namespace std;

int main(int argc, char *argv[])
{
    unsigned long n = 10;
    if (argc > 1)
     n = atol(argv[1]);

    cout << "N=" << n << endl;
    system("PAUSE");
    clock_t start = clock();
    int tof = TailOfFactorial(n);
    clock_t end = clock();
    cout << "Tail of " << n << "! is: " << tof << endl;
    cout << "Evaluation in "
     << static_cast<double>(end - start) / CLOCKS_PER_SEC
     << " seconds."
     << endl;
    system("PAUSE");
    return 0;
}
作者 : duncan_macleod(洋將) Java卓越專家貼文超過1000則
[ 貼文 1121 | 人氣 921 | 評價 2490 | 評價/貼文 2.22 | 送出評價 3 次 ] 
[ 給個讚 ]  [ 給個讚 ]  [ 回應本文 ]  [ 發表新文 ]  [ 回上頁 ] [ 回討論區列表 ] [ 回知識入口 ]
2003/10/24 下午 05:14:00

>我用 Python 稍微檢查了 999999! 的結果,我想 coco 的演算法是正確的。
>Base on coco''s algorithm,稍微作點修改,我以 Dev-cpp 編譯(Best-Optimization),計算 999999999! 需要 94.926 seconds,如果調高 process priority 到 high,則最快的紀錄約 92.143 seconds,配備 AMD Althlon K7 550 MHz + PC133 sdram on Windows2000 pro。

我也把 10 的倍數檢查拿掉,進步到 84.852 seconds。
作者 : gmmark12(MM)
[ 貼文 17 | 人氣 72 | 評價 100 | 評價/貼文 5.88 | 送出評價 0 次 ] 
[ 給個讚 ]  [ 給個讚 ]  [ 回應本文 ]  [ 發表新文 ]  [ 回上頁 ] [ 回討論區列表 ] [ 回知識入口 ]
2003/10/24 下午 06:56:18
感謝coco幫我抓錯,第二次的程式碼不止5!錯,凡25!、125!、625!都會出錯。

我已經將bug更正,希望大家再幫我看一次。要是大家確定沒問題,我就將我的演算法說明一遍。很抱歉也許我可以將coco的程式碼拿來自己檢查,但我使用Dev C++卻無法執行。我不太會用Dev,因為像clrscr()清除螢幕指令為何在Dev不能使用,我也不清楚。

以下為我的新程式碼,執行時間挺短,不會耽誤大家太多時間,但我這次把N以內所有的值全部列出來了。
#include <stdio.h>
#include <conio.h>
long main()
{
long n,i,j,m=1,k,q;
long fiv=0,t[4]={6,8,4,2};

scanf("%ld",&n);
for(j=1;j<=n;j++)
{
fiv=0; m=1;
k=j;
for(i=1;i<=j%10;i++)
{
if(i%5) m=(m*i)%10;
}
while(k>=5)
{
k=k/5;
for(i=1;i<=k%10;i++)
{
if(i%5) m=(m*i)%10;
}
fiv=(fiv+k)%4;
}
/* 6,8,4,2 */
if(j==1)
{
printf("(%5d,1)\t",1);
}
else
{
printf("(%5ld,%ld)\t",j,t[fiv]*m%10);
}
}
getch();
return 0;
}

要是各位想一個一個看:這是修改過的程式碼。

#include <stdio.h>
#include <conio.h>
long main()
{
long n,i,j,m=1,k,q;
long fiv=0,t[4]={6,8,4,2};

scanf("%ld",&n);
k=n;
fiv=0; m=1;
for(i=1;i<=n%10;i++)
{
if(i%5) m=(m*i)%10;
}
while(k>=5)
{
k=k/5;
for(i=1;i<=k%10;i++)
{
if(i%5) m=(m*i)%10;
}
fiv=(fiv+k)%4;
}
/* 6,8,4,2 */
if(n==1)
{
printf("(%5d,1)\t",1);
}
else
{
printf("(%5ld,%ld)\t",n,t[fiv]*m%10);
}
getch();
return 0;
}
作者 : gmmark12(MM)
[ 貼文 17 | 人氣 72 | 評價 100 | 評價/貼文 5.88 | 送出評價 0 次 ] 
[ 給個讚 ]  [ 給個讚 ]  [ 回應本文 ]  [ 發表新文 ]  [ 回上頁 ] [ 回討論區列表 ] [ 回知識入口 ]
2003/10/24 下午 08:37:02
我說欲求99999999!的末尾第一個不為零的值可以在1 sec 內求出不是唬人的,以下是我的演算法。

簡潔而言:要是我算52!的末尾數字。

S(52!)=1*2*3*4*5*6*7*8*9*10*....*52
   =(1*2*3*4*6*7*8*9)(11*12*13*14*16*17*18*19)...(51*52)
    (5*10*15*20*30*35*40*45)(25*50)(這行有5,待會要刪去)
   =(1*2*3*4*6*7*8*9)(1*2*3*4*6*7*8*9)...(1*2)(以下提出所有的5,相乘者不刪去)
   *(5^8)(1*2*3*4*6*7*8*9)*(25^2)(1*2)(其係數(1*2)(1*2*3*4*6*7*8*9)不可刪去,末尾相乘才成立。)
   
52!必須除以12個5,後得到一個末尾數字S,將此S再除以12個2。因此就能去除52!末尾的12個0。
S(1*2*3*4*6*7*8*9)=6
所以承上,跑過程式後,初步得到S(52!/(5^12)):S(50!)=6*6*6*6*6*6*(1*2)*(1*2)=4
這時要除以13個2,4%(2^12)=0,怎麼辦?
利用循環:4>>2>>6>>8>>4>>2>>6>>8>>4>>2>>6>>8>>4

所以,S(52!)=4,這用手算也是很快的。
作者 : duncan_macleod(洋將) Java卓越專家貼文超過1000則
[ 貼文 1121 | 人氣 921 | 評價 2490 | 評價/貼文 2.22 | 送出評價 3 次 ] 
[ 給個讚 ]  [ 給個讚 ]  [ 回應本文 ]  [ 發表新文 ]  [ 回上頁 ] [ 回討論區列表 ] [ 回知識入口 ]
2003/10/24 下午 10:29:11

>我說欲求99999999!的末尾第一個不為零的值可以在1 sec 內求出不是唬人的,以下是我的演算法。

我想沒有人有你在唬人的意思吧,請不要想太多....^^

你的演算法裡頭有幾點真的是很重要,base on 你的演算法,我稍微作了調整,可以把整個演算過程以 recursive 的方式來作,我想會更容易理解,而且即使使用遞迴會引進 function call 的負擔,還是比你的方式快。

修改的地方有:一是把 1*2*3*.., 1*2*3*4*6*.. 這些需要的計算換成查表。二是看法上的不同,在計算 5 的倍數相乘積的尾數時一樣是把 5 提出來,比如 N=57 時,在計算 5 * 10 * 15 *...* 55 的這步驟以 1*2*3*...*11 來取代(以求得尾數),在這裡等於又回到原來的問題,求 11! 的尾數,只是問題的 dimension 變小了。

int tableL[] = {6,1,2,6,4,4,4,8,4,6};
int tableS[] = {6, 8, 4, 2};

int recTOF(unsigned long n, int tableA[], int tableB[])
{
    if (n < 2) return 1;
    int q = n / 5;
    return tableA[n % 10] * recTOF(q, tableA, tableB) * tableB[q % 4] % 10;
}

N! 的尾數可以 recTOF(N, tableL, tableS) 求得。

這樣的解法應該是 log(N) 的複雜度,log5(999999999) 不過也才 12.88 而已,難怪會那麼快。
作者 : fuckyoursister(C36UX)
[ 貼文 70 | 人氣 1966 | 評價 0 | 評價/貼文 0 | 送出評價 0 次 ] 
[ 給個讚 ]  [ 給個讚 ]  [ 回應本文 ]  [ 發表新文 ]  [ 回上頁 ] [ 回討論區列表 ] [ 回知識入口 ]
2003/10/24 下午 10:31:38
>我說欲求99999999!的末尾第一個不為零的值可以在1 sec 內求出不是唬人的,
>以下是我的演算法。

天才!太佩服你了!

專家是可以訓練的,只是要達到天才的境界還是非常非常非常地困難ㄚ
作者 : milx(Milx) Java Script優秀好手貼文超過200則
[ 貼文 463 | 人氣 7517 | 評價 1150 | 評價/貼文 2.48 | 送出評價 14 次 ] 
[ 給個讚 ]  [ 給個讚 ]  [ 回應本文 ]  [ 發表新文 ]  [ 回上頁 ] [ 回討論區列表 ] [ 回知識入口 ]
2003/10/25 上午 02:00:24
哈哈哈...我成功了
用MM大大的演算法...再把他簡化
MM大大是天才...^^
然後用遞迴...瞬間答案就出來了....應該不會再錯了....
我寫了好幾天...再不對我就...


我是用javascript寫的...我不太會寫c...
不過邏輯是一樣的...語法也差不多...要改成c很容易...
http://home.kimo.com.tw/icenuclear/007.htm
這個網頁會印出 1~999階乘的的第一非零尾數...我不用一秒就跑完了(AMD XP 2500+)
作者 : lcwdl(混世魔王) 貼文超過500則人氣指數超過10000點
[ 貼文 951 | 人氣 10894 | 評價 1100 | 評價/貼文 1.16 | 送出評價 10 次 ] 
[ 給個讚 ]  [ 給個讚 ]  [ 回應本文 ]  [ 發表新文 ]  [ 回上頁 ] [ 回討論區列表 ] [ 回知識入口 ]
2003/10/25 上午 04:09:51
To 洋將:
您(參考COCO)所改的程式好像有個小bug:
在輸入625的時候會傳回1 (答案是6)

>#include <iostream>
>#include <cmath>
>#include <ctime>
>#include <stdlib.h>
>
>inline
>int TailOfFactorial(unsigned long N)
>{
> int loan = static_cast<int>(log(N) / log(5.0));
> int twos = 0;
> int tof = 1;
> for (unsigned long i = 1; i <= N; ++i) {
> int x = i;
> while (!(x % 10)) // x 為 10 的倍數
> x /= 10;
>
> while (!(x % 5)) // x 為 5 的倍數
> {
> --twos;
> x /= 5;
> }
>
> // x 是 2 的倍數,而且借貸的 2s 還不夠
> while ((twos < loan) && !(x & 0x1))
> {
> ++twos;
> x = x >> 1;
> }
> x %= 10; // 取個位數
> tof = (tof * x) % 10;
> }
>
> if (twos)
> tof = static_cast<int>(pow(2.0, twos) * tof) % 10;
>
> return tof;
>}
>
>using namespace std;
>
>int main(int argc, char *argv[])
>{
> unsigned long n = 10;
> if (argc > 1)
> n = atol(argv[1]);
>
> cout << 'N=' << n << endl;
> system('PAUSE');
> clock_t start = clock();
> int tof = TailOfFactorial(n);
> clock_t end = clock();
> cout << 'Tail of ' << n << '! is: ' << tof << endl;
> cout << 'Evaluation in '
> << static_cast<double>(end - start) / CLOCKS_PER_SEC
> << ' seconds.'
> << endl;
> system('PAUSE');
> return 0;
>}
作者 : lcwdl(混世魔王) 貼文超過500則人氣指數超過10000點
[ 貼文 951 | 人氣 10894 | 評價 1100 | 評價/貼文 1.16 | 送出評價 10 次 ] 
[ 給個讚 ]  [ 給個讚 ]  [ 回應本文 ]  [ 發表新文 ]  [ 回上頁 ] [ 回討論區列表 ] [ 回知識入口 ]
2003/10/25 上午 04:29:18
to MM:

你新的程式,目前我跑到1000000 (仍在繼續測試當中),都跟COCO以及Maple所跑出來的答案一樣哦 :)

很好奇的是:你拿掉5的想法是怎麼想出來的啊?

>我不太會用Dev,因為像clrscr()清除螢幕指令為何在Dev不能使用

因為clrscr()不是ANSI C的函式

作者 : gmmark12(MM)
[ 貼文 17 | 人氣 72 | 評價 100 | 評價/貼文 5.88 | 送出評價 0 次 ] 
[ 給個讚 ]  [ 給個讚 ]  [ 回應本文 ]  [ 發表新文 ]  [ 回上頁 ] [ 回討論區列表 ] [ 回知識入口 ]
2003/10/25 上午 10:26:48
To 混世魔王:謝謝你為我解答clrscr()的問題。

太好啦!那這次的階層問題是不是算解決了呢?感謝大家幫我測試程式,不過這個程式碼我只有把它寫到long的範圍。

我一直以為速度快、程式碼少、功能多的程式就是好程式,所以各位知道演算法後,怎麼寫讓時間更進步就看大家的意思了。像混世魔王、洋將等前輩就把它改成recursive,速度加快,程式碼也縮短了。

這個演算法我花了一整天的時間想,用了五六張紙一直做推演,也許這樣聽起來像個天才,不過我是ㄍ高三生,與各位相比離學科近多了,所以先想出這個程式也挺合理的。

最後,真的要謝謝各位抽空幫看程式。
作者 : duncan_macleod(洋將) Java卓越專家貼文超過1000則
[ 貼文 1121 | 人氣 921 | 評價 2490 | 評價/貼文 2.22 | 送出評價 3 次 ] 
[ 給個讚 ]  [ 給個讚 ]  [ 回應本文 ]  [ 發表新文 ]  [ 回上頁 ] [ 回討論區列表 ] [ 回知識入口 ]
2003/10/25 上午 10:33:40

>to MM:
>
>你新的程式,目前我跑到1000000 (仍在繼續測試當中),都跟COCO以及Maple所跑出來的答案一樣哦 :)

我想可以不需要再測下去了,"理論上" MM 採用的演算法可以正確地求出尾數來。
作者 : duncan_macleod(洋將) Java卓越專家貼文超過1000則
[ 貼文 1121 | 人氣 921 | 評價 2490 | 評價/貼文 2.22 | 送出評價 3 次 ] 
[ 給個讚 ]  [ 給個讚 ]  [ 回應本文 ]  [ 發表新文 ]  [ 回上頁 ] [ 回討論區列表 ] [ 回知識入口 ]
2003/10/25 上午 10:41:49
>我一直以為速度快、程式碼少、功能多的程式就是好程式,所以各位知道演算法後,怎麼寫讓時間更進步就看大家的意思了。像混世魔王、洋將等前輩就把它改成recursive,速度加快,程式碼也縮短了。

基本上你的演算法已經是 log(N) 了,怎麼寫都不會太慢。 :)

我 post 的部分真正改善速度的是引用另一個表格以查表代替實際的階層計算,以 recursive 形式來作則是讓程式碼更簡潔,邏輯上也更清晰罷了(前提是要瞭解背後的演算法)。
作者 : duncan_macleod(洋將) Java卓越專家貼文超過1000則
[ 貼文 1121 | 人氣 921 | 評價 2490 | 評價/貼文 2.22 | 送出評價 3 次 ] 
[ 給個讚 ]  [ 給個讚 ]  [ 回應本文 ]  [ 發表新文 ]  [ 回上頁 ] [ 回討論區列表 ] [ 回知識入口 ]
2003/10/25 下午 01:21:27

>To 洋將:
>您(參考COCO)所改的程式好像有個小bug:
>在輸入625的時候會傳回1 (答案是6)

謝謝你的提醒。

這是因為在將 log(625)/log(5) 轉成 int 的時候錯誤了,應該是 4 卻是得到 3。

演算法本身應該是沒問題的!
作者 : duncan_macleod(洋將) Java卓越專家貼文超過1000則
[ 貼文 1121 | 人氣 921 | 評價 2490 | 評價/貼文 2.22 | 送出評價 3 次 ] 
[ 給個讚 ]  [ 給個讚 ]  [ 回應本文 ]  [ 發表新文 ]  [ 回上頁 ] [ 回討論區列表 ] [ 回知識入口 ]
2003/10/25 下午 01:30:47

>To 混世魔王:謝謝你為我解答clrscr()的問題。
>
>太好啦!那這次的階層問題是不是算解決了呢?感謝大家幫我測試程式,不過這個程式碼我只有把它寫到long的範圍。
>
>我一直以為速度快、程式碼少、功能多的程式就是好程式,所以各位知道演算法後,怎麼寫讓時間更進步就看大家的意思了。像混世魔王、洋將等前輩就把它改成recursive,速度加快,程式碼也縮短了。
>
>這個演算法我花了一整天的時間想,用了五六張紙一直做推演,也許這樣聽起來像個天才,不過我是ㄍ高三生,與各位相比離學科近多了,所以先想出這個程式也挺合理的。
>
>最後,真的要謝謝各位抽空幫看程式。

你是高中生應該對整數數論有一定的熟悉度。
我在想你如果沒有課業上的壓力,是否有意有一邊有關這主題的討論,以比較有系統的方式來論證你的演算法?畢竟以你的程式碼來看不是很容易瞭解背後運用到的原理,而且你也沒有在特定一篇的回覆中,以比較完整的面貌來呈現你的想法。有許多環節你沒提到,但是這些環節缺了一個,你的演算法就倒了。

順利的話你明年就進大學了,也許還會繼續到研究所以上,現在先練習一下寫報告也不錯..^^

印象中,我高中時就只會一直算,很少有理論上的探討練習,像高中生只會"算"微分積分,到了大學碰到證明,倒的倒死的死,到了向量微積分更是屍橫遍野,我就是一例。
作者 : promiseway(promiseway)
[ 貼文 124 | 人氣 3991 | 評價 30 | 評價/貼文 0.24 | 送出評價 8 次 ] 
[ 給個讚 ]  [ 給個讚 ]  [ 回應本文 ]  [ 發表新文 ]  [ 回上頁 ] [ 回討論區列表 ] [ 回知識入口 ]
2003/10/25 下午 08:40:28
嗯^^
謝謝各位
雖然連發文ㄉ人自已本身都消失好幾天:D
不過我已經將他改成自已所需要ㄉ語言了
本篇文章也應該告一段落了,再次謝謝各位^^
作者 : sunyear(coco) VC++卓越專家C++頂尖高手貼文超過2000則
[ 貼文 2421 | 人氣 1485 | 評價 6060 | 評價/貼文 2.5 | 送出評價 5 次 ] 
[ 給個讚 ]  [ 給個讚 ]  [ 回應本文 ]  [ 發表新文 ]  [ 回上頁 ] [ 回討論區列表 ] [ 回知識入口 ]
2003/10/26 下午 11:15:02
家裡的網路掛了兩天,到剛剛才恢復,想不到這議題已有驚人的發展!
恭喜MM的方法的成功。
其實之前我也有想過只要把5因數提出後就不會有尾數零的問題了,
但想到最後的尾數除以和5因數同數量的2時,又會有進進位的問題,而作罷:
(...E2)/2 的尾數是1 (...O2)/2的尾數是6
E是指十位數為偶數,O是指十位數為奇數
(...E4),(...O4) (...E6),(...O6) (...E8),(...O8) 也都有同樣的問題,
所以才在之前回覆MM:
>(11*12*13....19)-->簡化成1*2*3...9
>就又一樣有進位的問題了!
因為十位以上的數字丟棄後,就無法確定除2的尾數了。

但我是多慮了...原因是既然階乘數的2因子太多了,只要2因子數量多出5因子
一個以上,那麼除相同5因子數量的2以內,結果都還是偶數,換句話說:
(...O2), (...O4), (...E6), (...O8) 這些除2會得奇數的數是不會發生的。
所以即使只保留尾數,還是可預期除2的尾數的。

說這些不是放馬後炮,可能MM並沒想到或想到但沒說明,但
要把 (11*12*13....19)-->簡化成1*2*3...9 之前要說明其可行的原理是相
當重要的。這篇就當作”補遺”給大家參考! ^^
作者 : sunyear(coco) VC++卓越專家C++頂尖高手貼文超過2000則
[ 貼文 2421 | 人氣 1485 | 評價 6060 | 評價/貼文 2.5 | 送出評價 5 次 ] 
[ 給個讚 ]  [ 給個讚 ]  [ 回應本文 ]  [ 發表新文 ]  [ 回上頁 ] [ 回討論區列表 ] [ 回知識入口 ]
2003/10/27 上午 07:57:06
更正:
(...E2), (...O4), (...E6), (...O8) 這些除2會得奇數的數是不會發生的。
作者 : sunyear(coco) VC++卓越專家C++頂尖高手貼文超過2000則
[ 貼文 2421 | 人氣 1485 | 評價 6060 | 評價/貼文 2.5 | 送出評價 5 次 ] 
[ 給個讚 ]  [ 給個讚 ]  [ 回應本文 ]  [ 發表新文 ]  [ 回上頁 ] [ 回討論區列表 ] [ 回知識入口 ]
2003/10/27 下午 12:36:12
to:洋將
我想把MM和你的重點文章轉貼到E-Home時發現(轉胋時總會看仔細一點^^)
發現
>int tableL[] = {6,1,2,6,4,4,4,8,4,6};
是否為
int tableL[] = {6,6,2,6,4,4,4,8,4,6};
之誤?
雖然這個錯誤在運算的過程會”巧合”的被淹蓋了,但總是使得閱讀上產生困感。
事實上tableL中的元素 6,均可改為1,雖然table是錯的,但最後答案都會是
對的。
6真是個奇妙的數!@_@

另外既然recTOF要做成遞迴,tableL,tableS可不必當參數傳,這樣可節省一點點
"微薄"的時間:
unsigned recTOF(unsigned long n)
{
return (n < 2)?1:tableL[n % 10] * recTOF(n/5) * tableS[n/5 % 4] % 10;
}
作者 : duncan_macleod(洋將) Java卓越專家貼文超過1000則
[ 貼文 1121 | 人氣 921 | 評價 2490 | 評價/貼文 2.22 | 送出評價 3 次 ] 
[ 給個讚 ]  [ 給個讚 ]  [ 回應本文 ]  [ 發表新文 ]  [ 回上頁 ] [ 回討論區列表 ] [ 回知識入口 ]
2003/10/27 下午 07:08:28
>to:洋將
>我想把MM和你的重點文章轉貼到E-Home時發現(轉胋時總會看仔細一點^^)
>發現
>>int tableL[] = {6,1,2,6,4,4,4,8,4,6};
>是否為
>int tableL[] = {6,6,2,6,4,4,4,8,4,6};
>之誤?
>雖然這個錯誤在運算的過程會”巧合”的被淹蓋了,但總是使得閱讀上產生困感。
>事實上tableL中的元素 6,均可改為1,雖然table是錯的,但最後答案都會是
>對的。

這不是筆誤,只是我覺得這樣子寫會使得程式碼所顯示的概念清晰一點,後來想想改成
int tableL[] = {1,1,2,6,4,4,4,8,4,6};
可能更好。

現在有一個函數如下:
L(n) =
n! 第一個不為零的尾數, if n in [1 4]
n!/5 第一個不為零的尾數, if n in [5 9]

這個 tableL[1] ~ tableL[9] 就是紀錄 L(1) ~ L(9) 的值,以 MM 提出的方式來計算時會用到,假設 N 第一個不為零的尾數為 M(N),那麼在計算 M(N!) 可拆解為 M(N/10 * L(9))、M(L(N % 10)) 與 {小於 N 的所有 5 的倍數之乘積},tableL 就是省略計算 L(N % 10) 這個部分(換以查表來產出),所以我直接把 L(1) ~ L(9) 預算出來放到 table 以供查詢,至於 table[0] 給定 6 是基於 6 乘 一個 M(n) 為偶數的 n 值有 identity 的作用(當然 1 也有這個特性),有了 tableL[0] 在就不必考慮當 N 為 10 的倍數時便沒有 L(N % 10) 這一項而必須採用不同的對待方式,所以我可以很單純地寫成簡單的 recursive 形式,其實 tableL[0] 設為 1 就可以了,觀念也很清晰。就像你講的 tableL 為 6 的 cell 都可以改成 1,不過我沒有這麼做只是想說或許別人比較可以看到出 tableL 存在的目的,而且改成 1 對效率沒什麼太大的影響,只是更不容易明白這個 table 的用意。
作者 : duncan_macleod(洋將) Java卓越專家貼文超過1000則
[ 貼文 1121 | 人氣 921 | 評價 2490 | 評價/貼文 2.22 | 送出評價 3 次 ] 
[ 給個讚 ]  [ 給個讚 ]  [ 回應本文 ]  [ 發表新文 ]  [ 回上頁 ] [ 回討論區列表 ] [ 回知識入口 ]
2003/10/27 下午 07:16:03
>說這些不是放馬後炮,可能MM並沒想到或想到但沒說明,但
>要把 (11*12*13....19)-->簡化成1*2*3...9 之前要說明其可行的原理是相
>當重要的。這篇就當作”補遺”給大家參考! ^^

的確是重要,所以在打字的時候要更小心..:)

MM 提到的是 M(11*12*...*14*16*...*19) = M(1*2*...*4*6*...*9),因為裡頭沒有 5 的因子在。
作者 : duncan_macleod(洋將) Java卓越專家貼文超過1000則
[ 貼文 1121 | 人氣 921 | 評價 2490 | 評價/貼文 2.22 | 送出評價 3 次 ] 
[ 給個讚 ]  [ 給個讚 ]  [ 回應本文 ]  [ 發表新文 ]  [ 回上頁 ] [ 回討論區列表 ] [ 回知識入口 ]
2003/10/27 下午 08:17:42
>這個 tableL[1] ~ tableL[9] 就是紀錄 L(1) ~ L(9) 的值,以 MM 提出的方式來計算時會用到,假設 N 第一個不為零的尾數為 M(N),那麼在計算 M(N!) 可拆解為 M(N/10 * L(9))、M(L(N % 10)) 與 {小於 N 的所有 5 的倍數之乘積},

糟糕!真的筆誤了.... ^^"

應該是"M(N!) 可拆解為 M(L(9)^(N/10))、M(L(N % 10)) 與 {小於 N 的所有 5 的倍數之乘積}"。
作者 : sunyear(coco) VC++卓越專家C++頂尖高手貼文超過2000則
[ 貼文 2421 | 人氣 1485 | 評價 6060 | 評價/貼文 2.5 | 送出評價 5 次 ] 
[ 給個讚 ]  [ 給個讚 ]  [ 回應本文 ]  [ 發表新文 ]  [ 回上頁 ] [ 回討論區列表 ] [ 回知識入口 ]
2003/10/27 下午 08:34:39
>這個 tableL[1] ~ tableL[9] 就是紀錄 L(1) ~ L(9) 的值,以 MM 提出的方式來計算
>時會用到,假設 N 第一個不為零的尾數為 M(N),那麼在計算 M(N!) 可拆解為 M
>(N/10 * L(9))、M(L(N % 10)) 與 {小於 N 的所有 5 的倍數之乘積},tableL 就是省
>略計算 L(N % 10) 這個部分(換以查表來產出),所以我直接把 L(1) ~ L(9) 預算出
>來放到 table 以供查詢,至於 table[0] 給定 6 是基於 6 乘 一個 M(n) 為偶數的 n 值
>有 identity 的作用(當然 1 也有這個特性),有了 tableL[0] 在就不必考慮當 N 為
>10 的倍數時便沒有 L(N % 10) 這一項而必須採用不同的對待方式,所以我可以很
>單純地寫成簡單的 recursive 形式,其實 tableL[0] 設為 1 就可以了,觀念也很清
>晰。就像你講的 tableL 為 6 的 cell 都可以改成 1,不過我沒有這麼做只是想說或
>許別人比較可以看到出 tableL 存在的目的,而且改成 1 對效率沒什麼太大的影
>響,只是更不容易明白這個 table 的用意。
這樣說也說得通,但如你說的改成
int tableL[] = {1,1,2,6,4,4,4,8,4,6};
會比較合你的說法。
我是很單純的的比對MM的演算和tableL直覺的認為:
S是求尾數的函數
S(Xn!) <---X十位以上的數,n為個位數
=S((1*2*3*4*6*7*8*9)(11*12*13*14*16*17*18*19)...(X1*X2*Xn...))
  *(含5因子的數)
=S(6*(X1*X2*3...Xn)) *(含5因子的數)
=S(6*n!) *(含5因子的數)
而tableL是S(6*(n!))值域表,所以tableL應為:
int tableL[] = {6,6,2,6,4,4,4,8,4,6};
這樣的解讀,只必需再解釋個位數階乘的適用問題:
由於程式中的這一行
若n為2~9的那麼n!必為偶數,所以
S(6*n!) =S(n!)
所以對2~9的階乘來說tableL仍是適用的,而對小於2的階乘來說,這行程式
if (n < 2) return 1;
解決了 這個問題。
無論如何tableL的前兩個元素,應全為1或全為6是比較好理解的。

作者 : duncan_macleod(洋將) Java卓越專家貼文超過1000則
[ 貼文 1121 | 人氣 921 | 評價 2490 | 評價/貼文 2.22 | 送出評價 3 次 ] 
[ 給個讚 ]  [ 給個讚 ]  [ 回應本文 ]  [ 發表新文 ]  [ 回上頁 ] [ 回討論區列表 ] [ 回知識入口 ]
2003/10/27 下午 09:13:18
我和你的看法不同罷了!

>這樣說也說得通,但如你說的改成
>int tableL[] = {1,1,2,6,4,4,4,8,4,6};
>會比較合你的說法。
>我是很單純的的比對MM的演算和tableL直覺的認為:
>S是求尾數的函數
>S(Xn!) <---X十位以上的數,n為個位數
>=S((1*2*3*4*6*7*8*9)(11*12*13*14*16*17*18*19)...(X1*X2*Xn...))
> *(含5因子的數)
>=S(6*(X1*X2*3...Xn)) *(含5因子的數)
>=S(6*n!) *(含5因子的數)
>而tableL是S(6*(n!))值域表,所以tableL應為:
我當初建立 tableL 只是用來當作 S(X1*X2*...*Xn) 的值域表。我把 S((1*2*3*4*6*7*8*9)(11*12*13*14*16*17*18*19)...) 這一部份合成一個 6 並抽離出來,用來除以 N/10 次 2,也就是 recursive call statement 的 tableB[q % 4] % 10 這一部份。

如果你把 S(6 * (X1*X2*Xn...)) 做到表格裡,那麼除以對應於 5 的因子個數的 2s 的動作就會比較不明顯。比如以 S(16!) 來說:
16! = (1*2...*4*6*...*9)*(11*12*...*14*16) * (5*10*15)
S(16!) = S(S(1*2...*4*6*...*9) * tableL[6]/(2^3) * S(3!))
=S(6 * table[6]/(2^3) * S(3!))
***^^^^^^^^^^^^ 合併
=S(table[6]/(2^3) * S(3!))
table[6]/(2^3) 這個部分為什麼可以用 tableA[n % 10] * tableB[q % 4] % 10 來作,是不是比較不明顯?
沒關係啦,反正你知我知,大家都知道這個程式作什麼、背後的原理與為什麼是對的就好了。^^
作者 : duncan_macleod(洋將) Java卓越專家貼文超過1000則
[ 貼文 1121 | 人氣 921 | 評價 2490 | 評價/貼文 2.22 | 送出評價 3 次 ] 
[ 給個讚 ]  [ 給個讚 ]  [ 回應本文 ]  [ 發表新文 ]  [ 回上頁 ] [ 回討論區列表 ] [ 回知識入口 ]
2003/10/27 下午 09:17:29

>table[6]/(2^3) 這個部分為什麼可以用 tableA[n % 10] * tableB[q % 4] % 10 來作,是不是比較不明顯?

應該說為什麼可以用 tableL[16 % 10] * tableS[16/5 % 4] 來求?
作者 : sunyear(coco) VC++卓越專家C++頂尖高手貼文超過2000則
[ 貼文 2421 | 人氣 1485 | 評價 6060 | 評價/貼文 2.5 | 送出評價 5 次 ] 
[ 給個讚 ]  [ 給個讚 ]  [ 回應本文 ]  [ 發表新文 ]  [ 回上頁 ] [ 回討論區列表 ] [ 回知識入口 ]
2003/10/28 上午 10:03:45
>如果你把 S(6 * (X1*X2*Xn...)) 做到表格裡,那麼除以對應於 5 的因子個數的 2s
>的動作就會比較不明顯。比如以 S(16!) 來說:
>16! = (1*2...*4*6*...*9)*(11*12*...*14*16) * (5*10*15)
>S(16!) = S(S(1*2...*4*6*...*9) * tableL[6]/(2^3) * S(3!))
>=S(6 * table[6]/(2^3) * S(3!))
>***^^^^^^^^^^^^ 合併
>應該說為什麼可以用 tableL[16 % 10] * tableS[16/5 % 4] 來求?
好像有點誤解...
tableL[] = {6,6,2,6,4,4,4,8,4,6}
是對應於6 * table[6]不包括/2^3

所以 S(16!)
=S(
 S((1*2*3*4*6*7*8*9)(11*12*13*14*15*16)) <---這個式子的值查tableL[]
 *S(3!)/2^3
 )
作者 : duncan_macleod(洋將) Java卓越專家貼文超過1000則
[ 貼文 1121 | 人氣 921 | 評價 2490 | 評價/貼文 2.22 | 送出評價 3 次 ] 
[ 給個讚 ]  [ 給個讚 ]  [ 回應本文 ]  [ 發表新文 ]  [ 回上頁 ] [ 回討論區列表 ] [ 回知識入口 ]
2003/10/28 下午 12:48:56
>好像有點誤解...
>tableL[] = {6,6,2,6,4,4,4,8,4,6}
>是對應於6 * table[6]不包括/2^3
>
>所以 S(16!)
>=S(
> S((1*2*3*4*6*7*8*9)(11*12*13*14*15*16)) <---這個式子的值查tableL[]
> *S(3!)/2^3
> )

我的意思就是,S(16!) 經查表 tableL[6] 為 4,那麼接下來處理 S(4*S(3!)/(2^3)) 就比較不直覺,不容易看出為什麼可以由 6 來作?應該是由 4 除以 2 作三次,也就是從 4 在 tableS 裡 right shift 3 次,4>>2>>6>>8 得到 8,而程式的作法則是一律由 6 來 shift。(我知道為什麼這樣做,但是程式碼表現出來不明顯)
作者 : sunyear(coco) VC++卓越專家C++頂尖高手貼文超過2000則
[ 貼文 2421 | 人氣 1485 | 評價 6060 | 評價/貼文 2.5 | 送出評價 5 次 ] 
[ 給個讚 ]  [ 給個讚 ]  [ 回應本文 ]  [ 發表新文 ]  [ 回上頁 ] [ 回討論區列表 ] [ 回知識入口 ]
2003/10/28 下午 04:03:32
>我的意思就是,S(16!) 經查表 tableL[6] 為 4,那麼接下來處理 S(4*S(3!)/(2^3)) 就比
>較不直覺,不容易看出為什麼可以由 6 來作?應該是由 4 除以 2 作三次,也就是從 4 在
>tableS 裡 right shift 3 次,4>>2>>6>>8 得到 8,而程式的作法則是一律由 6 來
>shift。(我知道為什麼這樣做,但是程式碼表現出來不明顯)
^^ 原來如此...
當我認為tableA應該是 {6,6,2,6,4,4,4,8,4,6} 的時候,是這樣想的:
unsigned tableS[] = {6, 8, 4, 2}
照算應該是 {1,3,9,7} 但這個表格乘上6的尾數表即為{6, 8, 4, 2}並不影響尾數計算
,所以沒有提出(雖然不知為何多此一舉)
只是覺得正因tableS多乘了一個6所以tableA中的元素除以6也不影響結果。 所以裡面
6的元素均可以改為1。

作者 : duncan_macleod(洋將) Java卓越專家貼文超過1000則
[ 貼文 1121 | 人氣 921 | 評價 2490 | 評價/貼文 2.22 | 送出評價 3 次 ] 
[ 給個讚 ]  [ 給個讚 ]  [ 回應本文 ]  [ 發表新文 ]  [ 回上頁 ] [ 回討論區列表 ] [ 回知識入口 ]
2003/10/28 下午 09:49:48
我在別的論壇看到有人提出 G(k)=(5k+1)(5k+2)(5k+3)(5k+4), for k >= 0 的觀念,他舉出 for any k >= 0,G(k) 的尾數換同於 G(k)=24,也就是說如果把 N! 中 5 的倍數提出來,剩下的四個一組形成 N/5 個 G(k, k = 0 ~ N/5-1) 相乘,那麼就可以看成是 2^(N/5 * 2)(因為 4 = 2^2)。

利用上述的特性,只要找出 N! 有幾個 5 的因數在裡頭,減掉同樣數目的 2,那麼就可透過查表的方式來得到 2^n 的尾數,然後在乘以 N/5*5+1 ~ N 這幾個數的尾數取 10 的餘數便是 N! 的第一個不為零的尾數。

我一樣是寫成遞迴形式,這裡頭有個巧的關係。N! 中有多少個 5 成在裡頭,其實就是
Sigma(m), m = 1, 2, ..., N/5

但是我用遞迴的形式,第一次只求出 N/5 個 5,在遞迴過程中就會一一算出 N/5-1, N/5-2, ..., 1。而 N! 可以 G(k) 形式分為多少組相乘? N/5 組,而每一個的尾數都是 4 = 2^2,所以在每次執行函式時,都會得到 2*(N/5) 個 2 與 (N/5) 個 5 相乘以及剩餘的 N/5*5+1 ~ N 的尾數乘積,除了不能分組的那最多三個數之外,剩下的便是 2 和 5 的對抗,2 總是多一倍出來,2, 5 相消之後總是會剩 (N/5) 個 2 相乘,而 2^(N/5) 查表即可得到(2^1=2, 2^2=4, 2^3=8, 2^4=16,... 之後尾數就循環了)。

成是碼雖然看起來比較長,但是其背後利用到的觀念比 MM 的作法少,但相同的是兩者皆為 O(log(N)) 的演算法。

int TOFG5(unsigned long n)
{
____static const int mtable[] = {6, 2, 4, 8};
____if (n < 2) return 1;

____unsigned long q = n / 5;
____int surplus = 1;
____for (unsigned long i = q * 5 + 1; i <= n; ++i)
________surplus *= i % 10;

____return surplus * mtable[q % 4] * TOFG5(q) % 10;
}
作者 : duncan_macleod(洋將) Java卓越專家貼文超過1000則
[ 貼文 1121 | 人氣 921 | 評價 2490 | 評價/貼文 2.22 | 送出評價 3 次 ] 
[ 給個讚 ]  [ 給個讚 ]  [ 回應本文 ]  [ 發表新文 ]  [ 回上頁 ] [ 回討論區列表 ] [ 回知識入口 ]
2003/10/29 上午 12:10:27
>我一樣是寫成遞迴形式,這裡頭有個巧的關係。N! 中有多少個 5 成在裡頭,其實就是
>Sigma(m), m = 1, 2, ..., N/5

這裡寫錯了,應該是:
Sigma(m), m = 1, 2, ..., (int)log5(N)
作者 : sunyear(coco) VC++卓越專家C++頂尖高手貼文超過2000則
[ 貼文 2421 | 人氣 1485 | 評價 6060 | 評價/貼文 2.5 | 送出評價 5 次 ] 
[ 給個讚 ]  [ 給個讚 ]  [ 回應本文 ]  [ 發表新文 ]  [ 回上頁 ] [ 回討論區列表 ] [ 回知識入口 ]
2003/10/29 下午 04:56:06
>int TOFG5(unsigned long n)
>{
>____static const int mtable[] = {6, 2, 4, 8};
>____if (n < 2) return 1;
>
>____unsigned long q = n / 5;
>____int surplus = 1;
>____for (unsigned long i = q * 5 + 1; i <= n; ++i)
>________surplus *= i % 10;
>
>____return surplus * mtable[q % 4] * TOFG5(q) % 10;
>}

又一個好厲害的方法 ^^
作者 : duncan_macleod(洋將) Java卓越專家貼文超過1000則
[ 貼文 1121 | 人氣 921 | 評價 2490 | 評價/貼文 2.22 | 送出評價 3 次 ] 
[ 給個讚 ]  [ 給個讚 ]  [ 回應本文 ]  [ 發表新文 ]  [ 回上頁 ] [ 回討論區列表 ] [ 回知識入口 ]
2003/10/29 下午 07:55:50
>又一個好厲害的方法 ^^

你是指程式縮排的方法嗎?? :)
作者 : sunyear(coco) VC++卓越專家C++頂尖高手貼文超過2000則
[ 貼文 2421 | 人氣 1485 | 評價 6060 | 評價/貼文 2.5 | 送出評價 5 次 ] 
[ 給個讚 ]  [ 給個讚 ]  [ 回應本文 ]  [ 發表新文 ]  [ 回上頁 ] [ 回討論區列表 ] [ 回知識入口 ]
2003/10/29 下午 08:46:59
>>又一個好厲害的方法 ^^
>你是指程式縮排的方法嗎?? :)
從數論分析到程式的實現,唯不包括 縮排
要在這個論壇縮排貼文可用”全形空白”解決
唯有人把程式copy後會莫明其妙的不能編譯,也是
一種防盗版的方法 XD
作者 : sunyear(coco) VC++卓越專家C++頂尖高手貼文超過2000則
[ 貼文 2421 | 人氣 1485 | 評價 6060 | 評價/貼文 2.5 | 送出評價 5 次 ] 
[ 給個讚 ]  [ 給個讚 ]  [ 回應本文 ]  [ 發表新文 ]  [ 回上頁 ] [ 回討論區列表 ] [ 回知識入口 ]
2003/10/29 下午 08:59:30
防盗版縮排示範:
int TOFG5(unsigned long n)
{
  static const int mtable[] = {6, 2, 4, 8};
  if (n < 2) return 1;
  unsigned long q = n / 5;
  int surplus = 1;
  for (unsigned long i = q * 5 + 1; i <= n; ++i)
    surplus *= i % 10;
  return surplus * mtable[q % 4] * TOFG5(q) % 10;
}
作者 : yannan(yannan)
[ 貼文 54 | 人氣 5 | 評價 130 | 評價/貼文 2.41 | 送出評價 2 次 ] 
[ 給個讚 ]  [ 給個讚 ]  [ 回應本文 ]  [ 發表新文 ]  [ 回上頁 ] [ 回討論區列表 ] [ 回知識入口 ]
2003/10/31 下午 04:37:17
參考洋將大大的程式,做了一個迴圈版的:
unsigned long TOF(unsigned long n){
  int tableA[]={6,1,2,6,4,4,4,8,4,6};
  int tableB[]={6,8,4,2};
  int i=n,q=1;
  while(i>1){
    i/=5;
    q=tableA[n%10]*q*tableB[i%4]%10;
    n=i;
  }
  return q;
}
 板主 : simula
 > C++ - 討論區
 - 最近熱門問答精華集
 - 全部歷史問答精華集
 - C++ - 知識庫
  ■ 全站最新Post列表
  ■ 我的文章收藏
  ■ 我最愛的作者
  ■ 全站文章收藏排行榜
  ■ 全站最愛作者排行榜
  ■  月熱門主題
  ■  季熱門主題
  ■  熱門主題Top 20
  ■  本區Post排行榜
  ■  本區評價排行榜
  ■  全站專家名人榜
  ■  全站Post排行榜
  ■  全站評價排行榜
  ■  全站人氣排行榜
 請輸入關鍵字 
  開始搜尋
 
Top 10
評價排行
C++
1 Raymond 13050 
2 青衫 4760 
3 simula 4690 
4 coco 4030 
5 白老鼠(Gary) 3670 
6 ozzy 2540 
7 Ben 2250 
8 Anderson 1960 
9 windblown 1650 
10 Kenny 1560 
C++
  專家等級 評價  
  一代宗師 10000  
  曠世奇才 5000  
  頂尖高手 3000  
  卓越專家 1500  
  優秀好手 750  
Microsoft Internet Explorer 6.0. Screen 1024x768 pixel. High Color (16 bit).
2000-2019 程式設計俱樂部 http://www.programmer-club.com.tw/
0.46875