数学与程序设计.ppt

Click to edit Master title style,,Click to edit Master text styles,,Second level,,Third level,,Fourth level,,Fifth level,,,,*,数学与程序设计,引例,[,问题描述,],有一个自然数,n,，在他的首尾两端添上一个,1,，由于,1,是自然数之首，便形成一个“两头蛇数”,1N1,如果“两头蛇”数,1N1,正好是原自然数,N,的,k,倍，问,n,是多少？,,现在请你编程解决两头蛇数,程序设计中的数学,数论,,组合数学,,母函数,,计算几何,,,……,程序设计中的数学,,基本数论,,组合数学,,计算几何,,,容斥原理,,母函数,,,……,初等数论,整除,,同余,,素数,,,指数取余,输入整数,m,n,k,，求,m,n,mod k,的值其中,m,n,k,为自然数（,m,n,在长整形范围内，,k<=46340,）a≡b (mod m),,c≡d (mod m),a×c≡b×d(mod m),,次数压缩？,同余,,穷举,(m mod k),n,,,3,89,mod 7,,89=64+16+8+1,,3,1,≡3 (mod 7),,3,2,≡3,2,(mod 7)≡2 (mod 7),,3,4,≡(3,2,),2,(mod 7)≡2,2,(mod 7)≡4,,3,8,≡(3,4,),2,(mod 7)≡4,2,(mod 7)≡2,,3,16,≡(3,8,)2 (mod 7)≡2,2,(mod 7)≡4,,3,32,≡(3,16,)2 (mod 7)≡4,2,(mod 7)≡2,,3,64,≡(3,32,)2 (mod 7)≡2,2,(mod 7)≡4,,3,89,≡(3,64,)×(3,16,)×(3,8,)×(3,1,) (mod 7) ≡5 (mod 7),,,质多项式,给定多项式,f(x)=a,n,*x,n,,＋,a,n-1,*x,n-1,＋,...,＋,a,0,*x,0,，如果,a,n,0 ,,我们称,f(x),是一个,n,次多项式。

类似自然数里质数的概念，也可以给出“质多项式,”,概念给定多项式,f(x),，如果找不到次数至少为,1,的多项式,g(x),和,h(x),满足,f(x)=g(x) * h(x),，我们称,f(x),为质多项式 为了简化起见，我们规定多项式的系数只能取两个数：,0,或,1,并且重新定义在,[0,1],上的加法和乘法如下：,0+0,＝,0  0+1,＝,1  1+0,＝,1  1+1,＝,0 0*0,＝,0  0*1,＝,0  1*0,＝,0  1*1,＝,1,,如：,(x,2,+x,1,)×(x,1,+1)=x,3,+x,2,+x,2,+x,1,=x,3,+x,1,,,对于给定的正整数,k,，求出次数为,k,的质多项式如：输入,1,输出,x+1,,输入,5,输出,x^5+x^2+1,质多项式解题思路,寻找质数,+,穷举,,穷举,k,次的多项式，检验能否被已经找到的质多项式整除，若不能则本身也是质多项式多项式除法 *,,0+0,＝,0  0+1,＝,1  1+0,＝,1  1+1,＝,0 0*0,＝,0  0*1,＝,0  1*0,＝,0  1*1,＝,1,,加法：,XOR,乘法：正常,,减法：,XOR,除法：正常,x,3,+x,、,x+1,、,x,2,+x,程序设计中的数学,,基本数论,,,组合数学,,计算几何,,,容斥原理,,母函数,,,……,平行四边形的个数,把三角形,ABC,的三边各,n,等分，过各等分点作各边的平行线，将三角形,ABC,分割成一些小平行四边形，计算这些小平行四边形的个数。

就一类平行四边形进行讨论,,方程的解,已知方程,,x,1,+x,2,+x,3,+……+x,m,=n,,其中,x,1,>=a,1,,x,2,>=a,2,,…,x,m,>=a,m,且,,,求方程的非负整数解的组数,令,x,1,’=,,x,1,-a,1,, x,2,’=x,2,-a,2,,…, x,m,’= x,m,-a,m,,x,1,’ + x,2,’ +…+ x,m,’= P,程序设计中的数学,基本数论,,组合数学,,计算几何,,,容斥原理,,母函数,,,……,蜂族的旅行,和其他昆虫不同，为了不至于迷路，蜜蜂在蜂巢（紧密连接的正六边形）中行走必须遵守一定的路线把一个正方形的中心看作原点如果一只蜜蜂要从,A(x1,y1),点飞到,B(x2,y2),点，且,AB,不在同一六边形的话，那么它必须按照蜂族的飞行规则，首先飞到包含,A,点的正六边形的中心，然后每次都只能从一个正六边形的中心飞到和它相邻的六边形中心，直到它飞到包含,B,点的正六边形的中心为止，然后再飞往,B,点知道正六边形的边长,d,与,A,、,B,点的坐标，算出蜜蜂的飞行距离A,、,B,都不会刚好落在某个六边形的边上）样例,,1.0 -3.2 2.2 3.3 0,,7.737,蜂族的旅行,A,、,B,在同一六边形，直接计算直线距离,,如何判断两点在同一正六边形？,,,确定所在的六边形并计算到顶点的距离,从,A,B,经过的六边形个数,程序设计中的数学,基本数论,,组合数学,,计算几何,,,容斥原理,,母函数,,,……,,小虫问题,在一个,7*7,的方格中，每个小方格内都有一条小虫，约定在同一个时刻方格中的小虫必须向周围（上下左右,4,个方向）爬一格。

证明：在爬了一格之后，至少有一个小方格是空的被绘坏的玉米地,“哈姆，外星人又在那了！”埃塞和哈姆他们的玉米地是长方形的每年在丰收之前，他们的玉米地都会很奇怪的遭到毁坏,(,据埃塞说是外星人干的,),所有破坏的地方都是以,1,米为半径的圆,哈姆发现，如果玉米地上建立一个适当的直角坐标系的话，那些,圆心的坐标将都为整数,万幸的是，埃塞和哈姆有玉米保险，但必须把损坏的面积统计出来程序设计中的数学,基本数论,,组合数学,,计算几何,,,容斥原理,,,★母函数,,,,……,质数分解问题,任何大于,1,的自然数,n,，都可以写成若干个大于等于,2,，且小于等于,n,的质数之和表达式,(,包括只有一个数构成的和表达式的情况,),，并且可能有不止一种质数和的形式例如,9,的质数和表达式就有四种本质不同的形式：,9 = 2+2+5 = 2+2+2+3 = 3+3+3 = 2+7,自然数,n (2

F(x)=a,0,x,0,+a,1,x,1,+…+a,n,x,n,+…,普通型母函数,设从,n,元集合,S={a,0,,a,1,,…,a,n,},中取个元素的组合为,b,k,，若限定元素,a,i,出现的次数不超过,m,i,，则该组合数系列的母函数为：,,,砝码称重,有重量为,1,，,3,，,5,克的砝码各两个，问,,（,1,）可以称出多少种不同重量的物品？,,,（,2,）若要称出重量为,7,克的物品，所使用的砝码有多少种本质不同的情况？,G(x)=(1+x+x,2,)(1+x,3,+x,6,)(1+x,5,+x,10,),,=1+x+x,2,+x,3,+x,4,+2x,5,+2x,6,+2x,7,+2x,8,+x,9,+2x,10,+2x,11,+2x,12,+2x,13,+x,14,+x,15,+x,16,+x,17,+x,18,（,1,）,19,（,2,）,2,。