《数学与程序设计(zy).ppt》由会员分享，可在线阅读，更多相关《数学与程序设计(zy).ppt（74页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、数数 学学 与与 程程 序序 设设 计计衡阳市八中 邹毅进制数进制数 1 1、某某个个国国家家的的钱钱币币面面值值有有1 1，7 7，7272，7373共共计计四四种种，如如果果要要用用现现金金付付清清1001510015元元的的货货物物，假假设设买买卖卖双双方方各各种种钱钱币币的的数数量量无无限限且且允允许许找找零零，那那么么交交易易过过程程中中至至少少需需要要流流通通_张张钱钱币币。（20092009年）年）信息学奥赛初赛中的部分数学题一览数学归纳法数学归纳法2 2、N N个人在操场里围成一圈，将这个人在操场里围成一圈，将这N N个人按顺时针方向从个人按顺时针方向从1 1到到N N编编号，
2、然后从第一个人起，每隔一个人让下一个人离开操场，显号，然后从第一个人起，每隔一个人让下一个人离开操场，显然，第一轮过后，具有偶数编号的人都离开了操场。依次做下然，第一轮过后，具有偶数编号的人都离开了操场。依次做下去，直到操场只剩下一个人，记这个人的编号为去，直到操场只剩下一个人，记这个人的编号为J(N)J(N)，例如，例如，J(5)=3J(5)=3，J(10)=5J(10)=5，等等。等等。（20072007年）年）排列组合排列组合3 3、将将边边长长为为 n n 的的正正三三角角形形每每边边 n n 等等分分，过过每每个个分分点点分分别别做做另另外外两两边边的的平平行行线线，得得到到若若干干
3、个个正正三三角角形形，我我们们称称为为小小三三角角形形。正正三三角角形形的的一一条条通通路路是是一一条条连连续续的的折折线线，起起点点是是最最上上面面的的一一个个小小三三角角形形，终终点点是是最最 下下面面一一行行位位于于中中间间的的小小三三角角形形。在在通通路路中中，只只允允许许由由一一个个小小三三角角形形走走到到另另一一个个与与其其有有公公共共边边的的且且位位于于同同一一行行或或下下一一行行的的小小三三角角形形，并并且且每每个个小小三三角角形形不不能能经经过过两两次次或或两两次次以以上上（图图中中是是 n=5 n=5 时时一一条条通通路路的的例例 子子）。设设 n=10n=10，则则该该正
4、三角形的不同的通路的总数为正三角形的不同的通路的总数为_。（20062006年）年）4、给给定定n个个有有标标号号的的球球，标标号号依依次次为为1，2，n。将将这这n个个球球放放入入r个个相相同同的的盒盒子子里里，不不允允许许有有空空盒盒，其其不不同同放放置置方方法法的的总总数数记记为为S(n,r)。例例如如，S(4,2)=7，这这7种种不不同同的的放放置置方方法法依依次次为为(1),(234),(2),(134),(3),(124),(4),(123),(12),(34),(13),(24),(14),(23)。当当n=7，r=4时，时，S(7,4)=。（20072007年）年）方法一：方法
5、一：S(x,y)=S(x-1,y)*y+S(x-1,y-1)S(x,y)=S(x-1,y)*y+S(x-1,y-1)方法二：方法二：C(7,1)*C(6,2)*C(4,2)*C(2,2)/P(3,3)+C(7*3)*C(4,2)+C(7,4)C(7,1)*C(6,2)*C(4,2)*C(2,2)/P(3,3)+C(7*3)*C(4,2)+C(7,4)5 5、书架上有书架上有21本书，编号从本书，编号从1 到到 21 从中选从中选4 本，其本，其中每两本的编号都不相邻的选法一共有中每两本的编号都不相邻的选法一共有_种。种。（20082008年）年）18C4.集合集合6、75名儿童到游乐场去玩。他
6、们可以骑旋转木马，坐滑行铁道，名儿童到游乐场去玩。他们可以骑旋转木马，坐滑行铁道，乘宇宙飞船。已知其中乘宇宙飞船。已知其中20人这三种东西都玩过，人这三种东西都玩过，55人至少玩过人至少玩过其中的两种。若每样乘坐一次的费用是其中的两种。若每样乘坐一次的费用是5元，游乐场总共收入元，游乐场总共收入700，可知有，可知有 名儿童没有玩过其中任何一种。名儿童没有玩过其中任何一种。（20042004年）年）图论图论7 7、已已知知a,a,b,b,c,c,d,d,e,e,f,f,g g七七个个人人中中，a a会会讲讲英英语语；b b会会讲讲英英语语和和汉汉语语；c c会会讲讲英英语语、意意大大利利语语和
7、和俄俄语语；d d会会讲讲汉汉语语和和日日语语；e e会会讲讲意意大大利利语语和和德德语语；f f会会讲讲俄俄语语、日日语语和和法法语语；g g会会讲讲德德语语和和法法语语。能能否否将将他他们们的的座座位位安安排排在在圆圆桌桌旁旁，使使得得每每个个人人都都能能与与他他身身边边的的人人交交谈谈？如如果果可可以以，请请以以“a a b b”开开头头写写出你的安排方案：出你的安排方案：。（20042004年）年）8、将数组、将数组32,74,25,53,28,43,86,47中的元素按从小到大中的元素按从小到大的顺序排列，每次可以交换任意两个元素，最少需要交换的顺序排列，每次可以交换任意两个元素，最
8、少需要交换 次。（次。（20052005年）年）9 9、拓拓扑扑排排序序是是指指将将有有向向无无环环图图G G中中的的所所有有顶顶点点排排成成一一个个线线性性序序列列，使使得得图图中中任任意意一一对对顶顶点点u u和和v v，若若 E(G)vE(G)，则则u u在在线线性性序序列列中中出出现现在在v v 之之前前，这这样样的的线线性性序序列列成成为为拓拓扑扑序序列列。如如下下的的有有向向无无环环图图，对对其其顶顶点点做做拓拓扑扑排排序序，则则所所有有可能的拓扑序列的个数为可能的拓扑序列的个数为_。（。（20092009年）年）程序设计中的数学基本数论组合数学计算几何概率母函数集合论一、数论一、
9、数论 研究整数的有关问题，如：研究整数的有关问题，如：整除整除 数的同余数的同余 素数素数 约数约数 数的进制表示数的进制表示 方程的整数解等。方程的整数解等。整除整除设设a a，b b都是非都是非0 0的整数，如果存在一个整数的整数，如果存在一个整数q q，使得使得b=aqb=aq，那么就说那么就说b b可被可被a a整除，记作整除，记作a|ba|b，且称且称b b是是a a的倍数，的倍数，a a是是b b的约数（因子）。的约数（因子）。整除的性质：整除的性质：（1 1）如果）如果a|ba|b且且b|cb|c，那么那么a|ca|c；（2 2）a|ba|b且且a|ca|c等价于对任意的整数等价
10、于对任意的整数x x，y y，有有a|(bxa|(bxcy);cy);（3 3）设设m0m0，那么那么a|ba|b等价于等价于(ma)|(mb)ma)|(mb)。几个特殊的整除的例子：几个特殊的整除的例子：（1 1）若）若2 2能整除能整除a a的最末位，则的最末位，则2|2|a a；若若4 4能整除能整除a a的最的最后两位，则后两位，则4|4|a a；（2 2）若若5 5能整除能整除a a的最末位，则的最末位，则5|5|a a；若若2525能整除能整除a a的的最后两位，则最后两位，则25|25|a a；（3 3）若若3 3能整除能整除a a的各位数字之和，则的各位数字之和，则3|3|a
11、a；若若9 9能整能整除除a a的各位数字之和，则的各位数字之和，则9|9|a a；（4 4）若若1111能整除能整除a a的偶位数字之和与奇位数字之和的的偶位数字之和与奇位数字之和的差，则差，则11|11|a a。同余同余 若若a,ba,b为为两两个个整整数数，且且它它们们的的差差a-ba-b能能被被某某个个自自然然数数m m所所整整除除，则则称称a a就模就模m m来说同余于来说同余于b b，或者说或者说a a和和b b关于模关于模m m同余。同余。记为：记为：ab(mod m)ab(mod m)它意味着：它意味着：a-b=mk(ka-b=mk(k为某一个整数为某一个整数)即即 a mod
12、 m=b mod ma mod m=b mod m 例如，例如，322(322(mod 5)mod 5)，此时此时k k为为6 6。同余的性质同余的性质 对于整数对于整数a,b,ca,b,c和自然数和自然数m,nm,n，则对模则对模m m同余满足：同余满足：1 1、同加性：若、同加性：若ab(mod m)ab(mod m)，则则a+cb+c(mod m)a+cb+c(mod m)2 2、同乘性：若同乘性：若ab(mod m)ab(mod m)，则则acbc(mod m)acbc(mod m)一般情况，一般情况，ab(mod m)ab(mod m)，cd(mod m)cd(mod m)则有：则有
13、：acbd(mod m)acbd(mod m)同余的性质同余的性质 3 3、同幂性：若、同幂性：若ab(mod m)ab(mod m)，则则a an nb bn n(mod m)(mod m)4 4、推理结论：若推理结论：若a mod p=xa mod p=x,a,a mod q=x mod q=x，p p、q q互质互质 则：则：a mod pq=xa mod pq=x 证明：因为证明：因为a mod p=x,a mod q=xa mod p=x,a mod q=x，p p、q q互质互质 则一定存在整数则一定存在整数s,ts,t，使使a=sp+xa=sp+x，a=tq+xa=tq+x 所以
14、：所以：sp=tqsp=tq 则一定存在整数则一定存在整数r r，使使s=rqs=rq 所以所以:a=rpq+xa=rpq+x 得出：得出：a mod pq=a mod pq=x x 5 5、（、（a*ba*b）mod k=(a mod k)*(b mod k)mod kmod k=(a mod k)*(b mod k)mod k但是，同余不满足同除性，即由但是，同余不满足同除性，即由ab(mod m)ab(mod m)得不到结果：得不到结果：a div nb div n(mod m)a div nb div n(mod m)例例3 3、指数取余、指数取余 键盘输入整数键盘输入整数m,n,km
15、,n,k，求求m mn n mod kmod k的值。的值。其中其中m,n,km,n,k为自然数，为自然数，m,nm,n在长整型范围内，在长整型范围内，k46340k46340。问题分析问题分析 用同余性质用同余性质3 3和性质和性质4 4来求解，比如要求来求解，比如要求3 38989 mod 7mod 7，则：则：3 31 13(3(mod 7)mod 7)3 32 2332 2(mod 7)2(mod 7)(mod 7)2(mod 7)3 34 4(3(32 2)2 2(mod 7)2(mod 7)22 2(mod 7)4(mod 7)4 3 38 8(3(34 4)2 2(mod 7)4
16、(mod 7)42 2(mod 7)2(mod 7)2 3 31616(3(38 8)2 2(mod 7)2(mod 7)22 2(mod 7)4(mod 7)4 3 33232(3(31616)2 2(mod 7)4(mod 7)42 2(mod 7)2(mod 7)2 3 36464(3(33232)2 2(mod 7)2(mod 7)22 2(mod 7)4(mod 7)4 3 38989(3(36464)(3)(31616)(3)(38 8)(3)(31 1)(mod 7)(mod 7)4423(mod 7)96(mod 7)5(mod 7)4423(mod 7)96(mod 7)5(
17、mod 7)程序实现时，首先将程序实现时，首先将n n分解成分解成2 2的幂次方，存放在一个数组的幂次方，存放在一个数组r r中，中，ri=1ri=1表示表示m mi i这一项需要做这一项需要做modmod运算。然后用递推的方法从小到大运算。然后用递推的方法从小到大逐个求出逐个求出m mi i mod k mod k 的值（的值（j j从从i i到到1 1）存放在数组）存放在数组d d中。中。begin readln(m,n,k);len:=0;n1:=n;while n10 do begin inc(len);rlen:=n1 mod 2;n1:=n1 div 2;end;d1:=m mod
18、 k;for i:=2 to len do di:=di-1*di-1 mod k;t:=1;for i:=1 to len do if ri=1 then t:=t*di mod k;writeln(t);end.素数的几个定理素数的几个定理 1、惟一分解定理、惟一分解定理 若若整整数数a2，那那么么a一一定定可可以以表表示示为为若若干干个个素素数数的的乘乘积积（惟惟一一的的形形式式），即即：a=p1p2p3ps，其其中中pj为为素素数数，称称为为a的的素素（质）因子，（质）因子，1js。例如：例如：1260=223357=223257。2、威尔逊（、威尔逊（Wilson）定理定理 若若P为
19、素数，则（为素数，则（P-1）！）！-1 （mod P）威尔逊逆定理也成立。威尔逊逆定理也成立。对正整数对正整数P，有（有（P-1）！）！-1（mod P），），则则P一定为素数一定为素数3 3、费马（、费马（FermatFermat）定理定理 若若P P为素数，为素数，a a为正整数，且为正整数，且a a和和P P互质，则：互质，则：a ap p-1-1 1 1（mod Pmod P）一般情况下，若一般情况下，若p p为质数，则：为质数，则：a ap p a a（mod Pmod P）这就是著名的这就是著名的费马小定理费马小定理。应用应用 基于费马定理的基于费马定理的Miller-Rabin
20、Miller-Rabin素数判断算法。若我们选取若素数判断算法。若我们选取若干个干个a a，都满足以上等式的话，几乎可以肯定都满足以上等式的话，几乎可以肯定p p是素数。尽管不能是素数。尽管不能完全确认，但在实际操作中是可行的。下面的程序假设要判断一完全确认，但在实际操作中是可行的。下面的程序假设要判断一个个longintlongint范围内的数是否为质数。范围内的数是否为质数。function Miller_Rabin(n:function Miller_Rabin(n:longintlongint):):booleanboolean;varvar s,i,a:s,i,a:longintlo
21、ngint;beginbegin if n=2 then exit(true);if n=2 then exit(true);for i:=1 to 10 do for i:=1 to 10 do begin begin a:=random(n-2)+2;a:=random(n-2)+2;if modular_exp(a,n-1,n)1 if modular_exp(a,n-1,n)1 then begin miller_ then begin miller_rabinrabin:=false;exit;end;:=false;exit;end;end;end;miller_ miller_r
22、abinrabin:=true;:=true;end;end;4 4、欧拉定理、欧拉定理 费马定理是用来阐述在素数模下，指数的同余性质。当模是费马定理是用来阐述在素数模下，指数的同余性质。当模是合数的时候，就要应用范围更广的欧拉定理了。合数的时候，就要应用范围更广的欧拉定理了。（1)1)欧拉函数欧拉函数 设设n n为正整数，欧拉函数为正整数，欧拉函数(n)(n)定义为不超过定义为不超过n n，且与且与n n互质的互质的正整数的个数。例如正整数的个数。例如(6)=2(6)=2。欧拉定理欧拉定理 若若a a与与m m互质，则互质，则a a(m)(m)1 (mod m)1 (mod m)例、键盘输入
23、一个整数例、键盘输入一个整数n n，输出欧拉函数输出欧拉函数(n)(n)的值的值 1 1n2 000 000 000n2 000 000 000素数（质数）素数（质数）除了除了1和本身以外，没有其它约数的大于和本身以外，没有其它约数的大于1的正整数。的正整数。例：输出n以内的素数。Program zhishu(input,output);Const maxn=1000;Var I,j,n:integer;prime:array2.maxn of integer;Begin readln(n);for I:=2 to maxn do primeI:=1;I:=2;while I*I=n do B
24、egin j:=I*2;while j=n do begin primej:=0;j:=j+I;end;I:=I+1;while primeI=0 do I:=I+1;End;For I:=2 to n do if primeI=1 then writeln(I:8);WritelnEnd.最大公约数最大公约数设a1,a2,a3,ak是k个非0整数，如果存在一个非0的整数d，使得d|a1,d|a2,d|ak，就称d为a1,a2,a3,ak的公约数。公约数中最大的一个称为最大公约数，记为GCD(a1,a2,a3,ak)。当GCD=1时，则称这n个数是互质的。最小公倍数最小公倍数设a1,a2,a3
25、,ak是k个非0整数，如果存在一个非0的整数d，使得a1|d,a2|d,ak|d，就称d为a1,a2,a3,ak的公倍数。公倍数中最小的一个称为最小公倍数，记为LCM(a1,a2,a3,ak)。最大公约数、最小公倍数的关系最大公约数、最小公倍数的关系 LCM(a,b)=a*b div GCD(a,b)例、编程求n个（n=100）正整数Ai(1=i=a1,x2=a2,xm=am 且 求方程的非负整数解的组数 令x1=x1-a1,x2=x2-a2,xm=xm-am x1+x2+xm=P平行四边形的个数把三角形ABC的三边各n等分，过各等分点作各边的平行线，将三角形ABC分割成一些平行四边形，计算这
26、些平行四边形的个数。组合数学先求不平行于底边的平行四边形的个数A同理，不平行于另外两条边的平行四边形的个数B、C都等于A，所以总的平行四边形的个数是组合数学例2：组合数的末十位输入n，r，输出C（n,r）的最后十位。其中0rn30000，输出时不足十位数也按十位输出，此时高位补0。输入：104输出：0000000210组合数学分析：1、C(n,r)一定是整数，因为连续r个自然数的积一定能被r!整除；2、本题的关键是如何避免除法，约分可以解决，具体方法是计算1到n之间的任意一个质数在C(n,r)中出现的次数。组合数学方法一：对C(n,r)式子中的分子分母上的每个数分解质因子，用一个数组T记录次数
27、，如果分子上的数分解出了一个质因子p，则Tp增加1，反之如果分母上的数分解出了质因子p，则Tp减少1，最后将每个质因子按其次数连乘即可。组合数学方法二：通过直接计算质数p在n!中的次数而得到数组T，质数p在n!中的次数为:如：n1000，p3时1000 div 3+1000 div 9+1000 div 27+1000 div 81+1000 div 243+1000 div 729333111371241498组合数学根据n div pk+1=(n div pk)div p，可以递推地求出p在n!中的次数。程序实现时，先求出1到n之间的所有质数，再对每个质数求次数，质数p在C(n,r)中的次
28、数等于“质数p在n!中的次数减去质数p在r!中的次数，再减去质数p在(n-r)!中的次数”。组合数学function f(n,p:longint):longint;var s,t:longint;begin t:=0;s:=n div p;while s0 do begin t:=t+s;s:=s div p;end;f:=t;end;组合数学方法三：利用公式C(n,r)=C(n-1,r-1)+C(n-1,r)，其实质就是求杨辉三角的第n行、第r列上的数。排列、组合及其应用方法一：生成法 生成第一个排列for i:=1 to n do ai:=i;从后向前找到一个顺序 从中找出一个比大的最小数
29、交换从小到大排序 返回排列、组合及其应用方法二：回溯法readln(n);s:=;top:=0;k:=0;while top=0 dobegink:=k+1;if knthen begink:=stacktop;s:=s-k;top:=top-1;endelse if not(k in s)then begintop:=top+1;stacktop:=k;s:=s+k;k:=0;if top=nthen 输出;end;end;排列、组合及其应用（2）选排列从m个元素中，任选n个进行排列（nm）（3）重复排列例：3个黄球，2个蓝球，4个白球，排成一排，问有多少种排法？排列、组合及其应用（4）条件
30、排列例：将1，2，3，4，5这5个数进行排列，要求4必须排在2的前面。（5）错位排列排列、组合及其应用例6、工作安排问题。工作1工作2工作3工作4工作n第1人12209113第2人1925223第3人23344321第4人2325664第n人451432312每一行表示某人对应每一项工作（列）的工作效率，要求每人选择一项工作使得总工作效率最大。排列、组合及其应用2、组合表示从m个元素中，任取n个的组合数排列、组合及其应用组合的生成方法readln(m,n);for i:=0 to n dobi:=i;输出;while b0=0 dobeginj:=n;while bj=m-n+j doj:=j
31、-1;bj:=bj+1;for i:=j+1 to n dobi:=bi-1+1;输出;end;程序设计中的数学基本数论组合数学计算几何概率母函数概率引例：先后抛两枚均匀的硬币，计算两枚都出现正面的概率。1、随机现象：某些现象，在个别试验中其结果呈现出不确定性，而在大量重复试验中其结果又具有统计规律性。几个概念：概率2、样本空间：某个试验所有可能的结果的集合。一般记为S。引例：先后抛两枚均匀的硬币，计算两枚都出现正面的概率。S正正、反反、正反、反正3、样本点：试验的每个结果。4、随机事件：S的子集，简称“事件”。概率5、事件AB称为事件A与事件B的和事件，当且仅当事件A和事件B至少有一个发生时
32、，事件AB发生。6、事件AB称为事件A与事件B的积事件，当且仅当事件A和事件B同时发生时，事件AB发生。概率7、如果在相同的条件下进行了n次试验，在这n次试验中，事件A发生了NA次，那么值NA/n称为事件A发生的“频率”。8、设S是某随机试验的样本空间，对于随机试验的每个事件A赋予一个实数P(A)，则称P(A)为事件A的“概率”。概率几个性质：（1）对于每一个事件A，0P(A)1。（2）对于不可能事件，P(A)0。而对于S，P(S)1。（3）对于任意的两个事件A和B，有：P(AB)P(A)P(B)P(AB)。概率1、等可能事件的概率试验中每个样本事件发生的可能性相同。如果样本空间中的基本事件总
33、数是n，而事件A包含的基本事件数为m，那么事件A的概率为：P(A)m/n。概率例1：先后抛两枚均匀的硬币，计算两枚都出现正面的概率和一枚出现正面、一枚出现反面的概率。S正正、反反、正反、反正两枚都出现正面的概率为1/4一枚出现正面、一枚出现反面的概率为1/2概率例2：在100件产品中，有95件合格品，5件次品，从中任取两件，计算：（1）两件都是合格品的概率。（2）两件都是次品的概率。（3）一件是合格品、一件是次品的概率。概率2、互斥事件有一个发生的概率如果事件A和B互斥，即它们不可能同时发生，则P(AB)0、P(AB)P(A)+P(B)，即事件AB（A和B中有一个发生）的概率，等于事件A和事件
34、B分别发生的概率之和。概率例3：现在有40支笔，其中有30支黑色的、10支红色的。从中任意取出4支，问：其中至少有1支红色笔的概率是多少？设4支中恰有1支、2支、3支、4支红笔的事件分别为A、B、C、D，则：P(A)P(B)P(C)P(D)事件A、B、C、D两两互斥，所以P(ABCD)P(A)P(B)P(C)P(D)概率3、相互独立事件同时发生的概率如果事件A是否对事件B发生的概率没有影响，同时事件B是否发生对事件A发生的概率也没有影响，则称A与B是相互独立的事件。此时有P(AB)P(A)P(B)，即两个相互独立事件同时发生的概率等于每个事件发生的概率的积。概率例4：如果有甲、乙两个篮球运动员，他们的罚球命中率分别是60%和50%，现在两人各罚球一次，正常情况下，计算：（1）两人都命中的概率。（2）只有1人命中的概率。（3）至少有1人命中的概率。上面两项的和概率例5：弹子球游戏有一个小球从正上方落下，往左下和往右下滑落的概率都是50%。计算小球落到下面各个出口的可能性有多少？