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

陳新龍

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

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

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

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

下面可以通過嵌套循環(huán)的方式來計算兩個方陣的人數(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)中判斷條件是否滿足要求，如果滿足要求，會進(jìn)行統(tǒng)計計數(shù)，當(dāng)滿足能夠變換12種隊形的時候輸出正確結(jié)果，并且結(jié)束循環(huán)。

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

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

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