规模化问题的解题策略 【关键字】 规模化 策略 算法【摘要】 问题规模化是近来信息学竞赛的一个新趋势，它意在通过扩大数据量来增加算法设计和编程实现的难度，这就向信息学竞赛的选手提出了更高层次的要求，本文试图探究一些解决此类问题的普遍性的策略
开始，本文给出了“规模化〞一词的定义，并据此将其分为横向扩展和纵向扩展两种类型，分别进行论述
在探讨横向扩展问题的解决时本文是以谋划策略的“降维〞思想为主要对象的；而重点讨论的是纵向扩展问题的解决，先提出了两种策略——分解法和精简法，然后结合一个具体例子讨论“剪枝〞在规模化问题中的应用
问题规模化是信息学竞赛向实际运用靠拢的一个表达，因此具有不可无视的意义
【正文】一 引 论〔一〕背景分析分析近年来国际、国内中学生信息学竞赛试题，可以看出信息学竞赛对于选手的要求已经不再仅仅局限于“算法设计〞，它同时在编程实现方面加强了考察力度，由侧重于考察理论知识转向理论考察与实践考察并重
这一命题宗旨的转变，给信息学竞赛注入了新的机能，为命题者开拓了另一个领域
其一表达有：试题由精致型(这类试题的难度主要表达在精妙算法的构造，属于一点即通的类型)向规模型开展，从而使得问题的实现复杂化
〔二〕对“规模化〞的理解规模一词在字典中的含义是：事物所具有的格式、形式或范围
在信息学竞赛中，问题的规模具体是指待处理数据量的大小，通常可以通过一组规模参数(S1,S2,…, Sk)来表示
例如以下问题 1 的规模就是(100)，而问题 2 的规模是(100,100)
问题 1：求数列的前 100 项之和
问题 2：求 100*100 的矩阵中的各项之和
问题 3：求数列的前 1000 项之和
“规模化〞即扩展问题的规模，它具体是指增加规模参数的个数或扩大规模参数的数值范围
我们知道，假如撇开计算机的硬件、软件等环境因素，可以认为一个特定算法的“运行工作量〞的大小，只
