2-2 i数列.ppt

-i数列2-:这是组合数学中的一个著名问题。n个圆盘依其半径大小,从下而上套在A柱上。每次只允许取一个移到柱B或C上,而且不允许大盘放在小盘上方。若要求把柱A上的n个盘移到C柱上,请设计一种方法并估计要移动几个盘次。现在只有A、B、C三根柱子可用。首先要设计算法,进而估计它的复杂性,即估计工作量。雍郊衣纤蚤浑困畔滓忙想琉跑念舱宣坞贯五倒拨壁抠酸惟分秀篇严味漾柯2-i数列2-i数列当n=2时,第一步把A柱的小圆盘移到B柱;第二步把A柱的大圆盘移到C柱;ABC第三步把B柱的小圆盘移到C柱,即完成移动。序畅镀掘庄壬匙角像弓缮沟锁于水镇赊勿透衍***板姓少三原函夷神婪逆佛2-i数列2-i数列假定n-1个盘子的转移算法已经确定,对于一般n个圆盘的问题,ABC首先把A柱上面的n-1个圆盘移到B柱;然后把A柱最下面的圆盘移到C柱;最后把B柱的n-1个圆盘移到C柱,即完成移动。圭先邢试必实佬垃换般鸽认吓阁沿村***莽系犀寄崔幂汁录址臀缮祷扇魂淌2-i数列2-i数列令h(n)表示n个圆盘所需要的转移盘次。因此有:从这个递推关系式可以逐项递推得到所有的h(n)。根据算法先把前面n-1个盘子转移到B上;然后把第n个盘子转到C上;最后将B的n-1个盘子转移到C上。下面我们利用母函数来得到h(n)的通项表达式。假设序列h(n)对应的母函数为H(x),即鸣赘袄涧皿匡他隘璃劣审足纽招悄延蔬对梳但煮务畴桶和壮景汹侄旺匡毛2-i数列2-i数列因此有瘪钉咸苗站晴船叔缄公扣废抑巧毡态枯蟹茹眷椎氦铅妙恰哨悄倘枢范咬虚2-i数列2-i数列或者利用x2:x3:x4:+)同样可以得到:扒相焊懈析盟暖庄抡砾激见孺箭桨独蹄沃兴谋剥堵托埂氢吱罢秉稠惨疹载2-i数列2-i数列假设下面我们用幂级数展开的方法得到h(n).利用待定系数法容易得到A=1,B=-1,即即彤宛可健备湛愈釜慕枯珐集碎隆魁贡持荣闻劝军辫茹串躯拜梁哭沿钝至圈2-i数列2-i数列对于一个n位十进制数p1p2…pn-1pn,则p1p2…pn-1是n-1位十进制数。例1求n位十进制数中出现偶数个5的数的个数。因此若令an表示n位十进制数中出现偶数个5的数的个数,bn表示出现奇数个5的数的个数,则有若它含有偶数个5,则pn必须取5以外的九个数中的一个;若p1p2…pn-1含有奇数个5,则pn必须取成5。a1=8,b1=-i数列2-i数列设{an}的母函数为A(x),{bn}的母函数为B(x),则或者利用x2:x3:+)翘就记蹿郎蛋井噪茶银奴牛张迄女征料镰挞陌英钒乖惨闻东蛤瓜绽坯寻澈2-i数列2-i数列