算法合集之《規(guī)?；瘑栴}的解題策略》

1、規(guī)?；瘑栴}的解題策略長沙市一中●謝婧1規(guī)?；瘑栴}的解題策略湖南省長沙市第一中學(xué)謝婧【關(guān)鍵字】規(guī)模化策略算法【摘要】問題規(guī)?；墙鼇硇畔W(xué)競賽的一個新趨勢，它意在通過擴(kuò)大數(shù)據(jù)量來增加算法設(shè)計(jì)和編程實(shí)現(xiàn)的難度，這就向信息學(xué)競賽的選手提出了更高層次的要求，本文試圖探索一些解決此類問題的普遍性的策略。開始，本文給出了“規(guī)?；币辉~的定義，并據(jù)此將其分為橫向擴(kuò)展和縱向擴(kuò)展兩種類型，分別進(jìn)行論述。在探討橫向擴(kuò)展問題的解決時本文是以謀劃策略的“降維”

2、思想為主要對象的；而重點(diǎn)討論的是縱向擴(kuò)展問題的解決，先提出了兩種策略——分解法和精簡法，然后結(jié)合一個具體例子研究“剪枝”在規(guī)?；瘑栴}中的應(yīng)用。問題規(guī)?；切畔W(xué)競賽向?qū)嶋H運(yùn)用靠攏的一個體現(xiàn)，因此具有不可忽視的意義【正文】一引論（一）背景分析（一）背景分析分析近年來國際、國內(nèi)中學(xué)生信息學(xué)競賽試題，可以看出信息學(xué)競賽對于選手的要求已經(jīng)不再僅僅局限于“算法設(shè)計(jì)”，它同時在編程實(shí)現(xiàn)方面加強(qiáng)了考察力度，由側(cè)重于考察理論知識轉(zhuǎn)向理論考察與實(shí)踐考察并

3、重。這一命題宗旨的轉(zhuǎn)變，給信息學(xué)競賽注入了新的機(jī)能，為命題者開拓了另一個領(lǐng)域。其一體現(xiàn)有：試題由精巧型(這類試題的難度主要體現(xiàn)在精妙算法的構(gòu)造，屬于一點(diǎn)即通的類型)向規(guī)模型發(fā)展，從而使得問題的實(shí)現(xiàn)復(fù)雜化。（二）對“規(guī)?；钡睦斫猓ǘΑ耙?guī)?；钡睦斫庖?guī)模一詞在字典中的含義是：事物所具有的格式、形式或范圍。在信息學(xué)競賽中，問題的規(guī)模具體是指待處理數(shù)據(jù)量的大小，通常可以通過一組規(guī)模參數(shù)(S1S2…Sk)來表示。例如下列問題1的規(guī)模就是(1

4、00)，而問題2的規(guī)模是(100100)。問題1：求數(shù)列的前100項(xiàng)之和。問題2：求100100的矩陣中的各項(xiàng)之和。問題3：求數(shù)列的前1000項(xiàng)之和。規(guī)模化問題的解題策略長沙市一中●謝婧3積就是線段的長度。第二步：在低維問題中求找規(guī)律。試想把長度相同的子線段歸類統(tǒng)計(jì)，那么對于長度為L的線段(ssL)：∵sL≤A1∴s≤A1L又∵s≥0，∴0≤s≤A1L，這樣的子線段共有A11L條。所以，一維體（(0A1)）的所有子一維體的階積和為Σi(

5、A11i)i=1..A1，設(shè)為Fg(A1)。第三步：將規(guī)律推廣至高維問題。我們將模型稍加推廣，看看n=2時的情況。這時我們可將二維體看成一個矩形，其階積就是矩形的面積。在上圖中，我們把一個矩形嵌入平面直角坐標(biāo)系。這里我們按照子矩形不同的長(x軸上的距離)、寬(y軸上的距離)來統(tǒng)計(jì)。我們先提取矩形中一個寬為1的單位矩形帶(如上圖的陰影部分)，然后討論矩形的長。根據(jù)解決一維體時的規(guī)律，我們知道在這個單位矩形帶中長為L的矩形共有A11L個，所

6、以在單位矩形帶中，所有子矩形的面積和為Fg(A1)。由于寬為1的單位矩形帶在原矩形中共有A2個，所有寬為1的子矩形的面積之和為1A2Fg(A1)。同理，所有寬為2的子矩形的面積之和為2(A21)Fg(A1)，因此所有寬為W的子矩形的面積之和為W(A21W)Fg(A1)。由此可知二維體所有子二維體的階積之和是Fg(A2)Fg(A1)。逐步推廣，可以得知求n維體（(0A1)(0A2)，…，(0An)）所有子n維體的階積和為Fg(A1)Fg(