[第七届蓝桥杯省赛C++B组]抽签
C++ 蓝桥 省赛 第七届
2023-09-11 14:18:49 时间
题目来源:第七届蓝桥杯省赛C++B组
算法标签:DFS
题目描述:
X星球要派出一个5人组成的观察团前往W星。
其中:
A国最多可以派出4人。
B国最多可以派出2人。
C国最多可以派出2人。
…
那么最终派往W星的观察团会有多少种国别的不同组合呢?
下面的程序解决了这个问题。
数组a[] 中既是每个国家可以派出的最多的名额。
程序执行结果为:
DEFFF CEFFF CDFFF CDEFF CCFFF CCEFF CCDFF CCDEF BEFFF BDFFF BDEFF BCFFF BCEFF BCDFF BCDEF
…
(以下省略,总共101行)
#include <stdio.h>
#define N 6
#define M 5
#define BUF 1024
void f(int a[], int k, int m, char b[])
{
int i,j;
if(k==N){
b[M] = 0;
if(m==0) printf("%s\n",b);
return;
}
for(i=0; i<=a[k]; i++){
for(j=0; j<i; j++) b[M-m+j] = k+'A';
______________________; //填空位置
}
}
int main()
{
int a[N] = {4,2,2,1,1,3};
char b[BUF];
f(a,0,M,b);
return 0;
}
仔细阅读代码,填写划线部分缺少的内容。
注意:不要填写任何已有内容或说明性文字。
题目答案:
16
题目思路:
很明显的深搜,不难想到我们需要填的肯定就是递归语句,则现在我们的问题就转换为了弄懂参数
起到什么作用。
f(int a[], int k, int m, char b[])
由题目可知一共有四个参数,其中a[N] = {4,2,2,1,1,3}
与printf("%s\n",b)
表明了a用来存放国家,b用来表示字符串是显而易见的。
那我们现在的目标转换为了弄清看k,m的作用。
因为上文,我们弄清了a,b的作用。
for(i=0; i<=a[k]; i++){//a[k]当前国家最大派出人员数量
for(j=0; j<i; j++) b[M-m+j] = k+'A';//字符串b拼接国家字符
______________________; //填空位置
我们可以明白k
的作用即为表达当前选择国家的下标。
现在我们的目标转向弄清m
的意思。
阅读b[M-m+j] = k+'A'
可以勉强清晰,这里的意思大概是给字符串b
赋予国别字符,其中M
是队伍人员总数,j
是国家派出的人数,所以m
大致起到也起到了计数的作用。
阅读退出条件
if(k==N){ //所有国家计数完毕
b[M] = 0;
if(m==0) printf("%s\n",b);//如果m==0则输出字符串
return;
且一开始递归时f(a,0,M,b);
m
的位置传的参数即为M
队伍最大人数,不难想出,m
表明的是队伍剩余位子,当所有国家计数完毕且队伍剩余位子为0时输出答案。
则综上我们不难给出答案。
f(a,k+1,m-i,b)
或者
f(a,k+1,m-j,b)
注意
1.a,b
作为数组不做变更只做传入。
2.k+1
表明递归到下一个国家选择
3.m-i
或者m-j
表明队伍空位减去一个国家派出的人数
4.i,j的范围实际相同,没有区别。
相关文章
- 《转》win7 安装ujson 出现的“error: Microsoft Visual C++ 9.0 is required. Get it from http://aka.ms/vcpython27”
- C++引用
- Java实现第十一届蓝桥杯C/C++ 大学 B 组大赛软件类 省赛真题(希望能和各位大佬能一起讨论算法题:讨论群:99979568)
- C++实现网络寻路
- java实现第二届蓝桥杯地铁换乘(C++)
- java实现第二届蓝桥杯地铁换乘(C++)
- 第二届蓝桥杯C++B组国(决)赛真题
- 第三届蓝桥杯C++B组国(决)赛真题
- 【思特奇杯·云上蓝桥-算法训练营】第十一届蓝桥杯大赛第二场省赛试题C&C++ 大学B组真题
- atitit.常用编程语言的性能比较 c c++ java
- 第十四届蓝桥杯集训——练习解题阶段(无序阶段)-ALGO-456 求链表各节点的平均值(C++解法)
- 蓝桥杯官网 试题 PREV-109 历届真题 扫地机器人【第十届】【省赛】【研究生组】【C++】【Java】【Python】三种解法
- 蓝桥杯官网 试题 PREV-265 历届真题 砝码称重【第十二届】【省赛】【研究生组】【C++】【C】【Java】【Python】四种解法
- 蓝桥杯官网 试题 PREV-267 历届真题 异或数列【第十二届】【省赛】【研究生组】【C++】【Java】两种解法
- 蓝桥杯官网 试题 PREV-274 历届真题 分果果【第十二届】【省赛】【研究生组】【C++】【Java】两种解法
- C++ 返回字符数组的写法
- C++每日面试之蓝桥杯 — 奖券数目(有些人很迷信数字,比如带“4”的数字)
- C++中二维数组的动态分配
- 第十三届蓝桥杯 C++ C 组省赛 J 题——重复的数 (AC)
- 第十三届蓝桥杯C++B组国赛F题——费用报销 (AC)
- 第十三届蓝桥杯Java、C++、Python组国赛真题——环境治理(三语言AC)
- 第十三届蓝桥杯Java、C++、Python组国赛真题——最大公约数(三语言AC)