《高一信息科技复习(精品).ppt》由会员分享，可在线阅读，更多相关《高一信息科技复习(精品).ppt（24页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、计算机的几种基本算法计算机的几种基本算法解析算法解析算法枚举算法枚举算法递推算法递推算法排序算法排序算法查找算法查找算法计算机解析算法计算机解析算法（1 1）采用解析的方法找出反映）采用解析的方法找出反映求解问题的前提条件与求解结求解问题的前提条件与求解结果之间关系的数学表达式，然果之间关系的数学表达式，然后通过计算表达式的结果来实后通过计算表达式的结果来实现问题的求解。现问题的求解。（2 2）解析算法经常采用赋值语）解析算法经常采用赋值语句来实现计算功能。句来实现计算功能。back计算机枚举算法计算机枚举算法（1）对某类问题的求解方法可以充分利用计算机）对某类问题的求解方法可以充分利用计算机
2、高速运算的优势，采用先列举出所有可能解，然高速运算的优势，采用先列举出所有可能解，然后再对这些解进行逐个筛选，检验出真正符合条后再对这些解进行逐个筛选，检验出真正符合条件的解方法称为枚举算法。件的解方法称为枚举算法。（2）枚举法的适用范围：需要例举的可能解的个）枚举法的适用范围：需要例举的可能解的个数不能太多，必须在可以接受的时间范围内能求数不能太多，必须在可以接受的时间范围内能求出所有的真正解。否则应采用更为有效的算法来出所有的真正解。否则应采用更为有效的算法来解决问题。解决问题。（3）枚举算法的一般结构为：在循环结构中嵌套）枚举算法的一般结构为：在循环结构中嵌套分支结构。其中循环结构用于分
3、支结构。其中循环结构用于“枚举枚举”；分子结；分子结构用于构用于“检验检验”。back计算机枚举算法练习计算机枚举算法练习（1）（）（P.23 例例4）在）在12008这这些自然数中找出所有能被些自然数中找出所有能被37整除整除的数来。的数来。文件名：找文件名：找37的倍数的倍数（2）在）在11000这些自然数中找出这些自然数中找出所有能被所有能被3和和5整除的数来。整除的数来。文件文件名：找名：找3和和5的倍数的倍数（3）在）在11000这些自然数中找这些自然数中找出所有被出所有被3和和5除都余除都余2的数来。的数来。文件名：找相同余数的解文件名：找相同余数的解（4）在）在11000这些自然
4、数中找这些自然数中找出所有被出所有被3除余除余2、被、被5除余除余3的数的数来。来。文件名：找不同余数的解文件名：找不同余数的解计算机枚举算法练习计算机枚举算法练习 计算机枚举算法练习计算机枚举算法练习（5）若有一个三位数满足）若有一个三位数满足:x=a3+b3+c3（其中（其中a、b、c分别是该三位数的分别是该三位数的百位、十位和个位数字），则称该百位、十位和个位数字），则称该三位数为水仙花数。请编程找出所三位数为水仙花数。请编程找出所有的水仙花数。有的水仙花数。文件名：找水仙花数文件名：找水仙花数计算机枚举算法练习计算机枚举算法练习（6）一张单据上的）一张单据上的5位数字为：位数字为：14
5、7，其千位数和百位数已经，其千位数和百位数已经模糊不清，但知道这个模糊不清，但知道这个5位数是位数是57或或67的倍数。现要求你设计一个的倍数。现要求你设计一个算法，能输出所有满足这些条件的算法，能输出所有满足这些条件的5位数，并统计出满足这些条件的位数，并统计出满足这些条件的5位数的个数。位数的个数。文件名：找连续文件名：找连续缺损的数字缺损的数字计算机枚举算法练习计算机枚举算法练习（7）一张单据上的）一张单据上的5位数字为：位数字为：147，其千位数和十位数已经模糊不清，但，其千位数和十位数已经模糊不清，但知道这个知道这个5位数是肯定是位数是肯定是57与与67的倍数。的倍数。现要求你设计一
6、个算法，能输出所有满现要求你设计一个算法，能输出所有满足这些条件的足这些条件的5位数，并统计出满足这位数，并统计出满足这些条件的些条件的5位数的个数，以协助判断该位数的个数，以协助判断该单据上的那个单据上的那个5位数。位数。文件名：找间隔文件名：找间隔缺损的数字缺损的数字双重循环知识要点双重循环知识要点 n n外层循环必须包含内层循环，不能外层循环必须包含内层循环，不能交叉；交叉；n n内外层循环的循环变量不能同名；内外层循环的循环变量不能同名；n n内层循环的变量值变化一轮，外层内层循环的变量值变化一轮，外层循环的变量值才变化一次；循环的变量值才变化一次；n n双重循环的循环总次数为外层循环
7、双重循环的循环总次数为外层循环的循环次数和内层循环的循环次数的循环次数和内层循环的循环次数之乘积。之乘积。计算机枚举算法练习计算机枚举算法练习（8）在一个直角三角形中，如果三）在一个直角三角形中，如果三条边的长度值都是整数，则称该三条边的长度值都是整数，则称该三角形的三条边长值为勾股数。现要角形的三条边长值为勾股数。现要求通过文本框输入固定的一条直角求通过文本框输入固定的一条直角边的长度值边的长度值a，再通过文本框输入允，再通过文本框输入允许的最大斜边长度值许的最大斜边长度值c，请你找出满，请你找出满足这些条件的所有勾股数。足这些条件的所有勾股数。文件名：求勾股数文件名：求勾股数计算机枚举算法
8、练习计算机枚举算法练习（9）现现有有600600个个变变形形金金刚刚需需要要包包装装，大大盒盒每每盒盒可可包包装装1515个个变变形形金金刚刚，小小盒盒每每盒盒可可包包装装1212个个变变形形金金刚刚。现现在在请请你你设设计计一一个个算算法法，输输出出所所有有可可能能的的包包装装方方案案，并并统统计计方方案案的的总总数数。文件名：包装方案文件名：包装方案 计算机枚举算法练习计算机枚举算法练习（10）今今有有鸡鸡兔兔同同笼笼，共共有有35个个头头，94只只脚脚。请请编编程程求求出出鸡鸡兔兔各各有几只。有几只。文件名：鸡兔同笼文件名：鸡兔同笼 计算机枚举算法练习计算机枚举算法练习（11）把把100
9、元元人人民民币币换换成成5元元、1元元和和5角角面面值值的的人人民民币币100张张，请请问问有有多多少少种种换换法法，并并给给出出每每种种换换法法的的方方案案。请请分分别别采采用用三三重重循循环环、双双重重循循环环、单单重重循循环环逐逐步步优优化化来来求求解解本本题题。文文件件名名：兑兑换换钱币钱币 计算机枚举算法练习计算机枚举算法练习（12）百百鸡鸡百百钱钱问问题题：公公鸡鸡每每只只5元元，母母鸡鸡每每只只3元元，小小鸡鸡3只只1元元。现现在在用用100元元钱钱买买100只只鸡鸡，请请编编程程求求出出公公鸡鸡、母母鸡鸡、小小鸡鸡各各有有几几只只。文件名：百鸡百钱问题文件名：百鸡百钱问题 计算
10、机枚举算法练习计算机枚举算法练习（13）请请求求解解1000以以内内的的素素数数。文件名：求素数文件名：求素数 back计算机递推算法计算机递推算法（1）对某类问题的求解可以从问题给定的初始条）对某类问题的求解可以从问题给定的初始条件开始，根据一定的规律一步步推出问题的最终件开始，根据一定的规律一步步推出问题的最终结果。这种方法称为递推算法。结果。这种方法称为递推算法。（2）递推法的适用范围：适用于有规律可循的数）递推法的适用范围：适用于有规律可循的数据序列中数据项的求解或者存在迭代关系的数据据序列中数据项的求解或者存在迭代关系的数据序列中数据项的求解。序列中数据项的求解。（3）递推算法的结构
11、特点：一般来说递推算法多）递推算法的结构特点：一般来说递推算法多采用循环结构来求解问题。对于能预先知道循环采用循环结构来求解问题。对于能预先知道循环次数的递推过程可采用计数循环方式，对不能预次数的递推过程可采用计数循环方式，对不能预知循环次数的递推问题可采用当型循环或直到型知循环次数的递推问题可采用当型循环或直到型循环方式加上标志控制来求解问题。循环方式加上标志控制来求解问题。递推算法设计要点递推算法设计要点（1）递推初始条件的设定）递推初始条件的设定 递推初始条件有时是问题本身直接给递推初始条件有时是问题本身直接给定的，有时则需要我们通过对问题进定的，有时则需要我们通过对问题进行分析和化简后
12、得到。行分析和化简后得到。递推算法设计要点递推算法设计要点（2）递推公式的确定）递推公式的确定n n正确确定递推公式是设计递推算法的关键。要正正确确定递推公式是设计递推算法的关键。要正确分析出递推初始条件和最终求解结果之间的变确分析出递推初始条件和最终求解结果之间的变化规律，并根据规律确定递推公式。化规律，并根据规律确定递推公式。n n当问题求解的变化规律比较复杂时可能需要若干当问题求解的变化规律比较复杂时可能需要若干个递推公式来组合求解问题。个递推公式来组合求解问题。n n有些问题的求解可能会找到不同的变化规律，可有些问题的求解可能会找到不同的变化规律，可以由不同的递推公式来求解问题，我们应
13、尽量采以由不同的递推公式来求解问题，我们应尽量采用简化问题的算法，提高解题的效率。用简化问题的算法，提高解题的效率。递推算法设计要点递推算法设计要点（3）循环次数的控制）循环次数的控制 n n对能预先知道循环递推次数的问题要特别注意正对能预先知道循环递推次数的问题要特别注意正确控制循环次数，应为它直接影响到递推结果的确控制循环次数，应为它直接影响到递推结果的正确与否；正确与否；n n对不能预先知道循环次数的问题要注意正确设置对不能预先知道循环次数的问题要注意正确设置好循环终止条件，再根据循环终止条件和问题求好循环终止条件，再根据循环终止条件和问题求解结果之间的关系正确获取问题的解。解结果之间的
14、关系正确获取问题的解。递推算法设计要点递推算法设计要点（1）递推初始条件的设定）递推初始条件的设定（2）递推公式的确定）递推公式的确定（3）循环次数的控制）循环次数的控制 back递推算法例题和练习递推算法例题和练习（1）请编程输出自然数奇数序列）请编程输出自然数奇数序列第第n项的值。项的值。文件名文件名:求奇数项值求奇数项值（2）求序列）求序列1，2，4，7，11，中第中第n项的值。项的值。文件名：求递增项值文件名：求递增项值递推算法例题和练习递推算法例题和练习（3）假设每对兔子出生假设每对兔子出生2 2个月后就个月后就可以每月生出可以每月生出1 1对小兔子。如果一月对小兔子。如果一月份出生
15、了份出生了1 1对小兔子，问一年后共有对小兔子，问一年后共有多少对小兔子？多少对小兔子？文件名文件名:兔子繁殖问题兔子繁殖问题（提示：可采用菲波那契数列递推求解）（提示：可采用菲波那契数列递推求解）递推算法例题和练习递推算法例题和练习（4）一只猴子采集了很多桃子。第一天一只猴子采集了很多桃子。第一天它吃了这些桃子的一半还多一个，第二天它吃了这些桃子的一半还多一个，第二天又吃了剩下桃子的一半还多一个，又吃了剩下桃子的一半还多一个，以后每天都是吃剩下桃子的一半还多一个，以后每天都是吃剩下桃子的一半还多一个，到第十天时还剩一个桃子了，问这个猴子到第十天时还剩一个桃子了，问这个猴子原来共采集了多少只桃
16、子。原来共采集了多少只桃子。文件名文件名:猴子吃桃子问题猴子吃桃子问题（提示：可采用倒递推循环（提示：可采用倒递推循环9 9次处理）次处理）递推算法例题和练习递推算法例题和练习（5）求任意输入的两个自然数的最求任意输入的两个自然数的最大公约数。大公约数。文件名：求最大公约数文件名：求最大公约数（提示：可采用辗转相除法递推处理）（提示：可采用辗转相除法递推处理）（6）求多项式求多项式 a an nx xn n+a+an-1n-1x xn-1n-1+a+an-2n-2x xn-2n-2+a+a1 1x+ax+a0 0的值。最高指数的值。最高指数n n的值、的值、x x的值的值和和各项各项系数系数的的值在程序运行后由键盘输入。值在程序运行后由键盘输入。文件名：求多项式值文件名：求多项式值（提示：可采用秦九韶变换后递推处理）（提示：可采用秦九韶变换后递推处理）