《解析与枚举算法PPT课件》由会员分享,可在线阅读,更多相关《解析与枚举算法PPT课件(11页珍藏版)》请在金锄头文库上搜索。
1、.,1,孙子算经中就记载了这样已个有趣的问题,书中是这样叙述的:“今有雉兔同笼,上有三十五头,下有九十四足,问雉兔各几何?”,设鸡有A只,兔有B只,则,A+B=35 2A+4B=94 A=(4*35-94)/2 B=(94-2*35)/2 Vb代码,.,2,解析算法,用解析的方法找出表示问题的前提条件与结果之间关系的数学表达式,并通过表达式的计算来实现问题求解。,.,3,.,4,枚举算法,按问题本身的性质,一一列举出该问题所有可能的解,并在逐一列举的过程中,检验每个可能的解是否是问题的真正解,若是,则采纳这个解,否则抛弃它。在列举的过程中,既不能遗漏,也不能重复。,.,5,一 一列举出所有可能
2、的解,(列举范围),检验每个可能的解是否是真正的解,(检验条件),重复模式 (循环结构),选择模式 (分支结构),循环嵌套分支,For 语句: for 循环变量=初值 to 终值 step 步长 语句块 next 循环变量,Do 语句: do while(until) 条件表达式 语句块 loop,.,6,今有雉兔同笼,上有三十五头,下有九十四足,问雉兔各几何?,分析:鸡有a只,兔有b只 列举范围:a:0,35 检验条件:2a+4b=94 Vb代码,.,7,将流程图补充完整:,开始,b= 35-a,Y,Y,N,N,输出 a、b,结束,将VB程序代码补充完整: Dim a as integer
3、Vb代码,0=a=35,A+b=94?,.,8,应用枚举算法,问题1:找出11000中所有能被7 和11整除的数。,分析: 列举范围:i:1,1000 检验条件:i能被7和11整除 (I mod 7=0 and I mod11=0),.,9,将流程图补充完整:,开始,i = 1,Y,Y,N,N,输出 i,i = i+1,结束,将VB程序代码补充完整: Dim i as integer i=1 练习1,i=1000?,i mod 7=0and i mod11=0?,.,10,应用枚举算法,问题2:一张单据上有一个5位数的号码,它的十位和个位数字已被涂抹的看不清,但知道这个5位数是37的倍数,设计一个算法,找出该单据可能的号码。,分析: 列举范围:n:12800,12899 检验条件:n是37的倍数 练习2,NO.128*,.,11,将流程图补充完整:,开始,结束,输出n,n=12800,将VB程序代码补充完整: Dim n as integer n=12800 练习2,Y,Y,N,N,n=12899?,n mod 37=0?,n = n+1,