《大数组合数学算法-ACM》由会员分享，可在线阅读，更多相关《大数组合数学算法-ACM（84页珍藏版）》请在金锄头文库上搜索。
1、大数运算与组合数学 ACM国际大学生程序设计竞赛 主讲 王树林 問題 當有一個很大的整數要運算時 如何算 例如 一個一佰位數的數字 int最大只能到232約十個位數的十進位數字 最簡單的方法 先看大數加法 就是改成手動去算加法 而不是由電腦算 123456789123 234123467890 寫成電腦程式 方法一 使用陣列 array 例如 inta 100 b 100 sum 100 然後sum i a i b i c記住 c是進位 carry 這邊我們要自行處理 那輸入呢 輸入成字串再把字串分解成陣列中各個元素 需要一個parse字串的副程式 voidparse char s int a
2、 inti j j strlen s for i 0 i 10 sum i sum i 10 c 1 else c 0 改進 array改成byte的元素 省空間 更省 一個元素就可以到255 256才進位 用bool用linklist方式 可以讓輸入的數字更大 其他 減法 乘法 除法 同樣的原理 大數運算 现将一些关键算法的实现方法描述如下 大数的一些简单计算的算法1 大数加法运算的实现算法 1 将A B按位对齐 2 低位开始逐位相加 3 对结果做进位调整 2 大数减法运算实现算法 1 将A B按位对齐 2 低位开始逐位相减 3 对结果做借位调整 大數運算 3 大数乘法运算实现算法 1 引入
3、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小 問 t a 1 t b 1 是大小於100位數或是否為整數 若小於100位數 就印該值 題意範例 SampleInpu
4、t293232214271239111SampleOutput 2 9 1 2 3 1 73 2 3 1 2 2 1 isnotanintegerwithlessthan100digits 21 42 1 21 7 1 18952884496956715554550978627384117011154680106 123 911 1 123 1 1 isnotanintegerwithlessthan100digits 例子 解法 1 t 1 It seasytoseethatit sanswerisn taintegerwithlessthan100digits 2 a b It seasy
5、toseethatit sansweris1 3 if a b 0 It sanswerisn taintegerwithlessthan100digits 証明 令 t a 1 t b 1 n n是整數 証明a b 0 t a 1 t b 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 t b a b y y是正整數 t a 1 t b 1 x y 1 x 1 x y 1 x 1 x y 1 x y 2 x y 3 x 0 x y 1 x y 2 x y 3 x 0
6、x y 1 加上x y 2 x y 3 x 0最多進一位數 Log10 x y 1 log10 t a b a b log10 t if a b log10 t 99 就一定會大於100位數若沒有大於100位數 有可能等於100位數 所以要算出來 5 x y 1 x 1 x y 1 x y 2 x y 3 x 0將這個值算出來 例子 討論 這題目一定要先判斷位數 如果大於100位就不用算了 不然會超過時間 且要用比較好的方法算真正的值 若用大數除法 會太慢 所以改成 x y 1 x 1 x y 1 x y 2 x y 3 x 0 這樣的方式來算 比較快 随机产生一个200位的数 intrand
7、om intp 201 随机产生一个200位的数 p 1 1 低位1为保证该素数为奇数inti for i 2 i 200 i p i rand 10 RAND MAX while p 200 0 高位不能为0 保证素数达到要求的长度p 200 rand 10 RAND MAX return0 乘法运算 intmultiply intm 101 intn 201 intproduct 301 两因子m n 乘积product intsum1 102 sum2 102 i j k s sum2 sum1中间过渡量for i 1 i 101 i sum2 i 0 sum2所有位置零for j 1
8、j 201 j 在n的每一位上处理m for i 1 i 101 i sum1 i 0 sum1所有位置零for i 1 i n j i 通过每一层循环 实现乘法的加法化 for s 1 s 101 s sum2 s m s sum1 s for k 1 k 101 k sum1 k sum2 k for k j k 100 j k product k sum2 k j 1 product k 即是实现了乘法过程中的加法 for i 1 i 301 i 进位处理 j product i 10 product i 1 j product i j 10 return0 比较两个数的大小 intcm
9、p inta 301 intab intb 201 intbb 比较两个数的大小 inti result result 0 a b for i 300 i ab i if a i 0 return1 for i 0 ib bb i result 1 a b break if a ab i b bb i result 1 a b break returnresult 除法运算 voiddivision inta 301 intb 201 intc 301 intd 201 除法函数 300位除200位 c为商 d为余数 intal bl t 301 al用来标识a的长度 bl用来标识b的长度in
10、ti j al2 for i 0 i0 i 测算a的长度if a i 0 al i break for i 200 i 0 i 测算b的长度if b i 0 bl i break 除法运算 续 al2 al for i 0 i al bl 1 i 高位开始 while cmp t al2 b bl 1 比较a b首位大小 for j 0 j bl j t al2 j b bl j 对位做减法for j 1 j 301 j if t j 0 完成借位 t j 10 t j 1 c al bl 1 i 高位开始逐位计算商 al2 for i 0 i 201 i d i t i 产生余数 组合数学研
11、究对象 组合数学研究的主要内容是依据一定的规则来安排某些事务的有关数学问题 这些问题包括四个方面 1 这种安排是否存在 即存在性问题 2 如果符合要求的安排是存在的 那么这样的安排又有多少 即计数问题 3 怎样构造这种安排 即算法构造问题 4 如果给出了最优化标准 又怎样得到得到最优安排 1 存在性问题 实际生活中的各种问题 有些可以当机立断判定其有解还是无解 但也有不少问题一时难以判定 例如 宴会上 奇数位客人能否在晚会上与他人握手奇数次 竞赛时不可能出现专门判定某个问题有解或无解的试题 但往往会在测试数据中加入无解的数据 2 计数问题 如果一个组合问题的解是存在的 自然会问有多少不同的解
12、例如 将8个 车 放在8 8的国际象棋棋盘上 如果他们两两不能互吃 那么称8个 车 处于一个安全状态 显然这种安全状态是存在的 问有多少种不同的安全状态 这就是一个计数问题 信息学竞赛中一般分为两种类型 一种是计算某种特性的对象有多少 另一种是枚举类型 把所有具有某种特性的对象都列举出来 3 构造性算法 一个组合问题 已经判定解是存在的 甚至已经推知有多少解 但关键还在于把解构造出来 有的哪怕出一个解也好 如魔方问题 正交拉丁问题 4 优化问题 一个问题的构造性算法可能不止一种 自然面临如何择优 如何改进 使得答案尽快地解出来 比如动态规划和线性规划问题的解决方法 组合问题的基本解题方法 1从
13、组合学基本概念基本原理出发的常规方法容斥原理Polya原理鸽笼原理递归方法生成函数方法 2通常与问题所涉及的组合数学概念无关的非常规方法 主要用于解那些需要独立思考见解独到和有所创新的问题 数学归纳法证明n个元素的集合 其子集恰为2n个一一对应技术将一个问题转化为另一种有常规算法的问题模式 例如 8 车 问题有多少个不同的安全状态 8个车处于安全状态当且仅当它们处于不同的8行和8列上 用一个排列a1 a2 a8 对应于一个安全状态 使ai表示第i行的ai列上放置一个车 这种对应显然是一对一的 因此 安全状态的总数等于这8个数的全排列的总数8 40320 3殊途同归方法 从不同的角度讨论计数问题
14、 以建立组合等式例如 对没有三条对角线交于一点的凸多边形 计算各边及对角线所组成的互不重叠的区域个数 区域总数为C n 4 C n 1 2 各区域顶点总数 包括重复计数 角度1 角度2 所有区域的内角和的总和的等式两边同除以180度得两式相减得区域总数 4数论方法 运用奇偶性 整除性等数论性质进行存在性问题的分析与推理 例子 设n位客人 在晚会上每人与他人握手d次 d是奇数 证明n是偶数 回溯方法 需要用计算机求解的组合试题一般有两种类型 1 能够用简明正确的组合公式揭示问题 2 不能对给定问题建立数学模型或虽然有数学模型但运用该数学模型求解有困难 在求解枚举类型问题时 会遇到此类问题 回溯方
15、法是一种常用的解题策略 N皇后问题 例子 一个n n的国际象棋棋盘上放置n个皇后 使其不能相互攻击 即任何两个皇后都不能处在棋盘的同一行同一列同一条斜线上 试问有多少中摆法 一如何求n皇后问题1状态 state 状态是指问题求解过程中每一步的状况 n皇后问题中 某行皇后所在列位置i即为该皇后问题的一个状态 2算符 operator 算符是把问题的一个状态变换到另一个状态的方法代号 n皇后的一种摆法对应n个元素的排列方案 a1 a2 an 必须满足条件 不产生对角线攻击和列攻击 3 结点 node 用以表明某状态特征及关联方式的基本信息单元 结点的数据结构一般为记录类型 Typenode rec
16、ordoperator 算符类型 state 状态类型 end Varstack array 1 maxdepth ofnode 节点数不超过maxdepth的一条路径 orVarstack array 1 20 ofinteger 当n 4时 初始状态 空棋盘 试放的顺序是从左至右 自上而下 求解n皇后问题 无非就是做两件事 1 从左至右逐条树枝地构造和检查解答树t 2 检查t的节点是否对应问题的目标状态 为了加快检查速度 一般规定 1 在扩展一个分支节点前进行检查 如果它不满足约束条件 则不再构造以它为根节点的子树 2 已处理过的节点若以后不会再用 则不必保留 即回溯过程中经过的节点不再保留 栈 重要的数据结构 递归过程make L 1分配一个连续的数组区域stack 1 maxdepth 顺序存放栈中表目 即当前路径的节点 2栈顶指针L作递归程序make的值参数 指出待扩展节点在当前路径序列stack中的顺序 算符作make过程的局部变量 算法框架 ProgramsearchVarstack array 1 maxdepth ofnode Proceduremake L inte
