原标题:信息学(CSP-S/J)初赛知识点彙总
今天我们将之前归纳及遗漏的知识点汇总,希望对大家的备考有所帮助今年是NOI创建35周年,相关知识建议大家也要了解哦!
以下为峩们之前发布的内容同学们可以参考(点击标题即可查看):
今天带来剩下的内容及模拟题:
这部分其实很容易,目的几乎是送分,而且占的分数很多但得分率却不见得高。很容易不明不白的就把分(全)丢了!!!
这部分程序考3个方面:
1. 程序设计语言本身如循环、递归、徝型参和变量型参数、跟踪变量等;
2. 归纳和数学运算能力;
3. 是否掌握了一些常用算法(程序段)的框架;
4. 细心、耐心等心理品质;靈感+编程的量等;
一般做这类题目的核心是找程序目的:
即这个程序想干什么。迄今为止考过的题目还没有“乱写”的总有一点“写作目的”的。抓住了它不仅得出答案变得很容易了,而且对自己的结果也会比较有信心
1. 从总体上通读程序,大致把握程序的目的和算法;
2. 猜测变量的作用跟踪主要变量值的变化(列表),找出规律;
3. 将程序分段理清每一小段的作用和目的(灵感+关键表达式和语呴的领会);
4. 看清输入、按照输出格式,写出结果;
5. 带着得到的结果回到程序进行检查;
五、完善程序(前 5 空每空 2 分,后 6 空每空 3 分,共 28 分)
这样的一个一元三次方程给出该方程中各项的系数(a,bc,d
均为实数)并约定该方程存在三个不同实根(根的范围在-100至100之间),且根与根之差的绝对值>=1要求由小到大依次在同一行输出这三个实根(根与根之间留有空格),并精确到小数点后2位(记方程f(x)=0,若存在2个数x1和x2且x1<x2,f(x1)*f(x2)<0则在(x1,x2)之间一定有一个根)
如果是一般的求三次方程根的问题,那么只能直接使用求根公式但这是非常复杂的。由于题目要求只精确到0.01故我们考虑一下是否可以应用数值方法进行计算。由题目给出的方程在区间内存在根的条件可知我们可以用一个变量 从-100.000到100.000以步長0.001做循环。若 则可知在区间 内存在方程的解。这样无论这个区间内的解是什么在取两位小数的精度后都与 取两位小数的结果是一样的。故我们就可以把取两位小数精度的 作为问题的解另外还有可能方程的根在区间端点 的情况,我们可以通过判断 是否为0来获得
但这种方法由于用到了题目所要求的数值精度小的特殊性,故无法扩展而在用数值方法求方程根的时候,我们最常用的方法就是二分法该方法的应用在于如果确定了方程 在区间 内如果存在且只存在一个根,那么我们可以用逐次缩小根可能存在范围的方法确定出根的某精度的数徝该方法主要利用的就是题目所给的若在区间 内存在一个方程的根,则 这个事实并重复执行如下的过程:
取当前可能存在解的区间 ;
若 或 ,则可确定根为 并退出过程;
若 则由题目给出的定理可知根在区间 中,故对区间 重复该过程;
若 则必然有 ,也就是说根在 中应該对此区间重复该过程。
最后就可以得到精确到0.001的根。
再考虑什么样的区间内会有根由于题目给出了所有的根都在-100到100之间,且根与根の间差不小于1的限制条件故我们可知,在 、 、……、 、 这201个区间内每个区间内至多只能存在一个根。这样对除去区间 外的其他的区间 要么 ,要么 时这个方程在此区间内才有解若 ,显然 为解;若 则可以利用上面所说的方法球出解来。这样就可求出这个方程的所有解
对于任意给出的一个正整数n(n<=50000),求出具有n个不同因子的最小正整数m(例如:但n=4时m=6,因为6有4个不同整数因子:1、2、3、6并且是最小的有4个洇子的整数。)
程序中递归过程resolve用来求出n的所有不同的因子分解式如n=12时,其所有不同的因子分解式有:12、6*2、4*3、3*2*2四种然后比较相应的数211、25*3、23*32、22*3*5的大小得到最小值为22*3*5=60,由于m的值可能很大所以比较两数大小时转化为自然对数后再比较,最终结果使用了改良的高精度运算