算法与数据结构

《算法与数据结构》由会员分享，可在线阅读，更多相关《算法与数据结构（91页珍藏版）》请在装配图网上搜索。

1、1华东理工大学计算机科学与工程系2023年年9月月22日日杨建国杨建国第第9章章 算法与数据算法与数据结结构构2华东理工大学计算机科学与工程系Really Achieving Your Childhood Dreams兰迪兰迪波许教授的最后一课波许教授的最后一课/Randy Pausch s Last Lecture/真真正实现你的童年梦想正实现你的童年梦想/人生的最后一堂课人生的最后一堂课/兰迪的最后一课兰迪的最后一课兰迪兰迪弗雷德里克弗雷德里克波许（波许（Randy Frederick Pausch）是美国卡内基梅隆大学的计算机科学、人机交互及）是美国卡内基梅隆大学的计算机科学、人机交互及

2、设计教授。设计教授。2006年年9月，他被诊断患有胰腺癌。尽管进行了手术和化疗，他还是于月，他被诊断患有胰腺癌。尽管进行了手术和化疗，他还是于2007年年8月被告知癌细月被告知癌细胞已经转移至肝臟及脾脏，至多可以再存活胞已经转移至肝臟及脾脏，至多可以再存活3到到6个月个月美国很多高校在资深教授退休前都会为他们安排讲授一堂面向全校学生的美国很多高校在资深教授退休前都会为他们安排讲授一堂面向全校学生的“最后一课最后一课”，表达学校师生，表达学校师生对其的崇敬和感激，让教授为自己的教学生涯划上一个完美的句号。卡内基梅隆大学将其命名为对其的崇敬和感激，让教授为自己的教学生涯划上一个完美的句号。卡内基梅

3、隆大学将其命名为“旅程旅程（Journey）”，希望演讲者能和听众一起分享自己的个人或学术旅程。波许虽然还没有准备退休，但是，希望演讲者能和听众一起分享自己的个人或学术旅程。波许虽然还没有准备退休，但是鉴于他的病情，他在鉴于他的病情，他在2007年年9月月18日做了题为：日做了题为：“真正实现你的童年梦想真正实现你的童年梦想”的最后一课，这也是的最后一课，这也是“旅程旅程”系系列的第一课列的第一课2007年年9月月21日，兰迪日，兰迪波许被波许被ABC世界新闻列为世界新闻列为“本周人物本周人物”，他也得到了国际媒体的关注。波许的，他也得到了国际媒体的关注。波许的“最后一课最后一课”成了互联网上

4、的热点，在发布一个月内被收看超过一百万次，他出版的最后一课一书则成了互联网上的热点，在发布一个月内被收看超过一百万次，他出版的最后一课一书则成为当前亚马逊网站上最为畅销的书籍之一成为当前亚马逊网站上最为畅销的书籍之一下载地址：下载地址：http:/www.simplecd.org/id/3199843华东理工大学计算机科学与工程系v问题问题九九：大学生如何工作？（组织能力、管理能力）：大学生如何工作？（组织能力、管理能力）（班干部、系院学校团委、社团、志愿者（班干部、系院学校团委、社团、志愿者）听说哥在大学听说哥在大学6个社团当官，个社团当官，我好崇拜哥我好崇拜哥不要崇拜哥，不要崇拜哥，哥是打

5、酱油的哥是打酱油的4华东理工大学计算机科学与工程系1.练内功：练内功：数据结构、算法、数据库、操作系统原理、计数据结构、算法、数据库、操作系统原理、计 算算 机体系结构、计算机网络、离散数学等基础打实。机体系结构、计算机网络、离散数学等基础打实。2.多实战：多实战：编程和调试并重。编程和调试并重。3.求实干：求实干：一丝不苟、强烈的好奇心。一丝不苟、强烈的好奇心。4.重视数学学习重视数学学习：离散数学、概率论、布尔代数、集合论和：离散数学、概率论、布尔代数、集合论和 数理逻辑。数理逻辑。5.培养团队精神：培养团队精神：不能单打独斗、学会协作。不能单打独斗、学会协作。6.激励创新意识、培养好奇心

6、、不要死记硬背：激励创新意识、培养好奇心、不要死记硬背：重要自己思重要自己思 想的提高。想的提高。7.有策略的有策略的“打工打工”：实习机会也很重要。实习机会也很重要。李开复给程序员的七个建议李开复给程序员的七个建议5华东理工大学计算机科学与工程系贝贝，如果你一贝贝，如果你一生可以做五个工生可以做五个工作，你希望做哪作，你希望做哪五个工作五个工作老师、省长、老师、省长、CEO、医生、记者医生、记者它们需要哪些能力它们需要哪些能力爱好、吃苦、认真、爱好、吃苦、认真、特长、乐观、交际特长、乐观、交际6华东理工大学计算机科学与工程系9.1 算法的发现算法的发现9.2 什么是算法什么是算法9.3 算法

7、的表示算法的表示9.4 基本的算法基本的算法9.5 数据结构数据结构算法与数据结构算法与数据结构7华东理工大学计算机科学与工程系推荐阅读：程序推荐阅读：程序员员2006.4算法算法的力量的力量8华东理工大学计算机科学与工程系【面试真题一面试真题一】一位商人有一位商人有8枚银元，其中有枚银元，其中有1枚略轻枚略轻的是假银元。姑娘您能用天平（不用的是假银元。姑娘您能用天平（不用砝码）将假银元找出来吗？砝码）将假银元找出来吗？妈呀你管谁叫妈呀你管谁叫姑娘呢！人家姑娘呢！人家是纯爷们儿！是纯爷们儿！9华东理工大学计算机科学与工程系【面试真题二面试真题二】还是出道题考考你吧！听还是出道题考考你吧！听好了

8、！东方明珠大概要多好了！东方明珠大概要多少个乒乓球垒积起来？少个乒乓球垒积起来？这叫什么题啊？这叫谁这叫什么题啊？这叫谁谁也回答不了！我谁也回答不了！我10华东理工大学计算机科学与工程系 把把23、3、465、2、57、561、36、35 变成以下形式变成以下形式的二维数组：的二维数组：23 3 465 57 2 36 561 35【面试真题三面试真题三】11华东理工大学计算机科学与工程系著名计算机科学家沃思（著名计算机科学家沃思（Niklaus Wirth）描述数据的类描述数据的类型、组织形式型、组织形式描述对数据描述对数据的操作步骤的操作步骤程序程序=数据结构数据结构+算法算法12华东理工

9、大学计算机科学与工程系三毛，计算机的灵魂是什么？三毛，计算机的灵魂是什么？软件软件程序程序算法算法软件的灵魂是什么软件的灵魂是什么程序的灵魂是什么程序的灵魂是什么？您真棒！您真棒！海宝，海宝，算法的灵算法的灵算法的灵算法的灵魂是什么？魂是什么？魂是什么？魂是什么？我也不知道，让我们去学习吧我也不知道，让我们去学习吧13华东理工大学计算机科学与工程系算法（算法（Algorithm）由九世纪数学家）由九世纪数学家al-Khwarizmi的名的名 字翻译而来字翻译而来它初期的概念是指它初期的概念是指解决问题解决问题或或执行任务执行任务的确定的过程的确定的过程1842年，年，Ada Byron为他设想

10、的自动计算器写了世界为他设想的自动计算器写了世界 上第一个算法。但这算法未能被真正实现，因为上第一个算法。但这算法未能被真正实现，因为Aba Byron未能造出他的自动计算器未能造出他的自动计算器现代意义上的计算机算法的概念是在现代意义上的计算机算法的概念是在1936年年Alan Turing 提出现代计算机的基本模型图灵机之后才清晰提出现代计算机的基本模型图灵机之后才清晰 起来起来算法是解决问题或执行任务的过程；它能够一步一步算法是解决问题或执行任务的过程；它能够一步一步 地在图灵机或等价的机器（如现代的计算机）上执行地在图灵机或等价的机器（如现代的计算机）上执行9.1 算法的发现算法的发现

11、14华东理工大学计算机科学与工程系算法常常是用算法常常是用伪程序伪程序、自然语言自然语言、程序语言程序语言、硬硬 件件描述描述由此可见，由此可见，算法的本质算法的本质是问题解决过程的概念，是问题解决过程的概念，而相应的程序只是一种它的表述而相应的程序只是一种它的表述小胖，很多网小胖，很多网民还不懂程序民还不懂程序与算法的关系，与算法的关系，你说说你说说程序就是算程序就是算法的衣服，法的衣服，是其中衣服是其中衣服的一件的一件15华东理工大学计算机科学与工程系1.什么是算法什么是算法解决某一特定问题的解决某一特定问题的一组一组有序有序的、的、明确明确的、的、可执行可执行 的、的、可终止可终止的步骤

12、集合的步骤集合9.2 什么是算法什么是算法p方法方法1：1+2，+3，+4，一直加到，一直加到100 加加99次次p方法方法2：100+(1+99)+(2+98)+(49+51)+50 =100+49100+50 加加51次次例：求例：求16华东理工大学计算机科学与工程系2.算法特性算法特性输入：有零个或多个输入：有零个或多个输出：至少一个输出：至少一个确定性：组成算法的每条指令清晰、无歧义确定性：组成算法的每条指令清晰、无歧义 有限性：每条指令执行次数有限，执行每条指令的有限性：每条指令执行次数有限，执行每条指令的 时间有限时间有限可行性：算法是能行的可行性：算法是能行的程序是算法用程序语言

13、的具体实现，程序可以不满程序是算法用程序语言的具体实现，程序可以不满 足有限性足有限性17华东理工大学计算机科学与工程系3.算法的评价算法的评价正确性正确性健壮性健壮性性能性（效率与低存储量）性能性（效率与低存储量）可读性可读性扩充性扩充性维护性维护性 为了有效地进行解题，不仅需要保证算法正确，还要为了有效地进行解题，不仅需要保证算法正确，还要考虑算法的质量，选择合适的算法。希望方法简单，运算考虑算法的质量，选择合适的算法。希望方法简单，运算步骤少步骤少18华东理工大学计算机科学与工程系4.算法的复杂性计算算法的复杂性计算时间复杂性时间复杂性：与问题规模、算法输入及算法本身相：与问题规模、算法

14、输入及算法本身相 关的操作次数的总和，常记为关的操作次数的总和，常记为T（n）渐进时间复杂性渐进时间复杂性：问题规模逐渐增大后时间复杂度问题规模逐渐增大后时间复杂度 的极限形式的极限形式如果存在一个常数如果存在一个常数C0，一个算法能够在，一个算法能够在Cn2的时的时 间内处理完规模大小为间内处理完规模大小为n的输入，则该算法的时间的输入，则该算法的时间 复杂性记为复杂性记为 O(n2)，称作，称作n2级级19华东理工大学计算机科学与工程系5.算法的分类算法的分类数值运算算法、数值运算算法、非数值运算算法非数值运算算法串行算法、串行算法、并行算法并行算法确定性算法、随机算法确定性算法、随机算法

15、描述算法的方法：文字、图形（符号）描述算法的方法：文字、图形（符号）20华东理工大学计算机科学与工程系6.算法研究的典型问题算法研究的典型问题分类分类排序排序搜索（图片、视频）搜索（图片、视频）遍历遍历集合运算集合运算21华东理工大学计算机科学与工程系7.描述算法设计的一般过程描述算法设计的一般过程22华东理工大学计算机科学与工程系算法常用设计方法算法常用设计方法:循环法循环法递归法递归法分治法分治法贪心法贪心法动态规划动态规划线性规划线性规划搜索与枚举搜索与枚举启发式搜索启发式搜索23华东理工大学计算机科学与工程系8.学习算法的方法学习算法的方法数学家的方法：数学家的方法：Dijkstra算

16、法、算法、A*算法等算法等工程师的方法工程师的方法:http:/theory.stanford.edu/amitp/GameProgramming/【典型例题典型例题】：货郎担问题：货郎担问题 某售货员要到若干个城市销售货物，已知各某售货员要到若干个城市销售货物，已知各城市之间的距离，要求售货员选择出发的城市以城市之间的距离，要求售货员选择出发的城市以及旅行路线，使每个城市仅仅过一次，最后回到及旅行路线，使每个城市仅仅过一次，最后回到出发城市，而路程最短出发城市，而路程最短24华东理工大学计算机科学与工程系9.3 算法的表示算法的表示1.为什么要设计算法表示为什么要设计算法表示25华东理工大学

17、计算机科学与工程系2.带序号的自然语言描述带序号的自然语言描述易懂却不直观，不严格易懂却不直观，不严格【例题例题】计算计算1到到100的和的和 1.0=s单元单元 2.1=n单元单元 3.s+n=s 4.n+1=n 5.判断判断n 100？是，转？是，转3；否则转；否则转6 6.输出输出s的值的值26华东理工大学计算机科学与工程系3.流程图流程图UML灵活、自由、形象、直观，可表示任何算法灵活、自由、形象、直观，可表示任何算法流程线流程线输入输入/输出输出处理处理判断判断起止起止连接点连接点【例题例题】计算计算1到到100的和的和开始结束0=s1=ns+n=s输出sn+1=nn100?TF27

18、华东理工大学计算机科学与工程系ABPTFAAPAP循环循环4.N-S图（盒图）图（盒图）特点：完全去掉了带箭头的流程线，算法所有处特点：完全去掉了带箭头的流程线，算法所有处 理步骤都写在一个大矩形框（表示简单、符合结理步骤都写在一个大矩形框（表示简单、符合结 构化思想）构化思想）处理处理判断判断【例题例题】计算计算1到到100的和的和0=s1=nn 100?s+n=sn+1=n输出输出s的值的值28华东理工大学计算机科学与工程系5.伪代码伪代码用介于自然语言与计算机语言之间的文字及符号来用介于自然语言与计算机语言之间的文字及符号来 描述算法描述算法方便、易懂、便于向计算机语言过渡方便、易懂、便

19、于向计算机语言过渡0=s1=nif n 100s+n=sn+1=nprint s【例题例题】计算计算1到到100的和的和29华东理工大学计算机科学与工程系b b 选择结构选择结构d d 循环结构循环结构c c 多选择结构多选择结构a a 顺序结构顺序结构P P1 1P P2 2CP P1 1P P2 2P Pn n L L1 1L L2 2 X=X=L Ln nP PA A或或while cwhile cuntil cuntil cP P1 1P P2 2输入输出输入输出重复重复子算法子算法定义定义选择选择语句标号语句标号处理处理6.PAD图图30华东理工大学计算机科学与工程系【例题例题】输入

20、年份，判断该年是否为闰年输入年份，判断该年是否为闰年算法开始算法开始算法结束算法结束x x 输入年份输入年份 x x是是400400的倍数的倍数 或者或者 x x是是4 4的倍数但不是的倍数但不是100100的倍数的倍数“x x是闰年是闰年”“x x不是闰年不是闰年”31华东理工大学计算机科学与工程系1.求和求和9.4 基本的算法基本的算法【例题例题】1到到100的奇数之和的奇数之和#include int main()int i,sum=0;for(i=1;i=100;i+)sum=sum+i;i=i+2;printf(sum=%d n,sum);这个程序这个程序对吗？对吗？32华东理工大学

21、计算机科学与工程系#include int main()int a=1,b=99,sum=0;for(;a=b;)sum=sum+a+b;a=a+2;b=b-2;printf(sum=%d n,sum);这个程序这个程序对吗？对吗？33华东理工大学计算机科学与工程系【面【面试题试题】百元百元钱买钱买百支笔百支笔问题问题（钢钢笔笔3元一支，元一支，圆圆珠笔珠笔2元一支，元一支，铅铅笔笔0.5元一支）。元一支）。问问：有哪些：有哪些购买购买方案？方案？34华东理工大学计算机科学与工程系2.乘积乘积【面试真题面试真题】利用递归调用手段编程计算利用递归调用手段编程计算N！#include int ma

22、in()int i,n,sum=1;scanf(%d,&n);for(i=1;i=n;i+)sum=sum*i;printf(sum=%d n,sum);35华东理工大学计算机科学与工程系#include int main()int n;int find(int i);scanf(%d,&n);printf(%d n,find(n);int find(int i)int n,val=1;for(n=i;n1;n-)val*=n;return val;36华东理工大学计算机科学与工程系#include int main()int n;int find(int n);scanf(%d,&n);pr

23、intf(n!=%d n,find(n);int find(int n)if(n=1)return 1;else return find(n-1)*n;37华东理工大学计算机科学与工程系3.最大和最小最大和最小【面试真题面试真题】四个数从小到大输出来四个数从小到大输出来#include int main()int t,a,b,c,d;scanf(%d,&a);scanf(%d,&b);scanf(%d,&c);scanf(%d,&d);if(ba)t=a;a=b;b=t;if(ca)t=a;a=c;c=t;if(da)t=a;a=d;d=t;if(cb)t=b;b=c;c=t;if(db)t=

24、b;b=d;d=t;if(dc)t=c;c=d;d=t;printf(%d,%d,%d,%d n,a,b,c,d);38华东理工大学计算机科学与工程系4.排序排序选择排序选择排序:先找一个最小的先找一个最小的交换交换,然后在剩下的找最然后在剩下的找最 小的小的交换交换【例题例题】把下列的数字从小到大排列把下列的数字从小到大排列:23,78,45,8,32,56第一次第一次:7845233256第二次第二次:2345783256第三次第三次:2332784556第四次第四次:2332457856第五次第五次:233245567839华东理工大学计算机科学与工程系冒泡排序冒泡排序:依次比较相邻的两

25、个数，将小数放在前依次比较相邻的两个数，将小数放在前 面，大数放在后面面，大数放在后面【例题例题】把下列的数字从小到大排列把下列的数字从小到大排列:23,78,45,8,32,56第一次第一次:23458325678第二次第二次:23832455678第三次第三次:2332455678【思考思考】如果上面的例题每次找最小的排在前面，如果上面的例题每次找最小的排在前面，则每次怎么排序？则每次怎么排序？40华东理工大学计算机科学与工程系插入排序插入排序:先取第一个先取第一个,然后取第二个然后取第二个,把前面两个排把前面两个排 序序,然后取第三个然后取第三个,把前三个排序把前三个排序,按照如此方法排

26、序按照如此方法排序,就像插牌就像插牌【例题例题】把下列的数字从小到大排列把下列的数字从小到大排列:23,78,45,8,32,56第一次第一次:23784583256第二次第二次:23784583256第三次第三次:23457883256第四次第四次:2345783256第五次第五次:2332457856第六次第六次:233245567841华东理工大学计算机科学与工程系快速排序：快速排序：堆排序：堆排序：希尔排序：希尔排序：桶式排序：桶式排序：合并排序：合并排序：基排序：基排序：42华东理工大学计算机科学与工程系5.查找查找顺序查找顺序查找:先从第一个数比较，然后第二个，直到相等先从第一个数

27、比较，然后第二个，直到相等【例题例题】找到找到62:4,21,36,14,62,91,8,22,7,81,77,10第一次第一次:第二次第二次:第三次第三次:第四次第四次:第五次第五次:42136146291822781771042136146291822781771042136146291822781771042136146291822781771042136146291822781771043华东理工大学计算机科学与工程系折半查找折半查找:数据有顺序。先从数中间比较，然后看数据有顺序。先从数中间比较，然后看 是大了还是小了，然后再找从中间到另一半的中间是大了还是小了，然后再找从中间到另一半

28、的中间 的数进行比较，一直这样比较，直到找到的数进行比较，一直这样比较，直到找到【例题例题】找到找到22:4,7,8,10,21,22,36,62,77,81,91第一次第一次:第二次第二次:第三次第三次:第四次第四次:478102122366277819147810212236627781914781021223662778191478102122366277819144华东理工大学计算机科学与工程系6.子算法子算法结构化编程的原则要将算法分成几个单元，称为结构化编程的原则要将算法分成几个单元，称为 子算法，每个子算法又分为更小的子算法，如选择子算法，每个子算法又分为更小的子算法，如选择 排

29、序排序45华东理工大学计算机科学与工程系7.递归递归迭代：如果算法的定义没有包含算法本身迭代：如果算法的定义没有包含算法本身递归：如果算法的定义包含算法本身递归：如果算法的定义包含算法本身46华东理工大学计算机科学与工程系9.5 数据结构数据结构47华东理工大学计算机科学与工程系重要的计算机专业课程重要的计算机专业课程重要的求职敲门砖重要的求职敲门砖重要的考研专业课程重要的考研专业课程程序设计竞赛核心课程程序设计竞赛核心课程它为操作系统、编译原理、数据库原理、软件工它为操作系统、编译原理、数据库原理、软件工 程程、图形学、图形学等后续课程的学习打下基础等后续课程的学习打下基础为什么学习为什么学

30、习数据结构数据结构48华东理工大学计算机科学与工程系进进程之程之间间就是用就是用链链表表结结构构内存分配就是用二叉平衡内存分配就是用二叉平衡树树键盘键盘的的输输入入、显显示器示器输输出就是用出就是用队队列列硬硬盘盘、内存内存、高速高速缓缓冲区切冲区切换换的的读读入就用到入就用到电电梯算法梯算法编译编译原理就用到很多原理就用到很多图图、栈栈数数组组到到处处都用都用异常异常结结构用到的异常构用到的异常链链文件索引用到的文件索引用到的B+树树高速高速缓缓冲区用到冲区用到hash 表表路由器就用到路由器就用到图图为什么学习为什么学习数据结构数据结构49华东理工大学计算机科学与工程系登录号：书名：作者名

31、：分类号：出版单位：出版时间：价格：书目卡片书目文件按书名按作者名按分类号索引表线性表例例1 书目自动检索系统书目自动检索系统为什么学习为什么学习数据结构数据结构50华东理工大学计算机科学与工程系树.例例2 人机对奕问题人机对奕问题51华东理工大学计算机科学与工程系 文件目文件目录间录间的的树树型关系型关系 例例3文件管理的树型结构文件管理的树型结构52华东理工大学计算机科学与工程系CEDABABACADBABCBDDADBDCEAEBECED图例例4多叉路口交通灯管理问题多叉路口交通灯管理问题53华东理工大学计算机科学与工程系A AB BH HI IG GC CE ED DF F181812

32、129 979795252565631311010858598986767212145458 83434（a a）城市距离图）城市距离图A AB BH HI IG GC CE ED DF F12129 979793131101021218 83434（b b）联通各城市最小生成树）联通各城市最小生成树例例5 多城市间最小距离问题多城市间最小距离问题54华东理工大学计算机科学与工程系例例6【八皇后【八皇后问题问题】高斯高斯1850年提出：在年提出：在88格的格的 国际象棋上摆放八个皇后，使其不能互相攻国际象棋上摆放八个皇后，使其不能互相攻 击，即任意两个皇后都不能处于同一行、同一击，即任意两个皇

33、后都不能处于同一行、同一 列或同一斜线上，问有多少种摆法列或同一斜线上，问有多少种摆法55华东理工大学计算机科学与工程系例例7【杨辉三角】【杨辉三角】第 1 行 1 1第 2 行 1 2 1 第 3 行 1 3 3 1第 4 行 1 4 6 4 156华东理工大学计算机科学与工程系以上所以上所举举例子中的数学模型正是数据例子中的数学模型正是数据结结构要构要讨讨论论的的问题问题。因此，。因此，简单简单地地说说，数据，数据结结构是一构是一门讨论门讨论描述描述现实现实世界世界实实体的体的数学模型数学模型(非数非数值计值计算算)及其上及其上的的操作操作在在计计算机中如何算机中如何表示和表示和实现实现的

34、学科。的学科。57华东理工大学计算机科学与工程系数据结构的研究内容数据结构的研究内容 数据的逻辑结构数据的逻辑结构 数据的存储结构数据的存储结构 数据的运算数据的运算：检索、排序、插入、删除、修改等：检索、排序、插入、删除、修改等 线性结构线性结构 非线性结构非线性结构 顺序存储顺序存储 链式存储链式存储 线性表线性表栈栈队队树形结构树形结构图形结构图形结构数据结构的三个方面：数据结构的三个方面：58华东理工大学计算机科学与工程系P1551.名名词词解解释释：算法、流程：算法、流程图图、数据、数据结结构构2.填空填空题题：（：（1）（）（10）3.选择题选择题：（：（1）（）（10）5.算法算

35、法设计题设计题：（：（5）、（）、（6）、（）、（7）59华东理工大学计算机科学与工程系1.编写一个程序，输入编写一个程序，输入m、n，打印最小公倍数和最大公约，打印最小公倍数和最大公约 数。用五种方法写出其算法的描述。数。用五种方法写出其算法的描述。2.试用递归的方法写一下计算菲波那契数列的通项试用递归的方法写一下计算菲波那契数列的通项f（n），），已知已知f1=1，f2=1，以后每项都是前两项的和。，以后每项都是前两项的和。3.用折半查找用折半查找1，2，3，4，5，6，7，8，9，10，11，12，13，14，15怎么找到怎么找到10，请画图表示查找过程。，请画图表示查找过程。4.用三种

36、方法对下列数字排序：用三种方法对下列数字排序：12，3，4，5，8，7，15，9，10，1，11，14，6，13，2，请画出排序过程。，请画出排序过程。5.算法的灵魂是什么？算法的灵魂是什么？6.用用C语言写出选择排序、冒泡排序、插入排序、顺序查找语言写出选择排序、冒泡排序、插入排序、顺序查找 和折半查找的程序（选做）。和折半查找的程序（选做）。60华东理工大学计算机科学与工程系1.write a program that prompt the user to specify the sizeof a t-shirt:S for small,M for medium,L for large a

37、nd X for extra large.The prices are$10,$20,$30 and$40,respectively.Display the price of a chosen size.Eg.PromptString.java61华东理工大学计算机科学与工程系2.write a program that displays even integer values from 1 to 20.Eg.DisplayEven.java62华东理工大学计算机科学与工程系3.输入一个华氏温度，要求输出摄氏温度。公式为输入一个华氏温度，要求输出摄氏温度。公式为c=5(F-32)/9，输出要求

38、有文字说明，取，输出要求有文字说明，取2位小数。位小数。Eg.DisplayTemperature.java63华东理工大学计算机科学与工程系4.编写一个程序，输入编写一个程序，输入a、b、c、d，输出其中最大者。，输出其中最大者。Eg.DisplayMax.java64华东理工大学计算机科学与工程系5.有一函数有一函数 y=x(x1)y=x(x1)y=2x-1(1x10)y=2x-1(1x10)y=3x-11(x10)y=3x-11(x10)写一程序输入输出值。写一程序输入输出值。65华东理工大学计算机科学与工程系6.打印出所有打印出所有水仙花数水仙花数，所谓，所谓水仙花数水仙花数是指一个三

39、是指一个三位数，其各位数字立方和等于该本身。例如：位数，其各位数字立方和等于该本身。例如：153是一个是一个水仙花数，因为水仙花数，因为153=13+53+33。66华东理工大学计算机科学与工程系7.一个数如果恰好等于它的因子之和，这个数就称为一个数如果恰好等于它的因子之和，这个数就称为 完完数数。例如，。例如，6 6的因子为的因子为1 1、2 2、3 3，而，而6=1+2+36=1+2+3，因此，因此6 6是是 完数完数。编程序找出。编程序找出10001000之内的所有完数，并按下面格式之内的所有完数，并按下面格式输出其因子：输出其因子：6 6itsitsfactorsfactorsarea

40、re1 1、2 2、3 3。67华东理工大学计算机科学与工程系8.有一分数序列：有一分数序列：2/12/1，3/23/2，5/35/3，8/58/5，13/813/8，21/1321/13求出求出这这个数列的前个数列的前2020项项之和之和。68华东理工大学计算机科学与工程系9.一球从一球从100100米高度自由下落，每次落地后返回原高度的米高度自由下落，每次落地后返回原高度的一半，再落下。求它在第一半，再落下。求它在第1010次落地次落地时时共共经过经过多少米？第多少米？第1010次反次反弹弹多高？多高？69华东理工大学计算机科学与工程系10.猴子吃桃问题。猴子第一天摘下若干个桃子，当即吃猴

41、子吃桃问题。猴子第一天摘下若干个桃子，当即吃了一半，还不过瘾，又多吃了一个。第二天早上又将剩了一半，还不过瘾，又多吃了一个。第二天早上又将剩下的桃子吃掉一半，又多吃一个。以后每天早上都吃了下的桃子吃掉一半，又多吃一个。以后每天早上都吃了前一天剩下的一半零一个。到第前一天剩下的一半零一个。到第1010天早上想再吃时，见天早上想再吃时，见只剩下一个桃子了。求第一天共摘多少桃子。只剩下一个桃子了。求第一天共摘多少桃子。70华东理工大学计算机科学与工程系11.打印以下图案打印以下图案*71华东理工大学计算机科学与工程系12.编写一个程序，将编写一个程序，将100200之间的素数打印出来。之间的素数打印

42、出来。72华东理工大学计算机科学与工程系13.编写一个程序，输入编写一个程序，输入m、n，打印最小公倍数和最大公，打印最小公倍数和最大公约数。约数。73华东理工大学计算机科学与工程系14.给一百分制，要求输出成绩等级给一百分制，要求输出成绩等级A、B、C、D、E。90分以上为分以上为A，8089分分为为B，7079分为分为C，60-69分为分为D，60分以分以下为下为E。74华东理工大学计算机科学与工程系15.给定一个不多于位的正整数，要求：给定一个不多于位的正整数，要求：求它是几位数求它是几位数分别打印出每一位数字分别打印出每一位数字按逆序打印出各位数字，如原数为按逆序打印出各位数字，如原数

43、为321，应输入，应输入12375华东理工大学计算机科学与工程系16.输入个整数，要求按由大到小的顺序输出。输入个整数，要求按由大到小的顺序输出。Eg.DisplaySort.java76华东理工大学计算机科学与工程系17.输入一行字符，分别统计出其中英文字母、空格、数输入一行字符，分别统计出其中英文字母、空格、数字和其他字符的个数。字和其他字符的个数。77华东理工大学计算机科学与工程系18.求求Sn=a+aa+aaa+aaaa（a的个数为的个数为n)之值，其中之值，其中a是一个数字。例如是一个数字。例如2+22+222+2222+22222（此时（此时n=5),n由由键盘输入。键盘输入。78

44、华东理工大学计算机科学与工程系79华东理工大学计算机科学与工程系80华东理工大学计算机科学与工程系21.用公式求用公式求。81华东理工大学计算机科学与工程系22.德国数学家德国数学家:【哥德巴赫猜想哥德巴赫猜想】的验证的验证。v任一大于或等于的偶数，总可分解为两个素数任一大于或等于的偶数，总可分解为两个素数(质数质数)之和。之和。v要求键盘输入一个不小于要求键盘输入一个不小于6的偶数的偶数N,然后输出然后输出6-N之间之间的这些哥德巴赫关系式的这些哥德巴赫关系式:6=3+3,8=3+5,.(每行输出一个每行输出一个式子式子)。v素数质数，判断素数的方法：用素数质数，判断素数的方法：用3与该数的

45、平方根之与该数的平方根之间的所有奇数去除这个数，均不能被整除者，即为素数。间的所有奇数去除这个数，均不能被整除者，即为素数。82华东理工大学计算机科学与工程系23.把一个两位的素数接到另外一个两位的素数后，得到把一个两位的素数接到另外一个两位的素数后，得到一个四位数，而这个四位数可以被这两个素数之和的一一个四位数，而这个四位数可以被这两个素数之和的一半整除，求出所有这样的素数对。半整除，求出所有这样的素数对。v两个素数不应相同两个素数不应相同v运行结果：运行结果：53,13,47,19,43,23,37,2983华东理工大学计算机科学与工程系24.(1)(1)一框鸡蛋一框鸡蛋,每次取每次取2

46、2、3 3、4 4、5 5、6 6个时分别剩下一个个时分别剩下一个,每次取每次取7 7个时不剩。问这框鸡蛋至少有多少个？个时不剩。问这框鸡蛋至少有多少个？(2)(2)一座七层宝塔，自上而下，每一层的灯都是上面一层一座七层宝塔，自上而下，每一层的灯都是上面一层灯的灯的2 2倍，共有倍，共有381381盏灯。问每一层各有多少盏灯？盏灯。问每一层各有多少盏灯？84华东理工大学计算机科学与工程系25.从小到大找出从小到大找出5 5个素数，使后面的数都比前面的数大个素数，使后面的数都比前面的数大121285华东理工大学计算机科学与工程系26.打印出斐波纳契列前打印出斐波纳契列前2020个数，并计算它们的

47、和。这个个数，并计算它们的和。这个数列的特点是：第一个数为数列的特点是：第一个数为0 0，第二个数为，第二个数为1 1，第三个数，第三个数是前二个数之和，以后的每个数都是它前面两个数之和，是前二个数之和，以后的每个数都是它前面两个数之和，即：即：0 0，1 1，1 1，2 2，3 3，5 5，8 8，13 13 86华东理工大学计算机科学与工程系27.找出找出1 19999之间全部同构数。之间全部同构数。v 同构数是这样一组数，它出现在平方数的右边同构数是这样一组数，它出现在平方数的右边v 例如：例如：5 5是是2525右边数，右边数，2525是是625625右边的数，右边的数，5 5和和25

48、25都是都是同构数同构数87华东理工大学计算机科学与工程系28.输入一个字符，如果它是一个大写字母，则把它变成输入一个字符，如果它是一个大写字母，则把它变成小写字母；如果它是一个小写字母，则把它变成大写字小写字母；如果它是一个小写字母，则把它变成大写字母；其它字符不变。母；其它字符不变。88华东理工大学计算机科学与工程系28.计算一元二次方程计算一元二次方程axax2 2+bx+c=0+bx+c=0的根。的根。89华东理工大学计算机科学与工程系29.任意输入一年，判断是否是闰年。任意输入一年，判断是否是闰年。v 闰年的条件是：能被闰年的条件是：能被4 4整除但不能被整除但不能被100100整除的年是闰整除的年是闰年，能被年，能被400400整除的年也是闰年。整除的年也是闰年。90华东理工大学计算机科学与工程系30.输入三角形三边，判断是否能组成三角形，若可以则输入三角形三边，判断是否能组成三角形，若可以则输出它的面积和三角形的类型。输出它的面积和三角形的类型。91华东理工大学计算机科学与工程系31.求一个整数任意次方的最后三位数，即求求一个整数任意次方的最后三位数，即求x xy y的最后三的最后三位数，要求位数，要求x,yx,y从键盘输入。从键盘输入。