算法设计分析之------ 递推与递归篇二

• 递归
• • Secret Cow Code S
  • 黑白棋子的移动
• 递推(动态规划)
• • 覆盖墙壁

题目链接：Secret Cow Code S

解题思路
如果我们按照正常的递归思路写，如下代码，由于n太大，会tle。

void solve(string ss){
    long long len = ss.size();
    if(len >= n){
        ans = ss[n-1];
        return ;
    }
    tp = ss[len-1];
    tp += ss.substr(0,len - 1);
    ss += tp;
    solve(ss);
}

因此我们需要换一个思路，由题目我们知道生成的字符的后半段与前一半是有联系的。因此我们可以思考如何将位置n的字符减小到原字符串中的位置。首先我们先不考虑增加字符串的额外操作，就只是把前半部分复制到后半部分，如果n在后半部分的话，如果总长度是T，那么将n 与 n - T/2 位置的子符串是一样的。由于题目是先将最后的字符串移到最前边，因此就是 n - 1 - T/2 . 同时还有一个特殊情况，如果n是后半部分的第一个位置，那么就应该是 n = T/2；

代码：

#include
#include
#include
using namespace std;

string s,tp;
long long n ,len ,t;

int main(){
    cin>>s>>n;
     len = t = s.size();
    while(t < n )t <<= 1;
    while(t != len){
        t >>= 1;
        if(n <= t)continue;
        if(t + 1 == n) n = t;
        else n = n - 1 - t;
    }
    cout< 
黑白棋子的移动 
题目链接：白棋子的移动
 解题思路：
 首先我们能找到规律，但是当最后四行也就是棋子各有两个的时候是没有规律的因此我们可以利用打表的方法来解决。
 规律就是我们总是先将连续部分白棋的最后一个棋子与连续部分黑棋的第一个棋子与后边的空格互换之后，再将空格与连续部分黑棋的最后两个互换。递归进行，一直到各剩余两个连续棋子。
 
实现技巧
 
我们需要在递归的时候记录两个变量一个是白棋连续部分最后的位置与黑棋连续部分最后的位置。
 
代码：
 
#include
#include
#include
using namespace std;

string s;
int n ,cnt,endb,enda;
string out[4] = {"ooo*o**--*", "o--*o**oo*", "o*o*o*--o*", "--o*o*o*o*"};
int a,b,c,d;

void solve(int endb,int enda){
    cnt++;
    if(enda  == 2){ // 处理最后两个是没有规律的打表输出
        for(int i = 0 ; i < 4 ; ++i){
            out[i] += s.substr(10);
            cout<
        a = enda , b = enda + 1 , c = endb - 1 , d = endb ;
        solve(endb - 2,enda);
    }
    else//将空格放到尾部
     {
         c = endb-1 , d = endb;
         solve(endb,enda - 1);
     }
    return;
}

void init(){
    for(int i = 0 ; i < n ; ++i)s += "o";
    for(int j = 0 ; j < n ; ++j) s += "*";
    s += "--";
    cout<
    cin>>n;
    init();
    solve(endb,enda);
    return 0;
}
 
递推(动态规划) 
覆盖墙壁 
题目链接：覆盖墙壁
 
解题思路：
 
 上面说的意境乘以2指的是其中一个F0 + … + F{n-3} 与 F{n-2} ， F{n-1}化简为了前一个表达式。
 
代码
 
#include
#include
using namespace std;

const int N = 1000010,mod = 1e4;

int f[N];
int pre[N];

int n;

int main(){
    cin>>n;
    pre[0] = f[0] = 1;
    for(int i = 1 ; i <= n ; ++i){
        f[i] = n >= 3 ? pre[i-1] + pre[i-3] : pre[i-1];
        f[i] %= mod;
        pre[i] = pre[i-1] + f[i];
        pre[i] %= mod;
    }
    cout<