经典算法1概要课件.ppt

1、任务：1.专业教育2.算法概述目标：通过算法的学习，能够理解很多概念；对以后的编程学习很有帮助；参加ACM 大赛作业：编写一个算法，“百鸡百钱”问题，查找什么是ACM 大赛 鸡翁一值钱五，鸡母一值钱三，鸡雏三值钱一。百钱买百鸡，问鸡翁、鸡母、鸡雏各几何？鸡翁一值钱五：公鸡五文一只，而现在百钱买百鸡（100文钱买鸡），所以公鸡数量要小于20，同理，母鸡数量要小于34，设公鸡x只，母鸡y只，小鸡z只，x+y+z=1005*x+3*y+1/3*z=100 且x，y，z为整数，所以可以得出正确答案，有三种情况 1.公鸡4只,母鸡18只,小鸡78只 2.公鸡8只,母鸡11只,小鸡81只 3.公鸡12只,

2、母鸡4只,小鸡84只 MicroSoft Visual Studio C+6.0 的使用程序代码及说明：1.注释 行注释和块注释2.编译预处理3.主程序一、void intreturn 0;二、不要把多个程序写在同一个项目中三、语句加分号；四、系统采用Visual C+6.0作业：1、鸡翁一值钱五，鸡母一值钱三，鸡雏三值钱一。百钱买百鸡，问鸡翁、鸡母、鸡雏各几何？2、输入三角形的三边长，求三角形面积（给定边长，使用秦九韶或海伦公式）3、求Fibonacci数列前40个数。这个数列有如下特点：第1，2两个数为1，1，从第三个数开始，该数是其前两个数之和。4、求一元二次方程的根：5、判断一个年份是

3、否是闰年程序的基本结构：程序的说明部分：预编译命令主函数 声明部分：执行部分：变量与数据类型 变量的基本概念 数据类型 定义变量和赋初值运算符、表达式、数学函数、赋值语句定义数据结构：数据类型：简单类型、复合（复杂）类型简单类型：简单类型有 int、float、double、char、bool复杂类型有：数组、结构类型、类语句：顺序语句、选择语句、循环语句顺序语句：赋值语句、输入语句、输出语句循环语句：循环记录次数选择语句：判断分支输入语句：cin输出语句：cout循环语句：for(i=1;i100;i+)int i,sum;i=1;sum=0;for(i=2;i=100;i+)sum=sum

4、+I;cout“sum=”sumendl;1.什么是计算机(硬件和软件)？2.计算机能够做什么？3.怎样做？4.软件工程思想计算机基础计算机基础 主要是包括二进制、操作系统(DOS、Windows)、信息处理工具（Word、C+)等典型算法典型算法 主要以算法为中心，讲解一些传统算法案例，通过案例掌握和理解以下内容：1.什么是算法 2.计算机能够做什么 3.算法都包含哪些类型 4.怎样描述算法 5.算法的特征 6.写算法应该注意哪些事情 7.计算机软件的本质（归结成计算）8.怎样学好计算机课程 9.一些常用的算法（案例）（大约30）计算机学习的难点（术语）简单会用一门语言C/C+1.什么是算法

5、 算法是计算机用来解决问题的步骤和方法，算法是软件的灵魂。计算机科学的定义：算法的学问，数据结构的转换2.计算机能够做什么：计算机本身处理能处理累加运算、逻辑运算；累加运算就是计算和循环、逻辑运算就是判断。从高级语言来看，目前如果能写成算法，并且算法里只包换存储操作（读写操作）、累加运算、逻辑运算，计算机就可以执行，至于计算机怎样认识这些语句，这得懂得计算机编译系统。3.算法都包含哪些类型：数学算法、计算机算法和某一专业算法（我们分别举例）4.怎样描述算法：自然语言传统流程图改进的流程图N-S图伪代码计算机语言 5.算法的特征 1)有穷性:有穷步骤后停止 2)确定性:必须有确切地定义 3)输入

6、 4)输出 5)可行性:算法是可行的，是可计算的6.写程序应该注意哪些事情程序设计规范（与建筑比较）：程序设计问题7.计算机软件的本质归结成计算8.怎样学好计算机课程9.一些常用的算法（案例）（大约30）程序设计=算法数据结构语言和环境编程的步骤如下：步骤一：理解问题所包含的意义（需要有专业知识、调研、查找）步骤二：把问题抽象为模型（建模过程、抽象成可计算的）步骤三：使用自然语言描述清晰（算法的5大特征）步骤四：画出改进的流程图或N-S图 如果画成N-S图一定是结构化程序设计（程序设计方法、注意流程图的画法）步骤五：改写成伪代码（赋值、输入、输出、条件语句、当循环、直到循环等）步骤六：定义数据

7、结构 不同的数据结构其算法不同步骤七：使用高级语言描述（源程序，写程序一定要规范*）步骤八：使用计算机运行程序(注意上机的步骤、程序优化)步骤九：写程序文挡写一程序，判断某一年是否为闰年步骤一：理解问题所包含的意义（调研、查找）按一回归年365天5小时48分45.5秒 首先知道什么是闰年步骤二：把问题抽象为模型能被4整除，但不能被100整除的是闰年能被100整除，同时被400整除的是闰年余下的年份不是闰年步骤三：使用自然语言描述清晰 E1设定检测年份 设定变量y为检测的年份 E2去掉不被4整除的年份若y不能被4整除，则输出y“不是闰年”。然后转到E6 E3 能被4整除，不能被100整除，则输出

8、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整除 print y：“是闰年”else if y被400整除 print y：“是闰年”else print y：“不是闰年”end if end if else print y：“不是闰年”end if yy+1

9、 END main()/*这是一个判断某一年份是否为闰年的程序*/int year;scanf(%d,&year);if(year%4=0)if(year%100=0)if(year%400=0)printf(%d is a leap year.n,year);else printf(%d is not a leap year.n,year);else printf(%d is a leap year.n,year);else printf(%d is not a leap year.n,year);步骤八：使用计算机运行程序（程序优化）上机步骤：选择一个语言系统比如：Visual C+等编辑

10、源程序编译或解释源程序为目标程序链接成可执行程序运行该程序循环语句：循环语句的三种形式：for循环；循环结束后i的值是多少？#includevoid 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=”sumend

11、l;break;强迫跳出本循环continue;结束本次循环，继续循环for()break;continue;数组：int a20;float b10;数组的初始化：int a5=0,1,2,3,4;从键盘上输入10个整数，并输出最小值；#includevoid main()int i,min,a;cout“input ten number:”endl;for(i=0;iai;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 Rk 则

13、kj （3）交换 若ik 则xRk RkRi Rix E2算法结束 步骤五：写成伪代码BEGINread（Rn）i1while i=n-1 kiji+1while jn if Rj Rk then kjjj+1 end if xRkRkRiRixii+1 print（Rn）END main()/*这是一个使用直接选择排序的排序算法*/int i,j,k,x;int r11;printf(input 10 numbers:n);for(i=1;i11;i+)/*调式程序*/scanf(%d,&ri);for(i=1;i11;i+)printf(%d,ri);i=1;while(i10)k=i;j

14、=i+1;while(j=10)if(rjrk)k=j;j=j+1;x=rk;rk=ri;ri=x;i=i+1;printf(n);printf(output 10 numbers:n);for(i=1;i11;i+)printf(%d,ri);为了方便，我们把算法分为数学算法，计算机算法和行业算法数学算法：关键怎样把数学公式变成数学表达式程序设计的三种结构：顺序结构、循环结构、分支结构顺序结构：主要用来赋值、输入输出循环结构：主要用于做重复运算分支结构：主要用于选择课后作业：1。书后P122。判断从2000年2100年的那些年份是闰年3。写出一个排序的例子4。求和1-1/2+1/3-1/10

15、0上机出现的问题：一、#include二、不要把两个文件写在一个文件中三、能读懂错误提示，包括错误和警告四、文件起名五、定义数据类型，如整型、双精度、数组一、编程的步骤二、定义数据结构三、程序设计的三种结构 中秋佳节，有贵客来到草原，主人要从羊群中选一只肥羊宴请宾客，当然要选最肥者，这样就要记录下每只羊的重量。数据类型：整型、浮点型字符类型：char A;运算符和表示式一、算术运算符、二、关系运算符 、=、=、!=三、逻辑运算符 !&（与）|（或）使用运算符连接起来的式子叫表达式有位同学中的一位做了好事，不留名，表扬信来了之后，校长问这位同学是谁做的好事。A说：不是我B说：是CC说：是DD说：

16、他胡说。已知个人说的是真话，一个人说的是假话。现在要根据这些信息，找出做好事的人。thisman 做了好事的人char thisman=;状态说的话关系表达式值Athisman!=AA!=A0Bthisman=CA=C0Cthisman=DA=D0Dthisman!=DA!=D1状态说的话关系表达式值Athisman!=AB!=A1Bthisman=CB=C0Cthisman=DB=D0Dthisman!=DB!=D1状态说的话关系表达式值Athisman!=AC!=A1Bthisman=CC=C1Cthisman=DC=D0Dthisman!=DC!=D1状态说的话关系表达式值Athisma

17、n!=AD!=A1Bthisman=CD=C0Cthisman=DD=D1Dthisman!=DD!=D0条件运算符：if(ab)?a:b;三目运算：表示式1？表示式2：表达式3 输入一个字符，判断它是否大写字母，如果是，将它转换成小写字母，如果不是，不转换。然后输出最后得到的字幅。#includevoid main()char ch;cinch;ch=(ch=A&ch=Z)?(ch+32):ch;cout结果是：chendl;switch语句,可以用于多分支选择语句。比如学分换算，比如成绩是A,对应分数是10085；成绩是B,对应分数是8470，成绩是C，对应分数是6960，成绩是D，对应分

18、数是60.#includevoid main()char grade;cingrade;switch(grade)caseA:cout10085endl;break;caseB:cout8470endl;break;caseC:cout6960endl;break;caseD:cout60endl;break;default:couterrorendl;百钱百鸡问题：100元买100只鸡，其中公鸡5元1只，母鸡3元1只，小鸡1元3只，要求每种鸡至少有1只，要求编写程序统计并输出所有购买方案。#include void main()int x,y,z;for(x=1;x20;x+)for(y=1

19、;y33;y+)for(z=1;z300;z+)if(x+y+z=100)&(15*x+9*y+z=300)cout“公鸡数”x“公鸡数”y“小鸡数”zendl;比如学分换算，比如成绩是A,对应分数是10085；成绩是B,对应分数是8470，成绩是C，对应分数是6960，成绩是D，对应分数是60.#includevoid main()char grade;cingrade;if(grade=A)cout10085endl;else if(grade=B)cout8470endl;else if(grade=C)cout6960endl;else if(grade=D)cout60endl;el

20、se cout“error”endl;二维数组:数组名下标下标int a34;a0 a00 a01 a02 a03a1 a10 a11 a12 a13a2 a20 a21 a22 a23 有一个3X4的距阵,要求编程序求出其中值最大的那个元素的值,以及其所在的行号和列号.1、输入三角形的三边长，求三角形面积（给定边长，使用秦九韶或海伦公式）2、求ax2+bx+c=0方程的解（求根公式）3、求Fibonacci数列前40个数。这个数列有如下特点：第1，2两个数为1，1，从第三个数开始，该数是其前两个数之和。4、题目：一个5位数，判断它是不是回文数。即12321是回文数，个位与万位相同，十位与千位

21、相 5、题目：一个整数，它加上100后是一个完全平方数，再加上168又是一个完全平方数，请问该数是多少？6、一个偶数总能表示为两个素数之和()（歌德巴赫猜想）7、打印水仙花数 13+53+33=153#includevoid main()long ge,shi,qian,wan,x;cinx;wan=x/10000;qian=x%10000/1000;shi=x%100/10;ge=x%10;if(ge=wan&shi=qian)/*个位等于万位并且十位等于千位*/cout“this number is a huiwen“endl;else coutthis number is not a h

22、uiwen1)要解决的问题-算法-定义数据结构-语言的描述-可执行程序-用户使用一、算法：建模过程 数学算法、计算机、行业算法 算法的特征：算法的描述：数学算法：把数学公式写成数学表达式、求和（项）、数论（分离数位）、输出位置和图形、枚举算法、递归算法、蒙特卡洛计算机算法：排序（选择、冒泡）行业算法：图书管理、学生成绩管理、学生定票二、语言或工具：对算法进行描述、程序设计方法C/C+标识符、变量、常量、表达式、语句数据的类型：int、float、double、char array struct三种程序设计结构：顺序、选择、循环三、可执行程序：调式、产品化、升级、维护、文档程序设计规范（向建筑学

23、习）：标识符的命名（起名规则）标识符包括文件名、变量名、函数名等（除保留字外）缩进（锯齿形状），括号要对齐注释：包括行注释、块注释和程序注释等程序设计问题：1具有健壮性（鲁棒性），使程序更加灵活2易于调试，加法和减法3优化程序设计#include#includevoid main()float a,b,c,s,area;cinabc);s=1.0/2*(a+b+c);if(a+b)c|(b+c)a|(a+c)b)coutLine is not Triangle“endl;else area=sqrt(s*(s-a)*(s-b)*(s-c);coutarea=“areaendl;#include

24、#include void main()float a,b,c,disc,x1,x2,realpart,imagpart;cinabc;coutThe equation;if(fabs(a)=1e-6)coutis not a quadratic;else disc=b*b-4*a*c;if(fabs(disc)=1e-6)couthas two equal roots“-b/(2*a)1e-6)x1=(-b+sqrt(disc)/(2*a);x2=(-b-sqrt(disc)/(2*a);couthas distinct real roots“x1x2endl;else realpart=-

25、b/(2*a);imagpart=sqrt(-disc)/(2*a);couthas complex roots:endl;coutrealpart“+”imagpart“i”endl;coutrealpart“-”imagpart“i”endl;#include#include void main()int a,b,c,d;cina;for(b=3;b=a/2;b+=2)for(c=2;csqrt(b)d=a-b;else break;for(c=2;csqrt(d)couta“=”b“+”d;算法类型:位置和图形例子1.输出杨辉三角形2.螺旋矩阵问题 思想和方法：首先计算出值，然后按位置输

26、出。题目：用*号输出字母C的图案。1.程序分析：可先用*号在纸上写出字母C，再分行输出。2.程序源代码：#include“iostream.h void main()cout*endl;cout*endl;cout*“endl;cout*)1)使用递归方法求n!1 (n=0,1)n!=n*(n-1)!(n1).数学公式写成数学表达式：算法思想；把数学公式写成数学表达式例子：求二元一次方程的根、求三角形面积、乘法口诀表等求和（项）：算法思想；先把求和的项定下来，然后求和例子：e、a+a2+a3+an+.数论：算法思想；使用筛发，或分离出数位例子：歌德巴赫猜想、求最大最小公约数、数的进制相互换算输

27、出位置和图形：算法思想；先计算出数值，然后在某一位置上输出结果例子：打印菱形图形、枚举算法：算法思想；在一定的范围区间里，求符合条件的结果例子：百鸡百钱问题、推理：算法思想；使用枚举方法，把给出的条件翻译成逻辑关系例子：排球占位问题：排球场的平面图如上图所示，其中，一，二，三，四，五，六为位置编号，二，三，四位置在前排，一，六，五位置在后排某女排队在开赛时于一，四位置放主攻手；二，五位置放二传手；三，六位置放副攻手队员所穿球衣号分别为，号可是每个队员的球衣号都与她们的位置号不同已知号，号队员不在后排；号，号队员不是二传手；号，号队员不在同一排；号，号队员不是副攻手；请编一个程序，推算出每个队员

28、的占位情况。递归算法：算法思想；把问题写成递推公式，即分段数学公式，然后使用语言描述例子：王小二自夸刀工不错，有人放一张大的煎饼在砧板上，问他：“饼不许离开砧板，切刀最多能分成多少块？”、n!实际问题：算法思想；把实际问题转化成数学或计算机方法例子：猜价格、找最重的羊、给选手打分排序问题：算法思想；通过比较把数据按递增或递减顺序排列例子：冒泡排序、交换排序难点：怎样把问题转化成对应的算法，剩下的就是编程经验例子：王小二自夸刀工不错，有人放一张大的煎饼在砧板上，问他：“饼不许离开砧板，切刀最多能分成多少块？”q(1)=1+1=2q(2)=1+1+2=4q(3)=1+1+2+3=7q(4)=1+1

29、+2+3+4=11q(n)=q(n-1)+4q(0)=1蒙特卡洛法（实验法）伪随机数的产生C/D=B/A=/4/1八皇后问题：八皇后问题是个相当经典的回溯问题：在一个8*8大小的棋盘上，在每排放一个皇后，要求改皇后的横竖斜排上没有其他的皇后，找出所有的可能性。（1）定义函数Try(i),用来试探放第i行上的皇后（2）讨论将第i行上的皇后放在j列位置的安全性，放在第i行只考虑来自列和对角线的攻击，定义q(i)=j表示第i行上的皇后放在第j列，让Cj=false，同时考虑通过（i,j）位置的两条对角线也就不安全了，可以令Li-j+9=false和Ri+j=false来表示在（i,j）位置放置皇后，

30、通过给位置的两条对角线上不安全了，这样得出了在（i,j）位置放皇后的安全条件是：nq=Cj&Li-j+9=false&Ri+j=false使用三个数组Cj、Lk、Rm（3）在放第i个皇后时候，选第j列，当nq为true时候，就可以将皇后放在（i,j）位置，这个时候做下面三件事情 放皇后qi=j;同时让第j列和过（i,j）位置的两条对角线变为不安全，即让Cj=false，Li-j+9=false，Ri+j=false 判断i是否为8，如果为8，让Num加1，输出该方案下8个皇后的位置;否则，没到8个，还要让皇后数i加1再试着放，这时还要递归调用Try(i+1)为了寻找不同的方案，当一个方案输出后

31、，要回溯，看看还有没有可能换一处放置，这时候将被拿起的皇后的所在位置的第j列的两条对角线回复安全。数字旋转方阵(1)size表示方阵的尺寸，size=N;(2)h表示行,v表示列；(3)begin表示每层的起始位置(4)number表示当前要填的数字1、第一个数字h=begin,v=begin,接下来可按填数的自然放向，先自上而下填A1块中的5个元素，这5个元素列号不变，行号加1；然后B1，这5个元素行号不变，列号加1；C1这5个元素列号不变，行号减1，D1这4个元素行号不变，列号减1；size*size的方阵填好后，就把问题变成对（size-2）*(size-2)的方阵去填，可以用递归的方法

32、编程，讨论size=0和size=1的边界条件，如果N为偶数，遇到size=0,退出递归函数，如果N为奇数，这时size=1,填上number,返回主函数。break语句和continue语句:continue语句的作用是结束本次循环，即跳过循环体下面尚未执行的语句，接着进行下一次是否执行循环的判定.break语句则是结束整个循环，不再判定执行循环的条件是否成立。例子：输出100到200之间能被3整除的奇数。#includevoid main()int n;for(n=100;n500;n+)if(n%2=0)continue;if(n%3=0&n=200)coutn200)break;伪代码

33、：伪代码（Pseudocode）是一种算法描述语言。使用伪代码的目的是为了使被描述的算法可以容易地以任何一种编程语言（Pascal，C，Java，etc）实现。因此，伪代码必须结构清晰、代码简单、可读性好，并且类似自然语言。介于自然语言与编程语言之间。C/C+的基本知识：概念：标识符、变量、常量、操作符(+、-、*、/、%、=、a;cout“good!”;选择语句：if(条件)语句块；else 语句块；循环结构 1、for（i=1;i=10;i+）循环体;2、while(条件)循环体;3、do 循环体;while(条件);#include void main()int x,y,z;for(x=

34、1;x20;x+)for(y=1;y33;y+)for(z=1;z300;z+)if(x+y+z=100)&(15*x+9*y+z=300)cout公鸡数x 母鸡数 y 小鸡数zendl;学好语言的秘笈，记住和语法有关的例子 Im beat。算法：1.什么是算法?2.计算机能够做什么?3.算法的特征?4.算法都包含哪些类型?5.怎样描述算法?6.写算法应该注意哪些事情?7.算法和程序设计的区别？8.程序设计的步骤？怎样描述算法：自然语言 改进的流程图 N-S图 伪代码 计算机语言问题：判断一个正整数是否是素数 S1:输入n的值 S2:i=2(i作为除数)S3:n被i除，得余数r S4:如果r=0表示n能被i整除，则打印n”不是素数”，算法结束；否则执行S5 S5:i=i+1;S6:如果i=n-1,返回S3；否则打印n”是素数”，然后算法结束。(其实条件i=n-1可以改成in;read(n)i=2;当 ik printf(“n是素数”)否则 printf(“n不是素数”)END#include#includevoid main()int n,i,k;cinn;k=sqrt(n);for(i=2;ik)coutn is a prime.endl;else coutn is not a prime.endl;