話說因為Worksheet有出現簡單的大數，所以就PO了篇簡單的大數文給大家參考:p。 //是說我絕對不會說內容是偷偷改自之前編的講義的:P -- 大部分程式語言中的資料型別,其所能儲存的值都有一定的範圍,那若要做的運算超出 這個範圍時該怎麼辦?或所需求精準度很高時該怎麼做?等咻碰嗎?!當然不可能啦,所以 這時候...嘿嘿~就必須自己寫一種資料結構了。 §大數的資料結構實踐(Data Structure Implementation) 我們分別使用一個陣列來儲存各個位數還有一個變數來紀錄大數。 例如:21474836472147483647 以上用大數儲存就如下 index : 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 value : 7 4 6 3 8 4 7 4 1 2 7 4 6 3 8 4 7 4 1 2 length = 20 話說為什麼是這樣反過來存呢？(其實我是正的存!只是index是從左到右寫而已XD(無誤)) 因為這樣兩個數字在做運算的時候，第i位才會剛好是對到陣列的第i-1格～ 嗯...我只是覺得這樣比較好寫啦XD，當然也是有人一直以來都是反過來做= =+。 而且我看大家作業大部分都反過來作，感覺這樣還要去對齊位數有點麻煩:p，如果一開始 輸入的時候就把字串reverse，可能會比較好做一點這樣...。 ※註:因為在 C 的語法中,陣列是由 0 開始存取,所以實際位數是到 length-1。但是以下 偽代碼,陣列都是由 1 開始到 length,這點要注意一下。 §大數加法(Addition) 一般來說,我們都是利用直式加減乘除法來做運算,所以說以下的運算方法,皆是使用 直式運算方式來思考。 BIGNUM_ADD (bignum a,bignum b) create c as a bignum c.length ← max( a.length , b.length ) for i ← 1 to c.length do c[i] ← a[i] + b[i] for i ← 1 to c.length do c[i+1] ← c[i+1] + c[i] / 10 c[i] ← c[i] mod 10 if c[c.length] ≠ 0 then c.length ← c.length + 1 return c §大數減法(Subtraction) 基本上有兩種想法,一種是最基本的借位補位直式減法,也就是平常最常用的方法。 再來另一種,就是利用補數的概念,來算減法。 也就是先求被除數的補數,再利用加法將兩數相加,最後在減掉多出位即可。 例如: 2147483647 – 123456789 = 2147483647 + (10000000000 – 0123456789) –1000000000 = 2147483647 + 9876543211 – 1000000000 = 12024026858 –1000000000 = 2024026858 其中 9876543211 為 0123456789 的 10 補數。而至於實際寫法,就請大家自己練習了。 §大數乘法(Multiplication) 與直式乘法相同,將兩邊的每一位相乘即可。其中要注意的是 a 的第 i 位乘以 b 的第 j 位,會對應到 c 的第 i + j 位,所以我們有以下的寫法。 BIGNUM_MULTIPLY (bignum a,bignum b) create c as a bignum c.length ← a.length + b.length for i ← 1 to a.length do for j ← 1 to b.length do c[i + j] ← c[i + j] + a[i] * b[j] for i ← 1 to c.length do c[i+1] ← c[i+1] + c[i] / 10 c[i] ← c[i] mod 10 if c[c.length] ≠ 0 then c.length ← c.length + 1 return c §大數除法(Division) 既然乘法是連加,那除法可以用連減的方式來解決囉?當然是可以的,只是當商數非常 大的時候,你的連減就會變的非常的慢,而且,我剛剛乘法也不是用連加的不是嗎 XD。 所以我們還是用老方法,直式除法,就像我們平常熟悉的,一位一位去減下來,所以有以下 的代碼。 BIGNUM_DIVIDE (bignum a,bignum b) create c as a bignum b move right for a.length – b.length digits // b * 10^(a .length-b.length) for i ← a.length – b.length downto 0 do if a > b then c[i] ← c[i] + 1 a ← a–b else if a <= b then b move left for 1 digit // b / 10 c.length ← a.length – b.length if c[c.length] = 0 then c.length ← c.length - 1 return c 別看上面寫的短短的,自己寫過就會知道有多不好寫了(笑)。 §大數優化(Bignumber optimization) 事實上,大數運算還可以運用一些技巧來進行優化,想一想?宣告的陣列本身的空間, 只記一位會不會浪費掉?因此很明顯的,我們可以利用「壓位數」的技巧來使運行速度增快 ,而壓位數的意思就是代表陣列裡一格不只存一位的意思,但是壓位數須要注意的是不要不 小心 Overflow 了,特別是乘法部分。而且壓位數的除法會變得複雜一點點,這就留給你們 自己想了。 ※建議:本人不建議直接使用 long long 存取(記憶體使用大並且也比較慢),而較建議用 int 存 7,8 位,只要運算過程記得形態轉換就 OK 了。 §小結(Conclusion) 以上介紹的就是基本的大數運算,不過上面只討論正數問題,當遇到負數怎麼辦呢,有 小數點又怎麼辦呢?嘿嘿!這時候就必須考驗你的智慧了!! 剛開始的時候大數常常會被直接當成一種考題,但是到後來會變成一種出題者心機的手 段,所以當看到一個題目時,先估計數值範圍是必要的!但是也不要以為,假如輸出答案是 在 int 或 long long 內就不用寫大數,在運算過程中 Overflow 或 Downflow 是常有的 事,所以大數的適用與否,必須經過適當的估計,當用則用,以免造成無法挽回的後果!! --

※ 發信站: 批踢踢實業坊(ptt.cc) ◆ From: 140.112.30.82 ※ 編輯: math120908 來自: 140.112.30.82 (10/27 08:58)