《大数运算与组合数学.ppt》由会员分享，可在线阅读，更多相关《大数运算与组合数学.ppt（84页珍藏版）》请在三一办公上搜索。
1、大数运算与组合数学,ACM国际大学生程序设计竞赛,問題,當有一個很大的整數要運算時,如何算?例如:一個一佰位數的數字.int 最大只能到 232 約十個位數的十進位數字.,最簡單的方法,先看大數加法.就是改成手動去算加法,而不是由電腦算.123456789123+234123467890-,寫成電腦程式,方法一:使用陣列(array)例如:int a100,b100,sum100;然後 sumi=ai+bi+c記住,c 是進位(carry),這邊我們要自行處理.,那輸入呢?,輸入成字串再把字串分解成陣列中各個元素.需要一個parse字串的副程式.,void parse(char*s,int*a
2、)int i,j;j=strlen(s);for(i=0;i=10)sumi=sumi-10;c=1;else c=0;,改進,array 改成 byte的元素.(省空間)更省?一個元素就可以到255,256才進位.用bool用link list 方式(可以讓輸入的數字更大)其他?,減法?乘法?除法?,同樣的原理.,大數運算,现将一些关键算法的实现方法描述如下：大数的一些简单计算的算法1、大数加法运算的实现算法(1)将A、B按位对齐；(2)低位开始逐位相加；(3)对结果做进位调整；2、大数减法运算实现算法(1)将A、B按位对齐；(2)低位开始逐位相减；(3)对结果做借位调整；,大數運算,3、大
3、数乘法运算实现算法(1)引入sum2、sum1中间过渡量；(2)在n的每一位上处理m；(3)通过每一层循环，实现乘法的加法化；(4)对结果做进位调整；4、大数除法运算的算法实现(1)引入al来标识a的长度,bl来标识b的长度；(2)测算a和b的长度；(3)高位开始，对位做减法，并完成借位；(4)高位开始逐位计算商(5)整理商,产生余数;5、大数取模运算的算法实现 在取模运算中用到了上面的除法运算，只需返回余数即可。,大整数的乘法,A,C,D,B,X=,Y=,例子,題意：本題目給三個數字t,a,b(都比2147483647小)，問(ta-1)/(tb-1)是大小於100位數或是否為整數，若小於1
4、00位數，就印該值。題意範例：Sample Input2 9 32 3 221 42 7123 911 1Sample Output(29-1)/(23-1)73(23-1)/(22-1)is not an integer with less than 100 digits.(2142-1)/(217-1)18952884496956715554550978627384117011154680106(123911-1)/(1231-1)is not an integer with less than 100 digits.,例子,解法：1）t=1 Its easy to see that it
5、s answer isnt a integer with less than 100 digits.2）a=b Its easy to see that its answer is 1.3）if(a%b!=0)Its answer isnt a integer with less than 100 digits.証明：令(ta-1)/(tb-1)=n,n是整數，証明a%b=0(ta-1)/(tb-1)=t(a-b)+t(a-2b)+t(a-3b)+t(a-nb)因為一定除的進(這是我們的假設)，所以a-nb=0,a%b=0 p-q,-q-p,a%b!=0,就不會是整數。,例子,令x=tb,a/
6、b=y,y是正整數，(ta-1)/(tb-1)=(xy-1)/(x-1)(xy-1)/(x-1)=x(y-1)+x(y-2)+x(y-3)+.+x0 x(y-1)x(y-2)+x(y-3)+.+x0 x(y-1)加上 x(y-2)+x(y-3)+.+x0 最多進一位數。Log10(x(y-1)=log10(t(a-b)=(a-b)*log10(t)if(a-b)*log10(t)=99),就一定會大於100位數若沒有大於100位數，有可能等於100位數，所以要算出來。5、(xy-1)/(x-1)=x(y-1)+x(y-2)+x(y-3)+.+x0 將這個值算出來.,例子,討論：這題目一定要先判
7、斷位數，如果大於100位就不用算了，不然會超過時間，且要用比較好的方法算真正的值，若用大數除法，會太慢，所以改成(xy-1)/(x-1)=x(y-1)+x(y-2)+x(y-3)+.+x0，這樣的方式來算，比較快!,随机产生一个200位的数,int random(int p201)/随机产生一个200位的数p1=1;/低位1为保证该素数为奇数int i;for(i=2;i=200;i+)pi=rand()*10/RAND_MAX;while(p200=0)/高位不能为0，保证素数达到要求的长度p200=rand()*10/RAND_MAX;return 0;,乘法运算,int multiply
8、(int m101,int n201,int product301)/两因子m、n，乘积productint sum1102,sum2102,i,j,k,s;/sum2、sum1中间过渡量for(i=1;i=101;i+)sum2i=0;/sum2所有位置零for(j=1;j201;j+)/在n的每一位上处理m for(i=1;i=101;i+)sum1i=0;/sum1所有位置零for(i=1;i=nj;i+)/通过每一层循环，实现乘法的加法化 for(s=1;s101;s+)sum2s=ms+sum1s;for(k=1;k=101;k+)sum1k=sum2k;for(k=j;k=100+
9、j;k+)productk=sum2k-j+1+productk;/即是实现了乘法过程中的加法for(i=1;i301;i+)/进位处理j=producti/10;producti+1+=j;producti-=j*10;return 0;,比较两个数的大小,int cmp(int a301,int ab,int b201,int bb)/比较两个数的大小int i,result;result=0;/a=b;for(i=300;i ab;i-)if(ai!=0)return 1;for(i=0;i bbb-i)result=1;/a b;break;if(aab-i bbb-i)result=
10、-1;/a b;break;return result;,除法运算,void division(int a301,int b201,int c301,int d201)/除法函数，300位除200位,c为商，d为余数int al,bl,t301;/al用来标识a的长度,bl用来标识b的长度int i,j,al2;for(i=0;i 0;i-)/测算a的长度if(ai!=0)al=i;break;for(i=200;i 0;i-)/测算b的长度if(bi!=0)bl=i;break;,除法运算（续）,al2=al;for(i=0;i al-bl+1;i+)/高位开始while(cmp(t,al2
11、,b,bl)!=-1)/比较a、b首位大小for(j=0;j bl;j+)tal2-j-=bbl-j;/对位做减法for(j=1;j 301;j+)if(tj 0)/完成借位 tj+=10;tj+1-;cal-bl+1-i+;/高位开始逐位计算商al2-;for(i=0;i 201;i+)di=ti;/产生余数,组合数学研究对象,组合数学研究的主要内容是依据一定的规则来安排某些事务的有关数学问题。这些问题包括四个方面：1。这种安排是否存在，即存在性问题；2。如果符合要求的安排是存在的，那么这样的安排又有多少，即计数问题；3。怎样构造这种安排，即算法构造问题；4。如果给出了最优化标准，又怎样得到
12、得到最优安排。,1。存在性问题,实际生活中的各种问题，有些可以当机立断判定其有解还是无解。但也有不少问题一时难以判定。例如，宴会上，奇数位客人能否在晚会上与他人握手奇数次。竞赛时不可能出现专门判定某个问题有解或无解的试题。但往往会在测试数据中加入无解的数据。,2。计数问题,如果一个组合问题的解是存在的，自然会问有多少不同的解。例如，将8个“车”放在88的国际象棋棋盘上，如果他们两两不能互吃，那么称8个“车”处于一个安全状态。显然这种安全状态是存在的。问有多少种不同的安全状态。这就是一个计数问题。信息学竞赛中一般分为两种类型：一种是计算某种特性的对象有多少；另一种是枚举类型，把所有具有某种特性的
13、对象都列举出来。,3。构造性算法,一个组合问题，已经判定解是存在的，甚至已经推知有多少解，但关键还在于把解构造出来，有的哪怕出一个解也好。如魔方问题，正交拉丁问题。,4。优化问题,一个问题的构造性算法可能不止一种，自然面临如何择优，如何改进，使得答案尽快地解出来。比如动态规划和线性规划问题的解决方法。,组合问题的基本解题方法,1 从组合学基本概念基本原理出发的常规方法 容斥原理 Polya原理 鸽笼原理 递归方法 生成函数方法,2 通常与问题所涉及的组合数学概念无关的非常规方法。主要用于解那些需要独立思考见解独到和有所创新的问题。数学归纳法 证明n个元素的集合，其子集恰为2n个 一一对应技术
14、将一个问题转化为另一种有常规算法的问题模式。例如，8“车”问题有多少个不同的安全状态。8个车处于安全状态当且仅当它们处于不同的8行和8列上。用一个排列a1，a2，a8，对应于一个安全状态，使ai表示第i行的ai列上放置一个车。这种对应显然是一对一的。因此，安全状态的总数等于这8个数的全排列的总数8！=40320。,3 殊途同归方法,从不同的角度讨论计数问题，以建立组合等式 例如，对没有三条对角线交于一点的凸多边形，计算各边及对角线所组成的互不重叠的区域个数。区域总数为C（n，4）C（n1，2）,各区域顶点总数（包括重复计数）角度1：,角度2：所有区域的内角和的总和的等式两边同除以180度得两式
15、相减得区域总数,4 数论方法,运用奇偶性，整除性等数论性质进行存在性问题的分析与推理。例子：设n位客人，在晚会上每人与他人握手d次，d是奇数，证明n是偶数。,回溯方法,需要用计算机求解的组合试题一般有两种类型：1。能够用简明正确的组合公式揭示问题。2。不能对给定问题建立数学模型或虽然有数学模型但运用该数学模型求解有困难。在求解枚举类型问题时，会遇到此类问题。回溯方法是一种常用的解题策略。,N皇后问题,例子，一个nn的国际象棋棋盘上放置n个皇后，使其不能相互攻击，即任何两个皇后都不能处在棋盘的同一行同一列同一条斜线上，试问有多少中摆法？一 如何求n皇后问题 1 状态（state）状态是指问题求解
16、过程中每一步的状况。n皇后问题中，某行皇后所在列位置i即为该皇后问题的一个状态。,2 算符（operator）算符是把问题的一个状态变换到另一个状态的方法代号。n皇后的一种摆法对应n个元素的排列方案（a1，a2，,an）必须满足条件：不产生对角线攻击和列攻击。3。结点（node）用以表明某状态特征及关联方式的基本信息单元。结点的数据结构一般为记录类型。Type node=record operator:算符类型；state：状态类型；end;Var stack：array1。maxdepth of node；节点数不超过maxdepth的一条路径orVar stack:array1.20 of
17、 integer;,当n4时，初始状态：空棋盘，试放的顺序是从左至右，自上而下（）,求解n皇后问题，无非就是做两件事：1。从左至右逐条树枝地构造和检查解答树t；2。检查t的节点是否对应问题的目标状态。为了加快检查速度，一般规定：1。在扩展一个分支节点前进行检查，如果它不满足约束条件，则不再构造以它为根节点的子树；2。已处理过的节点若以后不会再用，则不必保留，即回溯过程中经过的节点不再保留。,栈重要的数据结构,递归过程make（L）1 分配一个连续的数组区域stack1.maxdepth顺序存放栈中表目，即当前路径的节点。2 栈顶指针L作递归程序make的值参数，指出待扩展节点在当前路径序列st
18、ack中的顺序，算符作make过程的局部变量。,算法框架,Program searchVar stack:array1.maxdepth of node;.Procedure make(L:integer);Var Begin make(L+1);End;makeBegin make(1);End;,作为练习,一个售货亭前排着2N个人的队伍等候购物，假定他们都购买价值5元的同一货物。其中N个人持5元货币，N个人持10元货币，而售货员开始发售货物时没有零钱。问有多少种排队方式可使售货员能依次顺利地出售货物，而不出现找不出钱的局面。,从鸽笼原理到Ramsey理论,1 鸽笼原理：n1只鸽子飞回n鸽笼
19、子至少一个鸽笼含有不少于2只鸽子。数学描述：m（m=1）个元素分成n个组，那么总有一个组至少含有元素个数为m/n。上取整。例子：13个人的小组至少有13/12=2人生日在同一个月。,2 Ramsey问题和Ramsey数,用红篮两种颜色去涂n个顶点完全图的边，每边涂且仅涂一种颜色，得到的图叫做2色完全图，记为kn,Ramsey数,用 表示这样的正整数，即当时，任何一个2色完全图kn，或者含有红色完全图kp，或者含有蓝色完全图kg，两者必居其一；而当 存在2色完全图kn它不含红色完全子图kp和蓝色完全图kg，这个数就称之为Ramsey数。确定Ramsey数是很难的问题。到目前为止，主要还是研究，精
20、确求得的数值为数甚少,另一种表述,一对常数p和g对应一个常数n，使得n个人中或有p个人互相认识，或者有g个人互相不认识，这个n的最小值用 表示显然,Ramsey数上界估计公式,下面估计 的上界 可改进为：递归边界,上界估计程序,Program ramseyuses crt;Const maxn=50;Type rtype=array1.maxn,1.maxn of integer;Var r:rtype;ramsey数组 a,b:integer;ramsey数的两个参数,Procedure init;输入ramsey数的两个参数Begin clrscr;repeat write(a=);rea
21、dln(a);until(a1)and(a1)and(b=maxn);end;,Procedure mainvar I,j:integer;Begin for i:=2 to a do rI,2:=I;建立递归边界 for i:=2 to b do r2,i:=I;for i:=3 to a do for j:=3 to b do if(odd(ri-1,j)or(odd(rI,j-1)then rI,j:=ri-1,j+rI,j-1 else rI,j:=ri-1,j+rI,j-1-1;writeln(R(,a,b,)=,ra,b);end;Begin init;输入参数a和b main;计
22、算和输出ramsey数r（a，b）End；程序只能估计上界，一些运行结果与精确值有一定误差。要准确计算Ramsey数，只要将程序返回的整数值逐一递减。直至递减后的n值所对应的kn图中出现了不含红色完全子图kp或蓝色完全子图kg的情形，则n+1就是精确的RAMSEY数了。,排列组合与计数问题,两个基本计数原理 加法原理 乘法原理排列问题 线排列 从n个不同的元素中，取r个按次序排列，称为从n中取r个排列，其排列数记为P（n，r）圆排列 从集合Sa1,a2,an的n个不同元素中，取出r个元素按照某种次序排成一个圆圈，称这样的排列为圆排列。重排列 无限,有限重排列 一般地，把r只彩色球放到n个编号不
23、同的盒子中去的方法种数是,组合 C（n，r）非重组合 重组合H(n，r)或者C(n+r-1,r),ACM赛题,某机要部门安装了电子锁。m个工作人员每人发一张磁卡，卡上有开锁的密码特征。为了确保安全，规定至少要有n个人同时使用各自的磁卡才能将锁打开。现在需要你计算一下，电子锁上至少要有多少种特征，每个人的磁卡上至少有几个特征。如果特征的编号以小写英文字符表示，将每个人的磁卡的特征编号打印出来。要求输出的电子锁的总特征数最少。,解题分析,题意告诉我们，至少要有n个人在场并同时使用磁卡才能将锁打开。换言之，任意n1个人在一起，至少缺少一种开锁的密码特征，故不能打开电子锁，剩下的m-(n-1)个人中的
24、任意一个人到场，就一定能将锁打开。故电子锁至少应有C（m，mn1）中特征。对于任何一个工作人员来说，其余m1个人中任意n1个人在场，至少缺少一个这个工作人员磁卡上具有的特征而无法打开锁。所以每个人至少要有C（m-1,n-1）种特征。,虽然通过组合数学知识是能够求出电子锁的最少总特征数和每个人磁卡的最少特征数。但题目还要求枚举出电子锁的所有特征。并输出m张磁卡。,计算出特征数,1，2，.,#m 表示工作人员编号a，b等小写字母表示磁卡的特征编号，超过26个，用aa，ba，ca，.表示。,m4N2Make(1,0)开始递归,母函数,二项展开式从组合学角度看，相当于(x+y)(x+y)共n个括号相乘
25、相当于n个无区别的球，放到x，y两个编号不同的盒子中，每个盒子放入的球数不限。二项式定理,从二项式展开出发，人们自然会想到研究多项展开式：,普通母函数：下式称为序列 ai 的普通母函数,1 天平称物问题：设有质量分别为n1克，n2克,，nk克的整数值砝码，欲称i克的物体。物体在左，砝码在右，共有多少中不同的称法？设有ai种方法称i克物体，则a0，a1，,ai，作系数序列的母函数是,这是因为每个括号(1+xnj)如提供1，表示nj克砝码没有用上；如果提供xnj，表示nj砝码用上了。右边多项展开式中的每一个xi表示可称出i克物体，其系数便是i克物体的方案数。例子：共有1克，2克，3克，4克的砝码各
26、一枚，问能称出哪几种重量？有几种可能方案？,2 允许重复的组合问题 设有几种相异物体。如果允许重复，即每种物体的可取数依次为则从中取 个物体的可重复的组合数 为多少？,3 整数拆分,整数拆分就是把一个整数分解成若干整数的和。不定方程的解，非负整数解的个数,枚举整数拆分,题目：输入正整数m和k，输出将m拆分成k项整数和的所有方案。由交换律产生的诸个方案算作同一个方案，例如m6，k3时 1236 1326 2136算作1236,Program IntegersplitingConst maxm=100;Var k,M:integer;项数，数和 ans:array1.maxm of integer
27、;存储方案 Total:integer;拆分数Procedure print var I:integer;begin inc(total);累计拆分数 write(ans No.,total:4,:);for i:=1 to k-1 do write(ansi,+);拆分方案 writeln(ansk),=,m)end;,Procedure Solve(step,index,sum:integer);step形成的项数；index第step项的值；sum第1.Step项的和 var i:integerBegin if step=k then 若拆分成k项，且数和为M，则打印拆分方案；若k项的数
28、和不等于M，则执行空语句 if sum=m then print else for i:=index to m do 否则还未拆分第k项。在index.M之间选择某值i，使得前step项的数和加上i后小于等于M,If sum+i=m then begin ansstep+1:=I;i值作为第step项 solve(step+1,I,sum+i)递归搜索下一项的值 endEnd;Var i:integer;Begin repeat write(M=);输入数和M read(m);until m in 1.maxm;repeat write(k=);输入项数k read(k);until k in
29、 1.m;total:=0;拆分数初始化,For i:=1 to m div k do 试选1。M，分别作为第一项的值 begin ans1:=i;solve(1,i,i);i作为第1项的值，递归搜索首项为i的所有拆分方案 end;readln;End.End.,求普通母函数的系数序列,如果已经求得普通母函数，可以通过展开多项式的办法确定其系数序列。这个系数序列对研究组合问题有相当重要的意义。下面我们来编写一个程序从一个指定文件中读入普通母函数。文件格式为：每行表示一个多项式，按幂次数递增的顺序输入各项。每项系数在前，指数在后，各项间以空格隔开，每行最后加00，表示一个多项式输入结束。行间的回
30、车表明多项式之间的连乘关系。,算法分析,用单链表P存储普通型母函数的展开式，链结点存储当前项，结点形式为初始时，P为,程序清单,Program multiplyType link=node;指针 noderecord 项结点 time:integer;次幂 a:real;系数；next：link 指向下项的指针 end；,Var p,r:link;P存储以前各多项式的展开式；r加入当前多项式后展开的结果 f:text;输入文件Procedure init；文件读前准备Var str：string；Begin write(File Name=);readln(str);Assign(f,str)
31、;reset(f);End;,Procedure free(p:link);释放P链Begin if pnil then begin free(p.next);dispose(p);end;End;,Procedure add(time:integer;a:real;r:link);通过合并同类项，将aXtime链入r链Var t：link；Begin if r.next=nil 若次幂time最大，则aXtime加入r链尾 then begin new(r.next);r.next.time:=time;r.next.a:=a;r.next.next:=nil;end;Else if r.n
32、ext.time=time 将aXtime并入r中次幂为time的项 then begin r.next.a:=r.next.a+a;if r.next.a=0 then begin 删除r中为0的项 t:=r.next;r.next:=r.next.next;dispose(t);end;end;Else if(r.next.timetime)and(timer.time)若time次幂在r的相邻项之间，则在中间插入aXtime then begin,New(t);t.time:=time;t.a:=a;t.next:=r.next;r.next:=t;End;Else add(time,a
33、,r.next)往下递归合并End;,Procedure proceed;计算若干多项式之积Var time：integer；a：real；t：link；Begin new（p）；new（p.next）;中间p链初始化 p.next.time:=0;p.next.a:=1;p.next.next:=nil;read(f,a,time);读入第1个多项式的首项 while not eof(f)do begin new(r);r.next:=nil;展开式初始化 repeat aXtime乘以p链上的各项，并合并同类项，结果存入r链 if a0 then begin t:=p.next;while
34、 tnil do begin add(time+t.time,a*t.a,r);t:=t.next;end;end;read(f,a,time)读入当前多项式的下一项 until(a=0)or eof(f);,Read(f,a,time);再读下一项 if not eof（f）若当前项不是最后一项，则将当前展开的结果转赋给p，释放以前各多项式的展开式 then begin t:=p；p:=r;free(t);end;End;End;,Procedure print(r:link);打印结果Begin if rnil then begin write(a,r.time,_,r.a:3:0,);print(r.next);end;End;Begin init;文件读前准备 proceed;展开多项式 print（r.next）;打印展开式各项系数 writeln；End;,结束语,组合数学中的算法很多，有一定的难度希望大家在掌握组合数学基本概念和基本原理的基础上，适当作一些中等难度的题目。,
