清北學(xué)堂2012國(guó)慶NOIP課件數(shù)學(xué)方法、歸納與貪心.ppt

1、數(shù)學(xué)方法、歸納與貪心,武森,最大公約數(shù),Function gcd(a,b:longint); Begin If b=0 then gcd:=a; Else gcd:=gcd(b,a mod b); End;,最小公倍數(shù),A*B DIV GCD(A，B),素?cái)?shù),function ok(n:longint):boolean; var i:longint; begin ok:=ture; for i:=2 to trunc(sqrt(n)+1 do if (n mod i=0) then begin ok:=false;exit;end; end;,排列組合,遞歸回溯 非遞歸,高精度,高精度加法 高

2、精度減法 高精度乘法 位壓 高精度除法 模擬除法算式 二分答案 表達(dá)式計(jì)算 遞歸 棧,高精度加法,a b fillchar(c,sizeof(c),0); if a0b0 then len:=a0 else len:=b0; for i:=1 to len do begin inc(c,a+b); if c10 then begin dec(c,10); inc(ci+1); end; end; if clen+10 then inc(len); c0:=len; end;,高精度減法,fillchar(c,sizeof(c),0); if a0b0 then len:=a0 else len

3、:=b0; for i:=1 to len do begin inc(ci,ai-bi); if ci1) and (clen=0) do dec(len); c0:=len;,高精度乘低精度,fillchar(c,sizeof(c),0); len:=a0; for i:=1 to len do begin inc(ci,ai*b); inc(ci+1,(a*b) div 10); ci:=ci mod 10; end; inc(len); while (clen=10) do begin clen+1:=clen div 10; clen:=clen mod 10; inc(len); e

4、nd; while (len1) and (clen=0) do dec(len); c0:=len;,高精度乘高精度,fillchar(c,sizeof(c),0); for i:=1 to a0 do for j:=1 to b0 do begin inc(ci+j-1,ai*bj); inc(ci+j,ci+j-1 div 10); ci+j-1:=ci+j-1 mod 10; end; len:=a0+b0+1; while (len1) and (clen=0) do dec(len); c0:=len;,高精度除低精度,fillchar(c,sizeof(c),0); len:=a

5、0; d:=0; for i:=len downto 1 do begin d:=d*10+ai; ci:=d div b; d:=d mod b; end; while (len1) and (clen=0) then dec(len); c0:=len;,高精度除高精度,fillchar(c,sizeof(c),0); fillchar(d,sizeof(d),0); len:=a0;d0:=1; for i:=len downto 1 do begin multiply(d,10,d); /高精度成低精度 d1:=a; while(compare(d,b)=0) do 即d=b begi

6、n Subtract(d,b,d); /高精度減法 inc(c); end; end; while(len1)and(c.slen=0) do dec(len); c.len:=len;,位運(yùn)算,位運(yùn)算就是直接對(duì)整數(shù)在內(nèi)存中的二進(jìn)制位進(jìn)行操作。 程序中的所有數(shù)在計(jì)算機(jī)內(nèi)存中都是以二進(jìn)制的形式儲(chǔ)存的,例子,6=（110）2 11=（1011）2 0 - False 1 - True,符號(hào),C語言 Pascal語言 - a begin a:=a + b; b:=a - b; a:=a - b; end;,Swap,procedure swap(var a,b:longint); begin a:=

7、a xor b; b:=a xor b; a:=a xor b; end;,shl運(yùn)算,a shl b 把a(bǔ)轉(zhuǎn)為二進(jìn)制后左移b位（在后面添b個(gè)0） 例： 100 -1100100 400 -110010000 100 shl 2 = 400 實(shí)質(zhì)就是a乘以2的b次方 比乘法快！,shr運(yùn)算,a shr b 表示二進(jìn)制右移b位（去掉末b位） 10 shr 1= 5 應(yīng)用： 二分查找 堆的插入,應(yīng)用,去掉最后一位 | (101101-10110) | x shr 1 在最后加一個(gè)0| (101101-1011010)| x shl 1 在最后加一個(gè)1| (101101-1011011) | x s

8、hl 1+1 把最后一位變成1| (101100-101101) | x or 1 把最后一位變成0| (101101-101100) | x or 1-1 最后一位取反 | (101101-101100) | x xor 1 把右數(shù)第k位變成1 | (101001-101101,k=3) | x or (1 shl (k-1) 把右數(shù)第k位變成0 | (101101-101001,k=3) | x and not (1 shl (k-1) 右數(shù)第k位取反| (101001-101101,k=3) | x xor (1 shl (k-1) 取末三位 | (1101101-101) | x an

9、d 7 取末k位| (1101101-1101,k=5) | x and (1 shl k-1) 取右數(shù)第k位| (1101101-1,k=4) | x shr (k-1) and 1 把末k位變成1| (101001-101111,k=4) | x or (1 shl k-1) 末k位取反 | (101001-100110,k=4) | x xor (1 shl k-1) 把右邊連續(xù)的1變成0 | (100101111-100100000) | x and (x+1) 把右起第一個(gè)0變成1 | (100101111-100111111) | x or (x+1) 把右邊連續(xù)的0變成1 | (

10、11011000-11011111) | x or (x-1) 取右邊連續(xù)的1| (100101111-1111)| (x xor (x+1) shr 1 去掉右起第一個(gè)1的左邊| (100101000-1000) | x and (x xor (x-1),例題,n皇后問題 由n*n個(gè)方塊排成n行n列的正方形，稱之為“n元棋盤”。如果兩個(gè)皇后位于n元棋盤上的同一行、同一列或同一對(duì)角線上，則稱它們?cè)诨ハ喙簟，F(xiàn)要求找出使n元棋盤上的n個(gè)皇后互不攻擊的布局。,const maxn:=(1 shl n)-1; procedure dfs(row,l,r:longint); var pos,p:lon

11、gint; begin if rowmaxn then begin pos:=maxn and not (row or l or r); while pos0 do begin p:=pos and -pos; pos:=pos-p; dfs(row+p,(l+p)shl 1,(r+p)shr 1); end; end else inc(sum); end; begin dfs(0,0,0); writeln(sum); end;,排序,冒泡 快速排序 堆排序,貪心,貪心法（ Greedy algorithm），又稱貪心算法，是一種在每一步選擇中都采取在當(dāng)前狀態(tài)下最好或最優(yōu)（即最有利）的選擇，

12、從而希望導(dǎo)致結(jié)果是最好或最優(yōu)的算法。比如在旅行推銷員問題中，如果旅行員每次都選擇最近的城市，那這就是一種貪心算法。,貪心算法在有最優(yōu)子結(jié)構(gòu)的問題中尤為有效。最優(yōu)子結(jié)構(gòu)的意思是局部最優(yōu)解能決定全局最優(yōu)解。簡(jiǎn)單地說，問題能夠分解成子問題來解決，子問題的最優(yōu)解能遞推到最終問題的最優(yōu)解。 貪心算法與動(dòng)態(tài)規(guī)劃的不同在于它每對(duì)每個(gè)子問題的解決方案都做出選擇，不能回退。動(dòng)態(tài)規(guī)劃則會(huì)保存以前的運(yùn)算結(jié)果，并根據(jù)以前的結(jié)果對(duì)當(dāng)前進(jìn)行選擇，有回退功能。,合并果子,有n堆果子，每次可以合并任意兩堆，費(fèi)用為兩堆果子數(shù)。求最少的費(fèi)用將所有的果子合并。,購物,你就要去購物了，現(xiàn)在你手上有n種不同面值的硬幣，每種硬幣有無限多

13、個(gè)。為了方便購物，你希望帶盡量少的硬幣，但要能組合出1.X之間的任意值。 輸入 第一行兩個(gè)數(shù)X(1000),n(10) 以下n個(gè)數(shù)，表示每種硬幣的面值 輸出 最少需要攜帶的硬幣個(gè)數(shù) 如果無解輸出-1 樣例輸入 20 4 1 2 5 10 樣例輸出 5,區(qū)間覆蓋問題,設(shè)x1, x2, xn是實(shí)直線上的n個(gè)點(diǎn)。用固定長(zhǎng)度的閉區(qū)間覆蓋這n個(gè)點(diǎn)，至少需要多少個(gè)這樣的固定長(zhǎng)度閉區(qū)間? Input 7 3 1 2 3 4 5 -2 6 Output 3,刪數(shù)問題,給定n 位正整數(shù)a，去掉其中任意kn 個(gè)數(shù)字后，剩下的數(shù)字按原次序排列組成一個(gè)新的正整數(shù)。對(duì)于給定的n位正整數(shù)a 和正整數(shù)k，設(shè)計(jì)一個(gè)算法找出剩下數(shù)字組成的新數(shù)最小的刪數(shù)方案。 對(duì)于給定的正整數(shù)a，編程計(jì)算刪去k個(gè)數(shù)字后得到的最小數(shù)。 Input 178543 4 Output 13,多元Huffman編碼變形,在一個(gè)操場(chǎng)的四周擺放著n 堆石子?，F(xiàn)要將石子