【数学】大数组合数学算法-ACM复习进程.ppt

《【数学】大数组合数学算法-ACM复习进程.ppt》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、大数运算与组合数学－－ACM国际大学生程序设计竞赛主讲：王树林問題當有一個很大的整數要運算時,如何算?例如:一個一佰位數的數字.int最大只能到232約十個位數的十進位數字.最簡單的方法先看大數加法.就是改成手動去算加法,而不是由電腦算.123456789123+234123467890------------------------------------寫成電腦程式方法一:使用陣列(array)例如:inta[100],b[100],sum[100];然後sum[i]=a[i]+b[i]+c記住,c是進位(carry),這邊我們要自行處理.那輸入呢?輸入成字串再把字串分解成陣列中各

2、個元素.需要一個parse字串的副程式.voidparse(char*s,int*a){inti,j;j=strlen(s);for(i=0;i=10){sum[i]=sum[i]-10;c=1;}else{c=0;}}}改進array改成byte的元素.(省空間)更省?一個元素就可以到255,256才進位.用bool用linklist方式(可以讓輸入的數字更

3、大)其他?減法?乘法?除法?同樣的原理.大數運算现将一些关键算法的实现方法描述如下：大数的一些简单计算的算法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、，并完成借位；(4)高位开始逐位计算商(5)整理商,产生余数;5、大数取模运算的算法实现在取模运算中用到了上面的除法运算，只需返回余数即可。大整数的乘法ACDBX=Y=例子題意：本題目給三個數字t,a,b(都比2147483647小)，問(t^a-1)/(t^b-1)是大小於100位數或是否為整數，若小於100位數，就印該值。題意範例：SampleInput293232214271239111SampleOutput(2^9-1)/(2^3-1)73(2^3-1)/(2^2-1)isnotanintegerwithlessthan100digits.(21^42-1)/(21^7-1)

5、18952884496956715554550978627384117011154680106(123^911-1)/(123^1-1)isnotanintegerwithlessthan100digits.例子解法：1）t=1It’seasytoseethatit’sanswerisn’taintegerwithlessthan100digits.2）a=bIt’seasytoseethatit’sansweris1.3）if(a%b!=0)It’sanswerisn’taintegerwithlessthan100digits.証明：令(t^a-1)/(t^b-1)=n,n是

6、整數，証明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)/(x-1)(x^y-1)/(x-1)=x^(y-1)+x^(y-2)+x^(y-3)+….+x^0∵x^(y-1)>x^(y-2)+x^(y-3)+….+x^0∴x^(y-1)加上x^(y-2)+x^(y-3)+….+x^0最多進一位數。Log10(x^(

7、y-1))=log10(t^(a-b))=(a-b)*log10(t)∴if((a-b)*log10(t)>=99),就一定會大於100位數若沒有大於100位數，有可能等於100位數，所以要算出來。5、(x^y-1)/(x-1)=x^(y-1)+x^(y-2)+x^(y-3)+….+x^0將這個值算出來.例子討論：這題目一定要先判斷位數，如果大於100位就不用算了，不然會超過時間，且要用比較好的方法算真正的值，若用大數除法，會太慢，所以改成(x