《经典算法1概要课件》由会员分享，可在线阅读，更多相关《经典算法1概要课件（83页珍藏版）》请在金锄头文库上搜索。
1、任务： 专业教育 算法概述 目标：通过算法的学习，能够理解很多概念；对以后的编程学习很有帮助；参加ACM 大赛 作业：编写一个算法，“百鸡百钱”问题 ， 查找什么是ACM 大赛,鸡翁一值钱五，鸡母一值钱三，鸡雏三值钱一。百钱买百鸡，问鸡翁、鸡母、鸡雏各几何？ 鸡翁一值钱五：公鸡五文一只，而现在百钱买百鸡（100文钱买鸡），所以公鸡数量要小于20，同理，母鸡数量要小于34， 设公鸡x只，母鸡y只，小鸡z只， x+y+z=100 5*x+3*y+1/3*z=100 且x，y，z为整数，所以可以得出正确答案， 有三种情况 1.公鸡4只,母鸡18只,小鸡78只 2.公鸡8只,母鸡11只,小鸡81只 3
2、.公鸡12只,母鸡4只,小鸡84只,MicroSoft Visual Studio C+ 6.0 的使用 程序代码及说明： 1. 注释 行注释和块注释 2. 编译预处理 3. 主程序,一、void int return 0; 二、不要把多个程序写在同一个项目中 三、语句加分号； 四、系统采用Visual C+6.0,作业： 1、鸡翁一值钱五，鸡母一值钱三，鸡雏三值钱一。百钱买百鸡，问鸡翁、鸡母、鸡雏各几何？ 2、输入三角形的三边长，求三角形面积（给定边长，使用秦九韶或海伦公式） 3、求Fibonacci数列前40个数。这个数列有如下特点：第1，2两个数为1，1，从第三个数开始，该数是其前两个数
3、之和。 4、求一元二次方程的根： 5、判断一个年份是否是闰年,程序的基本结构： 程序的说明部分： 预编译命令 主函数 声明部分： 执行部分： 变量与数据类型 变量的基本概念 数据类型 定义变量和赋初值,运算符、表达式、数学函数、赋值语句 定义数据结构： 数据类型： 简单类型、复合（复杂）类型简单类型： 简单类型有 int、float、double、char、bool 复杂类型有： 数组、结构类型、类 语句：顺序语句、选择语句、循环语句 顺序语句：赋值语句、输入语句、输出语句 循环语句：循环记录次数 选择语句：判断分支,输入语句： cin 输出语句： cout 循环语句： for(i=1;i10
4、0;i+) int i,sum; i=1; sum=0; for(i=2;i=100;i+) sum=sum+I; cout“sum=”sumendl;,什么是计算机(硬件和软件)？ 计算机能够做什么？ 怎样做？ 软件工程思想,计算机基础 主要是包括二进制、操作系统(DOS、Windows)、信息处理工具（Word、C+)等 典型算法 主要以算法为中心，讲解一些传统算法案例，通过案例掌握和理解以下内容： 1. 什么是算法 2. 计算机能够做什么 3. 算法都包含哪些类型 4. 怎样描述算法 5. 算法的特征 6. 写算法应该注意哪些事情 7. 计算机软件的本质（归结成计算） 8. 怎样学好计算
5、机课程 9. 一些常用的算法（案例）（大约30） 计算机学习的难点（术语） 简单会用一门语言C/C+,什么是算法 算法是计算机用来解决问题的步骤和方法，算法是软件的灵魂。 计算机科学的定义：算法的学问，数据结构的转换 2. 计算机能够做什么： 计算机本身处理能处理累加运算、逻辑运算；累加运算就是计算和循环、逻辑运算就是判断。从高级语言来看，目前如果能写成算法，并且算法里只包换存储操作（读写操作）、累加运算、逻辑运算，计算机就可以执行，至于计算机怎样认识这些语句，这得懂得计算机编译系统。,3. 算法都包含哪些类型：数学算法、计算机算法和某一专业算法（我们分别举例） 4. 怎样描述算法： 自然语言
6、 传统流程图 改进的流程图 N-S图 伪代码 计算机语言,5. 算法的特征 1) 有穷性:有穷步骤后停止 2) 确定性:必须有确切地定义 3) 输入 4) 输出 5) 可行性:算法是可行的，是可计算的,6.写程序应该注意哪些事情 程序设计规范（与建筑比较）： 程序设计问题 7.计算机软件的本质 归结成计算 8.怎样学好计算机课程 9. 一些常用的算法（案例）（大约30）,程序设计=算法数据结构语言和环境,编程的步骤如下： 步骤一：理解问题所包含的意义（需要有专业知识、调研、查找） 步骤二：把问题抽象为模型（建模过程、抽象成可计算的） 步骤三：使用自然语言描述清晰（算法的5大特征） 步骤四：画出
7、改进的流程图或N-S图 如果画成N-S图一定是结构化程序设计（程序设计方法、注意流程图的画法）,步骤五：改写成伪代码（赋值、输入、输出、条件语句、当循环、直到循环等） 步骤六：定义数据结构 不同的数据结构其算法不同 步骤七：使用高级语言描述（源程序，写程序一定要规范*） 步骤八：使用计算机运行程序 (注意上机的步骤、程序优化) 步骤九：写程序文挡,写一程序，判断某一年是否为闰年 步骤一：理解问题所包含的意义（调研、查找）按一回归年365天5小时48分45.5秒 首先知道什么是闰年 步骤二：把问题抽象为模型 能被4整除，但不能被100整除的是闰年 能被100整除，同时被400整除的是闰年 余下的
8、年份不是闰年,步骤三：使用自然语言描述清晰 E1设定检测年份 设定变量y为检测的年份 E2去掉不被4整除的年份若y不能被4整除，则输出y“不是闰年”。然后转到E6 E3 能被4整除，不能被100整除，则输出y“是闰年”，然后转到E6 E4 若y能被100整除，又能被400整除，则输出y“是闰年”，否则输出y“不是闰年”，然后转到E6 E5 不满足上述条件不是闰年输出y“不是闰年” E6 判断下一年是否是闰年y赋值 y+1，转向E2 E7 判断到2100年结束直到y大于2100，算法停止,步骤五：写成伪代码 BEGIN y2000 while y2100 if y被4整除 if y不被100整除
9、 print y：“是闰年” else if y被400整除 print y：“是闰年” else print y：“不是闰年” end if end if else print y：“不是闰年” end if yy+1 END,main() /*这是一个判断某一年份是否为闰年的程序*/ int year; scanf(“%d“, ,步骤八：使用计算机运行程序（程序优化） 上机步骤： 选择一个语言系统比如：Visual C+等 编辑源程序 编译或解释源程序为目标程序 链接成可执行程序 运行该程序,循环语句： 循环语句的三种形式： for循环； 循环结束后i的值是多少？ #include voi
10、d main() int i,sum=0 for(i=1;i=100;i+) sum=sim+i; cout“sum=”sumendl; while循环 i=1; while(i=100) sum=sum+i; i+; cout“sum=”sumendl;,作业：1.打印乘法口诀表 2.输入一行字符，分别统计出其中的英文字母、空格、数字和其他字符的个数。,do-while i=1; do sum=sum+i; i+; while(i=100); cout“sum=”sumendl; break; 强迫跳出本循环 continue;结束本次循环，继续循环 for( ) break; contin
11、ue; ,数组： int a20; float b10; 数组的初始化： int a5=0,1,2,3,4; 从键盘上输入10个整数，并输出最小值； #include void main() int i,min,a; coutai; min=a0; for(i=1;i10;i+) if(aimin) min=ai;,cout“min=”minendl; ,写一程序，：给定一系列数，按照数值（排序码）的不增或不减进行排序列称排序 步骤一：理解问题所包含的意义（调研、查找） 首先知道什么是排序，（排序码、升序、降序等） 步骤二：把问题抽象为模型 排序有多种方法，包括插入排序、选择排序等，最简单的方
12、法是选择排序，我们采用选择方法 选择方法如下：假定第一个数最小，记住第一个数，然后把第一个数和其余的数进行比较，如果有比这个数还小的数，就记住那个数。经过这一遍比较后就找到最小的数，把这个数和第一个数进行交换。然后从第二个数开始，重复以上步骤，直到剩下最后一个数为止。,步骤三：使用自然语言描述清晰 E1每循环一次，选择一个最小的排序循环 i以1为步长，从1到n-1，执行下列语句 （1）准备 ki （2）选择 循环 j以1为步长，从i+1到n,执行下列语句 若Rj k 则xRk RkRi Rix E2算法结束,步骤五：写成伪代码 BEGIN read（ Rn） i1 while i= n-1 k
13、i ji+1 while jn if Rj Rk then kj jj+1 end if xRk RkRi Rix ii+1 print （Rn） END,main()/*这是一个使用直接选择排序的排序算法*/ int i,j,k,x; int r11; printf(“input 10 numbers:n“); for(i=1;i11;i+) /*调式程序*/ scanf(“%d“, ,为了方便，我们把算法分为数学算法，计算机算法和行业算法 数学算法：关键怎样把数学公式变成数学表达式,程序设计的三种结构： 顺序结构、循环结构、分支结构 顺序结构：主要用来赋值、输入输出 循环结构：主要用于做重
14、复运算 分支结构：主要用于选择,课后作业： 1。书后P12 2。判断从2000年2100年的那些年份是闰年 3。写出一个排序的例子 4。求和1-1/2+1/3-1/100,上机出现的问题： 一、#include 二、不要把两个文件写在一个文件中 三、能读懂错误提示，包括错误和警告 四、文件起名 五、定义数据类型，如整型、双精度、数组,一、编程的步骤 二、定义数据结构 三、程序设计的三种结构,中秋佳节，有贵客来到草原，主人要从羊群中选一只肥羊宴请宾客，当然要选最肥者，这样就要记录下每只羊的重量。,数据类型：整型、浮点型 字符类型： char A; 运算符和表示式 一、算术运算符 、 二、关系运算
15、符 、=、=、!= 三、逻辑运算符 ! &（与） |（或） 使用运算符连接起来的式子叫表达式,有位同学中的一位做了好事，不留名，表扬信来了之后，校长问这位同学是谁做的好事。 A说：不是我 B说：是C C说：是D D说：他胡说。 已知个人说的是真话，一个人说的是假话。现在要根据这些信息，找出做好事的人。thisman 做了好事的人 char thisman= ;,条件运算符： if(ab)?a:b; 三目运算： 表示式1？表示式2：表达式3 输入一个字符，判断它是否大写字母，如果是，将它转换成小写字母，如果不是，不转换。然后输出最后得到的字幅。 #include void main() char ch; cinch; ch=(ch=A ,switch语句,可以用于多分支选择语句。 比如学分换算，比如成绩是A ,对应分数是10085；成绩是B,对应分数是8470，成绩是C，对应分数是6960，成绩是D，对应分数是 void main() char grade; cingrade; switch(grade) caseA: cout“10085“endl;break; caseB: cout“8470“endl;break; caseC: cout“6960“endl;break; caseD: cout“60“endl;break; default:cout“error“e
