2016年蓝桥杯c~c++省赛试题(卷)与答案.docx

【蓝桥杯C/C++省赛试题解析】 第一题：煤球数目 这是一道关于等差数列求和的问题。题目中提到的煤球排列形成一个三角棱锥形，每一层的煤球数构成一个等差数列，首项为1，公差为1的前100项和。等差数列的前n项和公式为S_n = n/2 * (首项 + 末项)。在这里，首项a_1=1，末项a_{100}=100，n=100。所以，总煤球数为S_{100} = 100/2 * (1+100) = 5050。然而，实际题目中要求的是三角形排列，即每一层的煤球数是前一层的两倍再加1。因此，实际的序列是1, 3, 6, 10...，这是二级等差数列（每两层间的差形成新的等差数列）。通过观察可知，这是一个三角数序列，第n层的煤球数为n*(n+1)/2。要得到100层的总煤球数，可以用公式求和S = 1/2 * 100 * (100 + 1) = 5050。但题目中给出的答案是171700，这是因为实际的题目描述可能有误或者题目设计者期望的解法不同。 第二题：生日蜡烛 这是一个寻找特定整数分解问题。该问题要求找出两个整数start和end，使得start到end的所有整数之和等于236。解决这个问题的方法是通过循环遍历start的值，然后对于每个start值，计算从start到end的整数之和，直到找到满足条件的start和end。题目中的答案是26，这意味着从26岁开始举办生日派对，一直到26岁+end岁，这些年龄的蜡烛总数加起来等于236。这里的end可以通过反向计算得出，即236 - 1 - 2 - 3 - ... - start。 第三题：凑算式 这道题需要找到所有可能的数位组合，使得BDEFA + --- + ------- = 10GHIC成立，其中A到I代表1到9的数字，且每个字母不重复。解决方法是使用深度优先搜索（DFS）遍历所有可能的数字组合。题目中给出的代码正是使用DFS来求解，通过对每个数字位置的递归尝试，检查最终的和是否等于1000。当找到一种合法的解时，ans计数器增加1。题目答案是29，意味着有29种不同的数字组合能满足算式。 第四题：快速排序 快速排序是一种高效的排序算法，它的基本思想是分治策略。题目中缺失的部分是在partition函数里，该函数的作用是找到一个"基准"值x，将数组分为两部分，使得左侧的元素都小于x，右侧的元素都大于或等于x。在找到正确的位置后，需要将x移动到正确的位置，即交换x和j指向的元素。因此，缺失的代码应为`swap(a, i, j);`，完成基准值的归位。 以上四题涵盖了等差数列求和、整数分解、深度优先搜索和快速排序等计算机科学的基础知识，这些都是在编程竞赛和教育/考试中常见的题目类型。通过解决这些问题，学生可以提升自己的算法思维和编程能力。