問題求解與程序設(shè)計(jì)

1、問題求解與程序設(shè)計(jì),李文新2004.2-6,問題求解與程序設(shè)計(jì),課程內(nèi)容授課方式成績(jī)?cè)u(píng)定進(jìn)度安排信息學(xué)奧賽簡(jiǎn)介ACM大學(xué)生程序設(shè)計(jì)競(jìng)賽簡(jiǎn)介簡(jiǎn)單題 – 較難題作業(yè),課程內(nèi)容,信息學(xué)奧賽及ACM比賽題目透過比賽題目，提高分析問題和應(yīng)用計(jì)算機(jī)編程解決問題的能力為北大ACM代表隊(duì)培養(yǎng)后備人才,授課方式,每周二 9-10 ， 電教125 集中授課教師講授學(xué)生分組討論，全班討論學(xué)生講授每周兩小時(shí)上機(jī)，時(shí)間地點(diǎn)待定網(wǎng)上

2、計(jì)時(shí)做題,成績(jī)?cè)u(píng)定,總則：做夠一定數(shù)量的題目可以及格想要優(yōu)秀則需要在班里排名前10%期中20% + 期末40% + 作業(yè) 30% + 個(gè)人表現(xiàn)10%作業(yè)：每周2-4題，每月出1題,進(jìn)度安排,1-2 簡(jiǎn)單題3 模擬題4-5 圖論題6 組合數(shù)學(xué)題7 幾何題8-9 動(dòng)態(tài)規(guī)劃題10-11 搜索題12-14 綜合,信息學(xué)奧賽簡(jiǎn)介,對(duì)象組織形式考試方式

3、題目及評(píng)分我國(guó)的情況,ACM競(jìng)賽簡(jiǎn)介,對(duì)象組織形式考試方式題目及評(píng)分我國(guó)及我校的情況,ACM競(jìng)賽樣題,一個(gè)最簡(jiǎn)單的 ProblemSimple.doc,IOI2002試題,烏托邦 utopia.doc,例題：ioi2002 day 1 task 2 utopia,問題描述 – utopia.doc問題分析 兩個(gè)彼此獨(dú)立的序列對(duì)于一維問題求解符號(hào)序列 si數(shù)值序列 xi對(duì)xi重新排列并加

4、相應(yīng)的正負(fù)號(hào)，使其按新順序逐一相加后，等到符號(hào)si.,例題：ioi2002 day 1 task 2 utopia --問題的解,Definition – alternating sequenceA sequence of non-zero integers X=(xa, xa+1,…, xb,), a≤b is an alternating sequence if1) |xa|< |xa+1|<

5、…<|xb|, and2) for all i, a<i≤b, the sign of xi is different from the sign of xi-1.Here, |xa| is the absolute value of xa.,例題：ioi2002 day 1 task 2 utopia --問題的解,Lemma 1. Let X=(xa, xa+1,…, xb) be an alte

6、rnating sequence. The sign of xb is equal to the sign of ∑a≤i≤bxi , the total sum of elements in X.,例題：ioi2002 day 1 task 2 utopia --問題的解,ProofAssume: xb is positivenumber of elements in X is evenThen: xa+x

7、a+1 , xa+2+xa+3 , … , xb-1+xb are all positive, thus the total sum ∑a≤i≤bxi is positive.,例題：ioi2002 day 1 task 2 utopia --問題的解,Example 1.(-1,+2,-5,+6) = (-1+2)+(-5+6)=+2which is positive.Example 2.(+3,-4,+5,

8、-6,+7) =(+3)+(-4+5)+(-6+7)=+5, which is also positive.,例題：ioi2002 day 1 task 2 utopia --問題的解,Theorem 1.Let X=(xa, xa+1,…, xb), a≤b be an alternating sequence, and let S=(sa, sa+1,…, sb) , a≤b be a sequence of

9、signs. If the sign of xb is equal to sb , then there exists a sequence X’=(xia, xia+1,…, xib) such that {xa, xa+1,…, xb} ={xia, xia+1,…, xib}, and X’ is valid with respect to S.,例題：ioi2002 day 1 task 2 utopia

10、--問題的解,ProofThe proof is by induction on the number of k of elements in X. When k=1, it is easy to see that X’=X is a valid sequence with respect to S. Now we assume that k≥2. We let S1=S-sb, that is, S1=(sa,sa+1,…,sb-1

11、).Case 1. The sign of sb-1 is equal to xb ,Let X1=X-xa, that is, X1=(xa+1,xa+2,…,xb).Case 2. The sign of sb-1 is equal to xb-1 ,Let X1=X-xb, that is, X1=(xa,xa+1,…,xb-1).,例題：ioi2002 day 1 task 2 utopia --問題的

12、解,Example 3.X=(-4,+5,-7,+8),S=(+,-,-,+), we haveS1 = (+,-,-), X1=(-4,+5,-7),S2 = (+,-), X2=(+5,-7),S3 = (+), X3=(+5).Thus,X3’=(+5),X2’=(+5,-7),X1’=(+5,-7,-4),X’ =(+5,-7,-4,+8).,例題：ioi2002 day 1 task 2

13、 utopia --問題的解,Example 4.X=(-1,+2,-3) and S=(-,-,-),S1=(-,-), X1=(+2,-3),S2=(-), X2=(-3).Thus,X2’=(-3),X1’=(-3,+2),X’ =(-3,+2,-1).,例題：ioi2002 day 1 task 2 utopia --問題的解,Algorithm of utopiaS

14、tep 1. //read input1.1 read N;1.2 read 2N code numbers and partition them into A and B such that |A|=|B|;1.3 read a sequence of regions R=(r1, r2, …,rN );,例題：ioi2002 day 1 task 2 utopia --問題的解,Step 2.

15、//find x-coordinates of code pairs2.1 find a sequence of signs S=(s1, s2, …,sN ) such that for all j , 1≤j≤N, sj=‘+’ if rj=1,4; otherwise sj=‘-’. 2.2 find an alternating sequence X=(x1, x2, …,xN ) from A such that the

16、 sign of xN is equal to sN .2.3 given X and S , find a valid sequence X’=(xi1, xi2, …,xiN ) w.r.t S according to the proof of Theorem 1.,例題：ioi2002 day 1 task 2 utopia --問題的解,Step 3. //find y-coordinates of co

17、de pairs3.1 find a sequence of signs S=(s1, s2, …,sN ) such that for all j , 1≤j≤N, sj=‘+’ if rj=1,2; otherwise sj=‘-’. 3.2 find an alternating sequence Y=(y1, y2, …,yN ) from B such that the sign of yN is equal to

18、sN .3.3 given Y and S , find a valid sequence Y’=(yi1, yi2, …,yiN ) w.r.t S according to the proof of Theorem 1.,例題：ioi2002 day 1 task 2 utopia --問題的解,Step 4. //write outputprint (xi1,yi1),(xi2,yi2),…,(xiN,yi

19、N).,例題：ioi2002 day 1 task 2 utopia --問題的解,Theorem 2Algorithm Utopia is correct, and its running time is O(NlogN).ProofThe correctness of the algorithm is mainly due to Theorem 1. The complexity of each step

20、except Step2.2 and 3.2 os O(N), where Step 2.2 and 3.2 require O(NlogN) time for sorting.,例題：ioi2002 day 1 task 2 utopia --問題的解,Testing data,例題：ioi2002 day 1 task 2 utopia --問題的解,Grading4*25 = 100,例題：i