话说因为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)