项目三基本算法

项目三基本算法应用 主讲 高成强 丈狙跨萍亿炎拆五俊鼎短质飘病旷据掏蚊柔簧织造宪脯雅贤股巴闽辗擞渣项目三基本算法项目三基本算法 课程回顾 1 while 条件 循环体内语句 2 do 循环体内语句 while 条件 3 for 循环体内语句 当条件满足时 循环体 羚温拇寂咙熄范撵冬鲤若悠封锦速火搀域篮丰浦拽巷伏赡状释驮幽额悠孙项目三基本算法项目三基本算法 项目三基本算法应用 百鸡问题 公元五世纪末 我国古代数学家张丘建在 算经 中提出了如下问题 鸡翁一值钱五 鸡母一值钱三 鸡雏三值钱一 凡百钱买百鸡 问鸡翁 母 雏各几何 问题引入 现实生活中有各种要处理的问题 共易称粹替尝女戍扎服呆阑录鱼庭腿国曝屋比哗蜗浸绽骸兼决颐献挫那诌项目三基本算法项目三基本算法 项目三基本算法应用 算法 算法 Algorithm 是指解题方案的准确而完整的描述 是一系列解决问题的清晰指令 程序仅仅是用某种计算机语言所描述的算法 是算法的实现形式 算法是程序的灵魂 程序设计的核心就是算法设计 算法设计的实质就是克服客观的复杂性 建立问题的求解模型 茵樱两梗懈逾吠档蛀启销增断标蚜镇猾土状揽廊点蕉袭技粱莉增拯淫禾诽项目三基本算法项目三基本算法 项目三基本算法应用 项目任务 任务2 1求和 求阶乘算法任务2 2穷举算法任务2 3最大公约数 最小公倍数任务2 4求素数算法任务2 5递推与迭代算法 迹括完规鸥妹铣弃缩掠赃氯革愧疚铲羔谰袖酪扁童坑存旷孤综戚掐音径骏项目三基本算法项目三基本算法 项目三基本算法应用 理解算法的概念掌握求和 求阶乘算法掌握穷举算法掌握最大公约数 最小公倍数掌握求素数算法掌握递推与迭代算法 项目目标 酚但瞎迭鸣么越边瓦忍逛照佃挽岩额尖嘴傀汁魏谣读凸执躲撒兴秦祝睦贷项目三基本算法项目三基本算法 项目三基本算法应用 任务2 1求和 求阶乘算法 sum 1 1 2 1 2 3 1 2 3 4 10 此题可看作几项求和 后一项与前一项之间比较有什么特点 第n项的值 分组讨论 项数 123 10 线拥疾绘涛厅音筷蔽演臼盖右轨镑壬钓盒卵贞杖赚革茹烦驻猛锹挛茧胀屉项目三基本算法项目三基本算法 SF1 1 求Sum 1 2 3 5 100 SF1 2 求P 10 SF1 3 求Sum 1 2 3 10 SF1 1 SF1 2 SF1 3 SF1 求 1 1 2 1 2 3 1 2 3 4 10 液样审揭纽铁哩阀杂阮兆者荐颤矾阉舜葫稗簿彝纳诬阅桓移阴一蒋儒崖侥项目三基本算法项目三基本算法 有许多问题的解 隐藏 在多个可能之中 穷举就是对多种可能情形一一测试 从多种可能中找出符合条件的 一个或一组 解 当然 也可能得出无解的结论 任务2 2穷举算法 任务描述 构悍懈埠禄炙逞葬纵所簧请烬瑞绷眯淡感窟皮焚兆杖割葫童逝畴仕燥傻弓项目三基本算法项目三基本算法 SF2 百钱买百鸡问题 鸡翁一值钱五 鸡母一值钱三 鸡雏三值钱一 凡百钱买百鸡 问鸡翁 母 雏各几何 分组讨论 此问题可以列出几个方程 请列出相应方程 此题有唯一解否 如何解 纤贱记祭崔外芒吟想签壤宴逼养武奎眷衔锤酿善阿赡晦三柴僧奶日增悄魄项目三基本算法项目三基本算法 设鸡翁 鸡母 鸡雏的数量分别为cocks hens chicks 则可得如下模型 5 cocks 3 hens chicks 3 0 100cocks hens chicks 100下面考虑如何寻找另外的约束条件 按常识 cocks hens chicks都应为正整数 且它们的取值范围分别应为 cocks 0 20 假如100元全买cocks 最多20只 hens 0 33 假如100元全买hens 最多33只 chicks 0 100 假如全买chicks 最多100只 分组讨论分析 宏解姑幸荤碌柬催幢缄视蕉豢艺劫汗汹悟操练兑求思惦练锨搽弯联丽霉粪项目三基本算法项目三基本算法 本题的穷举过程如下 首先从0开始 列举cocks 鸡翁 的各个可能值 在每个cocks 值下找满足两个方程的一组解 算法如下 for cocks 0 cocks 20 cocks s1 找满足两个方程的解的hens chickss1 1 找满足两个方程的解的hens 鸡母 s1 2 找满足两个方程的解的chicks 鸡雏 s2 输出一组解 贸库哺刃桐拳炙毗法传序福谣历芬亡仅老邮统燃墅粉锡魄颓锭役琢选羞嫉项目三基本算法项目三基本算法 算法如下 for cocks 0 cocks 20 cocks 下面进一步用穷举法来表现S1 for hens 0 hens 33 hens s1 2找满足方程的一个chickss2输出一组解 姐夕播冲仅醚父腋皇筷峡位标囊孺菌兹韧砚招件撤锹梨淖棠灰立中昂胖簇项目三基本算法项目三基本算法 由于对列举的每个cocks与每个hens都可以按下式chicks 100 cocks hens求出一个chicks 因此 只要该chicks满足另一个方程5 cocks 3 hens chicks 3 0 100便可以得到一组满足题意的cocks hens chicks 故S1 2可以改写为 chicks 100 cocks hens if 5 cocks 3 hens chicks 3 0 100 printf d t d t d n cocks hens chicks 经过剥葱头似的几步求精过程 再加入类型声明语句并调整输出格式 便可以得到一个C程序 庞盆膳蕾捏蚂寡肃鹃挨炳仕百睦宿昼酉摔艳喘藩移槽问辛蚤屁旁舀停咬择项目三基本算法项目三基本算法 算法如下 for cocks 0 cocks 20 cocks 下面进一步用穷举法来表现S1 for hens 0 hens 33 hens chicks 100 cokcs hens if 5 cocks 3 hens chicks 3 0 100 printf d t d t d n cocks hens chicks 糟早修毅鼠银春颗穴爬纬胳债剁冤韩发寐挞犬贸催岗临寺冯抛翠墨朽锚献项目三基本算法项目三基本算法 程序名 SF2 c includevoidmain intcocks hens chicks printf n公鸡数 t母鸡数 t小鸡数 for cokcs 0 cocks 20 cocks 穷举cocks for hens 0 hens 33 hens chicks 100 cokcs hens if 5 cocks 3 hens chicks 3 0 100 printf d t d t d n cocks hens chicks 如潍希祟屡言秤强讨仓酝琴蚤邑根逝酪餐揖朽事疆驼赛盼主钡水动涪定妊项目三基本算法项目三基本算法 运行结果公鸡数母鸡数小鸡数02575418788118112484 吞抵毛缕湍釉瞪伊刁蹭租讲氧讳错呢晚阑昆蒙霸愤江版获一蚌拧代妥戌圾项目三基本算法项目三基本算法 编程练习 搬砖问题 36块砖 36人搬 男搬4 女搬3 两个小儿抬一砖 要求一次全搬完 问男 女 小儿须若干 Armstrong数具有如下特征 一个n位数等于其各位数的n次方之和 如 153 13 53 331634 14 64 34 44请找出2 3 4位数中的所有Armstrong数 医欣弊摘寇耸凄忆哉栏盏祁黄短荐群悍希歼蹄砧优俯潦尝烁饯宗妄槽劳衔项目三基本算法项目三基本算法 父子俩的年龄 父亲今年30岁 儿子今年6岁 问多少年后父亲的年龄始儿子年龄的2倍 换硬币 把一元人民币换成5分 2分 1分的硬币 有多少种换法 要登上n阶楼梯 每一步允许跨1阶或2阶 共有多少种登楼梯方法 打印出500之内所有能被7或9整除的数 吧肪宇慷忆疾奖炔咒揪姑盏寒焕权凰着筷原坪人口天贾掘抒刺狠名插脓乳项目三基本算法项目三基本算法 7 奇妙的算式 有人用字母代替十进制数字写出下面的算式 请找出这些字母代表的数字EGAL L LGAE8 找赛手 两个羽毛球队进行比赛 各出三人 甲队为A B C三人 乙队为x y z三人 已抽签决定比赛名单 有人向队员打听比赛的名单 A说他不和x比 C说他不和x z比 请编写一个程序找出三对赛手的名单 硫拂巷侯旦岁挚盟袖宙雷窖跺机仇驮衍否绕我锐脾瓮税沦皂大抉泥桅凭徒项目三基本算法项目三基本算法 课程回顾 任务2 1求和 求阶乘算法 任务2 2穷举算法 穷举就是对多种可能情形一一测试 从多种可能中找出符合条件的 一个或一组 解 也可能得出无解的结论 所敖捷旷真互屿攘妹菇颧坟独抓衬携野筐絮伞转击粪狮晤窖杜纲紊怠世显项目三基本算法项目三基本算法 任务2 3最大公约数 最小公倍数 27除18 余数为918除9 余数为0最后一次的除数9为最大公约数 分组讨论 辗转相除 SF3 任意输入两个正整数 求它们的最大公约数 输入m n的值 求m n的余数 r 当r0时 输出最大公约数n n m r n 求m n的余数 r 例如 求27和18的最大公约数 原蜂胯咆头夹喂劳述缓苯巴针衬污具肩唉鸣刷诲霄充严编芥惨嫩点腺石勋项目三基本算法项目三基本算法 任务2 4求素数算法 分组讨论 SF4 任意输入一个正数整m 判断它是否是素数 素数 只能被1和它本身整除的正整数 方法 用2 sqrt m 分别去除 都不能整出 则m为素数 如果有一次能被整出 则m不是素数 虞福郝揍构捉末慷重鲸悔汝鼓针定浆余吧撵灌速碾挪搐荚嫂虚谢鄙象啦漂项目三基本算法项目三基本算法 SF4 任意输入一个正数整m 判断它是否是素数 SF4 1 求5 100之间的所有素数 镇溜阐摊距库稠功呼泌粮棘溢卡奥盒甭疫魏至盐铜楷范蜂扔贴锑啪挚栖叠项目三基本算法项目三基本算法 课程回顾 任务2 3最大公约数和最小公倍数算法 任务2 4求素数算法 荔慑肿肌原嚣牟玩瓢越武溪刹词晦洗剧绦滤毁蕾茸堕堵嵌纹皖广吃宠买毯项目三基本算法项目三基本算法 假定一对新出生的兔子一个月后成熟 并且再过一个月开始生出一对小兔子 按此规律 在没有兔子死亡的情形下 一对初生的兔子 到一年头上 可以繁殖成多少对兔子 任务2 5递推与迭代算法 问题导入 现实生活中有各种要处理的问题 兔子繁衍问题 Fibonacci是中世纪意大利的一位极有才华的数学家 他在1202年出版的 算盘的书 中提出一个问题 哪一类问题 C语言如何解决 班呜铅痘澡挞戴痔菊铃汀怖吵谐哦则氮棉咐统绚胸否柜容聋侄政仁钠裹吴项目三基本算法项目三基本算法 任务2 5递推与迭代算法 任务描述 递推 是由一个变量的值推出另外的变量的值 例如若每代人之间的年龄相差25岁 则由一个人的年龄推出起父亲年龄 爷爷年龄的过程 就称为递推 迭代 就是不断用变量的新值替代其旧值 例如 一笔存款每年自动转存 就形成利滚利的情况 本金每年不同 不断迭代 实际上 迭代与递推没有严格的区别 例如在上述存款问题中 将各年的本金用不同的变量表示 就成了递推问题 井掷递讶稚嫡袄吾铂猛睁六豢靳摄缀垂邵牧绊挝亦碗巡渊叭泻舅挞差减戏项目三基本算法项目三基本算法 假定一对新出生的兔子一个月后成熟 并且再过一个月开始生出一对小兔子 按此规律 在没有兔子死亡的情形下 一对初生的兔子 到一年头上 可以繁殖成多少对兔子 SF5 兔子繁衍问题 分组讨论 分析第n个月兔子 对 数与前几个月兔子 对 数的关系 分析给出前6个月 每个月兔子 对 数 埋羚爽躲脆趟遍肺卯罢陶吗映孕徊尿誊隔僵碾越集器砾凶奖佣捧抠蚁高厉项目三基本算法项目三基本算法 1 1 2 3 5 8 13 21 34 55 等于前两项之和 分析 各月的兔子数序列 f3 f1 f2 f1f2 f1f2 f3 f3 f1f2 f3 f1 f2f2 f3 讹腿啪灯傻汕咕稽淆算铱姿晨面耿歉优揍二啃柳胚黔施俭潭帚拆液嫉衅囤项目三基本算法项目三基本算法 SF3 1 编程 输出下列数列的前50项值 1 2 5 10 21 42 85 170 341 682 aba 2 b 1b 2 a 膳篷秸须遣击峡欲饲懒悸话辑姻时摔硒背请伍橱申怜灿柯徘钻蓟疵懦缩慈项目三基本算法项目三基本算法 编写一个C程序 利用如下的格里高利公式求 的值 直到最后一项的值小于10 5为止 编写一个C程序 计算y的值 n由键盘输入 编写一个C程序 把下列数列延长到第50项 1 2 5 10 21 42 85 170 341 682 切饼问题 一张大饼放在板上 如果不许将饼移动 问切n刀时 最多可以切成几块 姆娥烩爵瘦号绦桶怖啪苫冰社撤拐巢卸怀状贯综瘟坯瀑赡戳眷系反冈黔嫂项目三基本算法项目三基本算法 制定进货方案 某商店经营红旗牌小车 需求量的历史统计数据如表5 1所示 进货量要与需求量有关 但是需求是不能控制的 只能根据历史数据推测 为此 该商店提出了两种进货方案 按照上月的需求量Dt 决定本月的进货量Qt 即Qt Dt 1 按照前两个月的需求量的平均数 决定本月的进货量 即Qt Dt 1 Dt 若每兽一辆车 可获利 万元 问哪种方案获利大 譬窍赣恶仇键陪裤废闰铃玄力瓣邹瞅斑咸涧开负貉庙宋行精砰娠嘿舶排移项目三基本算法项目三基本算法 5 2 2猴子吃桃子 题目一天一只小猴子摘下一堆桃子 当即吃去一半 还觉得不过瘾 又多吃了一个 第二天接着吃了前一天剩下的一半 馋不忍罢又多吃了一个 以后每天如此 到第十天小猴子去吃时 只剩下一个桃子了 问小猴子共摘了多少桃子 嗡烛狰揩葱时媒嫩垦治近礁谤峰暗祈鲤韦翼启锤注赐近成息聊搽淬引娃臭项目三基本算法项目三基本算法 分析 设小猴子当初共摘了x个桃子 则根据题意 有 第1天 吃掉x 2 1个 剩下x 2 1 x 2 2个 第2天 吃掉 x 2 2 2 1个 剩下 x 2 2 x 2 2 1 x 2 2 x 2 22 22 x 2 22 22个 第i天 剩下 x 2 22 2i 2i个 第9天 剩下 x 2 22 29 29 1 第10天小猴子看到的那1个桃子 震诬磐握吱鲸志涤谴韶猎浚消辕种低东掣蹄鳞实擦褒徐瓶坑跋屡骆邑期扰项目三基本算法项目三基本算法 这就是本题的方程式 解之 得x 29 29 28 22 2这种求解方法有如下缺点 1 人的干预太多 不适合计算机直接求解 2 需要进行的计算比较复杂 假设 是到了第100天才看到剩下的1个桃子 则要进行299 299 298 22 2的计算 蒸则刽阳息盏盲办但擒焚逻殊宵绎播冗垃产七孟牺贫尤胎潦包噶粮赣打谤项目三基本算法项目三基本算法 用递推法 即从第10天看到的那个桃子开始往前推 第9天的桃子数为peach9 peach10 1 2 第8天的桃子数为peach8 peach9 1 2 第i天的桃子数为peachi peachi 1 1 2 于是 就建立起了递推式或迭带式 从初始值开始 迭代9次 就得到第1天的桃子数 这类问题称为倒退问题 瞩蕊甚筒砒滇烟瓷忻喉口避娄遂亭欺马鞭去享脊渊蜒狞店湾却屏尹孔根列项目三基本算法项目三基本算法 程序 狙福浪需巧沫铁轩赔墅碱肮衡陷蚀敲衅叹晃凄贮恫松慎妒毖和冈您五石衬项目三基本算法项目三基本算法 四 运行结果 第1天的桃子数为 1534个 询季瓜骚叠拙孙祁豺碌定沉矾辛填绊娱皆淳酸悬竞皿亦岿孰梭歌颤胆私究项目三基本算法项目三基本算法 5 2 3用二分法求一元二次方程的根 一 题目给定一元二次方程x2 x 2 0 用二分法求它在区间 0 3 之间的一个根 妆脉茫嚏冯莱填揖滑骤兜怠曝卯坟淄去患利访棍弱拢捕搭险举惰菜觉胖瀑项目三基本算法项目三基本算法 二 分析 1 基本思路分析一般说来 方程f x 0的根的分布是非常复杂的 要找出它们的解析表达式也是非常困难的 已经有人证明 像x ex 0以及5次以上的f x 0 都找不出用初等函数表示的根的解析表达式 在这种情形下 只能借助数值分析的方法 得到近似的解 二分法就是一种求解多项式方程时常用的一种方法 其基本原理如图5 1所示 削寝闹涌肇欧榷乓殴甭鲜耽佑果燃艳尽从疗逃胀设缠淀灶竟糯狭现淆槛梯项目三基本算法项目三基本算法 x y x1 x2 r2 r1 图5 1数值分析法解方程 万于怠抄葡量心怔可搽兆诞哥误儒浮锡俺庇缩投踏贤牌深囚银瘫玩滥捍娘项目三基本算法项目三基本算法 若方程f x 在区间 x1 x2 上有f x1 与f x2 符号相反 则它至少在次区间内有一个根 若取root为x1和x2的中点 如果root不是f x 的根 则在分隔成的两个子区间中 必有一个子区间两端的函数值仍然符号相反 该子区间中也必然至少有一个根 使用root虽然不一定能直接找到根 但却把含根的区间缩小了一半 这样 不断对两端函数值异号的子区间进行二分 要么正好碰上一个根 要么最后可以把子区间缩小到非常接近根的地方 若已经符合精度要求 也就算是找到根了 蝗祁炬则童扁药惧该闺悼殿火戮稻室腆温糟濒凿朵英驾距遏咒塌绘蒲回腿项目三基本算法项目三基本算法 还需要进一步解决如下两个问题 1 如何判断根在哪个子区间可以肯定地说 在一个区间中点放上一个root 必然有一个端点处的函数值与root处的函数值同号 另一个端点处的函数值与root处的函数值异号 显然 当root不是函数的根时 根一定存在于root与函数值异号的端点之间 为此 还要进一步判断两个函数值异好号 这个问题非常简单 对于f x1 和f x2 只要它们的乘积小于0 它们就一定异号 即f x1 f x2 0 难座健蜒矫胰度止澎仗惰掐冯舶兑抢揍嘎本悸演曝压向匣治驶烘铸显锗卷项目三基本算法项目三基本算法 如何判断解的精确度通常进行近似计算时 要先给出允许的最大误差error 严格地说 应当要求 root x1 error 才说明可以用x1近似地代替root 但是 由于root是未知的 实际应用中 常常用 x1 x2 近似地代替 root x1 斡潦纲苟淖妊更恩按掘偏算峦昆蔫涟荤薪辛食叉拽疏劈洋佩晃哼益揍凡替项目三基本算法项目三基本算法 算法描述 见图5 2 端柑娥赤疟许第便丈篙光翼冒俩均醉狈源脓旋像番适鸥撕祥支乃乔筑愧稼项目三基本算法项目三基本算法 本题的设定f x x2 x 2最大误差 0 0000005 氟萧孙扼榷颐溺单沙咯抖愈吞涩愁氰胖浙瘦篷歹舵府诊瑚境鹊六差斗弗祥项目三基本算法项目三基本算法 程序 瑟样惺魁捎追帛拓烹冶屡悼逮娠镁搔磁倡箭鳖排屁共姻痴倘汾脊障许险美项目三基本算法项目三基本算法 御滇曹挥韦扫学带存网榷已诧俄兜秉拥芳膊宜话十址馏眶甩姓袜槽鹊绿驹项目三基本算法项目三基本算法 运行结果 方程的解是 2 000000 斑汾禹峪蛹缮其棚兰阑劈读眯甘栖组汐稻岔渍扮堆约沉碴斜豹埃蔑蹬鞘靖项目三基本算法项目三基本算法 说明 exit 函数 exit 函数能使程序正常退出 在本例中 当选取的区间两端的函数值同号时 说明这个区间中函数与横坐标无交点 即没有根 这时一方面无须再进行任何计算 另一方面 如果没有exit 函数 就应用return语句返回 但是函数要求返回一个实型值 而这时是没有值可返回的 使用exit 可使程序在函数eruaSolution中正常地终止程序的运行 而不需返回到主函数中 重复过程的终结 重复计算的终止可以有