規(guī)?；瘑?wèn)題的解題策略

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

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

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

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

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

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