大数算法与组合数学算法.ppt

大数运算与组合数学 問題 當有一個很大的整數要運算時, 如何算? 例如: 一個一佰位數的數字. int 最大只能到 232 約十個位數的十進位數字. 最簡單的方法 先看大數加法. 就是改成手動去算加法, 而不是由電腦算. 123456789123 + 234123467890 ------------------------------------ 寫成電腦程式 方法一: 使用陣列 (array) 例如: int a[100], b[100], sum[100]; 然後 sum[i]=a[i]+b[i]+c 記住, c 是進位(carry), 這邊我們要自行處理. 那輸入呢? 輸入成字串 再把字串分解成陣列中各個元素. 需要一個parse字串的副程式. void parse(char *s, int *a){ int i,j; j=strlen(s); for(i=0;ij;i++){ a[j-1-i]=s[0]-30; } } void add(int *a, int *b, int *sum){ int i,c; c=0; for(i=0;i100;i++){ sum[i]=a[i]+b[i]+c; if(sum[i]=10){ sum[i]=sum[i]-10; c=1; } else { c=0; } } } 改進 array 改成 byte的元素. (省空間) 更省? 一個元素就可以到255, 256才進位. 用bool 用link list 方式(可以讓輸入的數字更大) 其他? 減法? 乘法? 除法? 同樣的原理. 大數運算 现将一些关键算法的实现方法描述如下： 大数的一些简单计算的算法 1、大数加法运算的实现算法 (1)将A、B按位对齐； (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、大数取模运算的算法实现 在取模运算中用到了上面的除法运算，只需返回余数即可。 大整数的乘法 例子 題意： 本題目給三個數字t,a,b(都比2147483647小)，問(t^a - 1)/(t^b -1)是大小於100位數或是否為整數，若小於100位數，就印該值。 題意範例： Sample Input 2 9 3 2 3 2 21 42 7 123 911 1 Sample Output (2^9-1)/(2^3-1) 73 (2^3-1)/(2^2-1) is not an integer with less than 100 digits. (21^42-1)/(21^7-1) 18952884496956715554550978627384117011154680106 (123^911-1)/(123^1-1) is not an integer with less than 100 digits. 例子 解法： 1）t=1 ? It’s easy to see that it’s answer isn’t a integer with less than 100 digits. 2）a=b? It’s easy to see that it’s answer is 1. 3）if(a %b != 0) ? It’s answer isn’t a integer with less than 100 digits. 証明： 令(t^a - 1)/(t^b -1) = n, n是整數，証明a%b=0 (t^a - 1)/ (t^b - 1) = t^(a-b) +t^(a-2b)+t^(a-3b)+……+t^(a-nb) 因為一定除的進(這是我們的假設)，所以a-nb = 0,∴ a%b = 0 ∵ p-q, -q--p, ∴a%b!=0,就不會是整數。 例子 令x=t^b, a/b=y, y是正整數，(t^a - 1)/(t^b -1) = (x^y-1)/