设n为正整数,f(n)表示一下满足条件十进制n位数(称为波形数)的个数满足(i)每一位上的数码是1,2,3,4中的一个(ii)当n>=3时,每个数码都要么比其相邻左右两个数码都小,要么比其相邻左右两个数码
来源:学生作业帮助网 编辑:六六作业网 时间:2024/12/24 11:47:10
设n为正整数,f(n)表示一下满足条件十进制n位数(称为波形数)的个数满足(i)每一位上的数码是1,2,3,4中的一个(ii)当n>=3时,每个数码都要么比其相邻左右两个数码都小,要么比其相邻左右两个数码
设n为正整数,f(n)表示一下满足条件十进制n位数(称为波形数)的个数
满足(i)每一位上的数码是1,2,3,4中的一个
(ii)当n>=3时,每个数码都要么比其相邻左右两个数码都小,要么比其相邻左右两个数码都大
求:(1)f(10)的值
(2)f(2008)被13除得的余数
答案是8008和10
PS.kdlx2006 的递推过程中有个问题,就是这些结尾不仅仅只有一个,一定有很多数的结尾都是一样的两位,所以就不能只算一次
设n为正整数,f(n)表示一下满足条件十进制n位数(称为波形数)的个数满足(i)每一位上的数码是1,2,3,4中的一个(ii)当n>=3时,每个数码都要么比其相邻左右两个数码都小,要么比其相邻左右两个数码
兄弟,人家出题要答案,你出题要命啊-.-花了半天的时间,脑细胞都死光了.不知道你这题是属于哪套2008年的竞赛题,估计也是大题吧.如果是道填空题,我就吐血了.我用了很笨的办法,做的累死.但愿还有清晰高效的方法吧.
首先说一句,谢谢kdlx2006,给了一个递归的思路,这题我乱想了很久,以前也没碰过类似的题,单想求f(n)确实很难,所以想了很久还是用递归,可是也不好做哦.>_<
看楼主的问题补充,感觉楼主还是有点水品的,那我就能简则简地答咯.话不多说,开解!
补充定义:f(n),其中,f(n)表示在f(n)中还满足如下条件的数的个数:
i)此数首位为i
ii)此数第二位比首位大[小]
于是,先考察f(1)、f(2):
f(1)=1
f(2):=3;=2;=1;=1;=2;=3.
先做递归再看后面的情况:
递归公式:
f(n+1)=f(n)+f(n)+f(n);
f(n+1)=f(n)+f(n);
f(n+1)=f(n);
f(n+1)=f(n);
f(n+1)=f(n)+f(n);
f(n+1)=f(n)+f(n)+f(n);
然后再补充f(3)、f(4)、f(5):
f(3):=6;=5;=3;=3;=5;=6.
f(4):=14;=11;=6;=6;=11;=14.
f(5):=31;=25;=14;=14;=25;=31.
和斐波那契数列的原理一样,这样做是无法获得一个通式的.
由于对称,下面只考虑一半的情况:
将他们写出来,即:1 2 3;3 5 6;6 11 14;14 25 31...
下面,设某一组的3个数为a b c,则根据通式写下去:
a b c;c c+b c+b+a;c+b+a 2c+2b+a 3c+2b+a;3c+2b+a 5c+4b+2a 6c+5b+3a...
现在计算这四组数每组3数之和(即f(n)/2的值):
a+b+c;a+2b+3c;3a+5b+6c;6a+11b+14c
现在做待定系数法:
α(a+b+c)+β(a+2b+3c)+γ(3a+5b+6c)=6a+11b+14c
于是,可解得:α=-1,β=1,γ=2.
所以,终于得到了递推公式:
f(n+3)=2f(n+2)+f(n+1)-f(n)(n≥2) //注意!范围很重要!
后面的事就简单了.
(1)直接根据递推式求:
f(1)=1;f(2)=12;f(3)=28;f(4)=62;f(5)=140;
f(6)=314;f(7)=706;f(8)=1586;f(9)=3564;f(10)=8008.
(2)易知f(n+3)≡2f(n+2)+f(n+1)-f(n) (mod13)(n≥2)
于是,将余数先一个个写出来,期望能找到周期性,事实上余数是有周期的,从f(1)开始,余数数列为:1 (12 2 10 10 2 4 0 1 0 2 2 6) (12 2...
除第一个数外,以12个数为一周期,易推得f(2008)真好对应余数10
答完睡觉了zzz
不会做
有答案麻烦你给我留下言
我很感兴趣
f(1)=4
f(2)=可重复的从四个数字中取两个为16
当n>=3时,考虑f(n-1)最后两位数字
12 1
21 2
13 1
31 3
14 1
41 4
23 2
32 3
24 2
42 4
34 3
43 4
在n-1位...
全部展开
f(1)=4
f(2)=可重复的从四个数字中取两个为16
当n>=3时,考虑f(n-1)最后两位数字
12 1
21 2
13 1
31 3
14 1
41 4
23 2
32 3
24 2
42 4
34 3
43 4
在n-1位数字的最后加上第n-2位的数字构成n位数字共f(n-1)种
然后分上述12种情况考虑f(n)比f(n-1)多出的部分:
12 0种
21 2种(3 4)
13 1种(2)
31 2种(2 4)
14 2种(2 3)
41 2种(2 3)
23 1种(1)
32 1种(4)
24 2种(1 3)
42 1种(3)
34 2种(1 2)
43 0种
共16种
综上:f(n)=f(n-1)+16
由f(2)=12得f(n)=16(n-2)+12=16n-20(n>=2)
故f(10)=140
f(2008)=32128被13除的余数是5
这类问题通常都是用递归数列做
收起
第一问f(10)=(3^5+2*3^4+2^2*3^2+2^4*3+2^5+1*3^4+1^2*3*3+1^3*3^2+1^4*3+1^5)*2=1572
第二问是1吧 不确定..