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