問題求解與程序設計

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

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

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

4、相應的正負號，使其按新順序逐一相加后，等到符號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