2.3算法与程序框图应用举例
12.3 算法与程序框图应用举例
■到目前为止,我们对算法与程序框图已经 有了初步的了解,在本次课中,我们将通 过几个实例,进一步体会算法的思想方法, 体会算法在自然科学和社会生活中的广泛 应用
◼ 到目前为止，我们对算法与程序框图已经 有了初步的了解，在本次课中，我们将通 过几个实例，进一步体会算法的思想方法， 体会算法在自然科学和社会生活中的广泛 应用
○开始 输入a1,a2,ag,……a50 例1某班一共有 n=1,i=0,j=0 50名学生,请设计 一个算法,统计某 a 次数学考试后,班 1=1+ 上成绩及格(≥60 和不及格(50 画出程序框图。 是 输出i, (结束
例1.某班一共有 50名学生，请设计 一个算法，统计某 次数学考试后，班 上成绩及格（≥60 ）和不及格（＜60 ）的学生人数，请 画出程序框图。 n=1,i=0,j=0 输入a1,a2,a3,……a50 an≥60 i=i+1 n=n+1 n＞50 输出i,j 开始 j=j+1 结束 否 是 是 否
开始 i=1 ■例2猜数小游戏:主持 随机输入11000间的整数a 人随机输入1~1000之间 的整数a,让参与者猜是 输入一个整数b 哪个数。如果参与者所 猜之数与a不同,则提示 “高了”或“低了”, 让参与者继续猜,如果 是 b>a>否 参与者所猜之数与a相同 输出“高了”, 输出“低了”, 则游戏结束并输出猜数 请重新输入 请重新输入 的次数。请设计一个进 行上述游戏的算法,并 i=1+1 画出程序框图。 输出 结束
◼ 例2 猜数小游戏：主持 人随机输入1~1000之间 的整数a,让参与者猜是 哪个数。如果参与者所 猜之数与a不同，则提示 “高了”或“低了”， 让参与者继续猜，如果 参与者所猜之数与a相同， 则游戏结束并输出猜数 的次数。请设计一个进 行上述游戏的算法，并 画出程序框图。 开始 i=1 随机输入1~1000之间的整数a 输入一个整数b b=a b＞a 输出“高了”， 请重新输入 输出“低了”， 请重新输入 i=i+1 输出i 结束 否 是 否 是
■例3任意给定两个正数a,b,写出求a,b的最 大公约数的算法。(更相减损之术) 约数,又称因数。 整数a除以整数b(bO)除得的商正好是整数而没有 余数,我们就说a能被b整除,或b能整除a。a称 为b的倍数,b称为a的约数 如果一个数c既是数a的因数,又是数b的因数,那 么c叫做a与b的公因数。 两个数的公因数中最大的一个,叫做这两个数的 最大公因数
◼ 例3 任意给定两个正数a,b,写出求a,b的最 大公约数的算法。(更相减损之术) 约数，又称因数。 整数a除以整数b(b≠0) 除得的商正好是整数而没有 余数，我们就说a能被b整除，或b能整除a。a称 为b的倍数，b称为a的约数。 如果一个数c既是数a的因数，又是数b的因数，那 么c叫做a与b的公因数。 两个数的公因数中最大的一个，叫做这两个数的 最大公因数
开始 输入a,b a 是 a-a b b=b-a 输出a 结東
开始 输入a,b a=b a＞b a=a-b b=b-a 输出a 结束 是 否
例4已知n次多项式f(x) anx fan-1X taiX+ (ai∈R,=0,1,2,3…,n),设计一个算法,求当x=x时多项式f(x)的值, 并画出程序框图 (秦九韶算法) 秦九韶算法是中国南宋时期的数学家秦九韶提出的一种多项式简化算 法。在西方被称作霍纳算法。 秦九韶算法是一种将一元n次多项式的求值问题转化为n个一次式的算 法。其大大简化了计算过程,即使在现代,利用计算机解决多项式的 求值问题时,秦九韶算法依然是最优的算法 秦九韶(约公元1202年-1261年),字道古,南宋末年人,出生于 鲁郡(今山东曲阜一带人)。 早年曾从隐君子学数术,后因其父往四川做官,即随父迁徙,也认为 是普州安岳(今四川安岳县)人
◼ 例4 已知n次多项式f(x)= (ai∈ R,i=0,1,2,3,……,n )，设计一个算法，求当x=x0 时多项式f(x)的值， 并画出程序框图。 （秦九韶算法） 秦九韶算法是中国南宋时期的数学家秦九韶提出的一种多项式简化算 法。在西方被称作霍纳算法。 秦九韶算法是一种将一元n次多项式的求值问题转化为n个一次式的算 法。其大大简化了计算过程，即使在现代，利用计算机解决多项式的 求值问题时，秦九韶算法依然是最优的算法。 秦九韶（约公元1202年－1261年），字道古，南宋末年人，出生于 鲁郡（今山东曲阜一带人）。 早年曾从隐君子学数术，后因其父往四川做官，即随父迁徙，也认为 是普州安岳（今四川安岳县）人
开始 输入n,anX y-a. ⅰ=n-1 ≥0 是 输入a1 y=yx 否 ⅰ=i-1 输出y人 结束
开始 输入n,an,x y=an i=n-1 i≥0 输入ai y=yx+ai i=i-1 输出y 结束 是 否
例5某城市对居民用水实行阶 梯式收费,标准为:每月每户 生活用水20m以内(含)为第 级,按居民生活用水的供水(开始 价格收费;每月每户生活用水 超过20m3且低于或等于30m3 输入X 为第二级,超出的部分按供水 X≤20 价格的1.5倍收费;每月每户超 过30m3为第三级,超出的部分 x≤30 是 按供水价格的2倍收费.如果该 城市居民生活用水的供水价格 为124元/m3,另加收城市附加 y=404x31y=342X×124y=8x 费0.06元m3,污水处理费13元 m3,水资源费02元m,请设计 输出y 个算法,输入某户居民某个 结束 月的用水量,输出这个月的该 户居民所需缴纳的水费
◼ 例5 某城市对居民用水实行阶 梯式收费，标准为：每月每户 生活用水20m³以内（含）为第 一级，按居民生活用水的供水 价格收费；每月每户生活用水 超过20m³且低于或等于30m³ 为第二级，超出的部分按供水 价格的1.5倍收费；每月每户超 过30m³为第三级，超出的部分 按供水价格的2倍收费.如果该 城市居民生活用水的供水价格 为1.24元/m³,另加收城市附加 费0.06元/m³,污水处理费1.3元 /m³,水资源费0.2元/m³,请设计 一个算法，输入某户居民某个 月的用水量，输出这个月的该 户居民所需缴纳的水费。 开始 输入x x≤20 x≤30 y=4.04x-31 输出y 结束 y=3.42x-12.4 y=2.8x 否 是 是
■例6圆的周长和直径的比 值称为圆周率(T),它 是一个常数,也是一个无 开始 理数,历史上,有不少数 n=1,S=0,a=0 学家对圆周率做过研究, 到了现代,由于算法的改 b=a 进和计算机科学的发展, S=S+(=1)m1·1/2n-1 否 T值计算精度也迅速提高, 例如,利用莱布尼茨公式: n=n+1 T4=1-1/3+1/5-1/7+1/9 1/11+ 就可以近似计算π的值 a-b|<10 利用上面的公式设计 个算法,计算π的近似 /输出a_ 值,试画出程序框图 结束
◼ 例6 圆的周长和直径的比 值称为圆周率（π），它 是一个常数，也是一个无 理数，历史上，有不少数 学家对圆周率做过研究， 到了现代，由于算法的改 进和计算机科学的发展， π值计算精度也迅速提高， 例如，利用莱布尼茨公式： π/4=1-1/3+1/5-1/7+1/9- 1/11+…… 就可以近似计算π的值。 利用上面的公式设计 一个算法，计算π的近似 值，试画出程序框图。 开始 n=1,S=0,a=0 b=a S=S+(-1)n-1·1/2n-1 n=n+1 a=4s |a-b|＜10-5 输出a 结束 是 否