本文共 1959 字，大约阅读时间需要 6 分钟。
递归系列之入门题二
继续我们的递归水题吧；我感觉递归的水平基本上就是刷题刷出来的，见识多了，就6一些啊。还有就是要注意一下，我都没有写递归边界的哦；
1；杭电2045不容易系列之(3)—— LELE的RPG难题 有排成一行的ｎ个方格，用红(Red)、粉(Pink)、绿(Green)三色涂每个格子，每格涂一色，要求任何相邻的方格不能同色，且首尾两格也不同色．求全部的满足要求的涂法.
题目就是这样的，首尾不能同色，相邻不能同色。
跟以前的分析一样，同样是找f(n)与前面的关系。 要算f(n)； 第一就要研究第n-1个格子的状况；
先要解释一下f(n-1)是什么情况的种类数，当n-1个格子满足题目条件时的种类。
当n-1与第一个不同色的时候(那么此时f(n-1)就是此时n-1个格子的种类了)，那么此时f(n)的种类就应该是加上f(n-1);为什么呢？来分析一下。n-1与n相邻，则他们两个不能同色，但n-1又与第一个不同色，而n又不能他同色，只有三种颜色，那么n就没有选择，则它的种类数就要加上f(n-1)了。
当n-1与第一个格子相同时(此时就不能吧f(n-1)放进去了)。要研究f(n)这要怎么研究呢？先看看联系得到f(n-2)波？n-2与n-1相邻则他们两个不会同色，并且可以得出n-2与第一个也不会同色，是不是有f(n-2)的条件满足了。在就看怎么联系到f(n)了。n与n-1相邻则他们不会同色，并且n-1也与第一个同色，那么可以推出n有两种情况可以选择了。那么是不是将2乘以f(n-2)呢？答案是的。的确是这样子的。知道为什么吗？这个应该不难想到吧。N-1与第一个相同。那么f(n)就是与f(n-2)有联系了，而n有两种状态，当然是乘以2啊。
可以写递归方程了。 F(n) =f(n-1)+2*f(n-2); 2；杭电2569彼岸 悬崖中间飞着很多红，黄，蓝三种颜色的珠子，假设我们把悬崖看成一条长度为n的线段，线段上的每一单位长度空间都可能飞过红，黄，蓝三种珠子，而yifenfei必定会在该空间上碰到一种颜色的珠子。如果在连续3段单位空间碰到的珠子颜色都不一样，则yifenfei就会坠落。 比如经过长度为3的悬崖，碰到的珠子先后为 “红黄蓝”，或者 “蓝红黄” 等类似情况就会坠落，而如果是 “红黄红” 或者 “红黄黄”等情况则可以安全到达。 现在请问：yifenfei安然抵达彼岸的方法有多少种？ 这题是不是跟上面那题很类似啊。有三种颜色可选，连续三个单位不能同色。
同样的要求f(n)就要找关系式了。三个单位，就是前面3个，n；n-；,n-2；怎么来思考呢？
如果n-1与n-2同色，那么n就要3种选择，但是3*什么呢呢？应该是乘以(n-1与n-2同色的情况种类)，那就是是f(n-2)啊，n-1格子是与n-2相同的没有选择的，则可以推出应该是3*f(n-2)了。
如果n-1与n-2不同色，那么n就只有2种选择了。与n-1同色或者与n-2同色。那么2又是乘以什么呢？应该是乘以（n-1和n-2不同色的情况数）那是怎么表示呢？是f(n-1)-f(n-2)；可以理解吗？因为n-1与n-2同色的种类是f(n-2)。那么n-1与n-2不同色就应该是f(n-1)-f(n-2)，可以这样理解吧？
现在可以写出递归方程了吧 f(n) = 3*f(n-2) +2*(f(n-1)-f(n-2));=2*f(n-1)+f(n-2); 3;杭电2047阿牛的EOF牛肉串 准备在上面刻下一个长度为n的只由"E" "O" "F"三种字符组成的字符串（可以只有其中一种或两种字符，但绝对不能有其他字符）,阿牛同时禁止在串中出现O相邻的情况，他认为，"OO"看起来就像发怒的眼睛，效果不好。 你，NEW ACMer,EOF的崇拜者，能帮阿牛算一下一共有多少种满足要求的不同的字符串吗？
同样的分析；要求f(n)就要找它与前面的关系。
如果n-1为O，则n就有2种选择，应该是2*什么了。 n-1为O情况的种类有好多呢？那就去联系f(n-2)吧。n-1为O的情况应该是f(n-2)减去f(n-2)中n-2不为O的情况。
怎么去找f(n-2)中n-2不为O的情况呢？n-2不为O的情况，如果不出现OO不能相邻的情况，那么n-1应该是3*f（n-2），因为OO不能相邻则变成了f(n-1)，是不是可以得出上面的问题了。f(n-2)中n-2不为O的情况，应该是3*f(n-2)-f(n-1)吧。
如果n-1不为O的情况下，n应该有3种选择了吧。怎么求n-1不为O的情况的种类呢？那就应该直接是2*f(n-2)吧?那么就是3*2* f(n-2) 可以写递归方程了吧、 变形可得。F(n)=2*f(n-1)+2*f(n-2);
转载地址：https://blog.csdn.net/zw1996/article/details/51222799 如侵犯您的版权，请留言回复原文章的地址，我们会给您删除此文章，给您带来不便请您谅解！
发表评论
最新留言
关于作者
