1、大 数运算与组合数学 ACM国际大学生程序设计竞赛国际大学生程序设计竞赛主讲:王树林主讲:王树林問題 當有一個很大的整數要運算時 , 如何算 ? 例如 : 一個一佰位數的數字 . int 最大只能到 232約十個位數的十進位數字 .最簡單的方法 先看大數加法 . 就是改成手動去算加法 , 而不是由電腦算.123456789123+ 234123467890-寫成電腦程式 方法一 : 使用陣列 (array) 例如 : int a100, b100, sum100; 然後 sumi=ai+bi+c 記住 , c 是進位 (carry), 這邊我們要自行處理 .那輸入呢 ? 輸入成字串 再把字串分
2、解成陣列中各個元素 . 需要一個 parse字串的副程式 .void parse(char *s, int *a)int i,j;j=strlen(s);for(i=0;i=10)sumi=sumi-10;c=1; else c=0;改進 array 改成 byte的元素 . (省空間 ) 更省 ? 一個元素就可以到 255, 256才進位. 用 bool 用 link list 方式 (可以讓輸入的數字更大 ) 其他 ?減法 ? 乘法 ? 除法 ? 同樣的原理 .大數運算 现将一些关键算法的实现方法描述如下:大数的一些简单计算的算法 1、大数加法运算的实现算法 (1)将 A、 B按位对齐;
3、(2)低位开始逐位相加; (3)对结果做进位调整; 2、大数减法运算实现算法 (1)将 A、 B按位对齐; (2)低位开始逐位相减; (3)对结果做借位调整;大數運算 3、大数乘法运算实现算法 (1)引入 sum2 、 sum1中间过渡量; (2)在 n的每一位上处理 m; (3)通过每一层循环,实现乘法的加法化; (4)对结果做进位调整; 4、大数除法运算的算法实现 (1)引入 al来标识 a的长度 , bl来标识 b的长度; (2)测算 a和 b的长度; (3)高位开始,对位做减法,并完成借位; (4)高位开始逐位计算商 (5)整理商 , 产生余数 ; 5、大数取模运算的算法实现 在取模运算中用到了上面的除法运算,只需返回余数即可。