「其实这种题目,用代码的方法也是可以做出来的。」
作为前世的程式设计师,用代码解决问题算是徐晓的职业习惯了。
像这种相对简单的问题,用代码似乎有些没有必要,但代码的好处就是具有较强的推广性,哪怕问题变得复杂,也同样可以使用类似的代码去解决。
只是高中数竞应该是不允许使用计算机的,这让徐晓的这项技能就显得有些没有用武之地了。
「当然,像刚才那道西洋棋的题目,我们也可以继续进行推广,比如说把车换成象丶马,或是皇后等等。
「因为这些问题的计算量太大,大家回去思考一下建模思路就可以,不需要计算出具体的结果。」
何慕舟当场便思考了起来,这其中,把车换成象的问题,相对来说要比较容易思考一些。
之前的车是横竖移动,可以使用二分图匹配的思路进行建模,而象沿斜线移动,同样可以用二分图的思路,只是需要再格外区分一下黑白格。
可是当把棋子换成皇后的话,问题就马上变得完全不同了。
因为皇后是既可以横竖移动,又可以沿斜线移动,这让问题的复杂程度直接提升了不只一个数量级。
思考了一会儿,何慕舟还是不得不将这些问题暂时搁置下来。
而另一边,徐晓已经在草稿纸上写出了每种问题的处理思路。
「皇后问题可以用算法思维逼近,写一个DFS搜索程序,再用剪枝优化就可以了。」
「马的话,就用图论着色的建模方式,属于四色定理的变体,代码应该也不难写。」
只可惜自己手头并没有电脑,要不然徐晓分分钟就能把这些问题都给算出来。
接下来的课程,徐晓基本上都能听得大差不差,能够跟得上钱峰的节奏。
虽然徐晓自认为自己的天赋一般,但至少在专注状态下,他还不至于被这些竞赛生给拉开差距。
这个时候,钱峰又在黑板上写下一道新的题目。
【设S是{1,2,...,2005}的一个子集,且S中任意两个不同的元素之和不被9整除。求S的最大可能元素个数。】
「这是一道竞赛原题,大家先看一下题,然后我讲一下解题思路。」