用伪代码描述算法.pptx

第一章 如何用计算机解决问题第二节第二节 算法描述与设计算法描述与设计一、算法是“灵魂”1.算法存在于人们生活中，如：上街购物、顾客付款、营业员找银等。2.“韩信点兵问题”有不同的求解过程，就有不同的算法。3.算法解决问题的方法和步骤。算法是在有限步骤内求解某一问题所使用的一组定义明确的规则。通俗点说，就是计算机解就是计算机解题的过程题的过程。在这个过程中，无论是形成解题思路还是编写程序，都是在实施某种算法。前者是推理实现的算法，后者是操作实现的算法。4.算法的发现n n世界上最早的算法世界上最早的算法(P5)(P5)n n算法是尼克劳斯算法是尼克劳斯.沃斯（沃斯（N.WrithN.Writh提出的，他指出：）提出的，他指出：算法算法+数据结构数据结构=程序。程序。n n（即算法不能单独构成程序，它必须和数据结构合（即算法不能单独构成程序，它必须和数据结构合二为一）二为一）算法独立于任何具体的程序设计语言，一个算法独立于任何具体的程序设计语言，一个算法可以用多种程序设计语言来实现。算法可以用多种程序设计语言来实现。5-算法的特征算法的特征 算法要有一个清晰的起始步清晰的起始步，表示处理问题的起点，且每一个步骤只能有一个确定的只能有一个确定的后继步骤(1算法的确定性算法的确定性)，从而组成一个步骤的有限有限序列(2算法的有穷性算法的有穷性)；要有一个终止一个终止步步(序列的终止)表示问题得到解决或不能得到解决；每条规则必须是确定的、可行的(3算法的可行性算法的可行性)、不能存在二义性。算法总是对数据进行加工处理，因此，算法的执行过程中通常要有数据4 4输入输入(0个或多个个或多个)和数据5 5输出输出（至少一个）（至少一个）的步骤。n n(书书书书P6)P6)例：计算例：计算例：计算例：计算1+2+3+1+2+3+100=+100=？n n分析：计算这道题目的算法有限制范围，可以在有限时间内完成，分析：计算这道题目的算法有限制范围，可以在有限时间内完成，分析：计算这道题目的算法有限制范围，可以在有限时间内完成，分析：计算这道题目的算法有限制范围，可以在有限时间内完成，这是算法的第一个特征：这是算法的第一个特征：这是算法的第一个特征：这是算法的第一个特征：有穷性有穷性有穷性有穷性。计算时可以用纸笔、算盘、运。计算时可以用纸笔、算盘、运。计算时可以用纸笔、算盘、运。计算时可以用纸笔、算盘、运算器和计算机来完成，且计算过程是多样的，但结果是唯一的。这算器和计算机来完成，且计算过程是多样的，但结果是唯一的。这算器和计算机来完成，且计算过程是多样的，但结果是唯一的。这算器和计算机来完成，且计算过程是多样的，但结果是唯一的。这就是算法的就是算法的就是算法的就是算法的可行性、确定性可行性、确定性可行性、确定性可行性、确定性。n n计算方法：计算方法：计算方法：计算方法：把这把这把这把这100100个数按顺序相加。个数按顺序相加。个数按顺序相加。个数按顺序相加。用凑数法：用凑数法：用凑数法：用凑数法：1+99=1001+99=100，2+98=1002+98=100，3+97=1003+97=100，49+5149+51，最后只剩下，最后只剩下，最后只剩下，最后只剩下5050和和和和100100。计算机计算法：计算机计算法：计算机计算法：计算机计算法：令令令令S=0S=0，使，使，使，使1n1001n100，先执行，先执行，先执行，先执行S=S+n S=S+n，再执行，再执行，再执行，再执行n=n+1 n=n+1 n=1 n=1，S=0S=0时，时，时，时，S=1 n=2S=1 n=2，S=1S=1时，时，时，时，S=3 S=3 n=3n=3，S=3S=3时，时，时，时，S=6S=6n=4n=4，S=6S=6时，时，时，时，S=10 S=10 n=5n=5，S=10S=10时，时，时，时，S=15 n=6S=15 n=6，S=15S=15时，时，时，时，S=21S=21 n n算法的另外一个特征：算法的另外一个特征：算法的另外一个特征：算法的另外一个特征：输入、输出输入、输出输入、输出输入、输出。随时可以将程序改变：随时可以将程序改变：随时可以将程序改变：随时可以将程序改变：NN个连续数相加，个连续数相加，个连续数相加，个连续数相加，NN个奇数或偶数相加等个奇数或偶数相加等个奇数或偶数相加等个奇数或偶数相加等第一章 如何用计算机解决问题第二节第二节 算法描述与设计算法描述与设计 为了能更好地理解什么是算法，我为了能更好地理解什么是算法，我们利用日常生活中的们利用日常生活中的“打电话打电话”的例的例子来讨论。子来讨论。“打电话打电话”的过程。的过程。拿拿起起听听筒筒拨拨号号打不通打不通通了通了把听筒把听筒放下放下通话通话结束结束把听筒放下把听筒放下等会儿等会儿再拨再拨无人接听无人接听把听筒把听筒放下放下等会儿等会儿再拨再拨第一章 如何用计算机解决问题算法的概念：算法的概念：解决问题的方法和步解决问题的方法和步骤就是算法。骤就是算法。算法可以用多种方法来描述算法可以用多种方法来描述1 1、用自然语言来描述。、用自然语言来描述。2 2、用流程图来描述。、用流程图来描述。3 3、用伪代码描述算法。、用伪代码描述算法。1 1、用自然语言来描述。（书、用自然语言来描述。（书P6-P6-7 7）什么是自然语言。什么是自然语言。即用人们日常使用的语言和数即用人们日常使用的语言和数学语言描述的算法学语言描述的算法算法描述：算法描述：以以以以“韩信点兵问题韩信点兵问题韩信点兵问题韩信点兵问题”为例：为例：为例：为例：算法分析：算法分析：以以以以“韩信点兵问题韩信点兵问题韩信点兵问题韩信点兵问题”为例：为例：为例：为例：1、将、将N的初始值赋为的初始值赋为12、如果、如果N被被3、5、7整除后余数为整除后余数为2、3、2，则输出，则输出N的值，转入第的值，转入第4步步3、将、将N的值加的值加1，转到第，转到第2步步4、结束程序、结束程序书P7实践：若N=2，则密文与原文的对应关系是读入字符串的方法读入字符串的方法自然语言的优点：通俗易懂。自然语言的优点：通俗易懂。缺点：容易产生歧义。缺点：容易产生歧义。例如：例如：“这个人连老张也不认识这个人连老张也不认识这个人连老张也不认识这个人连老张也不认识”。意思之一：这个人不认识老张。意思之一：这个人不认识老张。意思之二：老张不认识这个人。意思之二：老张不认识这个人。2 2、用流程图来描述。、用流程图来描述。什么是流程图？（也称什么是流程图？（也称程序框图）它是算法的程序框图）它是算法的一种图形化表示方法。一种图形化表示方法。认识流程图符号认识流程图符号流程图的特点流程图的特点:与自然语言相比，用流程图描述与自然语言相比，用流程图描述算法形象、直观，更容易理解。算法形象、直观，更容易理解。1）用伪代码描述）用伪代码描述“韩信点兵问题韩信点兵问题”的算的算法法For I=1 to N if n能被能被3、5、7整除余数为整除余数为2、3、2 then 输出输出n end ifNext I3 3、用伪代码描述算法。、用伪代码描述算法。2 2)例如，判断一个四位数的年份是否为闰年。例如，判断一个四位数的年份是否为闰年。例如，判断一个四位数的年份是否为闰年。例如，判断一个四位数的年份是否为闰年。算法分析：算法分析：算法分析：算法分析：我们知道，如果我们知道，如果我们知道，如果我们知道，如果2 2月是月是月是月是2828天，则这一年是平年；如果是天，则这一年是平年；如果是天，则这一年是平年；如果是天，则这一年是平年；如果是2929天，则天，则天，则天，则这一年是闰年。判断闰年的条件是：如果该年份能被这一年是闰年。判断闰年的条件是：如果该年份能被这一年是闰年。判断闰年的条件是：如果该年份能被这一年是闰年。判断闰年的条件是：如果该年份能被4 4整除但不能整除但不能整除但不能整除但不能被被被被100100整除，或者能被整除，或者能被整除，或者能被整除，或者能被400400整除，则该年为闰年。整除，则该年为闰年。整除，则该年为闰年。整除，则该年为闰年。算法描述（伪代码）：算法描述（伪代码）：算法描述（伪代码）：算法描述（伪代码）：输入年份输入年份输入年份输入年份y yIF yIF y能被能被能被能被4 4整除整除整除整除 THENTHENIF y IF y 不能被不能被不能被不能被100100整除整除整除整除 THENTHEN输出输出输出输出“是闰年是闰年是闰年是闰年”ELSEELSEIF y IF y 能被能被能被能被400400整除整除整除整除 THENTHEN输出输出输出输出“是闰年是闰年是闰年是闰年”ELSEELSE输出输出输出输出“不是闰年不是闰年不是闰年不是闰年”END IFEND IFEND IFEND IFELSEELSE输出输出输出输出“不是闰年不是闰年不是闰年不是闰年”END IFEND IFn n使用伪代码描述算法没有严格的语法限制，使用伪代码描述算法没有严格的语法限制，书写格式也比较自由，只要把意思表达清书写格式也比较自由，只要把意思表达清楚就可以了，它更侧重于对算法本身的描楚就可以了，它更侧重于对算法本身的描述。述。n n在伪代码描述中，表示关键词的语句一般在伪代码描述中，表示关键词的语句一般用英文单词，其他语句可以用英文语句，用英文单词，其他语句可以用英文语句，也可以用汉语语句。也可以用汉语语句。伪代码的优缺点（书伪代码的优缺点（书P9P9）：）：用伪代码描述的算法简洁、易懂，用伪代码描述的算法简洁、易懂，修改起来也比较容易，并且很容修改起来也比较容易，并且很容易转化为程序语言代码。易转化为程序语言代码。缺点是不够直观。缺点是不够直观。练习：说出下面流程图的各框名称练习：说出下面流程图的各框名称开始框输入框处理框判断框处理框处理框处理框输出框结束框如果两个数有最大公约数如果两个数有最大公约数A，那么这两个数，以及这两个数的差，那么这两个数，以及这两个数的差，还有大数除以小数的余数，必然都是还有大数除以小数的余数，必然都是A的倍数。的倍数。所以当最后两个数刚好能整除时，较小的数就是最大公约数。所以当最后两个数刚好能整除时，较小的数就是最大公约数。1 1）什么是算法？）什么是算法？解决问题的方法和步骤就是算法解决问题的方法和步骤就是算法 小结小结：2 2）算法描述的方法有三种。）算法描述的方法有三种。用自然语言来描述用自然语言来描述用流程图来描述用流程图来描述用伪代码描述算法用伪代码描述算法 小结小结：