HZOJ Logo 张义丰的博客

博客

面试笔试算法(上)听课笔记 05-08

2021-05-08 21:54:19 By 张义丰

05-08——递归与排列组合问题----------------

OJ-240 图形打印四

递归

/*************************************************************************
    > File Name: 240.cpp
    > Author: dianjin
    > Mail: 3528956319@qq.com
    > Created Time: Sat 08 May 2021 06:19:40 PM CST
 ************************************************************************/

#include <bits/stdc++.h>
using namespace std;
int num[10] = {0, 1, 3, 9, 27, 81, 243, 729};
char ans[1005][1005];
void func(int x, int y, int n) {
    if (n == 1) {
        ans[x][y] = 'X';
        return ;
    }
    func(x, y, n-1);//左上
    func(x, y+num[n]/3*2, n-1);//右上
    func(x+num[n]/3*2, y, n-1);//左下
    func(x+num[n]/3, y+num[n]/3, n-1);//中间
    func(x+num[n]/3*2, y+num[n]/3*2, n-1);//右下
}
int main(){
    func(1, 1, 7);
    int t;
    while (cin >> t) {
        if (t == -1){
            break;
        }
        for (int i=1; i<= num[t]; i++) {
            for (int j = 1; j<=num[t];++j) {
                if (ans[i][j] == 'X'){
                    cout << 'X';
                }else{
                    cout << ' ';
                }
            }
            cout << endl;
        }
        cout << '-' << endl;
    }
    return 0;
}

OJ-235 递归实现指数型枚举

/*************************************************************************
    > File Name: 235_2.cpp
    > Author: dianjin
    > Mail: 3528956319@qq.com
    > Created Time: Sat 08 May 2021 06:39:57 PM CST
 ************************************************************************/

#include <bits/stdc++.h>
using namespace std;
int n, num[15];
void print(int x){
    cout << num[1];
    for (int i=2; i<=x; ++i){
        cout << ' ' << num[i];
    }
    cout << endl;
}
void func(int start, int ind) {
    for (int i = start; i<=n; ++i) {
        num[ind] = i;
        print(ind);
        func(i+1, ind+1);
    }
}
int main(){
    cin >> n;
    func(1, 1);
    return 0;
}

只有一个参数的递归函数(自己写的程序)

/*************************************************************************
    > File Name: 235.cpp
    > Author: dianjin
    > Mail: 3528956319@qq.com
    > Created Time: Sat 08 May 2021 06:35:01 PM CST
 ************************************************************************/

#include <bits/stdc++.h>
using namespace std;
bool c[15];
int n, a[15];
void dfs(int x){
    if (x > n) return ;
    for (int i=a[x-1]+1; i<=n; ++i){//注间这里的初始值,省掉了一下参数
        a[x] = i;
        cout << a[1];
        for (int j=2; j<=x; ++j){
            cout << ' ' << a[j];
        }
        cout << endl;
        dfs(x+1);
    }
}
int main(){
    cin >> n;
    dfs(1);
    return 0;
}

将ind参数改为全局变量cnt,体现“回溯”的思想

/*************************************************************************
    > File Name: 235_3.cpp
    > Author: dianjin
    > Mail: 3528956319@qq.com
    > Created Time: Sat 08 May 2021 06:39:57 PM CST
 ************************************************************************/

#include <bits/stdc++.h>
using namespace std;
int n, num[15], cnt = 1;
void print(){
    cout << num[1];
    for (int i=2; i<=cnt; ++i){
        cout << ' ' << num[i];
    }
    cout << endl;
}
void func(int start) {
    for (int i = start; i<=n; ++i) {
        num[cnt] = i;
        print();
        cnt ++;
        func(i+1);
        cnt --;
    }
}
int main(){
    cin >> n;
    func(1);
    return 0;
}

OJ-236 递归实现组合型枚举

自己写的

/*************************************************************************
    > File Name: 236.cpp
    > Author: dianjin
    > Mail: 3528956319@qq.com
    > Created Time: Sat 08 May 2021 07:22:16 PM CST
 ************************************************************************/

#include <bits/stdc++.h>
using namespace std;
int n, m, num[15];
void dfs(int k){
    if (k>m){
        cout << num[1];
        for (int i=2; i<=m; ++i) cout << " " << num[i];
        cout << endl;
    }else {
        for (int i=num[k-1]+1; i<=n; ++i){
            num[k] = i;
            dfs(k+1);
        }
    }
}
int main(){
    cin >> n >> m;
    dfs(1);
    return 0;
}

田船长演示的代码

/*************************************************************************
    > File Name: 236_2.cpp
    > Author: dianjin
    > Mail: 3528956319@qq.com
    > Created Time: Sat 08 May 2021 07:26:08 PM CST
 ************************************************************************/

#include <bits/stdc++.h>
using namespace std;
int n, m, num[15];
void print() {
    for (int i=1; i<=m; ++i) {
        if (i!=1) cout << " ";
        cout << num[i];
    }
    cout << endl;
}
void func(int start, int ind, int left) {
    if (left == 0){
        print();
        return ;

    }
    for (int i=start; i<=n; ++i){
        num[ind] = i;
        func(i+1, ind +1, left -1);
    }
}
int main(){
    cin >> n >> m;
    func(1, 1, m);
    return 0;
}

注意:

1,left可省略

2,for循环,条件可优化

OJ-237 递归实现排列型枚举

自己写的代码

/*************************************************************************
    > File Name: 237.cpp
    > Author: dianjin
    > Mail: 3528956319@qq.com
    > Created Time: Sat 08 May 2021 07:39:22 PM CST
 ************************************************************************/

#include <bits/stdc++.h>
using namespace std;
int n, num[10];
bool used[10];
void dfs(int k){
    if (k>n){
        cout << num[1];
        for (int i=2; i<=n; ++i) printf(" %d", num[i]);
        putchar('\n');
    }else{
        for (int i=1; i<=n; ++i) {
            if (!used[i]){
                num[k] = i;
                used[i] = true;
                dfs(k+1);
                used[i] = false;
            }
        }
    }
}
int main(){
    cin >> n;
    dfs(1);

    return 0;
}

田船长演示的代码

/*************************************************************************
    > File Name: 237_2.cpp
    > Author: dianjin
    > Mail: 3528956319@qq.com
    > Created Time: Sat 08 May 2021 07:44:02 PM CST
 ************************************************************************/

#include <bits/stdc++.h>
using namespace std;
int n, num[10], mark[10], cnt = 1;
void print(){
    for (int i=1; i<=n; ++i){
        i == 1 || putchar(' ');
        cout << num[i];
    }
    cout << endl;
}
void func() {
    if (cnt == n+1) {
        print();
        return ;
    }
    for (int i=1; i<=n; ++i){
        if (mark[i] == 0){
            mark[i] = 1;
            num[cnt] = i;
            cnt ++;
            func();
            cnt --;
            mark[i] = 0;
        }
    }
}
int main(){
    cin >> n;
    func();
    return 0;
}

【搜索】

深度优先搜索 DFS

广度优先搜索 BFS

(实例讲解及练习)

【深搜走地图】

/*************************************************************************
    > File Name: dfs.cpp
    > Author: dianjin
    > Mail: 3528956319@qq.com
    > Created Time: Sat 08 May 2021 08:45:42 PM CST
 ************************************************************************/

#include <bits/stdc++.h>
using namespace std;
int n, m, sx, sy;
int dir[4][2] = {0, 1, 1, 0, 0, -1, -1, 0};
char mmap[105][105];
int func(int x, int y){
    for (int i=0; i<4; ++i){
        int xx = x + dir[i][0];
        int yy = y + dir[i][1];
        if (mmap[xx][yy] == 'T'){
            return 1;
        }
        if (mmap[xx][yy] == '.'){
            mmap[xx][yy] = '!';
            if (func(xx, yy)){
                return 1;
            }
        }
    }
    return 0;
}
int main(){
    cin >> n >> m;
    for (int i=1; i<=n; ++i){
        for (int j=1; j<=m; ++j) {
            cin >> mmap[i][j];
            if (mmap[i][j] == 'S'){
                sx = i, sy = j;
            }
        }
    }
    if (func(sx, sy)) {
        cout << "YES" << endl;
    }else {
        cout << "NO" << endl;
    }
    for (int i = 1; i<= n; ++i){
        for (int j = 1; j<=m; ++j){
            cout << mmap[i][j];
        }
        cout << endl;
    }
    return 0;
}

评论

暂无评论

发表评论

可以用@mike来提到mike这个用户,mike会被高亮显示。如果你真的想打“@”这个字符,请用“@@”。