高一信息科技复习.pptVIP

计算机的几种基本算法 解析算法 枚举算法 递推算法 排序算法 查找算法 计算机解析算法 （1）采用解析的方法找出反映求解问题的前提条件与求解结果之间关系的数学表达式，然后通过计算表达式的结果来实现问题的求解。 （2）解析算法经常采用赋值语句来实现计算功能。 计算机枚举算法 （1）对某类问题的求解方法可以充分利用计算机高速运算的优势，采用先列举出所有可能解，然后再对这些解进行逐个筛选，检验出真正符合条件的解方法称为枚举算法。 （2）枚举法的适用范围：需要例举的可能解的个数不能太多，必须在可以接受的时间范围内能求出所有的真正解。否则应采用更为有效的算法来解决问题。 （3）枚举算法的一般结构为：在循环结构中嵌套分支结构。其中循环结构用于“枚举”；分子结构用于“检验”。 计算机枚举算法练习 （1）（P.23 例4）在1～2008这些自然数中找出所有能被37整除的数来。 [文件名：找37的倍数] （2）在1～1000这些自然数中找出所有能被3和5整除的数来。 [文件名：找3和5的倍数] （3）在1～1000这些自然数中找出所有被3和5除都余2的数来。 [文件名：找相同余数的解] （4）在1～1000这些自然数中找出所有被3除余2、被5除余3的数来。 [文件名：找不同余数的解] （5）若有一个三位数满足: x=a3+b3+c3 （其中a、b、c分别是该三位数的百位、十位和个位数字），则称该三位数为水仙花数。请编程找出所有的水仙花数。 [文件名：找水仙花数] （6）一张单据上的5位数字为：1□□47，其千位数和百位数已经模糊不清，但知道这个5位数是57或67的倍数。现要求你设计一个算法，能输出所有满足这些条件的5位数，并统计出满足这些条件的5位数的个数。[文件名：找连续缺损的数字] （7）一张单据上的5位数字为：1□4□7，其千位数和十位数已经模糊不清，但知道这个5位数是肯定是57与67的倍数。现要求你设计一个算法，能输出所有满足这些条件的5位数，并统计出满足这些条件的5位数的个数，以协助判断该单据上的那个5位数。[文件名：找间隔缺损的数字] 双重循环知识要点 外层循环必须包含内层循环，不能交叉； 内外层循环的循环变量不能同名； 内层循环的变量值变化一轮，外层循环的变量值才变化一次； 双重循环的循环总次数为外层循环的循环次数和内层循环的循环次数之乘积。 （8）在一个直角三角形中，如果三条边的长度值都是整数，则称该三角形的三条边长值为勾股数。现要求通过文本框输入固定的一条直角边的长度值a，再通过文本框输入允许的最大斜边长度值c，请你找出满足这些条件的所有勾股数。 [文件名：求勾股数] （9）现有600个变形金刚需要包装，大盒每盒可包装15个变形金刚，小盒每盒可包装12个变形金刚。现在请你设计一个算法，输出所有可能的包装方案，并统计方案的总数。[文件名：包装方案] （10）今有鸡兔同笼，共有35个头，94只脚。请编程求出鸡兔各有几只。 [文件名：鸡兔同笼] （11）把100元人民币换成5元、1元和5角面值的人民币100张，请问有多少种换法，并给出每种换法的方案。请分别采用三重循环、双重循环、单重循环逐步优化来求解本题。[文件名：兑换钱币] （12）百鸡百钱问题：公鸡每只5元，母鸡每只3元，小鸡3只1元。现在用100元钱买100只鸡，请编程求出公鸡、母鸡、小鸡各有几只。 [文件名：百鸡百钱问题] （13）请求解1000以内的素数。[文件名：求素数] 计算机递推算法 （1）对某类问题的求解可以从问题给定的初始条件开始，根据一定的规律一步步推出问题的最终结果。这种方法称为递推算法。 （2）递推法的适用范围：适用于有规律可循的数据序列中数据项的求解或者存在迭代关系的数据序列中数据项的求解。 （3）递推算法的结构特点：一般来说递推算法多采用循环结构来求解问题。对于能预先知道循环次数的递推过程可采用计数循环方式，对不能预知循环次数的递推问题可采用当型循环或直到型循环方式加上标志控制来求解问题。 递推算法设计要点 （1）递推初始条件的设定 递推初始条件有时是问题本身直接给定的，有时则需要我们通过对问题进行分析和化简后得到。 递推算法设计要点 （2）递推公式的确定 正确确定递推公式是设计递推算法的关键。要正确分析出递推初始条件和最终求解结果之间的变化规律，并根据规律确定递推公式。 当问题求解的变化规律比较复杂时可能需要若干个递推公式来组合求解问题。 有些问题的求解可能会找到不同的变化规律，可以由不同的递推公式来求解问题，我们应尽量采用简化问题的算法，提高解题的效率。 递推算法设计要点 （3）循环次数的控制 对能预先知道循环递推次数的问题要特别注意正确控制循环次数，