信息学奥赛-一本通-第二部分 基础算法 --＞ 第五章 搜索与回溯算法

news/2024/11/21 17:14:55/

1317：【例5.2】组合的输出
【题目描述】
排列与组合是常用的数学方法，其中组合就是从n个元素中抽出r个元素(不分顺序且r≤n)，我们可以简单地将n个元素理解为自然数1，2，…，n，从中任取r个数。

现要求你用递归的方法输出所有组合。

例如n＝5，r＝3，所有组合为：

1 2 3   1 2 4   1 2 5   1 3 4   1 3 5   1 4 5   2 3 4   2 3 5   2 4 5   3 4 5

【题目分析】

1.搜索函数参数:上一次搜索的数字i(i(n)>=i(n-1)),要搜索的数位cnt

2.结束的条件:满足个数的要求cnt==k+1

3.枚举与回溯方式:  

 for (int i = b; i <= n; i++) {
        if (vis[i] == 0) {
            vis[i] = 1;
            dfs(i + 1, r - 1);
            vis[i] = 0;
        }
    }


 

【代码实现】
#include <bits/stdc++.h>
 
using namespace std;
 
bool vis[21];
int n;
void dfs(int b, int r) {  //r 控制循环层数  b控制循环起点
    if (r == 0) {
        for (int i = 1; i <= n; i++)
            if (vis[i]) cout << "  " << i ;
        cout << endl;
        return ;
    };
 
    for (int i = b; i <= n; i++) {
        if (vis[i] == 0) {
            vis[i] = 1;
            dfs(i + 1, r - 1);
            vis[i] = 0;
        }
    }
}
int main() {
    //input data
    int  r;
    cin >> n >> r;
    dfs(1, r);
    return 0;
}

1318：【例5.3】自然数的拆分
【题目描述】
任何一个大于1的自然数n，总可以拆分成若干个小于n的自然数之和。

当n=7共14种拆分方法：

【题目分析】

7=1+1+1+1+1+1+1
7=1+1+1+1+1+2
7=1+1+1+1+3
7=1+1+1+2+2
.....
7=3+4
共14个

1.搜索函数参数:上一次搜索的数字i(i(n)>=i(n-1)),要搜索的数位cnt

2.结束的条件:和sum==n满足条件输出,sum>n不满足条件直接返回

3.枚举与回溯方式:  

 for (int i = m; i <= n; i++) {
        a[index]=i;

        sum+=i;

        dfs(i,index+i);

        sum-=i
    }

 【代码实现】
#include <bits/stdc++.h>
 
using namespace std;
 
int n;
int a[100005];
int sum = 0;
void dfs(int m, int index) {
    if (sum > n) return;
    if (sum == n) {
        cout << n << "=";
        cout << a[1];
        for (int i = 2; i < index; i++) {
            cout << "+" << a[i];
        }
        cout << endl;
        return;
    }
    for (int i = m; i < n; i++) {
        a[index] = i;
        sum += i;
        dfs(i, index + 1);
        sum -= i;
    }
}
int main() {
    //input data
    cin >> n;
    dfs(1, 1);
    return 0;
}

1212：LETTERS
【题目描述】
给出一个roe×col的大写字母矩阵，一开始的位置为左上角，你可以向上下左右四个方向移动，并且不能移向曾经经过的字母。问最多可以经过几个字母。

【题目分析】


 【代码实现】
#include <bits/stdc++.h>
 
using namespace std;
 
int n, m;
char a[25][25];
bool vis[30];
int maxc = 0;
int _next[4][2] = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
void dfs(int i, int j, int cnt) {
    maxc = max(cnt, maxc);
    for (int k = 0; k <= 3; k++) {
        int x = i + _next[k][0];
        int y = j + _next[k][1];
        if (x < 0 || y < 0 || x >= n || y >= m) continue;
        if (vis[a[x][y] - 'A']) continue;
        vis[a[x][y] - 'A'] = 1;
        dfs(x, y, cnt + 1);
        vis[a[x][y] - 'A'] = 0;
    }
}
int main() {
    //input data
    cin >> n >> m;
    getchar();
    for (int i = 0; i < n; i++) {
        cin.getline(a[i], 25);
    }
    vis[a[0][0] - 'A'] = 1;
    maxc++;
    dfs(0, 0, 1);
    cout << maxc;
    return 0;
}

1213：八皇后问题
【题目描述】
在国际象棋棋盘上放置八个皇后，要求每两个皇后之间不能直接吃掉对方。

【题目分析】


 

【代码实现】
#include <bits/stdc++.h>
 
using namespace std;
#define N 105
int a[N][N], b[N];
int vis[N][N];
int s;
void dfs(int step) {
    if (step == 8 + 1) {
        s++;
        for (int i = 1; i <= 8; i++)
            a[s][i] = b[i];
        return;
    }
    for (int i = 1; i <= 8; i++) {
        if (vis[0][i] == 0 && vis[1][step + i] == 0 && vis[2][step - i + 8] == 0) {
            vis[0][i] = 1;
            vis[1][i + step] = 1;
            vis[2][step - i + 8] = 1;
            b[step] = i;
 
            dfs(step + 1);
 
            vis[0][i] = 0;
            vis[1][i + step] = 0;
            vis[2][step - i + 8] = 0;
        }
    }
}
 
int main() {
    dfs(1);
    for (int t = 1; t <= s; t++) {
        printf("No. %d\n", t);
        for (int i = 1; i <= 8; i++) {
            for (int j = 1; j <= 8; j++) {
                if (a[t][j] == i) cout << "1 ";
                else cout << "0 ";
            }
            cout << endl;
        }
    }
    return 0;
}
1214：八皇后
【题目描述】
会下国际象棋的人都很清楚：皇后可以在横、竖、斜线上不限步数地吃掉其他棋子。如何将8个皇后放在棋盘上（有8 × 8个方格），使它们谁也不能被吃掉！这就是著名的八皇后问题。

对于某个满足要求的8皇后的摆放方法，定义一个皇后串a与之对应，即a=b1b2...b8，其中bi为相应摆法中第i行皇后所处的列数。已经知道8皇后问题一共有92组解（即92个不同的皇后串）。

给出一个数b，要求输出第b个串。串的比较是这样的：皇后串x置于皇后串y之前，当且仅当将x视为整数时比y小。

【题目分析】


【代码实现】
#include <bits/stdc++.h>
 
using namespace std;
 
int n = 8;
bool a[9][9];
int _count = 0;
int b[93][8];
void dfs(int m) {
    if (m == 9) {
//        printf("No. %d\n", ++_count);
        _count++;
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= n; j++) {
                if (a[j][i] == 1) b[_count][j] = i;
//                printf("%d ", a[j][i]);
            }
//            printf("\n");
        }
        return;
    }
    for (int i = 1; i <= n; i++) {  //第m行 第i列
        bool flag = 1;
        for (int j = 1; j <= n; j++) {
            for (int k = 1; k <= n; k++) {
                if (k == i && a[j][k] == 1) flag = 0;
                if (j - k == m - i && a[j][k] == 1) flag = 0;
                if (j + k == m + i && a[j][k] == 1) flag = 0;
                if (flag == 0) break;
            }
        }
        if (flag) {
            a[m][i] = 1;
            dfs(m + 1);
            a[m][i] = 0;
        } else continue;
    }
}
int main() {
    //input data
    dfs(1);
    int m;
    cin >> m;
    while (m--) {
        int k;
        cin >> k;
        for (int i = 1; i <= n; i++) {
            printf("%d", b[k][i]);
        }
        printf("\n");
    }
    return 0;
}

1215：迷宫
【题目描述】
一天Extense在森林里探险的时候不小心走入了一个迷宫，迷宫可以看成是由n×n的格点组成，每个格点只有22种状态，.和#，前者表示可以通行后者表示不能通行。同时当Extense处在某个格点时，他只能移动到东南西北(或者说上下左右)四个方向之一的相邻格点上，Extense想要从点A走到点B，问在不走出迷宫的情况下能不能办到。如果起点或者终点有一个不能通行(为#)，则看成无法办到。

【题目分析】


 【代码实现】
#include <bits/stdc++.h>
 
using namespace std;
 
int n, k;
int _next[4][2] = {{1, 0}, {0, 1}, {-1, 0}, {0, -1}};
char a[105][105];
bool vis[105][105];
int sx, sy, ex, ey;
bool flag = 0;
void dfs(int x, int y) {
    if (x == ex && y == ey) flag = 1;
    for (int i = 0; i <= 3; i++) {
        int nx = x + _next[i][0];
        int ny = y + _next[i][1];
        if (nx < 0 || ny < 0 || nx >= n || ny >= n) continue;
        if (vis[nx][ny] == 1 || a[nx][ny] == '#') continue;
        vis[nx][ny] = 1;
        dfs(nx, ny);
//        vis[nx][ny] = 0;
    }
}
int main() {
    //input data
    cin >> k;
    while (k--) {
        cin >> n;
        flag = 0;
        memset(vis, 0, sizeof(vis));
        for (int i = 0; i < n; i++) {
            getchar();
            for (int j = 0; j < n; j++) {
                scanf("%c", &a[i][j]);
            }
        }
        cin >> sx >> sy >> ex >> ey;
        vis[sx][sy] = 1;
        dfs(sx, sy);
        if (flag) cout << "YES" << endl;
        else cout << "NO" << endl;
    }
 
    return 0;
}

1216：红与黑
【题目描述】
有一间长方形的房子，地上铺了红色、黑色两种颜色的正方形瓷砖。你站在其中一块黑色的瓷砖上，只能向相邻的黑色瓷砖移动。请写一个程序，计算你总共能够到达多少块黑色的瓷砖。

【题目分析】

1.搜索函数参数:当前搜索的坐标(i,j),sum记录走过的黑色的瓷砖

2.结束条件:无条件

3.枚举方式(无回溯)

void dfs(int x, int y) {
    for (int i = 0; i <= 3; i++) {
        int nx = x + _next[i][0];
        int ny = y + _next[i][1];
        if (nx < 0 || ny < 0 || nx >= n || ny >= m) continue;
        if (vis[nx][ny] == 1 || a[nx][ny] == '#') continue;
        vis[nx][ny] = 1;
        sum++;
        dfs(nx, ny);
//        print();
    }
}

 【代码实现】
#include <bits/stdc++.h>
 
using namespace std;
 
int m, n;
int _next[4][2] = {{1, 0}, {0, 1}, {-1, 0}, {0, -1}};
char a[105][105];
//string a[105];
bool vis[105][105];
int sx, sy;
int sum = 0;
//void print() {
//    cout << "************************" << endl;
//    for (int i = 0; i < n; i++) {
//        for (int j = 0; j < m; j++) {
//            cout << a[i][j] << " ";
//        }
//        cout << endl;
//    }
//}
void dfs(int x, int y) {
    for (int i = 0; i <= 3; i++) {
        int nx = x + _next[i][0];
        int ny = y + _next[i][1];
        if (nx < 0 || ny < 0 || nx >= n || ny >= m) continue;
        if (vis[nx][ny] == 1 || a[nx][ny] == '#') continue;
        vis[nx][ny] = 1;
        sum++;
        dfs(nx, ny);
//        print();
    }
}
int main() {
    //input data
    while (cin >> m >> n, m + n != 0) {
        memset(vis, 0, sizeof(vis));
        sum = 0;
        for (int i = 0; i < n; i++) {
            getchar();
            for (int j = 0; j < m; j++) {
                scanf("%c", &a[i][j]);
                if (a[i][j] == '@') sx = i, sy = j;
            }
        }
//        print();
        vis[sx][sy] = 1;
        sum++;
        dfs(sx, sy);
        cout << sum << endl;
    }
 
    return 0;
}

 1217：棋盘问题
【题目描述】
在一个给定形状的棋盘（形状可能是不规则的）上面摆放棋子，棋子没有区别。要求摆放时任意的两个棋子不能放在棋盘中的同一行或者同一列，请编程求解对于给定形状和大小的棋盘，摆放 k个棋子的所有可行的摆放方案 C。

【题目分析】


 【代码实现】
#include <bits/stdc++.h>
 
using namespace std;
 
int n, k;
int sum = 0;
string a[10];
bool vis[10];
 
void dfs(int m, int row) {
    for (int i = row; i < n; i++) {
        for (int j = 0; j < n; j++) {
            if (a[i][j] == '.' || vis[j] == 1) continue;
            vis[j] = 1;
            if (m == k) sum++;
            else  dfs(m + 1, i + 1);
            vis[j] = 0;
        }
    }
}
int main() {
    //input data
    while (cin >> n >> k, n != -1) {
        sum = 0;
        memset(vis, 0, sizeof(vis));
        for (int i = 0; i < n; i++) {
            cin >> a[i];
//            cout<<a[i]<<endl;
        }
        dfs(1, 0);
        cout << sum << endl;
    }
    return 0;
}
1218：取石子游戏
【题目描述】
有两堆石子,两个人轮流去取。每次取的时候,只能从较多的那堆石子里取,并且取的数目必须是较少的那堆石子数目的整数倍，最后谁能够把一堆石子取空谁就算赢。

比如初始的时候两堆石子的数目是25和7。

25 7    -->    11 7    -->    4 7    -->    4 3    -->    1 3    -->    1 0
选手1取        选手2取        选手1取        选手2取        选手1取
最后选手1（先取的）获胜，在取的过程中选手2都只有唯一的一种取法。

给定初始时石子的数目，如果两个人都采取最优策略，请问先手能否获胜。

【题目分析】


【代码实现】
#include <bits/stdc++.h>
 
using namespace std;
 
 
bool check(int m, int n) {
    if (m < n) swap(m, n);
    if (m / n >= 2) return true;
    else return !check(m - n, n);
}
 
int main() {
    //input data
    int m, n;
    while (cin >> m >> n, m + n != 0) {
        if (check(m, n)) cout << "win" << endl;
        else cout << "lose" << endl;
    }
 
    return 0;
}
1219：马走日
【题目描述】
马在中国象棋以日字形规则移动。

请编写一段程序，给定n×m大小的棋盘，以及马的初始位置(x，y)，要求不能重复经过棋盘上的同一个点，计算马可以有多少途径遍历棋盘上的所有点。

【题目分析】


【代码实现】
#include <bits/stdc++.h>
 
using namespace std;
 
int m, n;
bool vis[15][15];
int _next[8][2] = {{1, 2}, {1, -2}, {-1, 2}, {-1, -2}, {2, 1}, {2, -1}, {-2, 1}, {-2, -1}};
int sum = 0;
int ans = 0;
void dfs(int x, int y) {
    for (int i = 0; i < 8; i++) {
        int nx = x + _next[i][0];
        int ny = y + _next[i][1];
        if (nx < 0 || nx >= m || ny < 0 || ny >= n) continue;
        if (vis[nx][ny] == 1) continue;
        vis[nx][ny] = 1;
        sum++;
        if (sum == m * n) ans++;
        else dfs(nx, ny);
        sum--;
        vis[nx][ny] = 0;
    }
}
int main() {
    //input data
    int k;
    cin >> k;
    while (k--) {
        int x, y;
        cin >> m >> n >> x >> y;
        sum = ans = 0;
        memset(vis, 0, sizeof(vis));
        vis[x][y] = 1;
        sum++;
        dfs(x, y);
        cout << ans << endl;
    }
    return 0;
}
1220：单词接龙
【题目描述】
单词接龙是一个与我们经常玩的成语接龙相类似的游戏，现在我们已知一组单词，且给定一个开头的字母，要求出以这个字母开头的最长的“龙”（每个单词都最多在“龙”中出现两次），在两个单词相连时，其重合部分合为一部分，例如beast和astonish，如果接成一条龙则变为beastonish，另外相邻的两部分不能存在包含关系，例如at和atide间不能相连。

【题目分析】


 【代码实现】
#include <bits/stdc++.h>
 
using namespace std;
 
int n;
string str;
//int len = 0;
string a[25];
int num[25];
int maxlen = 0;
 
 
int check(string s, string e) { //返回重复的个数
    int ls = min(s.size(), e.size());
    for (int i = 1; i < ls; i++) {
        if (s.substr(s.size() - i, s.size()) == e.substr(0, i)) return i;
    }
    return 0;
}
 
void dfs(int p, int len) {
    maxlen = max(maxlen, len);
    for (int i = 0; i < n; i++) {
        int k = check(a[p], a[i]);
        if (num[i] == 0 || k == 0) continue; //单词用完 不能拼接
        num[i]--;
        dfs(i, len + a[i].size() - k);
        num[i]++;
    }
}
int main() {
    //input data
    cin >> n;
    for (int i = 0; i <= n; i++) {  //read data and init
        cin >> a[i];
        num[i] = 2;
    }
 
    for (int i = 0; i < n; i++) {
        if (a[i][0] == a[n][0]) {
            num[i]--;
            dfs(i, a[i].size());
            num[i]++;
        }
    }
    cout << maxlen;
    return 0;
}
1221：分成互质组
【题目描述】
给定n个正整数，将它们分组，使得每组中任意两个数互质。至少要分成多少个组？

【题目分析】


 【代码实现】
#include <bits/stdc++.h>
 
using namespace std;
 
 
int ans = 1e9;
int d[15], group[15];
int n;
 
int gcd(int a, int b) {
    if (b == 0) return a;
    else return gcd(b, a % b);
}
 
void dfs(int pos, int cnt) {
    int i = 1;
    for (i = 1; i <= cnt + 1; i++) { //group的标号
        int j = 1;
        for (j = 1; j < pos; j++) {  //没有标号或者有互质组 j==pos
            if (group[j] == i && gcd(d[j], d[pos]) > 1)
                break;
        }
        if (j ==  pos) {
            group[pos] = i;
            int flag = 0;
            if (i > cnt) flag = 1;
            if (pos == n)
                ans = min(ans, cnt + flag);
            else
                dfs(pos + 1, cnt + flag);
        }
    }
}
int main() {
    //input data
    cin >> n;
    for (int i = 1; i <= n; i++)cin >> d[i];
    group[1] = 1;
    dfs(2, 1);
    cout << ans;
    return 0;
}
1222：放苹果
【题目描述】
把M个同样的苹果放在N个同样的盘子里，允许有的盘子空着不放，问共有多少种不同的分法？（用K表示）5，1，1和1，5，1 是同一种分法。

【题目分析】


 【代码实现】
#include <bits/stdc++.h>
 
using namespace std;
int m, n;
int ans;
int sum = 0;
int a[15];
void print() {
    for (int j = 1; j <= n; j++) {
        cout << a[j] << " ";
    }
    cout << endl;
}
void dfs(int _m, int _n) {
    for (int i = _m; i <= m; i++) {     //枚举情况
        if (sum + i <= m && _n <= n) {  //满足条件
            sum += i;                   //保存结果
            if (_n == n && sum == m) ans++; //达到目的地
            else dfs(i, _n + 1);
            sum -= i;                   //恢复状态
        }
    }
}
int main() {
    //input data
    int t;
    cin >> t;
    while (t--) {
        cin >> m >> n;
        ans = 0;
        sum = 0;
        memset(a, 0, sizeof(a));
        dfs(0, 1);
        cout << ans << endl;
    }
    return 0;
}


http://www.ppmy.cn/news/1548806.html

相关文章

Python-简单病毒程序合集(一)

Python-简单病毒程序合集(一)

前言&#xff1a;简单又有趣的Python恶搞代码&#xff0c;往往能给我们枯燥无味的生活带来一点乐趣&#xff0c;激发我们对编程的最原始的热爱。那么话不多说&#xff0c;我们直接开始今天的编程之路。 编程思路&#xff1a;本次我们将会用到os,paltform,threading,ctypes,sys,…
阅读更多...
编辑器vim 命令的学习

编辑器vim 命令的学习

1.编辑器Vim 1.vim是一个专注的编辑器 2.是一个支持多模式的编辑器 1.1见一见&#xff1a; vim 的本质也是一条命令 退出来&#xff1a;-> Shift:q 先创建一个文件 再打开这个文件 进入后先按 I 然后就可以输入了 输入完后&#xff0c;保存退出 按Esc --> 来到最后一…
阅读更多...
用 Python 从零开始创建神经网络（六）：优化（Optimization）介绍

用 Python 从零开始创建神经网络（六）：优化（Optimization）介绍

优化&#xff08;Optimization&#xff09;介绍 引言 引言 在随机初始化的模型中&#xff0c;或者即使是采用更复杂方法初始化的模型中&#xff0c;我们的目标是随着时间的推移培训或教育一个模型。为了训练一个模型&#xff0c;我们调整权重和偏差以提高模型的准确性和置信度…
阅读更多...
2024年11月15日Github流行趋势

2024年11月15日Github流行趋势

项目名称&#xff1a;MinerU 项目维护者&#xff1a;myhloli, dt-yy, Focusshang, drunkpig, papayalove等项目介绍&#xff1a;一站式开源高质量数据提取工具&#xff0c;支持从PDF、网页和多格式电子书中提取数据。项目star数&#xff1a;15,059项目fork数&#xff1a;1,105 …
阅读更多...
Debezium系列之：Debezium3版本使用快照过程中的指标

Debezium系列之：Debezium3版本使用快照过程中的指标

Debezium系列之：Debezium3版本使用快照过程中的指标 一、背景二、技术原理三、增量快照四、阻塞快照指标一、背景 使用快照技术的过程中可以观察指标，从而确定快照的进度二、技术原理 Debezium系列之：Debezium 中的增量快照Debezium系列之：Incremental snapshotting设计原理…
阅读更多...
datawhale11月组队学习 模型压缩技术2：PyTorch模型剪枝教程

datawhale11月组队学习 模型压缩技术2：PyTorch模型剪枝教程

文章目录 一、 prune模块简介1.1 常用方法1.2 剪枝效果1.3 二、三、四章剪枝测试总结 二、局部剪枝&#xff08;Local Pruning&#xff09;2.1 结构化剪枝2.1.1 对weight进行随机结构化剪枝&#xff08;random_structured&#xff09;2.1.2 对weight进行迭代剪枝&#xff08;范…
阅读更多...
计算机视觉中的双边滤波：经典案例与Python代码解析

计算机视觉中的双边滤波：经典案例与Python代码解析

&#x1f31f; 计算机视觉中的双边滤波&#xff1a;经典案例与Python代码解析 &#x1f680; Hey小伙伴们&#xff01;今天我们要聊的是计算机视觉中的一个重要技术——双边滤波。双边滤波是一种非线性滤波方法&#xff0c;主要用于图像去噪和平滑&#xff0c;同时保留图像的边…
阅读更多...
智能可观测护航“双十一”，电商零售高峰稳健冲刺！

智能可观测护航“双十一”，电商零售高峰稳健冲刺！

近期&#xff0c;“国补”等多轮刺激性政策的推出&#xff0c;激发了2024年”双十一“电商节消费热潮&#xff0c;各电商平台成交总额再创新高。伴随电商平台业务量的显著增长&#xff0c;零售、物流、制造、银行等全产业链业务系统的访问量也急速上升。面对海量的访问请求&…
阅读更多...
最新文章

Copyright @ 2022~2023