信息学之数学基础(38页).doc

《信息学之数学基础(38页).doc》由会员分享，可在线阅读，更多相关《信息学之数学基础(38页).doc（37页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。

1、-信息学之数学基础-第 37 页第一章 有关数论的算法1.1 最大公约数与最小公倍数1.2 有关素数的算法1.3 方程的整数解及应用1.4 求ab n1.算法1: 欧几里德算法求a，b的最大公约数 (); 0 ( b);2.算法2:最小公倍数*b ();3.算法3:扩展的欧几里德算法，求出()和满足()的整数x和y ( ); 0 ; 1; 0;( );(a b)*y;（理论依据：()1+(a b)y11+(a b)*b)y11(x1-(a b)*y1)1. 2有关素数的算法1.算法4:求前n个素数: ;1000;1 ; (); ; 1 (pi) x pi=0 ; ; ; ; ; ; ;0;1;

2、(n) (x); (x) (); p; ; ; ; 1 n (pi:5)1; t 10=0 ;(n);2.算法5:求不大于n的所有素数 3; 10000;1 ;(n); 1 n ai;a10;2; in 2*i; k ak0; ; ;1; (ai=0) (in) 1;0; 1 n ai0 (ai:5); 1; k 10 =0 ; .3.算法6:将整数分解质因数的积 ;1000;1 ; ; ;(),0);(p),0);0;1;(n1) (x); n 0 (); p; (n 0) x; (); ; ; ; ; 1 1 i (pi:5);.1.算法7：求方程的整数解 ( x00); ;(); c d

3、0 ( ); ; x0*(c d); y0*(c d); 例1：有三个分别装有a升水、b升水和c升水的量筒(a，b)1，cba0),现c筒装满水，问能否在c筒个量出d升水(cd0)。若能，请列出一种方案。算法分析：量水过程实际上就是倒来倒去，每次倒的时候总有如下几个持点：1.总有一个筒中的水没有变动；2不是一个筒被倒满就是另一个筒被倒光；3c筒仅起中转作用，而本身容积除了必须足够装下a简和b简的全部水外，别无其 它限制。 程序如下: ;0.1 ; ( ); ; 0 10; ( ); (a b)*y ; ( x00); ;(); c d0 ( ); ; x0*(c d); y0*(c d); (

4、 ); ; a10 a1=0 () b10 () (); (); (:5,:1:51:51:5); c1 b1=0 () a10 () (); (); (:5,:1:51:51:5); c1;.1.4 求ab n 1.算法8:直接叠代法求ab n f(): ; 2 b n*a; n; 2.算法9:加速叠代法 f(); 1; b0 1 b 2 =1 *t n; 2; *t n; 练习： 1.熟记并默写以上算法.第三章 排列与组合3.1 加法原理与乘法原理3.2 排列与组合概念与计算公式3.3 排列与组合的产生算法1.加法原理： 做一件事情，完成它可以有n类办法，在第一类办法中有m1 种不同的方法

5、，在第二类办法中有 m2种不同的方法，在第n类办法中有 种不同的方法。那么完成这件事共有 m12 种不同的方法。 2.乘法原理： 做一件事情，完成它需要分成n个步骤，做第一步有m1 种不同的方法，做第二步有 m2种不同的方法，做第n步有 种不同的方法，那么完成这件事有 1*m2*.* 种不同的方法。 3.两个原理的区别：一个与分类有关，一个与分步有关；加法原理是“分类完成”，乘法原理是“分步完成”。 练习： 1.由数字1，2，3，4，5可以组成多少个三位数（各位上的数字允许重复）？ 2.由数字0、1，2，3，4，5可以组成多少个三位数（各位上的数字允许重复）？ 3.由数字0，1，2，3，4，5

6、可以组成多少个十位数字大于个位数字的两位数？ 例 4. 一个三位密码锁,各位上数字由0,1,2,3,4,5,6,7,8,9十个数字组成,可以设置多少种三位数的密码(各位上的数字允许重复)？首位数字不为0的密码数是多少种？首位数字是0的密码数又是多少种？ 5.如图，要给地图A、B、C、D四个区域分别涂上3种不同颜色中的某一种，允许同一种颜色使用多次，但相邻区域必须涂不同的颜色，不同的涂色方案有多少种？ 6.某班有22名女生，23名男生. 选一位学生代表班级去领奖，有几种不同选法？ 选出男学生与女学生各一名去参加智力竞赛，有几种不同的选法？ 7.105有多少个约数？并将这些约数写出来. 8.从5幅

7、不同的国画、2幅不同的油画、7幅不同的水彩画中选不同画种的两幅画布置房间，有几种选法？ 9.若x、y可以取1，2，3，4，5中的任一个，则点()的不同个数有多少？ 10.一个口袋内装有5个小球另一个口袋内装有4个小球，所有这些小球的颜色各不相同 从两个口袋内任取一个小球，有 种不同的取法； 11.从两个口袋内各取一个小球，有 种不同的取法. 12.乘积（a123）(b1234)(c12345)展开共有 个项。 13. 种不同的安排方法。 (答案:125；180；15；1000，900，100；6；45，506；8；59；25；9；20；60；625） 3. 2 排列与组合的概念与计算公式 1排

8、列及计算公式 从n个不同元素中，任取m(mn)个元素按照一定的顺序排成一列，叫做从n个不同元素中取出m个元素的一个排列；从n个不同元素中取出m(mn)个元素的所有排列的个数，叫做从n个不同元素中取出m个元素的排列数，用符号 p()表示. p()(1)(2)(1)= ()!(规定01). 2组合及计算公式 从n个不同元素中，任取m(mn)个元素并成一组，叫做从n个不同元素中取出m个元素的一个组合；从n个不同元素中取出m(m c() 表示. c()()()!*m!)；c()(); 其他排列与组合公式 从n个元素中取出r个元素的循环排列数p()()!. n个元素被分成k类，每类的个数分别是n12这n

9、个元素的全排列数为 (n1!*n2!*.*!). k类元素,每类的个数无限,从中取出m个元素的组合数为c(1). 练习： 1（1）用0，1，2，3，4组合多少无重复数字的四位数？（96） （2）这四位数中能被4整除的数有多少个？（30） （3）这四位数中能被3整除的数有多少个？（36） 2用0，1，2，3，4五个数字组成无重复数字的五位数从小到大依次排列. （1） 第49个数是多少？（30124） （2） 23140是第几个数？（40） 求下列不同的排法种数：（1） 6男女排成一排，2女相邻；(p(7,7)*p(2,2)（2） 6男女排成一排，2女不能相邻；(p(6,6)*p(7,2)（3）

10、5男3女排成一排，3女都不能相邻;(p(5.5)*p(6,3)（4） 4男4女排成一排，同性者相邻；(p(4,4)*p(4,4)*p(2,2)（5） 4男4女排成一排，同性者不能相邻。(p(4,4)*p(4,4)*p(2,2)有四位医生、六位护士、五所学校。(1) 若要选派三位医生到五所学校之中的三所学校举办健康教育讲座，每所学校去一位医生有多少种不同的选派方法？(c(5,3)*p(4,3)(2) 在医生或护士中任选五人，派到五所学校进行健康情况调查，每校去且仅去一人，有多少种不同的选派方法？(p(10,5)(3) 组成三个体检小组，每组一名医生、两名护士，到五所学校中的三所学校为老师体检，有

11、多少种不同的选派方法？(c(5,3)*p(4,3)*c(6,2)*c(4,2)*c(2,2)平面上有三条平行直线，每条直线上分别有7，5，6个点，且不同直线上三个点都不在同一条直线上。问用这些点为顶点，能组成多少个不同四边形？(2250) 平面上有三条平行直线，每条直线上分别有7，5，6个点，且不同直线上三个点都不在同一条直线上。问用这些点为顶点，能组成多少个不同三角形？(751) 将N个红球和M个黄球排成一行。例如22可得到以下6种排法:红红黄黄 红黄红黄 红黄黄红 黄红红黄 黄红黄红 黄黄红红问题:当43时有多少种不同排法?(不用列出每种排法)(35)8.用20个不同颜色的念珠穿成一条项链

12、,能做多少个不同的项链.(2020)9在单词 中字母的排列数是(11(1!*4!*4!*2!)10求取自1,2的长为r的非减序列的个数为(c(1)1排列的产生方法：（递归，深度优先产生）程序如下： ; 4; 1 ; 1 ; ; ; 1 m (ai); (); ; 1 m bi a; bi; (1); bi; ;(b);(1);.方法根据上一个排列产生下一个排列程序如下： ; 5; 1 ; ; ; 1 m (ai); 1 m ai;1; (i0) (aia1) 1; i0 ; ajai 1; iijj; 1; k0) (ai() (i); i0 aii+1; 1 m aj1+1; ; 0;.练习

13、：已知n（1=20）个整数x12,（1=5000000），以及一个整数k（k0 则相对坐标原点,点p1在点p2的顺时针方向 若m0 则相对p0点,点p1在点p2的顺时针方向 若m0 则p1点向左拐 若mb ; (); a(p34) (p34)(p12) (p12)(p34) (p3, p4)(p12) (m(p231)*m(p241)0) (m(p413)*m(p423)0) (0) (p10)(p10) (p20)(p20) ; (); ; 11) (i1) (i1); (i) ; (1); ; (i) (j); (j) (j); i; (); (1); ; ; ;(f,);(f);();

14、0 1 (ii); (i0) (i0) (i=0 (); (); s; ; 1 (si:7:2,si:7:2,); ;.练习:1.巳知:平面上有n个点(n=2)12 前n项的和0122-1 例9:以下是的示例: 1.楼梯有n阶台阶,上楼可以一步上1阶,也可以一步上2阶,编一程序计算共有多少种不同的走法? 2.有一对雌雄兔,每两个月就繁殖雌雄各一对兔子.问n个月后共有多少对兔子? 3.有n*2的一个长方形方格,用一个1*2的骨牌铺满方格。求铺法总数？ 4.错位排列 首先看例题：例10：在书架上放有编号为1,2的n本书。现将n本书全部取下然后再放回去,当放回去时要求每本书都不能放在原来的位置上。例

15、如3时:原来位置为:123放回去时只能为:312或231这两种问题:求当5时满足以上条件的放法共有多少种?(不用列出每种放法) (44)1，2，3，错位排列是1,2,3的一个排列i1i2,使得i112233n 错位排列数列为 0,1,2,9,44,265,. 错位排列的递推公式是(1)(21)(n=3) 1+(-1)2 2，4，7，11，., 递推公式是: 1(1)/2+1 2.折线分平面的最大区域数的序列为: 2, 7, 16,29, ., 递推公式是(1)(21)+2n; 3.封闭曲线(如一般位置上的圆)分平面的最大区域数的序列为: 2, 4, 8, 14,., 递推公式是1+2(1)22

16、 6 数列 先看下面两个例题:例11:将一个凸多边形区域分成三角形区域的方法数?令表示具有1条边的凸多边形区域分成三角形的方法数。同时令h1=1，则满足递推关系11221h1(n=2)(想一想,为什么?)该递推关系的解为(221) (1,2,3,.) 其对应的序列为1,1,2,5,14,42,132,.从第二项开始分别是三边形,四边形,.的分法数 即k边形分成三角形的方法数为(242)/(1)(k=3)例12个+1和n个-1构成2n项 a122n 其部分和满足a12=0(1,2,3,.,2n)对与n该数列为 (2)/(1) (k=0) 对应的序列为 1,1,2,5,14,42,132,.序列1,1,2,5,14,42,132,.叫数列。例13：下列问题都是数列。1.有2n个人排成一行进入剧场。入场费5元。其中只有n个人有一张5元钞票，另外n人只有10元钞票，剧院无其它钞票，问有多少中方法使得只要有10元的人买票，售票处就有5元的钞票找零？2.一位大城市的律师在她住所以北n个街区和以东n个街区处工作。每天她走2n个街区去上班。如果他 从不穿越（但可以碰到）从家到办公室的对角线，那么有多少条可能的道路？3.在圆上选择2n个点,将这些点成对连接起来使得所得到的n条线段不相交的方法数?4个结点可够造多少个不同的二叉树?5.一个栈(无穷大)的进栈序列为1,2,3,有多少个不同的出栈序列?