《主题一与算法零距离》由会员分享,可在线阅读,更多相关《主题一与算法零距离(46页珍藏版)》请在金锄头文库上搜索。
1、主题一 与算法零距离任务一 初识算法算法(Algorithm): 就是解决问题的方法和步骤算法初体验案例: 华罗庚先生在统筹方法一文中曾经描述了这样的场景:想泡壶茶喝,却发现没有开水,水壶要洗,茶壶、茶杯要洗,不过火已经生了,茶叶也有了。分析: 已有条件: 未洗的水壶、茶壶、茶杯 已生火,有茶叶 目的:泡茶喝思考: 如何设计工作次序才能尽快喝到茶呢?请你试一试。洗水壶烧水洗茶杯拿茶叶洗茶壶泡茶拖动文本框从上到下排列拖动文本框从上到下排列猜数字猜数字 甲同学在纸条上书写一个1000以内的整数,要求乙同学猜出具体数字。 (猜对数字用了多少次?)猜数字算法一、按顺序猜二、随机+记忆猜三、最佳算法为“
2、二分查找法”:猜想数据范围的中间数。任务二任务二 算法的表示算法的表示 P6p自然语言法自然语言法p流程图表示法流程图表示法p伪代码表示法伪代码表示法方法一:自然语言法 用人们日常使用的语言来描术算法。 在学习程序设计的初期或交流算法思想的时候经常使用。 用自然语言表示法对“猜数字”游戏中的算法描述如下:(1)根据题意,约定数据区域为1,1000,先计算区域的中间值,将中间值500作为第一次猜的数字。(2)如果提示信息为“低了”,说明正确解肯定大于猜想值,将数据区域修正为501,1000;如果提示信息为“高了”,说明正确解肯定小于猜想值,将数据区域修正为1,499。(3)计算区域的中间值,将中
3、间值作为一下次猜的数字。(4)应用前面(2)(3)的方法重复进行,直到猜出结果方法二:流程图表示法处理处理条件判断条件判断(流程的控制方向)(流程的控制方向)二二分分查查找找法法猜猜数数字字流流程程图图方法三:为代码表示法伪代码是介于自然语言和计算机程序设计语言之间的种算法描述。猜数字: 最小值1,最大值1000Repeat(重复) 中间值(最小值+最大值)整除2 猜数为中间值 获取提示 IF “高了” ,最大值中间值-1 IF “低了”,最小值中间值+1 IF “正确”,问题求解成功,程序结束案例2 一个人带了一只狼、一只羊和一个人带了一只狼、一只羊和一棵白菜想要过河。河上有一条独一棵白菜想
4、要过河。河上有一条独木船,每次除了人以外,只能带一木船,每次除了人以外,只能带一样东西。另外,如果人不在旁时,样东西。另外,如果人不在旁时,狼就要吃羊,羊就要吃白菜。问应狼就要吃羊,羊就要吃白菜。问应该怎样安排渡河,才能做到既把所该怎样安排渡河,才能做到既把所有东西都带过河,在河上来回的次有东西都带过河,在河上来回的次数又最少?数又最少?河算法一 先带羊到对岸再空船返回再带狼到对岸带羊返回留羊,带白菜到对岸空船返回最后带羊到对岸用计算机实现算法的过程 用计算机实现算法能够大大提高解决问题的效率和准确性。用计算机实现算法的过程调试程序程序设计语言的发展 电脑每做的一次动作,一个步骤,都是按照以经
5、用计算机语言编好的程序来执行的,程序是计算机要执行的指令的集合,而程序全部都是用我们所掌握的语言来编写的。所以人们要控制计算机一定要通过计算机语言向计算机发出命令。 程序设计语言的发展 计算机语言的种类非常的多,总的来说可以分成机器语言,汇编语言,高级语言三大类。 Visual C C#高级语言高级语言程序设计语言的发展机器语言机器语言 计算机所能识别的语言只有机器语言,即由0和1构成的代码 (二进制代码)。机器语言十进制数十进制数 二进制数二进制数0 001 012 103 114 1005 1016 1107 1118 1000程序设计语言的发展汇编语言: 汇编语言的实质和机器语言是相同的
6、,都是直接对硬件操作,只不过指令采用了英文缩写的标识符,更容易识别和记忆。 汇编语言示例START:IN AL,20H MOV BL,AL IN AL,30H MOV CL,AL MOV AX,0 ADLOP: ADD AL,BL ADC AH,0 DEC CL JNZ ADLOP HLT 程序设计语言的发展高级语言 : 高级语言是目前绝大多数编程者的选择。和汇编语言相比,它不但将许多相关的机器指令合成为单条指令,并且去掉了与具体操作有关但与完成工作无关的细节,大大简化了程序中的指令,编程者也就不需要有太多的专业知识。 程序设计语言的发展高级语言包括了很多编程语言,如:Basic语言 Visu
7、al Basic Pascal语言 Delphi C语言 C# Visual C+ C+Builder SQL语言 JSP ASP PHPJava 高级语言示例pprogram Gxp3;p var d1,d2,x,min:real;p beginpmin:=10000; x:=3;pwhile x15 do p beginp d1:=sqrt(9+(x+3)*(x-3);p d2:=sqrt(36+(15-x)*(15-x)p if (d1+d2)min then min:=d1+d2;p x:=x+0.001;p end;pwriteln(min:10:2);p end.思考:有一40千克
8、的铅块,把它分成4块(每块为整数重量),用这4块铅块作为天平称的砝码,可以称出1-40千克任何重量(整数重量)的物体,问:如何分割?注意:1.天平两边都可以放砝码。2.以上所有的数值均为整数,而不是小数。3.一次性称出重量,而不能分步称出,然后求其总和。 任务二 算法的表示自然语言法流程图表示法伪代码表示法解解一一元元二二次次方方程程算算法法流流程程图图真(是)真(是)假(否)假(否)人、羊、狼、白菜、船 用自然语言法和流程图法描述三种算法描述形式各有什么优缺点?算法的结构 算法的结构是指算法中各个处理步聚的执行次序和模式。 算法通常有三种结构:p 顺序结构p 选择结构p 循环结构顺序结构选择结构循环结构 请列举生活中和学习中属于顺序结构、选择结构、循环结构的实例,能否列出流程图?算法的性质有限性确定性可行性有0个或多个输入一定要有输出任务三 算法的评价算法的评价取数游戏轮次 数据(10个数)甲取数过程乙取数过程获胜者175 90 7 99 81 40 36 29 71 23275 90 64 14 48 59 90 17 70 51345双方对方案进行描述