经典算法1概要.ppt

任务 专业教育算法概述目标 通过算法的学习 能够理解很多概念 对以后的编程学习很有帮助 参加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只 母鸡4只 小鸡84只 MicroSoftVisualStudioC 6 0的使用程序代码及说明 1 注释行注释和块注释2 编译预处理3 主程序 一 voidintreturn0 二 不要把多个程序写在同一个项目中三 语句加分号 四 系统采用VisualC 6 0 作业 1 鸡翁一值钱五 鸡母一值钱三 鸡雏三值钱一 百钱买百鸡 问鸡翁 鸡母 鸡雏各几何 2 输入三角形的三边长 求三角形面积 给定边长 使用秦九韶或海伦公式 3 求Fibonacci数列前40个数 这个数列有如下特点 第1 2两个数为1 1 从第三个数开始 该数是其前两个数之和 4 求一元二次方程的根 5 判断一个年份是否是闰年 程序的基本结构 程序的说明部分 预编译命令主函数声明部分 执行部分 变量与数据类型变量的基本概念数据类型定义变量和赋初值 运算符 表达式 数学函数 赋值语句定义数据结构 数据类型 简单类型 复合 复杂 类型简单类型 简单类型有int float double char bool复杂类型有 数组 结构类型 类语句 顺序语句 选择语句 循环语句顺序语句 赋值语句 输入语句 输出语句循环语句 循环记录次数选择语句 判断分支 输入语句 cin 输出语句 cout 循环语句 for i 1 i 100 i inti sum i 1 sum 0 for i 2 i 100 i sum sum I cout sum sum endl 什么是计算机 硬件和软件 计算机能够做什么 怎样做 软件工程思想 计算机基础主要是包括二进制 操作系统 DOS Windows 信息处理工具 Word C 等典型算法主要以算法为中心 讲解一些传统算法案例 通过案例掌握和理解以下内容 1 什么是算法2 计算机能够做什么3 算法都包含哪些类型4 怎样描述算法5 算法的特征6 写算法应该注意哪些事情7 计算机软件的本质 归结成计算 8 怎样学好计算机课程9 一些常用的算法 案例 大约30 计算机学习的难点 术语 简单会用一门语言C C 什么是算法算法是计算机用来解决问题的步骤和方法 算法是软件的灵魂 计算机科学的定义 算法的学问 数据结构的转换2 计算机能够做什么 计算机本身处理能处理累加运算 逻辑运算 累加运算就是计算和循环 逻辑运算就是判断 从高级语言来看 目前如果能写成算法 并且算法里只包换存储操作 读写操作 累加运算 逻辑运算 计算机就可以执行 至于计算机怎样认识这些语句 这得懂得计算机编译系统 3 算法都包含哪些类型 数学算法 计算机算法和某一专业算法 我们分别举例 4 怎样描述算法 自然语言传统流程图改进的流程图N S图伪代码计算机语言 5 算法的特征1 有穷性 有穷步骤后停止2 确定性 必须有确切地定义3 输入4 输出5 可行性 算法是可行的 是可计算的 6 写程序应该注意哪些事情程序设计规范 与建筑比较 程序设计问题7 计算机软件的本质归结成计算8 怎样学好计算机课程9 一些常用的算法 案例 大约30 程序设计 算法 数据结构 语言和环境 编程的步骤如下 步骤一 理解问题所包含的意义 需要有专业知识 调研 查找 步骤二 把问题抽象为模型 建模过程 抽象成可计算的 步骤三 使用自然语言描述清晰 算法的5大特征 步骤四 画出改进的流程图或N S图如果画成N S图一定是结构化程序设计 程序设计方法 注意流程图的画法 步骤五 改写成伪代码 赋值 输入 输出 条件语句 当循环 直到循环等 步骤六 定义数据结构不同的数据结构其算法不同步骤七 使用高级语言描述 源程序 写程序一定要规范 步骤八 使用计算机运行程序 注意上机的步骤 程序优化 步骤九 写程序文挡 写一程序 判断某一年是否为闰年步骤一 理解问题所包含的意义 调研 查找 按一回归年365天5小时48分45 5秒首先知道什么是闰年步骤二 把问题抽象为模型 能被4整除 但不能被100整除的是闰年 能被100整除 同时被400整除的是闰年 余下的年份不是闰年 步骤三 使用自然语言描述清晰E1 设定检测年份 设定变量y为检测的年份E2 去掉不被4整除的年份 若y不能被4整除 则输出y 不是闰年 然后转到E6E3 能被4整除 不能被100整除 则输出y 是闰年 然后转到E6E4 若y能被100整除 又能被400整除 则输出y 是闰年 否则输出y 不是闰年 然后转到E6E5 不满足上述条件不是闰年 输出y 不是闰年 E6 判断下一年是否是闰年 y赋值y 1 转向E2E7 判断到2100年结束 直到y大于2100 算法停止 步骤五 写成伪代码BEGINy 2000whiley 2100 ify被4整除ify不被100整除printy 是闰年 elseify被400整除printy 是闰年 elseprinty 不是闰年 endifendifelseprinty 不是闰年 endify y 1 END main 这是一个判断某一年份是否为闰年的程序 intyear scanf d 步骤八 使用计算机运行程序 程序优化 上机步骤 选择一个语言系统比如 VisualC 等编辑源程序编译或解释源程序为目标程序链接成可执行程序运行该程序 循环语句 循环语句的三种形式 for循环 循环结束后i的值是多少 includevoidmain inti sum 0for i 1 i 100 i sum sim i cout sum sum endl while循环i 1 while i 100 sum sum i i cout sum sum endl 作业 1 打印乘法口诀表2 输入一行字符 分别统计出其中的英文字母 空格 数字和其他字符的个数 do whilei 1 do sum sum i i while i 100 cout sum sum endl break 强迫跳出本循环continue 结束本次循环 继续循环for break continue 数组 inta 20 floatb 10 数组的初始化 inta 5 0 1 2 3 4 从键盘上输入10个整数 并输出最小值 includevoidmain inti min a cout a i min a 0 for i 1 i 10 i if a i min min a i cout min min endl 写一程序 给定一系列数 按照数值 排序码 的不增或不减进行排序列称排序步骤一 理解问题所包含的意义 调研 查找 首先知道什么是排序 排序码 升序 降序等 步骤二 把问题抽象为模型 排序有多种方法 包括插入排序 选择排序等 最简单的方法是选择排序 我们采用选择方法 选择方法如下 假定第一个数最小 记住第一个数 然后把第一个数和其余的数进行比较 如果有比这个数还小的数 就记住那个数 经过这一遍比较后就找到最小的数 把这个数和第一个数进行交换 然后从第二个数开始 重复以上步骤 直到剩下最后一个数为止 步骤三 使用自然语言描述清晰E1 每循环一次 选择一个最小的排序 循环i以1为步长 从1到n 1 执行下列语句 1 准备 k i 2 选择 循环j以1为步长 从i 1到n 执行下列语句若R j k则x R k R k R i R i xE2 算法结束 步骤五 写成伪代码BEGINread R n i 1whilei n 1 k ij i 1whilej n ifR j R k thenk jj j 1endif x R k R k R i R i xi i 1 print R n END main 这是一个使用直接选择排序的排序算法 inti j k x intr 11 printf input10numbers n for i 1 i 11 i 调式程序 scanf d 为了方便 我们把算法分为数学算法 计算机算法和行业算法数学算法 关键怎样把数学公式变成数学表达式 程序设计的三种结构 顺序结构 循环结构 分支结构顺序结构 主要用来赋值 输入输出循环结构 主要用于做重复运算分支结构 主要用于选择 课后作业 1 书后P122 判断从2000年 2100年的那些年份是闰年3 写出一个排序的例子4 求和1 1 2 1 3 1 100 上机出现的问题 一 include二 不要把两个文件写在一个文件中三 能读懂错误提示 包括错误和警告四 文件起名五 定义数据类型 如整型 双精度 数组 一 编程的步骤二 定义数据结构三 程序设计的三种结构 中秋佳节 有贵客来到草原 主人要从羊群中选一只肥羊宴请宾客 当然要选最肥者 这样就要记录下每只羊的重量 数据类型 整型 浮点型字符类型 charA 运算符和表示式一 算术运算符 二 关系运算符 三 逻辑运算符 与 或 使用运算符连接起来的式子叫表达式 有 位同学中的一位做了好事 不留名 表扬信来了之后 校长问这 位同学是谁做的好事 A说 不是我B说 是CC说 是DD说 他胡说 已知 个人说的是真话 一个人说的是假话 现在要根据这些信息 找出做好事的人 thisman做了好事的人charthisman 条件运算符 if ab a b 三目运算 表示式1 表示式2 表达式3输入一个字符 判断它是否大写字母 如果是 将它转换成小写字母 如果不是 不转换 然后输出最后得到的字幅 includevoidmain charch cin ch ch ch A switch语句 可以用于多分支选择语句 比如学分换算 比如成绩是A 对应分数是100 85 成绩是B 对应分数是84 70 成绩是C 对应分数是69 60 成绩是D 对应分数是voidmain chargrade cin grade switch grade case A cout 100 85 endl break case B cout 84 70 endl break case C cout 69 60 endl break case D cout 60 endl break default cout error endl 百钱百鸡问题 100元买100只鸡 其中公鸡5元1只 母鸡3元1只 小鸡1元3只 要求每种鸡至少有1只 要求编写程序统计并输出所有购买方案 includevoidmain intx y z for x 1 x 20 x for y 1 y 33 y for z 1 z 300 z if x y z 100 比如学分换算 比如成绩是A 对应分数是100 85 成绩是B 对应分数是84 70 成绩是C 对应分数是69 60 成绩是D 对应分数是voidmain chargrade cin grade if grade A cout 100 85 endl elseif grade B cout 84 70 endl elseif grade C cout 69 60 endl elseif grade D cout 60 endl elsecout error endl 二维数组 数组名 下标 下标 inta 3 4 a 0 a00a01a02a03a 1 a10a11a12a13a 2 a20a21a22a23有一个3X4的距阵 要求编程序求出其中值最大的那个元素的值 以及其所在的行号和列号 1 输入三角形的三边长 求三角形面积 给定边长 使用秦九韶或海伦公式 2 求ax2 bx c 0方程的解 求根公式 3 求Fibonacci数列前40个数 这个数列有如下特点 第1 2两个数为1 1 从第三个数开始 该数是其前两个数之和 4 题目 一个5位数 判断它是不是回文数 即12321是回文数 个位与万位相同 十位与千位相5 题目 一个整数 它加上100后是一个完全平方数 再加上168又是一个完全平方数 请问该数是多少 6 一个偶数总能表示为两个素数之和 歌德巴赫猜想 7 打印水仙花数13 53 33 153 includevoidmain longge shi qian wan x cin x wan x 10000 qian x 10000 1000 shi x 100 10 ge x 10 if ge wan 结构与结构数组结构体类型的定义结构体是用来描述不同类型的数据比如学生信息 1 姓名 2 性别 3 生日 4 身高 5 体重structstudent charname 20 charsex unsignedlongbirthday floatheight floatweight 初始化 structstudent charname 20 charsex unsignedlongbirthday floatheight floatweight student LiMing F 19861208 1 75 68 结构数组 函数函数的定义 函数返回值的类型名函数名 类型名形式参数1 类型名形式参数2 函数体说明部分语句部分 函数的返回值return表达式 return 表达式 函数的调用 对于有返回值的调用 没有返回值的调用形式参数和实际参数函数的嵌套调用 作业 猜价格 给定一个商品的价格区间 使用最短时间猜出商品的价格 最重要的提示 写完程序一定要保存1 猜价格2 使用筛法求3 100之间的素数3 使用递归的方法求n 递推算法的程序实现递推数列的定义 1 2 3 4 n 1 n fact n n fact n 1 fact 1 1有了通用公式和边界条件后 采用循环结构 从边界条件出发 利用通项公式通过若干递推过程就可以求出解来 王小二自夸刀工不错 有人放一张大的煎饼在砧板上 问他 饼不能离开砧板 切100刀最多能分成多少块 q 1 1 1 2q 2 1 1 2 4q 3 1 1 2 3 7q 4 1 1 2 3 4 11q n q n 1 nq 0 1 递归及其实现递归有递推和回推两部分构成 一家有兄弟5个 有人问大哥的年龄 大哥说 我比老二大两岁 又问老二的年龄 老二说 我比老三大两岁 去问老三的年龄 老三说我比老四大两岁 去问老四的年龄 老四说我比老五大两岁 又去问老五的年龄 老五说我的年龄是10岁 问兄弟之间的年龄各是多少 age 5 age 4 2age 4 age 3 2age 3 age 2 2age 2 age 1 2age 1 10age 2 12age 3 14age 4 16age 5 1810 n 1 age n age n 1 2 n 1 要解决的问题 算法 定义数据结构 语言的描述 可执行程序 用户使用一 算法 建模过程数学算法 计算机 行业算法算法的特征 算法的描述 数学算法 把数学公式写成数学表达式 求和 项 数论 分离数位 输出位置和图形 枚举算法 递归算法 蒙特卡洛计算机算法 排序 选择 冒泡 行业算法 图书管理 学生成绩管理 学生定票二 语言或工具 对算法进行描述 程序设计方法C C 标识符 变量 常量 表达式 语句数据的类型 int float double chararraystruct三种程序设计结构 顺序 选择 循环 三 可执行程序 调式 产品化 升级 维护 文档程序设计规范 向建筑学习 标识符的命名 起名规则 标识符包括文件名 变量名 函数名等 除保留字外 缩进 锯齿形状 括号要对齐注释 包括行注释 块注释和程序注释等程序设计问题 1 具有健壮性 鲁棒性 使程序更加灵活2 易于调试 加法和减法3 优化程序设计 include includevoidmain floata b c s area cin a b c s 1 0 2 a b c if a b c b c a a c b cout LineisnotTriangle endl else area sqrt s s a s b s c cout area area endl include includevoidmain floata b c disc x1 x2 realpart imagpart cin a b c cout1e 6 x1 b sqrt disc 2 a x2 b sqrt disc 2 a cout hasdistinctrealroots x1 x2 endl else realpart b 2 a imagpart sqrt disc 2 a cout hascomplexroots endl cout realpart imagpart i endl cout realpart imagpart i endl include includevoidmain inta b c d cin a for b 3 bsqrt b d a b elsebreak for c 2 csqrt d cout a b d 算法类型 位置和图形例子1 输出杨辉三角形2 螺旋矩阵问题思想和方法 首先计算出值 然后按位置输出 题目 用 号输出字母C的图案 1 程序分析 可先用 号在纸上写出字母C 再分行输出 2 程序源代码 include iostream h voidmain cout endl cout endl cout endl cout endl 作业 题目 打印出杨辉三角形 要求打印出10行如下图 11112113311464115101051 题目 猴子吃桃问题 猴子第一天摘下若干个桃子 当即吃了一半 还不瘾 又多吃了一个 第二天早上又将剩下的桃子吃掉一半 又多吃了一个 以后每天早上都吃了前一天剩下的一半零一个 到第10天早上想再吃时 见只剩下一个桃子了 求第一天共摘了多少 函数的嵌套和递归用弦截法求方程f x x3 5x2 16x 80 0的根递归调用 自己调用自己 直接调用自己 间接调用自己 题目 有5个人坐在一起 问第五个人多少岁 他说比第4个人大2岁 问第4个人岁数 他说比第3个人大2岁 问第三个人 又说比第2人大两岁 问第2个人 说比第一个人大两岁 最后问第一个人 他说是10岁 请问第五个人多大 1 程式分析 利用递归的方法 递归分为回推和递推两个阶段 要想知道第五个人岁数 需知道第四人的岁数 依次类推 推到第一人 10岁 再往回推 age 5 age 4 2age 4 age 3 2age 3 age 2 2age 2 age 1 2age 1 10 10 n 1 age n age n 1 2 n 1 使用递归方法求n 1 n 0 1 n n n 1 n 1 数学公式写成数学表达式 算法思想 把数学公式写成数学表达式例子 求二元一次方程的根 求三角形面积 乘法口诀表等 求和 项 算法思想 先把求和的项定下来 然后求和例子 e a a2 a3 an 数论 算法思想 使用筛发 或分离出数位例子 歌德巴赫猜想 求最大最小公约数 数的进制相互换算 输出位置和图形 算法思想 先计算出数值 然后在某一位置上输出结果例子 打印菱形图形 枚举算法 算法思想 在一定的范围区间里 求符合条件的结果例子 百鸡百钱问题 推理 算法思想 使用枚举方法 把给出的条件翻译成逻辑关系例子 排球占位问题 排球场的平面图如上图所示 其中 一 二 三 四 五 六为位置编号 二 三 四位置在前排 一 六 五位置在后排 某女排队在开赛时于一 四位置放主攻手 二 五位置放二传手 三 六位置放副攻手 队员所穿球衣号分别为 号 可是每个队员的球衣号都与她们的位置号不同 已知 号 号队员不在后排 号 号队员不是二传手 号 号队员不在同一排 号 号队员不是副攻手 请编一个程序 推算出每个队员的占位情况 递归算法 算法思想 把问题写成递推公式 即分段数学公式 然后使用语言描述例子 王小二自夸刀工不错 有人放一张大的煎饼在砧板上 问他 饼不许离开砧板 切 刀最多能分成多少块 n 实际问题 算法思想 把实际问题转化成数学或计算机方法 例子 猜价格 找最重的羊 给选手打分 排序问题 算法思想 通过比较把数据按递增或递减顺序排列例子 冒泡排序 交换排序难点 怎样把问题转化成对应的算法 剩下的就是编程经验 例子 王小二自夸刀工不错 有人放一张大的煎饼在砧板上 问他 饼不许离开砧板 切 刀最多能分成多少块 q 1 1 1 2q 2 1 1 2 4q 3 1 1 2 3 7q 4 1 1 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列 让C j false 同时考虑通过 i j 位置的两条对角线也就不安全了 可以令L i j 9 false和R i j false来表示在 i j 位置放置皇后 通过给位置的两条对角线上不安全了 这样得出了在 i j 位置放皇后的安全条件是 nq C j 否则 没到8个 还要让皇后数i加1再试着放 这时还要递归调用Try i 1 为了寻找不同的方案 当一个方案输出后 要回溯 看看还有没有可能换一处放置 这时候将被拿起的皇后的所在位置的第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 的方阵去填 可以用递归的方法编程