有基础班_day07考试

zxcvbnm

2025-07-08 16:04:46

发布于：上海

6阅读

0回复

0点赞

题目
卡卡卡（文件）
数量（文件）
抽奖（文件）
神秘遗迹的探险之路
逃出秘境

卡卡卡（文件）

题目描述

在卡卡卡山上有 n 个粉精灵（编号从 1 到 n），他们计划从中选择 r 个人去山下采购 r 种不同的物资。你需要列出所有可能的分配情况。输出需要按照字典序排列。

输入格式

第一行包含两个整数 n 和 r，分别表示粉精灵的数量和需要选择的人数。
你需要输出所有可能的选择方式，每行输出一个组合。

输出格式

输出所有可能的分配情况，按照字典序排序。

思路分析

1. 组合问题

这是一个典型的 组合生成问题，我们需要从 n 个元素中选择 r 个元素，所有的组合都需要按字典序输出。
可以使用回溯算法（DFS）来生成所有可能的组合。

2. 字典序输出

字典序意味着较小的编号会排在前面。即从小到大顺序排列，这也正是组合数的一种自然排序方式。

3. 使用回溯算法

使用 dfs（深度优先搜索）来实现回溯，逐个选择精灵，直到选择了 r 个为止。
使用 vis 数组标记当前选择的精灵，确保每个精灵只出现一次。

代码实现

#include <iostream>
#include <cstdio>
using namespace std;

int n, r;         // n：精灵数量，r：选择的人数
int vis[20];       // 标记每个精灵是否被选择
int a[20];         // 存储当前选择的精灵编号

// 递归函数，生成组合
void dfs(int k) {
    if(k == r + 1) {  // 当已经选择了 r 个精灵
        for(int i = 1; i <= r; i++) {   // 输出当前组合
            printf("%d", a[i]);
            if(i == r) printf("\n");  // 最后一个元素后换行
            else printf(" ");         // 其他元素之间加空格
        }
        return;
    }
    for(int i = 1; i <= n; i++) {   // 遍历所有精灵
        if(vis[i]) continue;  // 如果已经选择了，跳过
        vis[i] = 1;           // 标记为选择
        a[k] = i;             // 选择第 i 个精灵
        dfs(k + 1);           // 继续选择下一个精灵
        vis[i] = 0;           // 回溯，标记为未选择
    }
    return;
}

int main() {
    // 重定向文件输入输出
    freopen("Kaka.in", "r", stdin);
    freopen("Kaka.out", "w", stdout);

    // 输入 n 和 r
    cin >> n >> r;

    // 从 1 开始进行组合生成
    dfs(1);

    // 关闭文件流
    fclose(stdin);
    fclose(stdout);

    return 0;
}

数量（文件）

题目描述

在一个迷宫中，有障碍物和可以走的空白方格。我们从给定的起点坐标出发，计算到达终点的所有可能路径的数量。路径只能经过空白方格，且不能经过障碍物，且每个方格最多只能经过一次。

思路分析

1. 深度优先搜索（DFS）

由于每个方格最多只能访问一次，DFS是解决此问题的一个非常好的选择。我们可以通过递归的方式，尝试从当前点（起点）开始，探索所有的有效路径，直到达到终点。

2. 回溯（Backtracking）

在DFS的过程中，我们会在进入一个新的方格前，标记该方格为已访问，然后在尝试完所有可能的方向后回溯，将该方格标记为未访问，继续探索其他路径。

3. 边界条件和递归出口

递归的终止条件：当我们到达终点时，增加路径计数。
如果当前点是障碍物或已经访问过的点，则不能继续向该方向移动。

4. 方向控制

题目中允许上下左右四个方向移动，可以通过方向数组来控制每次递归的方向。

算法步骤

初始化：读入迷宫的大小，障碍物的位置，以及起点和终点。
构建迷宫和障碍物标记：通过一个二维数组表示迷宫，true表示障碍物，false表示空地。
DFS搜索：从起点开始，遍历所有可行的路径，遇到终点时，路径计数加一。
输出结果：输出从起点到终点的路径总数。

代码实现

#include<bits/stdc++.h>
using namespace std;
bool vis[9][9];//定义vis数组，vis[i][j]标记(i,j)是否被访问过
bool MAP[9][9];//定义MAP数组，MAP[i][j]=false表示不是障碍物   MAP[i][j]=true是障碍物 
int n, m, t, ans, sx, sy, fx, fy;//定义n,m,t,ans,sx,sy,ex,ey 
int dir[4][2] = { 0,1,1,0,0,-1,-1,0 };//定义方向数组 
void dfs(int x, int y) {//定义函数dfs(x,y)表示当前在(x,y)位置
	if (x == fx && y == fy) { //判断是否x==fx且y==fy，判断是否到达终点 
		ans++;//路径数量+1
		return; //返回 
	}
    vis[x][y] = 1;//vis[x][y]=1,标记(x,y)访问过
	for (int i = 0; i < 4; i++) {//for循环遍历方向数组
		int nx = x + dir[i][0], ny = y + dir[i][1];//求出邻居位置(nx,ny)
		if (nx >= 1 && nx <= n && ny >= 1 && ny <= m && !vis[nx][ny] && MAP[nx][ny] == false) {//判断邻居是否在地图内且没有被访问过且不是障碍物，如果成立就走过去
			dfs(nx,ny);//去(nx,ny)的位置(从（nx，ny）开始搜索) 
		}
	}
	vis[x][y] = 0;//(x,y)位置所有的方向都尝试过了， 回退，将(x,y)位置标记为未访问过 
}
int main() {
    freopen("quantity.in", "r", stdin);
    freopen("quantity.out", "w", stdout);
	cin >> n >> m >> t;//输入n，m，t
	cin >> sx >> sy >> fx >> fy;//输入sx,sy,fx,fy
	for (int i = 0; i < t; i++) {//for循环输入t个障碍物的位置并标记
		int x, y;
		cin >> x >> y;
		MAP[x][y] = true;
	}
	dfs(sx, sy); //调用dfs(sx,sy),从(sx,sy)位置开始搜索
	cout << ans;//输出答案
    fclose(stdin);
    fclose(stdout);
	return 0;
}

抽奖（文件）

题目分析

本题要求模拟抽奖过程，给定 n 个小球，每个小球有一个积分，要求输出所有可能的抽取顺序，按小球编号的字典序排序。

问题理解

输入：给定一个整数 n 和一个长度为 n 的积分数组 a，每个小球的积分都是唯一的。
输出：输出所有小球积分的抽取顺序，要求按小球编号的字典序从小到大排列每个抽取的顺序。

字典序排列

在本题中，要求按“小球编号的字典序”输出所有排列，这意味着在处理时我们必须关注小球的索引，而不是其积分大小。因此，输出应该按照原始输入顺序排列小球，而不是积分的大小。

解题思路

回溯：利用回溯算法生成所有可能的排列。在回溯过程中使用一个 visited[] 数组来判断当前元素是否已经被选中。
输出：每生成一个排列，就输出。

关键步骤

回溯算法：选择一个数字后递归下去，直到所有数字都被选择完。

代码实现

#include <iostream>
#include <cstdio>
#include <algorithm>
using namespace std;

const int MAXN = 20;
int a[MAXN], t[MAXN];
bool vis[MAXN];
int n;

void dfs(int k) {
    if(k == n+1) {  // 如果选择了所有的数字
        for(int i = 1; i <= n; i++) {
            cout << a[t[i]];  // 输出当前排列
            if(i == n) cout << endl;
            else cout << " ";
        }
        return;
    }
    
    for(int i = 1; i <= n; i++) {
        if(vis[i]) continue;  // 如果该数字已经选择过，跳过
        t[k] = i;  // 记录选择的是a[i]（而非值本身）
        vis[i] = true;  // 标记该数字已被选择
        dfs(k + 1);  // 递归选择下一个位置
        vis[i] = false;  // 回溯，取消选择
    }
}

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

    cin >> n;

    for(int i = 1; i <= n; i++) {
        cin >> a[i];
    }

    dfs(1);  // 从位置1开始生成排列
    
	fclose(stdin);
    fclose(stdout);
    return 0;
}

神秘遗迹的探险之路

题目分析

我们需要在一个迷宫中从左上角的起点走到右下角的终点，计算所有可能的不同路径数。迷宫中的部分区域是安全的（用 * 表示），而部分区域则有危险（用 @ 表示），我们只能走在 * 区域内。

输入

一个 n x m 的迷宫矩阵。
其中 * 表示可以通行的区域，@ 表示障碍或陷阱。
迷宫的起点（左上角）和终点（右下角）一定是 *。

输出

输出从左上角到右下角的不同路径数量。

思路分析

深度优先搜索（DFS）：利用递归深度优先搜索算法遍历所有可能的路径。
状态空间：每次递归时，我们记录当前位置，避免重复访问已经走过的区域。
递归终止条件：当到达终点（右下角）时，记录找到了一条路径。

关键点

每次从当前位置 x, y 可以选择向上、下、左、右移动（即四个方向）。
需要确保当前移动不超出迷宫的边界，也不能进入障碍区 @。
路径是不同的仅依赖于它们所经过的不同区域，长度无关。

算法设计

DFS算法：从起点 (1, 1) 开始进行深度优先搜索，每次向四个方向扩展搜索，确保每个区域只被访问一次。到达终点时计数增加。
边界检查：确保移动不超出迷宫边界且不经过障碍。
回溯：每次递归后需要撤销当前的访问状态，以便进行其他尝试。

代码实现

#include <iostream>
#include <fstream>
#include <vector>
using namespace std;

int n, m;  // 迷宫的行数和列数
vector<string> mp;  // 迷宫地图
vector<vector<bool>> vis;  // 标记访问情况
int ans = 0;  // 记录路径数

// 四个方向的偏移量：右、左、下、上
int dx[] = {0, 0, 1, -1};
int dy[] = {1, -1, 0, 0};

// 深度优先搜索
void dfs(int x, int y) {
    // 到达终点
    if (x == n - 1 && y == m - 1) {
        ans++;
        return;
    }

    // 向四个方向探索
    for (int i = 0; i < 4; i++) {
        int nx = x + dx[i], ny = y + dy[i];
        // 判断新位置是否有效：在迷宫范围内，未访问过，且是通行区域
        if (nx >= 0 && nx < n && ny >= 0 && ny < m && !vis[nx][ny] && mp[nx][ny] == '*') {
            vis[nx][ny] = true;  // 标记为已访问
            dfs(nx, ny);  // 递归搜索
            vis[nx][ny] = false;  // 回溯，撤销访问标记
        }
    }
}

int main() {
    // 文件输入输出
    freopen("adventure.in", "r", stdin);
    freopen("adventure.out", "w", stdout);

    cin >> n >> m;
    mp.resize(n);
    vis.resize(n, vector<bool>(m, false));

    // 读取迷宫地图
    for (int i = 0; i < n; i++) {
        cin >> mp[i];
    }

    // 从起点(0, 0)开始进行DFS搜索
    vis[0][0] = true;  // 起点已经访问
    dfs(0, 0);

    // 输出结果
    cout << ans << endl;
	
	fclose(stdin);
    fclose(stdout);
    return 0;
}

逃出秘境

题目分析

坤坤误入了一个秘境，想要从秘境出去，他需要破解大门上的密码。密码由 8 个不同的数字组成，每个数字的范围是 0 到 9，并且每个数字都不相同。坤坤采取的暴力破解方式是从最小的数字开始逐个尝试，直到成功破解。

已知他最后尝试的一组密码，我们需要计算他已经尝试了多少组密码。密码的每一组是一个由 8 个不重复的数字组成的排列，且所有密码都按照字典序排列。

输入输出格式

输入格式

输入一个 8 位的数字，表示坤坤最后尝试的密码。这个密码可能有前导零。

输出格式

输出一个整数，表示坤坤已经尝试了多少组密码。

思路分析

我们知道密码是由 8 个不重复的数字组成的，因此一共有 10P8（即 10! / (10-8)!）种不同的排列。这个排列数等于 10!，即 10 的阶乘。我们的目标是计算给定密码在所有可能的排列中的位置。

排列数的计算：我们可以使用字典序的排列计算来确定最后一个尝试的密码在所有排列中的位置。
利用深度优先搜索（DFS）：通过递归的方法来遍历所有的排列，直到找到与输入密码相等的排列。每次递归时，计数已经尝试过的密码的数量。
回溯：我们需要确保数字不重复，因此每个数字只能出现一次。

解决方案

主要步骤

将输入密码转换为一个字符数组，便于逐个检查。
通过递归计算所有排列，并检查当前排列与输入密码的匹配情况。
当找到匹配的密码时，输出已经尝试过的密码数量。

代码实现

#include <iostream>
#include <fstream>
#include <vector>
#include <string>
using namespace std;

int ans = 0;  // 记录已经尝试的密码数量
vector<int> a(9);  // 存储当前排列
vector<bool> vis(10, false);  // 标记每个数字是否被使用
string sx;  // 输入的密码

// 深度优先搜索 (DFS)
void dfs(int k) {
    if (k == 9) {  // 到达最后一个数字时
        ans++;  // 尝试了一组密码
        string s = "";
        for (int i = 1; i <= 8; i++) {
            s += char(a[i] + '0');  // 将数字转换成字符并拼接
        }
        if (s == sx) {  // 如果当前排列与输入密码匹配
            cout << ans << endl;  // 输出已经尝试的密码数
            return;  // 找到目标密码，结束
        }
        return;
    }
    
    for (int i = 0; i <= 9; i++) {
        if (vis[i]) continue;  // 如果数字已被使用，跳过
        a[k] = i;
        vis[i] = true;  // 标记数字为已使用
        dfs(k + 1);  // 递归尝试下一个数字
        vis[i] = false;  // 回溯，撤销标记
    }
}

int main() {
    // 文件输入输出
    freopen("run.in", "r", stdin);
    freopen("run.out", "w", stdout);

    // 读取最后尝试的密码
    cin >> sx;

    // 初始化DFS
    dfs(1);
	
	fclose(stdin);
    fclose(stdout);
    return 0;
}