藍(lán)橋杯競賽真題——閱兵方陣

陳新龍

最近培訓(xùn)藍(lán)橋杯競賽題時(shí)，注意到一道難度適中的題目。這是一道來自第九屆藍(lán)橋杯Java組的國賽題目，今天就和大家分享一下解題的思路。

閱兵方陣：x國要參加同盟閱兵的活動(dòng)。主辦方要求每個(gè)加盟國派出的士兵恰好能組成2個(gè)方陣。x國發(fā)現(xiàn)弱小的y國派出了130人的隊(duì)伍，他們的士兵在行進(jìn)中可以變換2種隊(duì)形。隊(duì)形的變化：130=81+49=9*9+7*7和130=121+9=11*11+3*3兩種方式。x國君很受刺激，覺得x國面積是y國的6倍，理應(yīng)變出更多隊(duì)形。于是他發(fā)號施令：我們要派出一支隊(duì)伍，在行進(jìn)中要變出12種隊(duì)形！手下人可慘了，要忙著計(jì)算至少多少人才能組成12種不同的方陣。聰明的你可以利用計(jì)算機(jī)的優(yōu)勢幫助國君計(jì)算一下需要多少士兵嗎？（不要失去信心，偷偷告訴你1105人可以組成四種隊(duì)列了。）

首先就是理解題目，簡單來說就是把一個(gè)數(shù)字拆分成兩個(gè)數(shù)字，拆分的兩個(gè)數(shù)字要進(jìn)行平方根，平方根得出來的數(shù)字還需要是一個(gè)整數(shù)。例如數(shù)字41，可以拆成16和25，繼續(xù)開平方根拆成4和5。

題目難點(diǎn)在于找一個(gè)可以拆分成12組符合條件的最小那個(gè)數(shù)字。依照慣例第一思路肯定是窮舉法，將所有的可能全部羅列出來然后進(jìn)行統(tǒng)計(jì)。雖然題目中已經(jīng)給出了提示，1105就可以組成四種隊(duì)列，那么想要組成12種隊(duì)列，肯定會(huì)超過1105，我們暫時(shí)也不知道這個(gè)數(shù)字的下限，暫時(shí)先算到1000000停止，防止數(shù)字太小了算不出結(jié)果。

下面可以通過嵌套循環(huán)的方式來計(jì)算兩個(gè)方陣的人數(shù)，外層的循環(huán)控制第一方陣的人數(shù)，內(nèi)層的循環(huán)來控制第二方陣的人數(shù)。并做了一定優(yōu)化，外循環(huán)判斷第一方陣的人數(shù)是否超出了預(yù)期，如果已經(jīng)超出了預(yù)期直接結(jié)束循環(huán)，內(nèi)循環(huán)中判斷條件是否滿足要求，如果滿足要求，會(huì)進(jìn)行統(tǒng)計(jì)計(jì)數(shù)，當(dāng)滿足能夠變換12種隊(duì)形的時(shí)候輸出正確結(jié)果，并且結(jié)束循環(huán)。

窮舉法當(dāng)然會(huì)消耗更多時(shí)間，你還可以對代碼進(jìn)行進(jìn)一步的優(yōu)化，優(yōu)化的地方我已經(jīng)標(biāo)注出來給大家參考了。

當(dāng)然同樣算法用Scratch也能編寫，在已經(jīng)知道正確答案的情況下，將初始值設(shè)定為160220，免得浪費(fèi)時(shí)間。設(shè)置第一方陣人數(shù)為1，設(shè)置第二方陣人數(shù)為總?cè)藬?shù)減第一方陣的平方，結(jié)合雙重循環(huán)的方式進(jìn)行統(tǒng)計(jì)計(jì)算將正確的結(jié)果輸出在列表中。

通過這道題我們也可以發(fā)現(xiàn)，窮舉法這種解題思路比較直觀，易于理解，但是最大的缺點(diǎn)是運(yùn)算量比較大，解題效率不高，在競賽中，時(shí)間是有限的，競賽的最終目標(biāo)就是求出問題解，因此，如果題目的規(guī)模不是很大，在規(guī)定的時(shí)間與空間限制內(nèi)能夠求出解，那么最好是采用枚舉法，而不需太在意是否還有更快的算法，這樣可以使你有更多的時(shí)間去解答其他難題。當(dāng)然也歡迎大家提出更好的解題思路進(jìn)行分享。