递归数列与循环结构分析

·同步参考· 数学通讯(2008年 第 19期 ) 23 递归数列与循环结构 分析 定性数据统计分析pdf销售业绩分析模板建筑结构震害分析销售进度分析表京东商城竞争战略分析 熊惠民 (武汉华中师范大学数学与统计学学院,030079) Logo语言的初始人hlour Rpert曾将计箅机 称为“会讲数学浯言的生物”,也就是说 ,数学是算法 的灵魂和本质 因此 ,理解算法的一个有效方式是将 算法语言转化为数学语言 , 算法与数列有着天然的联系。一个算法总包含 一些变且,随耆算法语句一条一条地执行 ,每个变量 的值都在不断发生变化 ,从而按照语句先后顺序获 得一系列的数值 ,即形成一个数列 因此 ,可以用数 列的观点来理解和处理算法 , 算法有三种基本逻辑结构 :顺序、条件、循环 ,其 屮循环绀构是中学算法教学的难点,本文讨论用递 归数列来分析循环结构.其基本思想是 :将算法语言 ⒒接“翻译”成递归数列语言 ,然后再去求解递归数 歹刂 例 1 (⒛07年 高考宁夏、海南卷)如果执行程 刂榧图(图 I),那 么输出的s= (A)245() (B)2500 (C)2550 (D)2625 图 1 解 该算法包含一个循环结构 ,有 两个变量 屁 与s,设经过 '次 循环后其值分别为尼j与Sj('≥0), 则山程序框图知 循环初值 : 虑0=1,S。 =0 ‘ ` ① 循环体 : S氵 =s氵 I+2芡j l(f≥1) ② △=花氵I+1(犭 ≥I) ③ 循环体进人条件 : f=0或诧j l≤50 ④ (注 :因循环初值总有意义 ,故 犭总可以为⑴ 由③知{幻}是一个公差为 I的等差数列 ,因此 庀f=乃0+f=f+1(犭≥0) ⑤ 将⑤代人② ,得 sJ=S`l+2F(犭≥⊥) 从而 户E⒏ =户氵曳ˉl+氵∶2″ Sf=SO+2∑″=扌 (Ⅰ +⊥ )(f≥⊥) 因此 , S氵 =石 (f+I)(犭≥0) 将⑤代人④ ,知 0≤f≤sO。(注 :根据箅法框图 的葸义 ,求循环次数 f的范围时 ,必须满足它是垠长 的一串从 0开始的连续自然数柒 ) 故所求 S值为 SsO=sO·(∞ +I)=乃sO, 例 2 (2007年 高考山东卷)阅 读程序框图(图 2)、 若输人的 ″是 ⊥00,则 输出的变且 s和r的值 依次是 图 2 (A) 2500,2500 (I;) 2550,2550 数学通讯(⒛08年第 19期 ) ·同步参考· (C)2500,2550 (D)2550,25α ) 解 该算法包含一个循环结构 ,有三个变量 m, s与T,设经过 犭次循环后其分别为″J,s与η(犭≥ ⑴ ,则由 题 快递公司问题件快递公司问题件货款处理关于圆的周长面积重点题型关于解方程组的题及答案关于南海问题 目条件和程序框图知 , 循环初值 : ″0=100,sO=0,T。=0 ① 循环体 : s·Sf叫+’I,丬 (j≥D ② ,:氵 ≡(刀f~1^l)-1=,oj~1∷2(犭 :≥1) ③ η=η丬十(mi~I-1)(氵≥l) ④ 循环体进人条件 :′ ·f=0或△.≥2 ⑤ 由③知{奸}是一个公差为 2ˉ的等差数列 ,因 此 ∫ ″氵=″ 0ˉ 2J=⊥∞ -2扌 (J≥0) ⑥ 将⑥代人② ,得 岛=Sj.+[lO0-2(氵-1)]=s~l2ˉF+10z (f≥D ' 从而 盗斗丁舀S1· ⊥盛⒛+舀 呷2 S;F SOˉ 2茗 丨十l∞f=-j2十1010(犭≥D 因此 , s`=-￡2+10⊥ 氵(f≥0) 将⑥代人④ ,得 η=η l+[·lO0-zr氵-D-1]=η .ˉ 2氵 + 101('≥ D 按同样的方法,可求得 η=-f2+iO0氵(犭≥o) 将⑥代人⑤,知 0≤犭≤sO。故所求 S与 T的值 分另刂为ssll=2550,TsO=2500。 例 3 (20⒓ 年北京海淀区模拟 试题 中考模拟试题doc幼小衔接 数学试题 下载云南高中历年会考数学试题下载N4真题下载党史题库下载 )这是一 个计箅机程序钠流程 : (1)初始值`=l,y=1,z=1,,I=0; (2)″ =″ +1(将当前 ″十1的值赋予新的″); (3)岔 =J+2(将当前 =艹 2的值赋予新的 J); (4)丿 =2丿(将当前 2丿 的值赋予新的丿); (5)z=z+w(将当前 z+ヵ的值赋予新的 z); (ω 如果z)匆00,则执行语句(7),否则回到语 句(2)继续进行 ; (7)打印″,z: (8)程序终止 . 试求由语句(7)打印的数值是多少 . 解 该算法包含一个循环结构 ,有变量 氵,丿 , z,″,设经过 J次循环后其值分别为曲,y,布,勹”(j ≥0),则 由程序流程知 循环初值 : a·0=1,tyO=1,zO=0,″0=0 ① 循环体: · ∶ ″氵=″f~j+1(j≥。1) ② 曲±而△+2(犭≥D ' ③ 宀=2y丬(氵≥D ④ 幻=白 -I+￡山(J≥1) ⑤ 循环体进人条件 : 犭=0或 J=1或 竹≤9000 ⑥ (注Ⅱ因此时循环扁于直到型循环,故循环次数 j总可以为 l) 由②知{奶}是一个公差为 1‘ 的等差数列,因此 ,a;=夕aO+犭=j(讠≥0) ⑦ 由③知{奶}是一个公差为2的等差数列,因此 1i=幻+2J=1+2f(J≥0) ⑧ 由④知{执}是一个公比为2的等差数列,因此 y=lyO·2扌 =犭 (讠≥0) ⑨ `将⑧⑨代人⑤,得 z|〓zj-l十(1+2F)2氵 (F∶≥1) 变形,得 z.+(∵4氵 +2)2J〓 z;~I![-4(犭-1)十 2]2jˉ! (J≥ 1) 所以,{动+(-4犭 +a)2氵|是一个常数列,因此 动=zO十2-(ˉ 4'+2)2氵 =(2j-⊥)2H+2(J≥ 0) ⑩ 将⑩代人⑥,知 0≤ J≤8.故 由语句(7)打 印的 数值是 ″:=8,zg〓%gz‘ 例4 ⑿007年 高考海南样卷)图 3给出的是 计算告 +÷ +告 +⋯ +嘉的值的一个程序框图, 其中判断框内应填人的条件是 ( ) (A)￡ )10, (B)扌 (10, (C,J>⒛. (D,f<⒛. 解 该算法包含一个循环结构,有变量 s,″, ',设 经过 J次循环后其值分别为Sf,″`J`(r≥0),则 由程序框图知 循环初值 : SO=0,″ 0=2,氵 0〓 亠 ① ·同步参考· 数学通讯(2008年 第 ⊥7期 ) 25 “一一对应”在计数中的应用 陈荣华 (福建省三明市建宁一中,35450O) 我们先来看一个例子 : ⊥00个人进行淘汰赛 (指 每场 比赛淘汰一个 人),问进行多少场比赛能产生一名冠军 解 笫 l轮要进行m场比赛 ,留下 ~sO名选手 ; 第 2轮要进行b场比赛 ,留下乃 名选手 ; 笫 3轮要进行 ⒓ 场比赛 ,⊥ 名选手轮空,留 下 13名选手 ; 第 4轮要进行 6场 比赛,1名选手轮空,留下 7 名选手 ; 第 5轮要进行 3场 比赛,1名选手轮空 ,留下 4 名选手 ; 第 6轮要进行 2场比赛 ,留下 2名选手 ; 最后一场决赛 ,产生一名冠军 , 所以共举行的比赛场数为 ~sll+z~s十12+6+3 +2+1=99。 显然这种做法思路比较简单 ,但计算较繁,我们 可以用另外一种方式来解决 :我们发现每一场比赛 对应着一个被淘汰的人 ;反之 ,每一个被淘汰的人对 应着一场比赛 所以所需比赉的场数应该与要淘汰 的人数相等 ,即 ” 场 从上例可以看出,当要计算一个有限柒合的元 素个数比较困难时,我们经常可以把它转化为丿J一 图 3 循环体 : s=岛丬+彳∶0》) ② ″` =″Ⅱl卜2(r≥l) ③ 氵` =f`l+⊥ (r≥l) ④ 曲③细l{″`}足一个公差为2的等差数,ll,因此 ″` 二 ″0+2'=2+2/(`≥0) ⑤ I妇 ④知 "`|足 一个公差为 1的等差数列,因此 氵` =fO+r=1+r(r≥⑴ ⑥ 将⑤代人②,得 菡黾=蛊 ⒊1+直嘉(r≥D S氵 =SO+告 十 ⋯ +劳 =告 +⋯ i击 (r≥D⑦ 令 S`=告+⋯ +击 ,贝刂r=ltl因哔 r可取 0, 1,2,¨ 、10,将其代人⑥式 ,得 {f`}为数列 1,2,3,⋯ , 11, 即当 犭=1,2,3,⋯ ,L0时进人循环体,当 犭=n 退出循环体 显然退出条件 J>I0满 足要求 ,故 选 (A), 顺便指出,如果例 6是一道填空题 ,则判断框内 应填人的条件可有无限多个 ,如 f=Ⅱ,扌 ≥Ⅱ,″ > 18,″ )19,″ =⒛ ,″ ≥⒛ 等 , 应该说明的是 ,本文的目的是试图为循环结构 的分析提供一般的方法,文 中有些实例是比较简单 的情形 ,它们通常根据直觉就可直接作出判断,而不 需转换为递归数列语言,而且 ,也并不是所右算法都 能采用递归数列来进行分析理解的 本文的方法特 别适合于循环结构复杂的情形 ,它具有思路清晰、操 作机械、不易出错等优点,渎者应根据具体怙况灵活 运用 S`=S` 11 所以 ? ??(`≥1) (刂攵秆:日 J叨 :2008-03-17)