大数运算及排列组合PPT课件

大整数运算,由于编程语言提供的基本数值数据类型表示的数值范围有限，不能满足较大规模的高精度数值计算，因此需要利用其他方法实现高精度数值的计算，于是产生了大数运算。,1,-,思路：但凡大数运算思路一致，都是用数组存，然后处理进位,2,-,1.大数存储的实现,作为实现大数存储最常见的一类方法是利用数组。将一个有n位的大数存入数组,每个数组的一个元素表示一位十进制数,若是n没有超过普通PC机允许的定义范围,这种算法是简单易行的。如果出现超大数,则可以采用万进制的方法加以存储,在此就不多做介绍了。,3,-,2.大数计算的算法,2.1大数加法大数加法运算实现算法如下:(1)将数组A、B按位对齐;（数组一般都是先从低位开始存放）(2)低位开始逐位相加;(3)对结果做进位调整。,4,-,5,-,2.2大数减法,大数减法运算实现算法如下:(1)将A、B按位对齐;(2)低位开始逐位相减;(3)对结果做借位调整。,6,-,2.3大数乘法,大数乘法运算实现算法如下:(1)通过每一层循环,实现乘法的加法化;(2)对结果做进位调整。思路：乘法比加法稍微复杂一些，进位多，先计算后统一处理进位的方法比较好.总结：大数乘法是二重循环，先乘，后统一进位.,7,-,8,-,2.4大数除法,解题思路基本的思想是反复做减法，看看从被除数里最多能减去多少个除数，商就是多少。一个一个减显然太慢，如何减得更快一些呢？以7546除以23为例来看一下：开始商为0。先减去23的100倍，就是2300，发现够减3次，余下646。于是商的值就增加300。然后用646减去230，发现够减2次，余下186，于是商的值增加20。最后用186减去23，够减8次，因此最终商就是328。所以本题的核心是要写一个大整数的减法函数，然后反复调用该函数进行减法操作。计算除数的10倍、100倍的时候，不用做乘法，直接在除数后面补0即可。,9,-,2.5大数取模,在取模运算中用到了上面的除法运算,只需返回余数即可。,10,-,排列组合,11,-,排列的定义及其计算公式,排列有两种定义，但计算方法只有一种，凡是符合这两种定义的都用这种方法计算。定义的前提条件是mn，m与n均为自然数。从n个不同元素中，任取m个元素按照一定的顺序排成一列，叫做从n个不同元素中取出m个元素的一个排列。从n个不同元素中，取出m个元素的所有排列的个数，叫做从n个不同元素中取出m个元素的排列数。用具体的例子来理解上面的定义：4种颜色按不同颜色，进行排列，有多少种排列方法，如果是6种颜色呢。从6种颜色中取出4种进行排列呢。排列用符号A(n,m)表示，mn。计算公式是：A(n,m)n(n-1)(n-2)(n-m+1)n!/(n-m)!此外规定0!=1，n!表示n(n-1)(n-2)1,12,-,组合的定义及其计算公式,组合的定义有两种。定义的前提条件是mn。从n个不同元素中，任取m个元素并成一组，叫做从n个不同元素中取出m个元素的一个组合。从n个不同元素中，取出m个元素的所有组合的个数，叫做从n个不同元素中取出m个元素的组合数。用例子来理解定义：从4种颜色中，取出2种颜色，能形成多少种组合。组合用符号C(n,m)表示，mn。公式是：C(n,m)=A(n,m)/m!或C(n,m)=C(n,n-m)。,13,-,基本公式整理,只要记住下面公式，就会计算排列组合：(在列式中n为下标,m为上标)排列A(n,m)n(n-1)(n-2)(n-m+1)n!/(n-m)!组合C(n,m)=A(n,m)/A(m,m)=A(n,m)/m!C(n,m)=C(