历年noip普及组(c++)完善程序题总结材料归纳.doc

文档中的内容主要涉及两道编程题目，分别是关于“哥德巴赫猜测”的验证程序和“过河问题”的最短时间计算。下面是这两道题目的详细分析及知识点解析： 一、【哥德巴赫猜测】验证程序 这个程序的目的是验证哥德巴赫猜测，即验证所有大于2的偶数是否可以表示为两个质数之和。程序首先通过一个for循环找出小于或等于n的所有质数，然后遍历所有偶数，尝试将它们拆分为两个已找到的质数。 1. 知识点：质数判断。在`for(i=3;i<=n;i++)`循环中，使用了内层循环`for(j=1;j<=r;j++)`来判断i是否为质数，这是通过检查i是否能被已知的质数p[j]整除实现的。质数定义为只能被1和自身整除的正整数。 2. 优化：代码中的效率较低，因为每个偶数都与所有的质数进行配对检查，导致时间复杂度为O(n^3)。优化方法可以使用更高效的质数筛选算法如埃拉托斯特尼筛法先生成所有质数，然后进行匹配，降低时间复杂度。 3. 关键代码： - `tmp=1;` 初始化变量tmp为真，表示当前数i可能是质数。 - `p[j];` 当前质数 - `p[r]=j;` 将找到的新质数存入数组p中 - `p[j]+p[k]` 检查当前偶数是否能由两个已知质数之和构成 - `1004` 作为输出，表示当验证到2010时，所有大于2的偶数满足哥德巴赫猜测。 二、【过河问题】 这个问题是关于最小化所有人过独木桥所需总时间的优化问题。每两个人一起过桥时，时间取决于较慢者的速度。目标是找出一个方案，使得所有人都能过桥，且总时间最小。 1. 知识点：动态规划。此问题可以使用动态规划解决，定义状态表示当前有多少人位于左岸或右岸，以及灯在哪个岸。状态转移方程用于找出达到目标状态的最小时间。 2. 关键代码： - `num=0; ans=0;` 初始化人数和总时间 - `if(pos[i]==right)` 检查人是否在右岸 - `max(a, b)` 返回较大值，用于比较时间 - `go()` 函数用于递归地处理不同阶段的过桥情况 3. 解决策略：采用回溯或者动态规划方法，对于每一步操作（两人一起过桥或一人带灯返回），计算出新的状态和所需时间，选择最优解。 总结： 这两道题目涉及的编程知识点包括： - 质数判断和生成 - 优化算法的选择 - 动态规划解决问题 - 递归和回溯策略 - 空间和时间复杂度分析 在实际编程中，应注重算法的效率，选择合适的数据结构和算法来提高程序性能。对于这类问题，可以运用计算机科学的基本原理，结合数学和逻辑思维，设计出高效的解决方案。