Aczy156

Algorithm19 递推与递归

[TOC]

递推与递归

斐波那契数列 （高精度）

https://www.luogu.com.cn/problem/P1255

(相似题目：https://www.luogu.com.cn/problem/P2437)

题目大意：上楼梯，一次上一步或者一次上两步，问上n阶的楼梯可以有多少种走法

1、递推公式：d[i] = d[i-1]+d[i-2];

2、斐波那契数列在n=50的时候就已经将int爆掉，所以如果n=5000的时候需要用高精度。

AC代码：

#include <iostream>
using namespace std;
#define maxn 5005
typedef long long ll;
#include <cstring>
const int N = 2005;

struct BigInt {
    int len, s[N];

    BigInt() {memset(s, 0, sizeof(s));len = 1;}
    BigInt(int num) { *this = num; }
    BigInt(char *num) { *this = num; }

    BigInt operator=(int num) {
        char c[N];
        sprintf(c, "%d", num);
        *this = c;
        return *this;
    }

    BigInt operator=(const char *num) {
        len = strlen(num);
        for (int i = 0; i < len; i++) s[i] = num[len - 1 - i] - '0';
        return *this;
    }

    string str() {
        string res = "";
        for (int i = 0; i < len; i++) res = (char) (s[i] + '0') + res;
        return res;
    }

    void clean() {while (len > 1 && !s[len - 1]) len--;}

    BigInt operator + (const BigInt &b) {
        BigInt c;
        c.len = 0;
        for (int i = 0, g = 0; g || i < len || i < b.len; i++) {
            int x = g;
            if (i < len) x += s[i];
            if (i < b.len) x += b.s[i];
            c.s[c.len++] = x % 10;
            g = x / 10;
        }
        return c;
    }

    BigInt operator - (const BigInt &b) {
        BigInt c;
        c.len = 0;
        int x;
        for (int i = 0, g = 0; i < len; i++) {
            x = s[i] - g;
            if (i < b.len) x -= b.s[i];
            if (x >= 0) g = 0;
            else {
                x += 10;
                g = 1;
            };
            c.s[c.len++] = x;
        }
        c.clean();
        return c;
    }

    BigInt operator * (const BigInt &b) {
        BigInt c;
        c.len = len + b.len;
        for (int i = 0; i < len; i++) for (int j = 0; j < b.len; j++) c.s[i + j] += s[i] * b.s[j];
        for (int i = 0; i < c.len - 1; i++) {
            c.s[i + 1] += c.s[i] / 10;
            c.s[i] %= 10;
        }
        c.clean();
        return c;
    }

    bool operator < (const BigInt &b) {
        if (len != b.len) return len < b.len;
        for (int i = len - 1; i >= 0; i--)
            if (s[i] != b.s[i]) return s[i] < b.s[i];
        return false;
    }

    BigInt operator += (const BigInt &b) {
        *this = *this + b;
        return *this;
    }

    BigInt operator -= (const BigInt &b) {
        *this = *this - b;
        return *this;
    }
};

istream &operator>>(istream &in, BigInt &x) {
    string s;
    in >> s;
    x = s.c_str();
    return in;
}

ostream &operator<<(ostream &out, BigInt &x) {
    out << x.str();
    return out;
}

int n;
BigInt d[maxn];

int main() {
    scanf("%d", &n);
    d[1] = 1, d[2] = 2;
    for (int i = 3; i <= n; ++i) d[i] = d[i - 1] + d[i - 2];
    cout << d[n] << endl;
    return 0;
}

分形-谢尔宾斯基三角

特点：数据规模是二倍的上升；大规模可以缩减成小规模去算去模拟；

https://www.luogu.com.cn/problem/P1498

#include <iostream>
using namespace std;
#define maxl 1030
int n, a[maxl][maxl];
#include <cstring>
#define cl(a, b) memset(a, b, sizeof(a))
#include <cmath>

void draw(int x, int y, int h) {
    if (h == 2) {
        a[x][y] = 1;
        return;
    }
    int nowh = h >> 1;
    for (int i = x; i < x + nowh; ++i)
        for (int j = y; j < y + nowh; ++j)
            a[i][j] = 1;
    draw(x, y + nowh, nowh);
    draw(x + nowh, y, nowh);
    draw(x + nowh, y + nowh, nowh);
}

void print() {
    for (int i = 1; i <= n; i++) {
        int j = 1;
        while (a[i][j]) {printf(" ");j++;}
        for (; j <= n; j++) {
            if (i & 1) {
                if (a[i][j] == 0)printf("/\\");
                else printf("  ");
            } else {
                if (a[i][j] == 0) {
                    printf("/__\\");
                    j++;
                } else printf("  ");
            }
        }
        printf("\n");
    }
}

int main() {
    scanf("%d", &n);
    n = pow(2, n);
    cl(a, 0); // init
    draw(1, 1, n); // draw
    print(); // print
    return 0;
}

分治思想

https://www.luogu.com.cn/problem/P1228

题目大意：用四种形状来覆盖正方形

思路：分成四个大块，然后把没有点的那个模块的剩下三个模块的端点给覆盖上即可。

#include <iostream>
using namespace std;
#define maxl 1030
int k, x, y, a[maxl][maxl];
#include <cmath>
#include <cstring>
#define cl(a, b) memset(a, b, sizeof(a))

void draw(int x, int y, int h) {
    if (h >= 2) {
        int nowh = h>>1;
        for (int i = x; i < x+h; ++i) {
            for (int j = y; j < y+h; ++j) {
                if (a[i][j]) {
                    if (i<x+nowh && j<y+nowh) {a[x+nowh][y+nowh] = a[x+nowh-1][y+nowh] = a[x+nowh][y+nowh-1] = 1;printf("%d %d 1\n", x+nowh, y+nowh);}
                    else if (i>=x+nowh && j<y+nowh) {a[x+nowh][y+nowh] = a[x+nowh-1][y+nowh-1] = a[x+nowh-1][y+nowh] = 2;printf("%d %d 3\n", x+nowh-1, y+nowh);}
                    else if (i<x+nowh && j>=y+nowh) {a[x+nowh][y+nowh] = a[x+nowh][y+nowh-1] = a[x+nowh-1][y+nowh-1] = 3;printf("%d %d 2\n", x+nowh, y+nowh-1);}
                    else if (i>=x+nowh && j>=y+nowh) {a[x+nowh-1][y+nowh-1] = a[x+nowh-1][y+nowh] = a[x+nowh][y+nowh-1] = 4;printf("%d %d 4\n", x+nowh-1, y+nowh-1);}
                    draw(x, y, nowh);draw(x+nowh, y, nowh);draw(x, y+nowh, nowh);draw(x+nowh, y+nowh, nowh);
                    return;
                }
            }
        }
    }
}

int main() {
    scanf("%d%d%d", &k, &x, &y); k = pow(2, k);
    cl(a, 0); a[x][y] = 5; // init
    draw(1, 1, k); // draw
    return 0;
}
Posted on Feb 1, 2021