蓝桥杯竞赛真题——阅兵方阵

陈新龙

最近培训蓝桥杯竞赛题时，注意到一道难度适中的题目。这是一道来自第九届蓝桥杯Java组的国赛题目，今天就和大家分享一下解题的思路。

阅兵方阵：x国要参加同盟阅兵的活动。主办方要求每个加盟国派出的士兵恰好能组成2个方阵。x国发现弱小的y国派出了130人的队伍，他们的士兵在行进中可以变换2种队形。队形的变化：130=81+49=9*9+7*7和130=121+9=11*11+3*3两种方式。x国君很受刺激，觉得x国面积是y国的6倍，理应变出更多队形。于是他发号施令：我们要派出一支队伍，在行进中要变出12种队形！手下人可惨了，要忙着计算至少多少人才能组成12种不同的方阵。聪明的你可以利用计算机的优势帮助国君计算一下需要多少士兵吗？（不要失去信心，偷偷告诉你1105人可以组成四种队列了。）

首先就是理解题目，简单来说就是把一个数字拆分成两个数字，拆分的两个数字要进行平方根，平方根得出来的数字还需要是一个整数。例如数字41，可以拆成16和25，继续开平方根拆成4和5。

题目难点在于找一个可以拆分成12组符合条件的最小那个数字。依照惯例第一思路肯定是穷举法，将所有的可能全部罗列出来然后进行统计。虽然题目中已经给出了提示，1105就可以组成四种队列，那么想要组成12种队列，肯定会超过1105，我们暂时也不知道这个数字的下限，暂时先算到1000000停止，防止数字太小了算不出结果。

下面可以通过嵌套循环的方式来计算两个方阵的人数，外层的循环控制第一方阵的人数，内层的循环来控制第二方阵的人数。并做了一定优化，外循环判断第一方阵的人数是否超出了预期，如果已经超出了预期直接结束循环，内循环中判断条件是否满足要求，如果满足要求，会进行统计计数，当满足能够变换12种队形的时候输出正确结果，并且结束循环。

穷举法当然会消耗更多时间，你还可以对代码进行进一步的优化，优化的地方我已经标注出来给大家参考了。

当然同样算法用Scratch也能编写，在已经知道正确答案的情况下，将初始值设定为160220，免得浪费时间。设置第一方阵人数为1，设置第二方阵人数为总人数减第一方阵的平方，结合双重循环的方式进行统计计算将正确的结果输出在列表中。

通過这道题我们也可以发现，穷举法这种解题思路比较直观，易于理解，但是最大的缺点是运算量比较大，解题效率不高，在竞赛中，时间是有限的，竞赛的最终目标就是求出问题解，因此，如果题目的规模不是很大，在规定的时间与空间限制内能够求出解，那么最好是采用枚举法，而不需太在意是否还有更快的算法，这样可以使你有更多的时间去解答其他难题。当然也欢迎大家提出更好的解题思路进行分享。