数学知识及其相关算法.pdf

数学知识及其相关算法数学知识及其相关算法 第一章 有关数论的算法 2 1 1 最大公约数与最小公倍数最大公约数与最小公倍数 2 1 2 有关素数的算法有关素数的算法 3 1 3 方程方程ax by c的整数解及应用的整数解及应用 5 1 4 求求a b mod n 7 第二章 高精度计算 8 2 1 高精度加法高精度加法 8 2 2 高精度减法高精度减法 10 2 高精度乘法 高精度乘法 12 2 4 高精度除法高精度除法 16 练习练习 21 第三章 排列与组合 21 3 1 加法原理与乘法原理加法原理与乘法原理 21 练习 21 3 2 排列与组合的概念与计算公式排列与组合的概念与计算公式 22 练习 22 3 排列与组合的产生算法 排列与组合的产生算法 23 练习 26 第四章 计算几何 27 4 1 基础知识基础知识 27 4 2 线段的相交判断线段的相交判断 27 4 寻找凸包算法 寻找凸包算法 29 练习练习 32 1 第五章 其它数学知识及算法 32 5 1 鸽巢原理鸽巢原理 32 5 2 容斥原理及应用容斥原理及应用 32 5 常见递推关系及应用常见递推关系及应用 33 第一章第一章 有关数论的算法有关数论的算法 1 1 最大公约数与最小公倍数最大公约数与最小公倍数 1 算法 1 欧几里德算法求 a b 的最大公约数 function gcd a b longint longint begin if a mod b 0 then gcd b else gcd gcd b a mod b end function gcd a b longint longint begin if b 0 then gcdd a else gcd gcd b a mod b end 2 算法 2 最小公倍数 acm a b div gcd a b 3 算法 3 扩展的欧几里德算法 求出 gcd a b 和满足 gcd a b ax by 的整数 x 和 y 一组解 function exgcd a b longint var x y longint longint var t longint begin if b 0 then begin exgcd a x 1 y 0 end else begin exgcdt exgcd b a mod b x y t x x y y t a div b y end end 理论依据 gcd a b ax by bx1 a mod b y1 bx1 a a div b b y1 ay1 b x1 a div b y1 2 1 2 有关素数的算法有关素数的算法 1 算法 4 求前 n 个素数 program BasicMath Prime const maxn 1000 var pnum n longint p array 1 maxn of longint function IsPrime x longint boolean var i integer begin for i 1 to pnum do if sqr p i x then begin if x mod p i 0 then begin IsPrime false exit end end else begin IsPrime true exit end IsPrime true end procedure main var x longint begin pnum 0 x 1 while pnum n do begin inc x if IsPrime x then begin inc pnum p pnum x end end end procedure out var i t integer begin for i 1 to n do begin write p i 5 t t 1 if t mod 10 0 then writeln end end begin readln n main out end 2 算法 5 求不大于 n 的所有素数 program sushu3 const maxn 10000 3 var i k n integer a array 1 maxn of integer begin readln n for i 1 to n do a i i a 1 0 i 2 while i n do begin k 2 i while k n do begin a k 0 k k i end i i 1 while a i 0 and i n do i i 1 end k 0 for i 1 to n do if a i 0 then begin write a i 5 k k 1 if k mod 10 0 then writeln end end 3 算法 6 将整数分解质因数的积 program BasicMath PolynomialFactors const maxp 1000 var pnum n longint num p array 1 maxp of longint procedure main var x longint begin fillchar num sizeof num 0 fillchar p sizeof p 0 pnum 0 x 1 while n 1 do begin inc x 4 if n mod x 0 then begin inc pnum p pnum x while n mod x 0 do begin n n div x inc num pnum end end end end procedure out var j i integer begin for i 1 to pnum do for j 1 to num i do write p i 5 writeln end begin main out end 1 3 方程方程 ax by c 的整数解及应用的整数解及应用 1 算法 7 求方程 ax by c 的整数解 procedure equation a b c longint var x0 y0 longint var d x y longint begin d exgcd a b x y if c mod d 0 then begin writeln no answer halt end else begin x0 x c div d y0 y c div d 5 end end 2 方程 ax by c 整数解的应用 例 1 有三个分别装有 a 升水 b 升水和 c 升水的量筒 gcd a b 1 c b a 0 现 c 筒装满水 问能否在 c 筒个量出 d 升水 c d 0 若能 请列出一种方案 算法分析 量水过程实际上就是倒来倒去 每次倒的时候总有如下几个持点 1 总有一个筒中的水没有变动 2 不是一个筒被倒满就是另一个筒被倒光 3 c 筒仅起中转作用 而本身容积除了必须足够装下 a 简和 b 简的全部水外 别无其 它限制 程序如下 program mw type node array 0 1 of longint var a b c node d step x y longint function exgcd a b longint var x y longint longint var t longint begin if b 0 then begin exgcd a x 1 y 0 end else begin exgcd exgcd b a mod b x y t x x y y t a div b y end end procedure equation a b c longint var x0 y0 longint var d x y longint begin d exgcd a b x y if c mod d 0 then begin writeln no answer halt end else begin 6 x0 x c div d y0 y c div d end end procedure fill var a b node var t longint begin if a 1 0 then repeat if a 1 0 then fill c a else if b 1 b 0 then fill b c else fill a b inc step writeln step 5 a 1 5 b 1 5 c 1 5 until c 1 d else repeat if b 1 0 then fill c b else if a 1 a 0 then fill a c else fill b a inc step writeln step 5 a 1 5 b 1 5 c 1 5 until c 1 d end 1 4 求求 a b mod n 1 算法 8 直接叠代法求 a b mod n function f a b n longint longint 7 var d i longint begin d a for i 2 to b do d d mod n a d d mod n f d end 2 算法 9 加速叠代法 function f a b n longint longint var d t longint begin d 1 t a while b 0 do begin if t 1 then begin f d exit end if b mod 2 1 then d d t mod n b b div 2 t t t mod n end f d end 第二章第二章 高精度计算高精度计算 2 1 高精度加法高精度加法 高精度加法程序如下 program HighPrecision1 Plus const fn inp hp1 inp fn out hp1 out maxlen 100 max length of the number type hp record len integer length of the number 8 s array 1 maxlen of integer s 1 is the lowest position s len is the highest position end var x array 1 2 of hp y hp x input y output procedure PrintHP const p hp var i integer begin for i p len downto 1 do write p s i end procedure init var st string j i integer begin assign input fn inp reset input for j 1 to 2 do begin readln st x j len length st for i 1 to x j len do change string to HP x j s i ord st x j len 1 i ord 0 end close input end procedure Plus a b hp var c hp c a b var i len integer begin fillchar c sizeof c 0 if a len b len then len a len get the bigger length of a b else len b len for i 1 to len do plus from low to high begin inc c s i a s i b s i if c s i 10 then begin dec c s i 10 inc c s i 1 add 1 to a higher position end 9 end if c s len 1 0 then inc len c len len end procedure main begin Plus x 1 x 2 y end procedure out begin assign output fn out rewrite output PrintHP y writeln close output end begin init main out end 2 2 高精度减法高精度减法 高精度减法程序如下 高精度减法程序如下 program HighPrecision2 Subtract const fn inp hp2 inp fn out hp2 out maxlen 100 max length of the number type hp record len integer length of the number s array 1 maxlen of integer s 1 is the lowest position s len is the highest position end var x array 1 2 of hp y hp x input y output positive boolean procedure PrintHP const p hp var i integer begin for i p len downto 1 do write p s i 10 end procedure init var st string j i integer begin assign input fn inp reset input for j 1 to 2 do begin readln st x j len length st for i 1 to x j len do change string to HP x j s i ord st x j len 1 i ord 0 end close input end procedure Subtract a b hp var c hp c a b suppose a b var i len integer begin fillchar c sizeof c 0 if a len b len then len a len get the bigger length of a b else len b len for i 1 to len do subtract from low to high begin inc c s i a s i b s i if c s i 1 and c s len 0 do dec len c len len end function Compare const a b hp integer 1 if a b 0 if a b 1 if ab len then len a len get the bigger length of a b else len b len while len 0 and a s len b s len do dec len find a position which have a different digit if len 0 then compare 0 no difference else compare a s len b s len end procedure main begin if Compare x 1 x 2 10 do begin inc c s len 1 c s len div 10 c s len c s len mod 10 inc len end while len 1 and c s len 0 do dec len 13 c len len end procedure main begin Multiply x z y end procedure out begin assign output fn out rewrite output PrintHP y writeln close output end begin init main out end 2 高精度乘一个整型数据 integer 只需要将上述程序的 hp 类型定义如下即可 type hp record len integer length of the number s array 1 maxlen of longint s 1 is the lowest position s len is the highest position end 3 高精度乘高精度 程序如下 program HighPrecision4 Multiply2 const fn inp hp4 inp fn out hp4 out maxlen 100 max length of the number type hp record len integer length of the number s array 1 maxlen of integer s 1 is the lowest position s len is the highest position 14 end var x array 1 2 of hp y hp x input y output procedure PrintHP const p hp var i integer begin for i p len downto 1 do write p s i end procedure init var st string j i integer begin assign input fn inp reset input for j 1 to 2 do begin readln st x j len length st for i 1 to x j len do change string to HP x j s i ord st x j len 1 i ord 0 end close input end procedure Multiply a b hp var c hp c a b var i j len integer begin fillchar c sizeof c 0 for i 1 to a len do for j 1 to b len do begin inc c s i j 1 a s i b s j inc c s i j c s i j 1 div 10 c s i j 1 c s i j 1 mod 10 end len a len b len 1 the product of a number with i digits and a number with j digits can only have at most i j 1 digits while len 1 and c s len 0 do dec len 15 c len len end procedure main begin Multiply x 1 x 2 y end procedure out begin assign output fn out rewrite output PrintHP y writeln close output end begin init main out end 2 4 高精度除法高精度除法 1 高精度除以整型数据 integer 程序如下 program HighPrecision3 Multiply1 const fn inp hp5 inp fn out hp5 out maxlen 100 max length of the number type hp record len integer length of the number s array 1 maxlen of integer s 1 is the lowest position s len is the highest position end var x y hp z w integer procedure PrintHP const p hp 16 var i integer begin for i p len downto 1 do write p s i end procedure init var st string i integer begin assign input fn inp reset input readln st x len length st for i 1 to x len do change string to HP x s i ord st x len 1 i ord 0 readln z close input end procedure Divide a hp b integer var c hp var d integer c a div b d a mod b var i len integer begin fillchar c sizeof c 0 len a len d 0 for i len downto 1 do from high to low begin d d 10 a s i c s i d div b d d mod b end while len 1 and c s len 0 do dec len c len len end procedure main begin Divide x z y w end procedure out begin assign output fn out rewrite output 17 PrintHP y writeln writeln w close output end begin init main out end 2 高精度除以高精度 程序如下 program HighPrecision4 Multiply2 const fn inp hp6 inp fn out hp6 out maxlen 100 max length of the number type hp record len integer length of the number s array 1 maxlen of integer s 1 is the lowest position s len is the highest position end var x array 1 2 of hp y w hp x input y output procedure PrintHP const p hp var i integer begin for i p len downto 1 do write p s i end procedure init var st string j i integer begin assign input fn inp reset input for j 1 to 2 do begin readln st 18 x j len length st for i 1 to x j len do change string to HP x j s i ord st x j len 1 i ord 0 end close input end procedure Subtract a b hp var c hp c a b suppose a b var i len integer begin fillchar c sizeof c 0 if a len b len then len a len get the bigger length of a b else len b len for i 1 to len do subtract from low to high begin inc c s i a s i b s i if c s i 1 and c s len 0 do dec len c len len end function Compare const a b hp integer 1 if a b 0 if a b 1 if ab len then len a len get the bigger length of a b else len b len while len 0 and a s len b s len do dec len find a position which have a different digit if len 0 then compare 0 no difference else compare a s len b s len end procedure Multiply10 var a hp a a 10 var i Integer begin 19 for i a len downto 1 do a s i 1 a s i a s 1 0 inc a len while a len 1 and a s a len 0 do dec a len end procedure Divide a b hp var c d hp c a div b d a mod b var i j len integer begin fillchar c sizeof c 0 len a len fillchar d sizeof d 0 d len 1 for i len downto 1 do begin Multiply10 d d s 1 a s i d d 10 a s i c s i d div b d d mod b while d b do begin d d b inc c s i end while compare d b 0 do begin Subtract d b d inc c s i end end while len 1 and c s len 0 do dec len c len len end procedure main begin Divide x 1 x 2 y w end procedure out begin assign output fn out rewrite output PrintHP y writeln PrintHP w writeln close output end 20 begin init main out end 练习练习 求 n n0 and a i a i 1 do i i 1 if i 0 then begin j m while a j a i do j j 1 temp a i a i a j a j temp 24 k i 1 l m while k0 and a i n m i do dec i if i 0 then begin a i a i 1 for j i 1 to m do a j a j 1 1 end until i 0 end 练习练习 已知 n 1 n 20 个整数 x1 x2 xn 1 xi 5000000 以及一个整数 k k0 则相对坐标原点 点 p1 在点 p2 的顺时针方向 若 m0 则相对 p0 点 点 p1 在点 p2 的顺时针方向 若 m0 则 p1 点向左拐 若 mb then max a else max b end function min a b real real begin if a min p3 x p4 x and max p3 x p4 x min p1 x p2 x and max p1 y p2 y min p3 y p4 y and max p3 y p4 y min p1 y p2 y and m p2 p3 p1 m p2 p4 p1 0 and m p4 p1 p3 m p4 p2 p3 0 or t 0 and sqr p1 x list 0 x sqr p1 y list 0 y sqr p2 x list 0 x sqr p2 y list 0 y then comp true else comp false end procedure sort l r integer var i j integer x p begin if r l 11 and comp list i list i 1 do begin swap list i list i 1 dec i end end end else begin x list l random r l 1 i l j r repeat while comp list i x do inc j while comp x list j do dec j if i j sort l j 30 sort j 1 r end end procedure init var i integer begin assign f input txt reset f readln f n for i 0 to n 1 do begin readln f list i x list i y if list i y list 0 y or list i y list 0 y and list i x 0 do dec top inc top s top i end for i 1 to top do write list s i x 7 2 list s i y 7 2 writeln end begin init graham readln end 31 练习练习 1 巳知 平面上有 n 个点 n 2 fn