计算机导论 指导教师:杨建国 二零零九年九月.

Presentation on theme: "计算机导论 指导教师:杨建国 二零零九年九月."— Presentation transcript:

1 计算机导论 指导教师:杨建国 二零零九年九月

2 思考 问题七：大学生如何提高实践能力？ 上课认真学 课后作业自己做（多看书多看网站多实践） 参加USRP、做老师的项目 培训 实习

3 李开复给程序员的七个建议 1.练内功：数据结构、算法、数据库、操作系统原理、计 算 机体系结构、计算机网络、离散数学等基础打实。
2.多实战：编程和调试并重。 3.求实干：一丝不苟、强烈的好奇心。 4.重视数学学习：离散数学、概率论、布尔代数、集合论和 数理逻辑。 5.培养团队精神：不能单打独斗、学会协作。 6.激励创新意识、培养好奇心、不要死记硬背：重要自己思 想的提高。 7.有策略的“打工”：实习机会也很重要。

4 贝贝，如果你一生可以做五个工作，你希望做哪五个工作
送给学生的话 它们需要哪些能力 贝贝，如果你一生可以做五个工作，你希望做哪五个工作 爱好、吃苦、认真、特长、乐观、交际 老师、省长、CEO、医生、记者

5 计算机算法 7.1 算法的发现 7.2 什么是算法 7.3 算法的表示 7.4 基本的算法
电子计算机，俗称电脑，是一种电子化的计算工具。在中国大陆也经常用计算机来指代电子计算机。就目前而言，电子计算机是根据预先设定好的程序来进行信息处理的一种设备。电子计算机分为巨型计算机（又称“超级计算机”）、大型计算机、中型计算机、小型计算机、微型计算机（简称“微机”，其中包括个人计算机，PC），已经逐步进入社会各个领域，尤其是进入了家庭和个人领域，极大地改变了社会的日常面貌。 从1930年代中期到1940年代后期，许多人在开发现代的、数字的、电子的，通用电子计算机。许多试验型的机器被造了出来并且可能是图灵完备化的。这些机器在当时都被宣称为第一台电子计算机，然而它们都只有有限的处理通用问题的能力，所以他们的设计最终都被抛弃了。 计算机发明于1946年。大约在1940—1942年间，在研制导弹的过程中，急需要有一种能迅速计算的工具，以便对导弹的飞行进行控制。在它偏离人所预测的轨道时，把它拉回到轨道上来。这样就产生了能在1／10秒或1／100秒的时间内计算出导弹运行轨迹同预定轨道的偏差的电子计算机。电子计算机不以十进位制进行计算，而是用二进位制计算的。它的出现是当代世界上最大的发明之一。第一台计算机的发明者是一位名叫冯·诺埃门的数学家。

6 推荐阅读：程序员2006.4《算法的力量》 内容简介 《算法导论(原书第2版)》一书深入浅出，全面地介绍了计算机算法。对每一个算法的分析既易于理解又十分有趣，并保持了数学严谨性。本书的设计目标全面，适用于多种用途。涵盖的内容有：算法在计算中的作用，概率分析和随机算法的介绍。本书专门讨论了线性规划，介绍了动态规划的两个应用，随机化和线性规划技术的近似算法等，还有有关递归求解、快速排序中用到的划分方法与期望线性时间顺序统计算法，以及对贪心算法元素的讨论。本书还介绍了对强连通子图算法正确性的证明，对哈密顿回路和子集求和问题的NP完全性的证明等内容。全书提供了900多个练习题和思考题以及叙述较为详细的实例研究。 　　《算法导论(原书第2版)》一书内容丰富，对本科生的数据结构课程和研究生的算法课程都是很实用的教材。本书在读者的职业生涯中，也是一本案头的数学参考书或工程实践手册。 　　在有关算法的书中，有一些叙述非常严谨，但不够全面，另一些涉及了大量的题材，但又缺乏严谨性。《算法导论》将严谨性和全面性融为一体。 　　《算法导论(原书第2版)》一书深入讨论各类算法，并着力使这些算法的设计和分析能为各个层次的读者接受。各章自成体系，可以作为独立的学习单元。算法以英语和伪代码的形式描述，具备初步程序设计经验的人就能看懂。说明和解释力求浅显易懂，不失深度和数学严谨性。 　　《算法导论(原书第2版)》一书自第1版出版以来，已经成为世界范围内广泛使用的大学教材和专业人员的标准参考书。第2版增加了论述算法作用、概率分析与随机算法、线性规划等几章。同时，对第1版的几乎每一节都作了大量的修订。一项巧妙而又重要的修改是提前引入循环不变式，并在全书中用来证明算法的正确性。在不改变数学和分析重点的前提下，作者将许多数学基础知识从第一部分移到了附录中，并在开始部分加入了一些富有诱导性的题材。 　★经典的算法书,被卓越网，《程序员》等评选为2006年最受读者喜爱的十大IT图书之一。 　★算法领域的标准教材，全球多所知名大学选用 　★MIT名师联手铸就，被誉为“计算机算法的圣经” 　★编写上采用了“五个一”，即一章介绍一个算法、一种设计技术、一个应用领域和一个相关话题。 作者简介 　　本书的四位作者均是算法领域的大师级人物，Thomas H. Cormen，Charles E. Leiserson和Ronald L. Rivest是MIT的教授，Clifford Stein是MIT的博士，现在哥伦比亚大学做教授，四人姓氏的首字母联在一起即是此书的非常酷的英文简称（CLRS 2e）。其中第三作者Ronald L. Rivest更是RSA算法的老大（算法名字里面的R即指他），并因此获得过图灵奖。 媒体推荐 书评 在有关算法的书中，有一些叙述非常严谨，但不够全面，另一些涉及了大量的题材，但又缺乏严谨性。《算法导论》将严谨性和全面性融为一体。 　　本书深入讨论各类算法，并着力使这些算法的设计和分析能为各个层次的读者接受。各章自成体系，可以作为独立的学习单元。算法以英语和伪代码的形式描述，具备初步程序设计经验的人就能看懂。说明和解释力求浅显易懂，不失深度和数学严谨性。 　　本书自第1版出版以来，已经成为世界范围内广泛使用的大学教材和专业人员的标准参考书。第2版增加了论述算法作用、概率分析与随机算法、线性规划等几章。同时，对第1版的几乎每一节都作了大量的修订。一项巧妙而又重要的修改是提前引入循环不变式，并在全书中用来证明算法的正确性。在不改变数学和分析重点的前提下，作者将许多数学基础知识从第一部分移到了附录中，并在开始部分加入了一些富有诱导性的题材。

7 一位商人有8枚银元，其中有1枚略轻的是假银元。姑娘您能用天平（不用砝码）将假银元找出来吗？
【面试真题一】 妈呀你管谁叫姑娘呢！人家是纯爷们儿！ 一位商人有8枚银元，其中有1枚略轻的是假银元。姑娘您能用天平（不用砝码）将假银元找出来吗？

8 还是出道题考考你吧！听好了！东方明珠大概要多少个乒乓球垒积起来？ 这叫什么题啊？这叫谁谁也回答不了！我……
【面试真题二】 还是出道题考考你吧！听好了！东方明珠大概要多少个乒乓球垒积起来？ 这叫什么题啊？这叫谁谁也回答不了！我……

9 源代码 【面试真题三】 把23、3、465、2、57、561、36、35 变成以下形式 的二维数组： 23 3 465 57 36 561
35 这是典型的桶排序算法， 假设有9个桶，每个桶里存放N个数字。桶应该是唯一的。 所以推出结论： 1。桶是唯一的（我们因此可以利用Hashtable的唯一性来做到）； 2。桶内成员可以不排序，因此可以利用数组或者Vector来做到； 3。Hashtable需要主键key来唯一标识，正好数字1~9是不重复的，是唯一的； 3。把每个数值的第一位取出来，以第一位值做为key找到hashtable中的相应vector，再将vector.addElements(该数值); 4。完成; 具体做法： 1.生成桶，9个桶，每个桶以数字1~9做为主键命名 Hashtable table=new Hashtable(); for(int i=1;i<10;i++){ Vector vector=new Vector(); table.put(new String(i), vector); } 2. 遍历每个数字，将当前数字的第一位分解出来，办法有很多种，比如除十法，这里介绍直接转字符串再取第一位法： 假设你的要处理的数字们放在数组里面int[] tmp; for(int i=0;i<tmp.length;i++){ int num=tmp[i]; String str=new String(num); char ch=str.charAt(0); //压入到桶里，先把想要的桶找到，利用主键 Vector vect=(Vector)table.get(""+ch); //找到桶后再把数值压到桶里 vect.addElements(new Integer(num)); } //取出来的时候，有多种方法，一种是利用key取出Vector,再遍历Vector，得到其中元素，元素的key为String, 内容为Integer 另一种方法是先遍历hashtable再遍历vector 同样的应用还有给一幅被洗过的扑克牌进行升或降排弃，因此可以建13个桶(A~K)，每个桶内的牌再按花色排序（相当于对Vector排序，也可以不用Vector而直接用数组或者ArrayList等等） 我看了你的修改提问，现回答如下： 即使不能使用java己经封装好的Hashtable类，自己也可以很轻易地利用代码编写出类似于Hashtable的集合类，用来包容其它对象，并以主键key来唯一标识. 如果你不想这样思考，那么直接用数组来实现桶排序也很方便，外层数组长度是固定的，即1~9共9个数组元素 Elements e=new Elements[9]。 这九个数组元素不是数字，必须是你自定义的类。并用这个类形成链表结构 比如： public class Element{ int data;//存数字 Element next=null;//下一个元素是谁 } 比如有数字 51,52,53 这三个数都是以5打头，那么他们应该放在一个桶里面，即第五号桶，也就是外层数组的第个元素中。 if( 判断该数字，是否应该放在5号桶){ Elements tmp=new Elements(); tmp.data=该数字; Elements current=e[4]; if(current==null){current=tmp;}//如果该桶以前从未放过数字，则放进去的就是头部，直接引用就行了，比如51应该放在头部 else{//如果该桶以前己经放过数字，如51,己经放了，现在放52。52就应该做为51的next元素，而53就是52的next就行了 while(current!=null){current=current.next;}//遍历，从而取到最后一个元素的引用 //取到最后一个元素后，current=tmp;即可,这样就形成了链表结构 } } 通过上述代表形成的结果是， 外层结构是9个元素组成的数组 每个数组元素是Elements类对象形成的链表结构,有头有层通过next字段串连起来。 如果要排序，只需要对每个链表内部进行排序就可以了 源代码

10 著名计算机科学家沃思（ Niklaus Wirth ）
程序=数据结构+算法 描述对数据的操作步骤 描述数据的类型、组织形式 著名计算机科学家沃思（ Niklaus Wirth ）

11 我也不知道，让我们去学习吧…… 程序的灵魂是什么？ 您真棒！ 三毛，计算机的灵魂是什么？ 软件的灵魂是什么 软件 程序 算法 海宝，算法的灵魂是什么？

12 7.1 算法的发现 算法（Algorithm）由九世纪数学家al-Khwarizmi的名字翻 译而来
它初期的概念是指解决问题或执行任务的确定的过程 1842年，Ada Byron为他设想的自动计算器写了世界上第 一个算法。但这算法未能被真正实现，因为Aba Byron未能 造出他的自动计算器 现代意义上的计算机算法的概念是在1936年Alan Turing 提 出现代计算机的基本模型图灵机之后才清晰起来 算法是解决问题或执行任务的过程；它能够一步一步地在 图灵机或等价的机器（如现代的计算机）上执行

13 小胖，很多网民还不懂程序与算法的关系，你说说
算法常常是用伪程序、自然语言、程序语言、硬件描述 由此可见，算法的本质是问题解决过程的概念，而相应 的程序只是一种它的表述 小胖，很多网民还不懂程序与算法的关系，你说说 程序就是算法的衣服，是其中衣服的一件

14 7.2 什么是算法 7.2.1 什么是算法 解决某一特定问题的一组有序的、明确的、可执行的、可终 止的步骤集合

15 7.2.2 算法特性 输入：有零个或多个 输出：至少一个 确定性：组成算法的每条指令清晰、无歧义 有限性：每条指令执行次数有限，执行每条指令的时间有限 可行性：算法是能行的 程序是算法用程序语言的具体实现，程序可以不满足有限性

16 7.2.3 算法的评价 正确性 健壮性 性能性（效率与低存储量） 可读性 扩充性 维护性

17 7.2.4 算法的复杂性计算 时间复杂性：与问题规模、算法输入及算法本身相关 的 操作次数的总和，常记为T（n） 渐进时间复杂性: 问题规模逐渐增大后时间复杂度的极 限形式 如果存在一个常数C>0，一个算法能够在Cn2的时间内处 理完规模大小为n的输入，则该算法的时间复杂性记为 O(n2)，称作n2级

18 7.2.5 算法的分类 数值运算算法、 非数值运算算法 串行算法、并行算法 确定性算法、随机算法 描述算法的方法：文字、图形（符号）

19 7.2.6 算法研究的典型问题 分类 排序 搜索（图片、视频） 遍历 集合运算

20 7.2.7 描述算法设计的一般过程

21 算法常用设计方法: 循环法 递归法 分治法 贪心法 动态规划 线性规划 搜索与枚举 启发式搜索

22 7.2.8 学习算法的方法 数学家的方法 工程师的方法 【典型例题】：货郎担问题 某售货员要到若干个城市销售货物，已知各城市之间 的距离，要求售货员选择出发的城市以及旅行路线，使每 个城市仅仅过一次，最后回到出发城市，而路程最短

23 7.3 算法的表示 7.3.1 为什么要设计算法表示 好好学习 好 读 书 不 好 读 书 不

24 7.3.2 带序号的自然语言描述 易懂却不直观，不严格 【例题】计算1到100的和 1. 0=>s单元 2. 1 => n单元 3. s+n =>s 4. n+1 =>n 5.判断n100？是，转3；否则转6 6.输出s的值

25 7.3.3 流程图－UML 灵活、自由、形象、直观，可表示任何算法 流程线 输入/输出 处理 判断 起止 连接点 【例题】计算1到100的和
开始 结束 0=>s 1=>n s+n =>s 输出s n+1=>n n100? T F 【例题】计算1到100的和

26 特点：完全去掉了带箭头的流程线，算法所有处理步骤 都写在一个大矩形框（表示简单、符合结构化思想）
7.3.4 N-S图（盒图） 特点：完全去掉了带箭头的流程线，算法所有处理步骤 都写在一个大矩形框（表示简单、符合结构化思想） A B P T F 处理 判断 循环 【例题】计算1到100的和 0=>s 1=>n n100? s+n =>s n+1=>n 输出s的值

27 7.4.5 伪代码 用介于自然语言与计算机语言之间的文字及符号来描述算法 方便、易懂、便于向计算机语言过渡 【例题】计算1到100的和 0=>s 1=>n if n100 s+n =>s n+1=>n print s

28 7.4.6 PAD图 P1 P2 C Pn P A 或 while c until c b 选择结构 d 循环结构 c 多选择结构
X=… Ln P A 或 while c until c 输入输出 重复 子算法 定义 选择 语句标号 处理

29 【例题】输入年份，判断该年是否为闰年 算法开始 算法结束 x {输入年份} x是400的倍数 或者 x是4的倍数但不是100的倍数 “x是闰年” “x不是闰年”

30 7.4 基本的算法 7.2.1 求和 【例题】1到100的奇数之和 #include <stdio.h> 这个程序对吗？
int main() { int i,sum=0; for (i=1;i<=100;i++) sum=sum+i; i=i+2; } printf("sum= %d \n",sum); 这个程序对吗？ #include <stdio.h> int main() { int i,sum=0; for (i=1;i<=100;) sum=sum+i; i=i+2; } printf("sum= %d \n",sum);

31 #include <stdio.h> 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); 这个程序对吗？ #include <stdio.h> int main() { int a=1,b=13,sum=0; for (;a<=b;) sum=sum+a+b; if(a==b) sum=sum-a; a=a+2; b=b-2; } printf("sum= %d \n",sum);

32 7.2.2 乘积 【面试真题】利用递归调用手段编程计算N！ #include <stdio.h> int main() { int i,n,sum=1; scanf("%d",&n); for (i=1;i<=n;i++) sum=sum*i; } printf("sum= %d \n",sum);

33 #include <stdio.h>
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;n>1;n--) val*=n; return val;

34 #include <stdio.h>
int main() { int n; int find(int n); scanf("%d",&n); printf("n!=%d \n",find(n)); } int find(int n) if(n==1) return 1; else return find(n-1)*n;

35 7.2.3 最大和最小 【面试真题】四个数从小到大输出来 #include <stdio.h> int main() {
int t,a,b,c,d; scanf("%d",&a); scanf("%d",&b); scanf("%d",&c); scanf("%d",&d); if(b>a) { t=a; a=b; b=t; } if(c>a) { t=a; a=c; c=t; } if(d>a) { t=a; a=d; d=t; } if(c>b) { t=b; b=c; c=t; } if(d>b) { t=b; b=d; d=t; } if(d>c) { t=c; c=d; d=t; } printf("%d,%d,%d,%d \n",a,b,c,d); }

36 7.2.4 排序 1.选择排序:先找一个最小的交换,然后在剩下的找最小的交换 【例题】把下列的数字从小到大排列:23,78,45,8,32,56 第一次: ８ 78 45 23 32 56 第二次: ８ 23 45 78 32 56 第三次: ８ 23 32 78 45 56 第四次: ８ 23 32 45 78 56 第五次: ８ 23 32 45 56 78

37 2.冒泡排序:依次比较相邻的两个数，将小数放在前面，大数 放在后面
【例题】把下列的数字从小到大排列:23,78,45,8,32,56 第一次: 23 45 8 32 56 78 第二次: 23 8 32 45 56 78 第三次: ８ 23 32 45 56 78 冒泡排序在最初被编写为将列表中最大元素“向下冒泡”，PPT是将最小元素“向上冒泡”，其实思想一样，PPT这样讲是为了方便与插入排序和选择排序相比较。 【思考】如果上面的例题每次找最小的排在前面，则每次 怎么排序？

38 3.插入排序:先取第一个,然后取第二个,把前面两个排序,然后
取第三个,把前三个排序,按照如此方法排序,就像插牌 【例题】把下列的数字从小到大排列:23,78,45,8,32,56 第一次: 23 78 45 8 32 56 第二次: 23 78 45 8 32 56 第三次: 23 45 78 8 32 56 第四次: ８ 23 45 78 32 56 第五次: ８ 23 32 45 78 56 第六次: ８ 23 32 45 56 78

39 4.快速排序： 5.堆排序： 6.希尔排序： 7.桶式排序： 8.合并排序： 9.基排序：

40 1.顺序查找:先从第一个数比较，然后第二个，直到相等
7.2.5 查找 1.顺序查找:先从第一个数比较，然后第二个，直到相等 【例题】找到62:4,21,36,14,62,91,8,22,7,81,77,10 第一次: 4 21 36 14 62 91 8 22 7 81 77 10 第二次: 4 21 36 14 62 91 8 22 7 81 77 10 第三次: 4 21 36 14 62 91 8 22 7 81 77 10 第四次: 4 21 36 14 62 91 8 22 7 81 77 10 第五次: 4 21 36 14 62 91 8 22 7 81 77 10

41 2.折半查找:数据有顺序。先从数中间比较，然后看是大了还 是小了，然后再找从中间到另一半的中间的数进行比较， 一直这样比较，直到找到
【例题】找到22:4,7,8,10,21,22,36,62,77,81,91 第一次: 4 7 8 10 21 22 36 62 77 81 91 第二次: 4 7 8 10 21 22 36 62 77 81 91 第三次: 4 7 8 10 21 22 36 62 77 81 91 第四次: 4 7 8 10 21 22 36 62 77 81 91

42 7.2.6 子算法 结构化编程的原则要将算法分成几个单元，称为子算法， 每个子算法又分为更小的子算法，如选择排序

43 7.2.7 递归 迭代：如果算法的定义没有包含算法本身 递归：如果算法的定义包含算法本身

44 作业题 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.用三种方法对下列数字排序：12，3，4，5，8，7，15， 9，10，1，11，14，6，13，2，请画出排序过程。 5.算法的灵魂是什么？ 6.用C语言写出选择排序、冒泡排序、插入排序、顺序查找 和折半查找的程序（选做）。

45 附录：编程典型例题 1.write a program that prompt the user to specify the size
of a t-shirt: S for small,M for medium,L for large and X for extra large.The prices are $10,$20,$30 and $40,respectively.Display the price of a chosen size. Eg. PromptString.java

46 2.write a program that displays even integer values from 1 to 20.
Eg. DisplayEven.java

47 3.输入一个华氏温度，要求输出摄氏温度。公式为c=5(F-32)/9，输出要求有文字说明，取2位小数。
Eg. DisplayTemperature.java

48 4.编写一个程序，输入a、b、c、d，输出其中最大者。
Eg. DisplayMax.java

49 5.有一函数 y= x (x<1) y= 2x-1 (1≤x<10) y= 3x-11 (x≥10) 写一程序输入输出值。

50 6. 打印出所有"水仙花数"，所谓"水仙花数"是指一个三位数，其各位数字立方和等于该本身。例如：153是一个水仙花数，因为153=1^3+5^3+3^3。

51 7.一个数如果恰好等于它的因子之和，这个数就称为"完数"。例如，6的因子为1、2、3，而6=1+2+3，因此6是"完数"。编程序找出1000之内的所有完数，并按下面格式输出其因子：6　its　factors　are　1、2、3 。

52 8.有一分数序列：2/1，3/2，5/3，8/5，13/8，21/13…求出这个数列的前20项之和。

53 9.一球从100米高度自由下落，每次落地后返回原高度的一半，再落下。求它在第10次落地时共经过多少米？第10次反弹多高？

54 10.猴子吃桃问题。猴子第一天摘下若干个桃子，当即吃了一半，还不过瘾，又多吃了一个。第二天早上又将剩下的桃子吃掉一半，又多吃一个。以后每天早上都吃了前一天剩下的一半零一个。到第10天早上想再吃时，见只剩下一个桃子了。求第一天共摘多少桃子。

55 11.打印以下图案 　　　　　* 　　　　 *** ***** ******* ***** *** *

56 12.编写一个程序，将100－200之间的素数打印出来。

57 13.编写一个程序，输入m、n，打印最小公倍数和最大公约数。

58 14.给一百分制，要求输出成绩等级‘A’、’B’、’C’、’D’、　’E’。90分以上为‘A’，80～89分为’B’，70～79分为’C’，60-69分为’D’，60分以下为’E’ 。

59 15.给定一个不多于５位的正整数，要求： 求它是几位数 分别打印出每一位数字 按逆序打印出各位数字，如原数为321，应输入123

60 16.输入４个整数，要求按由大到小的顺序输出。 Eg. DisplaySort.java

61 17.输入一行字符，分别统计出其中英文字母、空格、数字和其他字符的个数。

62 18.求Sn=a+aa+aaa+…+aaa…a（a的个数为n)之值，其中a是一个数字。例如2+22+222+2222+22222（此时n=5),n由键盘输入。

63

64

65 21.用公式　　　　　　求π 。

66 22.德国数学家:【哥德巴赫猜想】的验证 。 任一大于或等于６的偶数，总可分解为两个素数(质数)之和。 要求键盘输入一个不小于6的偶数N,然后输出6--N之间的这些哥德巴赫关系式:6=3+3,8=3+5,.....(每行输出一个式子)。 素数＝质数，判断素数的方法：用3与该数的平方根之间的所有奇数去除这个数，均不能被整除者，即为素数。

67 23.把一个两位的素数接到另外一个两位的素数后，得到一个四位数，而这个四位数可以被这两个素数之和的一半整除，求出所有这样的素数对。
两个素数不应相同 运行结果：53,13,47,19,43,23,37,29

68 24.(1)一框鸡蛋,每次取2、3、4、5、6个时分别剩下一个,每次取7个时不剩。问这框鸡蛋至少有多少个？
(2)一座七层宝塔，自上而下，每一层的灯都是上面一层灯的2倍，共有381盏灯。问每一层各有多少盏灯？

69 25.从小到大找出5个素数，使后面的数都比前面的数大12

70 26.打印出斐波纳契列前20个数，并计算它们的和。这个数列的特点是：第一个数为0，第二个数为1，第三个数是前二个数之和，以后的每个数都是它前面两个数之和，即：0，1，1，2，3，5，8，13……

71 27.找出1－99之间全部同构数。 同构数是这样一组数，它出现在平方数的右边 例如：5是25右边数，25是625右边的数，5和25都是同构数

72 28.输入一个字符，如果它是一个大写字母，则把它变成小写字母；如果它是一个小写字母，则把它变成大写字母；其它字符不变。

73 28.计算一元二次方程ax2+bx+c=0的根。

74 29.任意输入一年，判断是否是闰年。 闰年的条件是：能被4整除但不能被100整除的年是闰年，能被400整除的年也是闰年。

75 30.输入三角形三边，判断是否能组成三角形，若可以则输出它的面积和三角形的类型。

76 31.求一个整数任意次方的最后三位数，即求xy的最后三位数，要求x,y从键盘输入。