设n为正整数,f(n)表示一下满足条件十进制n位数(称为波形数)的个数

设n为正整数,f(n)表示一下满足条件十进制n位数(称为波形数)的个数
满足(i)每一位上的数码是1,2,3,4中的一个
(ii)当n>=3时,每个数码都要么比其相邻左右两个数码都小,要么比其相邻左右两个数码都大
求:(1)f(10)的值
(2)f(2008)被13除得的余数
答案是8008和10
PS.kdlx2006 的递推过程中有个问题,就是这些结尾不仅仅只有一个,一定有很多数的结尾都是一样的两位,所以就不能只算一次

兄弟,人家出题要答案,你出题要命啊-.-花了半天的时间,脑细胞都死光了.不知道你这题是属于哪套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