递归与递推¶

例题 #1 汉诺塔问题¶

1205

【题目描述】

约19世纪末，在欧州的商店中出售一种智力玩具，在一块铜板上有三根杆，最左边的杆上自上而下、由小到大顺序串着由64个圆盘构成的塔。目的是将最左边杆上的盘全部移到中间的杆上，条件是一次只能移动一个盘，且不允许大盘放在小盘的上面。

这是一个著名的问题，几乎所有的教材上都有这个问题。由于条件是一次只能移动一个盘，且不允许大盘放在小盘上面，所以64个盘的移动次数是：18,446,744,073,709,551,615

这是一个天文数字，若每一微秒可能计算(并不输出)一次移动，那么也需要几乎一百万年。我们仅能找出问题的解决方法并解决较小N值时的汉诺塔，但很难用计算机解决64层的汉诺塔。

假定圆盘从小到大编号为1, 2, ...

【输入】

输入为一个整数(小于20）后面跟三个单字符字符串。

整数为盘子的数目，后三个字符表示三个杆子的编号。

【输出】

输出每一步移动盘子的记录。一次移动一行。

每次移动的记录为例如 a->3->b 的形式，即把编号为3的盘子从a杆移至b杆。

下面是 P1096 [NOIP2007 普及组] Hanoi 双塔问题的代码

#include <bits/stdc++.h>
using namespace std;
long long n, lc;
int a[222];

void chen() {
    for (int i = 0; i < lc; i++) //先加
        a[i] = a[i] * 2;

    for (int i = 0; i < lc; i++) { //进位
        a[i + 1] += a[i] / 10;
        a[i] %= 10;
    }
    if (a[lc] != 0)
        lc++;
}

void pre(int n) {
    a[0] = 1;
    lc = 1;
    //计算2^(n+1)-2
    for (int i = 1; i <= n + 1 ; i++) {
        chen();

    }
   a[0] -= 2;
    //借位
    for (int i = 0; i < lc; i++) {
        if (a[i] < 0) {
            a[i + 1] -= 1;
            a[i] += 10;
        } else
            break;
    }
}

int main() {
    //freopen("hanoi.in", "r", stdin);
    //freopen("hanoi.out", "w", stdout);

    cin >> n;
    pre(n);

    for (int i = lc-1; i>=0; i--) {
        cout << a[i];
    }
    return 0;
}

例题 #2 递推矩形¶

题目描述

给出一个 \(n \times n\) 的矩阵，矩阵中，有些格子被染成白色，有些格子被染成黑色，现要求矩阵中白色**矩形**的数量。

输入格式

第一行，一个整数 \(n\)，表示矩形的大小。

接下来 \(n\) 行，每行 \(n\) 个字符，这些字符为 \(\verb!W!\) 或 \(\verb!B!\)。其中 \(\verb!W!\) 表示白格，\(\verb!B!\) 表示黑格。

输出格式

一个正整数，为白色矩形数量。

对于\(100\%\)的数据，\(n ≤ 150\)；

典型O(n^3)扫描线，记录过去信息匹配。

/*
Code bnxt Ntsc_Hodaka
*/

#include <bits/stdc++.h>
using namespace std;
#define int unsigned long long
#define mp make_pair
#define pii pair<int,int>

///----///
#define rd read()
inline int read() {
    int xx = 0, ff = 1;
    char ch = getchar();
    while (ch < '0' || ch > '9') {
        if (ch == '-')
            ff = -1;
        ch = getchar();
    }
    while (ch >= '0' && ch <= '9') xx = xx * 10 + (ch - '0'), ch = getchar();
    return xx * ff;
}
inline void write(int out) {
    if (out < 0)
        putchar('-'), out = -out;
    if (out > 9)
        write(out / 10);
    putchar(out % 10 + '0');
}

///----///
const int N = 2e2 + 5;
const int M = 1e7 + 5;
const int INF = 1e9 + 5;
const int MOD=1e9+7;
const double eps=1e-7;

bool f1;
///----///
int n,rt,idx,m;

int a[N][N], qz[N][N], fac[N],inv[N], g;
int ret, ans;
char s[N];
bool f2;


signed main(){
    n=rd;
    for(int i=1;i<=n;i++){
        for(int j=1;j<=n;j++){
            char c;
            cin>>c;
            if(c=='W')a[i][j]=0;
            else a[i][j]=1;
        }
    }

    for(int i=1;i<=n;i++){
        for(int j=1;j<=n;j++){
            qz[i][j]=qz[i-1][j]+a[i][j];
        }
    }

    for(int i=1;i<=n;i++){
        for(int j=i;j<=n;j++){
            int h=0;
            for(int k=1;k<=n;k++){
                if(qz[j][k]-qz[i-1][k])h=k;
                else ans+=k-h;
            }
        }
    }

    cout<<ans<<endl;
    return 0;
}


/*

*/

递归与递推¶

例题 #1 汉诺塔问题¶

例题 #2 递推 矩形¶

例题 #2 递推矩形¶