2017 年蓝桥杯 C 语言 B 组省赛第 2 题: 等差素数列

题目

标题:等差素数列

2,3,5,7,11,13,….是素数序列。
类似:7,37,67,97,127,157 这样完全由素数组成的等差数列,叫等差素数数列。
上边的数列公差为30,长度为6。

2004年,格林与华人陶哲轩合作证明了:存在任意长度的素数等差数列。
这是数论领域一项惊人的成果!

有这一理论为基础,请你借助手中的计算机,满怀信心地搜索:

长度为10的等差素数列,其公差最小值是多少?

注意:需要提交的是一个整数,不要填写任何多余的内容和说明文字。

题目分析

首先, 素数 (质数) 都是大于 1 的, 因此 1 不是素数, 这点在题目中也有说明.
本题的解题思路是这样的:
我们首先需要定义一个用于判断一个数是不是素数的函数, 下面这个函数就可以判断一个大于 2 的数是不是一个素数, 如果是素数就返回真:

bool f(int x){
    for(int i=2;i<x;i++){
        if(x%i==0){
            return 0;
        }
    }
    return 1;
}

这里需要注意的是, 如果把上面这个判断素数的函数写成下面这样是不对的, 因为如果一个数能够整除除了自身和 1 之外的其他数则可以断定该数不是素数, 但是如果一个数不能够整除除了自身和 1 之外的其他数中的一个, 是不能判断其是不是素数的, 错误的素数判断程序如下:

bool f(int x){
    for(int i=2;i<x;i++){
        if(x%!=0){
            return 1;
        }
    }
    return 0;
}

之后, 我们需要从素数的起始位置, 也就是数字 2 开始, 从小到大依次判断前 1 个数加 1 是不是素数, 如果不是素数且之前计算出来的数字个数小于 10, 那么第 2 个素数开始进行上面的逐个加 1 的操作, 直到第 99999 个数字 (这个数字不一定是素数, 如果不是素数不参加之前的运算) 为止, 如果不能以 1 为公差找到 10 个数字, 则之后还是从数字 2 开始逐个加 2 并判断是不是素数, 如果不是素数则从第二个素数开始逐个进行加 2 的操作, 直到第 99999 个数字为止, 如果不能以 2 为公差找到 10 个数字, 则之后从数字 2 开始进行加 3 的操作…直到第 99999 个数字为止.

如果计算之后找不到结果可以将上面提到的有关搜索范围适当扩大.

在具体的编程实现上有以下两种.

程序 1:

#include<iostream>
#include<bits/stdc++.h>
using namespace std;

int a[99999];
bool f(int x){
    for(int i=2;i<x;i++){
        if(x%i==0){
            return 0;
        }
    }
    return 1;
}

int main(){

    for(int a=2;a<99999;a++){ //遍历首项
        for(int b=1;b<999;b++){ //遍历公差

//使用十层 if 判断寻找符合条件的数值, 能抵达第十层的说明满足条件, 输出之
            if(f(a)){
                if(f(a+b*1)){
                    if(f(a+b*2)){
                        if(f(a+b*3)){
                            if(f(a+b*4)){
                                if(f(a+b*5)){
                                    if(f(a+b*6)){
                                        if(f(a+b*7)){
                                            if(f(a+b*8)){
                                                if(f(a+b*9)){
                                                    cout<<b<<endl;
                                                }else{
                                                    continue;
                                                }
                                            }else{
                                                continue;
                                            }
                                        }else{
                                            continue;
                                        }
                                    }else{
                                        continue;
                                    }
                                }else{
                                    continue;
                                }
                            }else{
                                continue;
                            }
                        }else{
                            continue;
                        }
                    }else{
                        continue;
                    }
                }else{
                    continue;
                }
            }else{
                continue;
            }
        }
    }

    return 0;
}

程序 2:

#include<iostream>
#include<bits/stdc++.h>
#define MAX 999999
using namespace std;
int a[MAX];

bool f(int x){ //判断一个数字是不是素数的函数
    for(int i=2;i<x;i++){
        if(x%i==0){
            return 0;
            //如果能整除, 则表示这是一个非素数, 返回假 (0)
        }
    }
    return 1;
    //如果不能整除, 则表示这是一个素数, 返回真 (0)
}

int main(){

//遍历从 2 到 99999 之间的数字, 将其中的素数标记为 1
    for(int i=2;i<99999;i++){
        if(f(i)){
            a[i]=1;
        }
    }

    for(int delta=1;delta<999;delta++){
    //遍历从 1 到 999 之间的公差
        for(int i=2;i<99999;i++){
        //遍历数组 a[i]

            int step;
            for(step=0;step<10;step++){
            //限制只遍历数组 a[i] 中的 10 个数字

                //如果第 i+delta*step 个数字不是素数就退出
                if(a[i+delta*step]!=1){
                    break;
                }
            }

            //如果能完整的走完 10 步则表示找到了答案
            if(step==10){
                cout<<delta<<endl;
                return 0;
            }
        }
    }
    return 0;
}

本题的正确答案:
210

2016 年蓝桥杯 C 语言 B 组省赛第 3 题: 凑算式 (两种方法)

题目

凑算式

     B      DEF
A + --- + ------- = 10
​     C      GHI


(如果显示有问题,可以参见【图1.jpg】)


这个算式中A~I代表1~9的数字,不同的字母代表不同的数字。

比如:
6+8/3+952/714 就是一种解法,
5+3/1+972/486 是另一种解法。

这个算式一共有多少种解法?

注意:你提交应该是个整数,不要填写任何多余的内容或说明性文字。

图 1
图 1

题目分析

本题就是一个无重复全排列的问题, 在 C++ 中实现无重复全排列有以下两种主要方式:

  1. 通过 next_permutation() 函数实现全排列

next_permutation() 全排列函数只能对有序数列的数组进行全排列, 示例如下:

#include<iostream>
#include<bits/stdc++.h>
using namespace std;
int main(){
    int a[3]={0,1,2};
    while(next_permutation(a,a+3)){
        cout<<a[0]<<a[1]<<a[2];
        cout<<endl;
    }
    return 0;
}
  1. 通过循环实现全排列

假设我们要对从 1 到 3 这个三个数字进行全排列, 那么我们可以使用如下的方式进行:

#include<iostream>
#include<bits/stdc++.h>
using namespace std;

int main(){
    for(int a=1;a<=3;a++){
        for(int b=1;b<=3;b++){
            if(b!=a){
                for(int c=1;c<=3;c++){
                    if(c!=a&&c!=b){
                    cout<<a<<" "<<b<<" "<<c<<endl;
                    }
                }
            }
        }
    }
    return 0;
}

另外, 在本题中需要注意的是, 本题给出的算式是存在除法的, 涉及除法就不得不考虑精度的问题. 为了解决精度的问题, 一方面我们可以使用将整型强制转换成 double 型的方式, 另一方面也可以使用将除法转换成乘法的方式进行计算.

根据上面的分析, 我们可以有两种方法计算本题.

方法一: 使用 C++ 中的 next_permutation() 函数计算, 程序如下:

#include<iostream>
#include<bits/stdc++.h> //万能头文件, 包含所有函数
using namespace std;
int main(){
    int a[9]={1,2,3,4,5,6,7,8,9};
    int sum=0;
    while(next_permutation(a,a+9)){
    //对数组a的前9个元素进行全排列, 也就是对全部元素进行全排列

        double sum2=(double)a[0]+(double)a[1]/a[2]+double(a[3]*100+a[4]*10+a[5])/(a[6]*100+a[7]*10+a[8]);
        if(sum2==10.0){
            sum++;
        }
    }
    cout<<sum<<endl;;
    return 0;
}

方法二: 使用九层 for 循环计算, 程序如下:

#include<iostream>
#include<bits/stdc++.h>
using namespace std;

int main(){
    int ans=0;
    for(int a=1;a<=9;a++){
        for(int b=1;b<=9;b++){
            if(b!=a){
                for(int c=1;c<=9;c++){
                    if(c!=a&&c!=b){
                        for(int d=1;d<=9;d++){
                            if(d!=a&&d!=b&&d!=c){
                                for(int e=1;e<=9;e++){
                                    if(e!=a&&e!=b&&e!=c&&e!=d){
                                        for(int f=1;f<=9;f++){
                                            if(f!=a&&f!=b&&f!=c&&f!=d&&f!=e){
                                                for(int g=1;g<=9;g++){
                                                    if(g!=a&&g!=b&&g!=c&&g!=d&&g!=e&&g!=f){
                                                        for(int h=1;h<=9;h++){
                                                            if(h!=a&&h!=b&&h!=c&&h!=d&&h!=e&&h!=f&&h!=g){
                                                                for(int i=1;i<=9;i++){
                                                                    if(i!=a&&i!=b&&i!=c&&i!=d&&i!=e&&i!=f&&i!=g&&i!=h){
                                                                        double sum2=(double)a+(double)b/c+double(d*100+e*10+f)/(g*100+h*10+i);
                                                                        if(sum2==10.0){
                                                                            ans++;
                                                                        }
                                                                    }
                                                                }
                                                            }
                                                        }
                                                    }
                                                }
                                            }
                                        }
                                    }
                                }
                            }
                        }
                    }
                }
            }
        }
    }
    cout<<ans<<endl;
    return 0;
}

2016 年蓝桥杯 C 语言 B 组省赛第 2 题: 生日蜡烛 (三种解法)

题目

生日蜡烛

某君从某年开始每年都举办一次生日party,并且每次都要吹熄与年龄相同根数的蜡烛。

现在算起来,他一共吹熄了236根蜡烛。

请问,他从多少岁开始过生日party的?

请填写他开始过生日party的年龄数。
注意:你提交的应该是一个整数,不要填写任何多余的内容或说明性文字。

题目分析

这道题可以使用循环来解决. 根据实际情况, 首先假设”某君”的年龄没有超过100岁, 之后假设他从 0 岁开始过生日并吹蜡烛, 之后一直累加, 直到他吹蜡烛的总数为 236, 如果从 0 岁开始计算没有出现吹了 236 根蜡烛的情况, 那么就从 1 岁开始计算, 直到计算出吹了 236 根蜡烛的情况.

在具体的程序实现方式上有三种不同的解法.

第一种解法是, 第一层 for 循环用来遍历开始过生日的年龄, 第二层 for 循环用来遍历现在的年龄, 第三层 for 循环用来遍历从开始年龄到现在年龄之间吹的蜡烛的总数, 程序如下:

#include<iostream>
#include<bits/stdc++.h>
using namespace std;

int main(){
    for(int start=1;start<100;start++){
    //遍历开始过生日的年龄

        for(int now=1;now<100;now++){
        //遍历现在的年龄

            int sum=0;
            if(start<=now){
            //现在的年龄需要大于过去的年龄

                for(int i=start;i<=now;i++){
                //累加计算蜡烛总数
                    sum=sum+i;//注意这里要累加的变量是 i 不是 start
                }
                if(sum==236){
                //如果蜡烛总数为 236 则输出结果
                cout<<"开始的时间:"<<endl;
                cout<<start<<endl;
                cout<<"现在的时间:"<<endl;
                cout<<now<<endl;
                }
            }
        }
    }
    return 0;
}

第二种解法是, 第一层 for 循环用来遍历开始过生日的年龄, 第二层 for 循环用来遍历下一次过生日时的年龄并进行累加, 程序如下:

#include<iostream>
#include<stdio.h>
using namespace std;
int main(){
    for(int i=0;i<200;i++){ //i 为开始年龄
        int sum=0;
        //sum 要调用它的循环外最近的地方定义并初始化

        for(int j=i;j<200;j++){
        //j 为下次过生日时的年龄

            sum=sum+j;
            //计算吹蜡烛的总数

            if(sum==236){
                cout<<"开始的年龄是:"<<i<<endl;
                cout<<"现在的年龄是:"<<j<<endl;
            }
        }
    }
    return 0;
}

第三种解法是, 利用等差数列的求和公式进行计算.

等差数列的前 n 项和:

S_n=\frac{n(a_1+a_n)}{2}

等差数列的第 n 项值:

a_n=a_1+(n-1)d

等比数列的前 n 项和:

S_n=\frac{a_1(1-q^n)}{1-q}

等比数列的第 n 项值:

a_n=a_1q^{(n-1)}

根据等差数列的数学原理, 我们可以编写出如下计算程序:

#include<iostream>
#include<bits/stdc++.h>
using namespace std;

int main(){
    for(int i=1;i<=100;i++){
    //i 为数列的首项

        double sum=0;
        int a=0;
        int b=0;
        for(int j=1;j<=100;j++){
        //j 为数列递增的次数

            b=j+1;
            //目前数列有 b 项 (项数比递增的次数多 1)

            a=i+b-1;
            //计算本数列最后一项的值

            sum=b*(i+a)/2;
            //计算本数列的和

            /*每计算出一次 sum 的值都要立即进行一次判断
            判断语句不能放在本次循环的外面
            因为一个循环会遍历所有的数值之后才退出
            如果把判断语句放在循环的外面
            则不能使每次循环得出的数值都被判断*/
            if(sum==236){
            cout<<"开始过生日的年龄为:"<<i<<endl;
        }
        }

    }
    return 0;
}

在使用循环遍历的时候, 如果不能计算出我们想要的结果, 这个时候可以把循环的次数改小一些, 之后进行单步调试, 看看是不是和我们手算出来的结果一致.

2016 年蓝桥杯 C 语言 B 组省赛第 1 题: 煤球数目

题目

煤球数目

有一堆煤球,堆成三角棱锥形。具体:
第一层放1个,
第二层3个(排列成三角形),
第三层6个(排列成三角形),
第四层10个(排列成三角形),
….
如果一共有100层,共有多少个煤球?

请填表示煤球总数目的数字。
注意:你提交的应该是一个整数,不要填写任何多余的内容或说明性文字。

题目分析

本题是一个找规律的问题, 找到的规律如下:

第1层: 0+1=1
第2层: 1+2=3
第3层: 3+3=6
第4层: 6+4=10
……

可以看到, 规律就是上一层的煤球个数加上本层的层数就可以得到本层的煤球个数.

之后用编程实现, 代码如下:

#include<iostream>
#include<bits/stdc++.h>
using namespace std;
int main(){
    int sum=0;
    int sum2=0;
    for(int i=1;i<=100;i++){
        sum=sum+i;
        sum2=sum2+sum;
    }
    cout<<sum2<<endl;
    return 0;
}

本题正确答案:
171700

2014 年蓝桥杯 C 语言 B 组省赛第 3 题: 李白打酒

题目

标题:李白打酒

话说大诗人李白,一生好饮。幸好他从不开车。

一天,他提着酒壶,从家里出来,酒壶中有酒2斗。他边走边唱:

无事街上走,提壶去打酒。
逢店加一倍,遇花喝一斗。

这一路上,他一共遇到店5次,遇到花10次,已知最后一次遇到的是花,他正好把酒喝光了。

请你计算李白遇到店和花的次序,可以把遇店记为a,遇花记为b。则:babaabbabbabbbb 就是合理的次序。像这样的答案一共有多少呢?请你计算出所有可能方案的个数(包含题目给出的)。

注意:通过浏览器提交答案。答案是个整数。不要书写任何多余的内容。

题目分析

关于方案数量的问题往往都是使用深搜. 使用递归实现深搜可以使我们不必关心遍历的具体过程, 只需要把题目中给出的条件转换成程序语言即可.
根据题目信息, 变量有”店”, “酒”和”花”, 因此我们的递归函数必须包含这三个变量, 即:

void f(int dian, int hua, int jiu)...

根据”逢店加一倍,遇花喝一斗。”可以得出如下两个对函数 f() 自身进行调用的语句:

if(遇到店){
  f(dian-1,hua,jiu*2);
}

if(遇到花){
  f(dian,hua-1,jiu-1);
}

递归的边界是遇到了 5 次店, 10 次花, 并且最后酒喝光了, 即:

dian==0&&hua==0&&jiu==0

但是上面的分析过程 (对递归边界的定义) 是存在错误的. 我们根据上面的分析过程可以写出下面这个 (错误的) 程序:

#include<iostream>
#include<bits/stdc++.h>
using namespace std;
int ans=0;

void f(int dian, int hua, int jiu){
        if(dian>0&&jiu>=0){
            f(dian-1,hua,jiu*2);
        }

        if(hua>0&&jiu>=1){
            f(dian,hua-1,jiu-1);
        }

        if(dian==0&&hua==0&&jiu==0){
            ans++;
        }

    }

int main(){

    f(5,10,2);
    cout<<ans<<endl;

    return 0;
}

上面这个程序的运行结果是:
27

“27”看上去也”像是”一个正确答案. 但是, 如果我们仔细分析题目就会发现, 上面这个程序没有满足题目中给出的下面这个条件:

已知最后一次遇到的是花,他正好把酒喝光了

也就是说, 李白最后一次遇到的是花, 而且在刚遇到的花的时候, 他的酒壶里还剩 1 斗酒, 随后”遇花喝一斗”把酒壶里面的酒都喝光了. 至此, 李白一共遇到了 5 次店, 10 次花, 并且喝完了全部的酒.

但是, 在上面的程序中, 计算的仅仅是李白”遇到了 5 次店, 10 次花, 并且喝完了全部的酒”, 存在李白最后连续遇到了两次花, 每次喝一斗, 最后把酒喝完的情况, 也存在李白最后连续遇到了四次花, 每次喝一斗, 最后把酒喝完的情况(题目中没有提到酒壶容量的上限).

为了满足这个”已知最后一次遇到的是花,他正好把酒喝光了”的条件, 我们先把最后一次遇到花并喝一斗酒的情况减去, 这样只需要计算李白遇到 5 次店, 9 次花, 并剩下了 1 斗酒有多少种情况就可以了, 正确的程序如下:

#include<iostream>
#include<bits/stdc++.h>
using namespace std;
int ans=0; //定义全局变量用于计数

void f(int dian, int hua, int jiu){

/*模拟李白遇到店的情况
若要遇到店, 则剩下的店的数量必须大于 0
遇到店的时候, 剩下的花的数量不变但必须不为负数
遇到店之前不能把酒壶里面的酒喝成负数*/
        if(dian>0&&jiu>=0&&hua>=0){
            f(dian-1,hua,jiu*2);
        }

/*模拟李白遇到花的情况
若要遇到花, 则剩下的花的数量必须大于 0
遇到花的时候, 剩下的店的数量不变但必须不为负数
遇到花之前酒壶里面的酒至少要剩 1 斗以便于遇到花时喝*/        
        if(hua>0&&jiu>=1&&dian>=0){
            f(dian,hua-1,jiu-1);
        }

        if(dian==0&&hua==0&&jiu==1){
            ans++;
        }

    }

int main(){
    f(5,9,2);
    cout<<ans<<endl;
    system("pause");
    return 0;
}

本题正确答案:
14

2014 年蓝桥杯 C 语言 B 组省赛第 2 题: 切面条

题目

标题:切面条

一根高筋拉面,中间切一刀,可以得到2根面条。

如果先对折1次,中间切一刀,可以得到3根面条。

如果连续对折2次,中间切一刀,可以得到5根面条。

那么,连续对折10次,中间切一刀,会得到多少面条呢?

答案是个整数,请通过浏览器提交答案。不要填写任何多余的内容。

题目分析

本题其实可以不需要使用编程的方式解决, 这是一个数列找规律的问题. 对于找规律的问题需要记住的一点就是要手算出尽可能多的项, 这样找出来的规律才比较可靠 (题目中已经给出了数列的前三个值, 如果最终的规律可以靠前三个数列导出的话, 那么这道题就没什么考点了, 因此至少需要计算出数列中第 4 个数的值).

数列的规律可以从以下几个方面寻找:

  • 两个数值间的关系是否和两个数之间的差值有关系, 差值的变化是否具有某种规律, 例如呈指数增长的差值;
  • 前两个数的和 (或者差, 积, 商) 是否可以得出其后的数.

通过使用 Windows 系统中的”画图”工具绘制出前 4 种情况(如果时间充裕的话可以在得出结果后绘制第 5 种情况以验证对规律的猜测是否正确), 如图 1

图 1
图 1

由此, 我们可以得到关于面条个数的这样一个数列:

2, 3, 5, 9

接着我们可以得到这样一个规律:

2+0=2 (对折 0 次)
2+1=3 (对折 1 次)
3+2=5 (对折 2 次)
5+4=9 (对折 3 次)

进而得到:

2+2^0=3 (对折 1 次)
3+2^1=5 (对折 2 次)
5+2^2=9 (对折 3 次)

规律找到这里, 我们可以使用程序进行之后的计算, 程序如下:

#include<iostream>
#include<bits/stdc++.h>
using namespace std;

int main(){
    int a=2;
    int ans=2;

    for(int i=0;i<=9;i++){
            ans=ans+pow(a,i);
    }
    cout<<ans<<endl;
    return 0;
}

程序运行结果:

1025

如果不知道 C/C++ 用于求次方的函数是什么, 也可以使用循环代替, 下面的程序同样可以计算出最终结果:

#include<iostream>
#include<bits/stdc++.h>
using namespace std;

int main(){
    int ans=5;

    for(int i=2;i<=9;i++){
        int b=2;
        int a=2;
        for(int j=1;j<i;j++){
            b=b*a; //a 在循环的过程中必须始终为 2
        }
            ans=ans+b;
    }
    cout<<ans<<endl;
    return 0;
}

程序运行结果:

1025

在运行程序之前可以先设置断点进行单步调试, 看看程序运行的前几步是不是和我们手动计算出来的结果 (和规律) 一致.

另外, 正如本文开头所说的, 本题可以不通过编程的方式解决, 因为这可以看做是一个数学问题, 就是找数列的规律. 但是为什么我们上面找到数列的规律后还需要用程序计算呢? 因为上面得到的规律中, 等号左边的变量有两个, 每一步的计算都需要上一步的结果作为支撑 (当然, 也可以不编程, 直接借助系统中的计算器逐步计算, 这个方法也可以用于对程序计算结果的验证), 每一步的计算都不是独立的, 这样的规律显然不适合手算, 之前找到的规律如下:

2+2^0=3 (对折 1 次)
3+2^1=5 (对折 2 次)
5+2^2=9 (对折 3 次)

为了方便手算, 我们必须想办法去掉一个变量, 于是, 就有了下面这个规律:

1+2^0+2^0=3 (对折 1 次)
1+2^1+2^1=5 (对折 2 次)
1+2^2+2^2=9 (对折 3 次)

进而得到:

1+2*2^0=3 (对折 1 次)
1+2*2^1=5 (对折 2 次)
1+2*2^2=9 (对折 3 次)

进而又可得到:

1+2^1=3 (对折 1 次)
1+2^2=5 (对折 2 次)
1+2^3=9 (对折 3 次)

在上面的规律中, 对每次对折的求解都不依赖上一次对折得出的相关数值, 变量只有一个, 即对折的次数, 因此可以通过一次计算就得出对折 10 次后再在中间切一刀能够得到的面条个数, 计算过程与结果为:

1+2^10=1025

本题需要注意的一点是, 得到两根面条的时候 (第 1 次切的时候) 对折的次数是 0 次.
本题的关键是正确地找出数列中的多个数值, 如果只找出前三个数值则本题很可能会得出错误的结果.