蓝桥杯C/C++ B组真题 |21xrx.com

蓝桥杯C/C++ B组真题

2023-07-07 12:54:18 深夜i 25 0

蓝桥杯 C/C++ B组真题竞赛

本文介绍了蓝桥杯C/C++ B组的真题题目及其思路，旨在帮助参赛者更好地准备和应对竞赛。

蓝桥杯是全国性的计算机竞赛，吸引了众多计算机爱好者的参与。其中，C/C++ B组是比较有难度的竞赛，需要参赛者对算法和数据结构有较为深入的了解。

本次B组的真题共有6道题目，难度从入门到提高不等，分别是：

1、输出乘法口诀表

2、判断素数

3、统计单词个数

4、环形链表的约瑟夫问题

5、汉诺塔问题

6、邻接矩阵的遍历

对于这些题目，我们分别进行分析和解答。

第一题，输出乘法口诀表，比较简单。只需要使用两层循环，分别控制乘法表的行和列，输出对应行列数的乘积即可。代码如下：

for (int i = 1; i <= 9; i++) {
  for (int j = 1; j <= i; j++) {
    cout << j << "x" << i << "=" << i * j << " ";
  }
  cout << endl;
}

第二题，判断素数，需要用到判断素数的常见方法——试除法。从 2 到该数的平方根范围内进行试除，如果能被整除，则该数不是素数。代码如下：

bool isPrime(int num) {
  if (num < 2) return false;
  for (int i = 2; i * i <= num; i++) {
    if (num % i == 0) return false;
  }
  return true;
}

第三题，统计单词个数，可以使用字符串流（stringstream）进行分割和统计单词数。其中使用 getline 函数从输入中读取字符串，然后利用字符串流进行分割，最后统计单词个数即可。代码如下：

string line;
getline(cin, line);
stringstream ss(line);
string word;
int cnt = 0;
while (ss >> word) {
  cnt++;
}
cout << cnt << endl;

第四题，环形链表的约瑟夫问题，需要用到链表的基本操作，如删除节点和遍历节点。具体方法是，先将节点放入链表中，然后根据题目要求进行删除节点，即每隔 m 个节点删除第 m 个节点，最后输出最后一个节点的编号即可。代码如下：

struct Node {
  int val;
  Node* next;
  Node(int val) : val(val), next(NULL) {}
};
int josephus(int n, int m) {
  Node* head = new Node(1);
  Node* cur = head;
  for (int i = 2; i <= n; i++) {
    cur->next = new Node(i);
    cur = cur->next;
  }
  cur->next = head;
  while (cur->next != cur) {
    for (int i = 1; i < m; i++)
      cur = cur->next;
    
    Node* nextNode = cur->next;
    cur->next = nextNode->next;
    delete nextNode;
  }
  int ans = cur->val;
  delete cur;
  return ans;
}

第五题，汉诺塔问题，这是一道经典的问题，需要进行递归求解。将当前汉诺塔问题分为三步：

1. 将前 n - 1 个盘子从 A 移到 B，借助 C

2. 将第 n 个盘子从 A 移到 C

3. 将 B 的 n - 1 个盘子借助 A 移到 C

递归求解第一步和第三步，然后将第二步输出即可。代码如下：

void hanoi(int n, char a, char b, char c) {
  if (n == 1)
    cout<< a << "->" << c << endl;
    return;
  
  hanoi(n - 1, a, c, b);
  cout << a << "->" << c << endl;
  hanoi(n - 1, b, a, c);
}

第六题，邻接矩阵的遍历，需要用到深度优先搜索（DFS）或者广度优先搜索（BFS）算法进行遍历，从而统计连通块的个数。具体方法是，从任意一个点开始进行 DFS 或 BFS，遍历整个矩阵，统计连通块的个数。注意，已经遍历的点需要打上标记，避免重复计算。代码如下：

const int N = 510;
int g[N][N];
bool vis[N][N];
int dx[4] = 1;
int dy[4] = 1;
bool check(int x, int y, int n, int m) {
  return x >= 1 && x <= n && y >= 1 && y <= m && !vis[x][y] && g[x][y];
}
void dfs(int x, int y, int n, int m) {
  vis[x][y] = true;
  for (int i = 0; i < 4; i++) {
    int nx = x + dx[i];
    int ny = y + dy[i];
    if (check(nx, ny, n, m)) {
      dfs(nx, ny, n, m);
    }
  }
}
int dfsArea(int n, int m) {
  int ans = 0;
  for (int i = 1; i <= n; i++) {
    for (int j = 1; j <= m; j++) {
      if (g[i][j] && !vis[i][j]) {
        ans++;
        dfs(i, j, n, m);
      }
    }
  }
  return ans;
}
int bfsArea(int n, int m) {
  int ans = 0;
  queue<pair<int,int>> q;
  for (int i = 1; i <= n; i++) {
    for (int j = 1; j <= m; j++) {
      if (g[i][j] && !vis[i][j]) {
        ans++;
        q.push( j);
        vis[i][j] = true;
        while(!q.empty()) {
          auto p = q.front();
          q.pop();
          int x = p.first, y = p.second;
          for (int k = 0; k < 4; k++) {
            int nx = x + dx[k];
            int ny = y + dy[k];
            if (check(nx, ny, n, m)) {
              q.push(nx);
              vis[nx][ny] = true;
            }
          }
        }
      }
    }
  }
  return ans;
}
int main() {
  int n, m;
  cin >> n >> m;
  for (int i = 1; i <= n; i++) {
    for (int j = 1; j <= m; j++) {
      cin >> g[i][j];
    }
  }
  int ans1 = dfsArea(n, m);
  memset(vis, false, sizeof vis);
  int ans2 = bfsArea(n, m);
  cout << ans1 << endl << ans2 << endl;
  return 0;
}

综上所述，这些题目涵盖了基本编程知识和算法思想，也具有一定的难度，对于参赛者来说是不可或缺的练习材料。希望大家多多练习，不断提高自己的编程技巧和算法水平。

上一篇: idea打包java可执行jar包

下一篇: Jenkins安装Node.js

评论区

相似文章