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 次.
本题的关键是正确地找出数列中的多个数值, 如果只找出前三个数值则本题很可能会得出错误的结果.

2014 年蓝桥杯 C 语言 B 组省赛第 1 题: 啤酒和饮料

题目

标题:啤酒和饮料

啤酒每罐2.3元,饮料每罐1.9元。小明买了若干啤酒和饮料,一共花了82.3元。

我们还知道他买的啤酒比饮料的数量少,请你计算他买了几罐啤酒。

注意:答案是一个整数。请通过浏览器提交答案。

不要书写任何多余的内容(例如:写了饮料的数量,添加说明文字等)。

题目分析

这里使用使用循环暴力破解即可, 根据啤酒和饮料的价格以及一共花费了八十多块钱可以大致估计, 啤酒的数量不会超过 50 罐, 饮料的价格不会超过 60 罐, 由于有啤酒和饮料两个, 因此用两个嵌套的 for 循环对其进行遍历即可.

下面先来看一个有问题的程序.

下面这个程序在逻辑上是符合的, 但是无法运行出结果:

#include <iostream>
using namespace std;
int main(){
    for (int i=1; i<=50; i++){
        for (int j=1; j<=60; j++){
            if((i<j)&&(i*2.3+j*1.9==82.3)){
                cout<<i<<" "<<j<<endl;
            }
        }
    }
    return 0;
}

无法出结果的原因是, 如果参与运算的有浮点数, 那个其运算结果是不能用于比较是否相等的 (“==”两边不能是浮点数), 因为浮点数的精度不同可能导致两个本来相同的浮点数不相等.

正确的比较方法是计算两个数的差值, 如果差值小于一个极小的数就表明这两个数字是相等的, 正确的程序如下:

#include<iostream>
#include<cmath>
using namespace std;
int main(){
    for (int i=1; i<=50; i++){
        for (int j=1; j<=60; j++){
            if((i<j)&&abs((i*2.3+j*1.9) - 82.3)<0.0000000000001){
                //abs()库函数用于求绝对值
                cout<<i<<" "<<j<<endl;
            }
        }
    }
    return 0;
}

运行结果:

11 30

当然, 本题也可以通过将题目中给出的数据都扩大 10 倍, 将浮点类型转换成 int 类型之后再计算, 程序如下:

#include<iostream>
#include<bits/stdc++.h>
using namespace std;
int main(){
    for(int pj=1;pj<60;pj++){
        for(int yl=1;yl<60;yl++){
            if(pj<yl&&pj*23+yl*19==823){
                cout<<"啤酒:"<<pj<<endl;
                cout<<"饮料:"<<yl<<endl;
            }
        }
    }
    return 0;
}

运行结果:

啤酒:11
饮料:30

其中 11 是啤酒的罐数且满足啤酒的罐数小于饮料的罐数 (可以在得出结果后使用 PC 中的计算器验证一下).
本题正确答案:
11

2013 年蓝桥杯 C 语言 B 组省赛第 3 题: 第39级台阶

题目

题目标题: 第39级台阶

小明刚刚看完电影《第39级台阶》,离开电影院的时候,他数了数礼堂前的台阶数,恰好是39级!

站在台阶前,他突然又想着一个问题:

如果我每一步只能迈上1个或2个台阶。先迈左脚,然后左右交替,最后一步是迈右脚,也就是说一共要走偶数步。那么,上完39级台阶,有多少种不同的上法呢?

请你利用计算机的优势,帮助小明寻找答案。

要求提交的是一个整数。
注意:不要提交解答过程,或其它的辅助说明文字。

题目分析

本题的正确答案是:

51167078

这里涉及递归, 斐波那契数列和动态规划, 可以使用深度优先搜索 (DFS) 的思想解决问题.

首先说一下深度优先搜索. 深搜的原则就是对每一个可能的路径都深入访问直到不能继续深入访问为止, 而且每个节点只访问一次. 深搜的应用条件是上一步的走法和下一步的走法的规则是一样的且该问题具备边界以结束深搜.

首先可以简化一下这个问题, 去掉题目中要求的”走偶数步”的限制. 之后, 剩下的问题就是每次上一个或者两个台阶, 一共有多少种走法, 第一步有两种可能(走一个台阶或者走两个台阶), 随后的每走过一步的下一步也都是有两种走法(走一个台阶或者走两个台阶).

假设函数 f(n) 可以计算在上面的条件下走完 n 阶台阶会有多少种走法, 则:

走完 1 个台阶之后 (走了 1 步), 剩余的走法有 f(n-1) 种;

走完 2 个台阶之后 (走了 1 步), 剩余的走法有 f(n-2) 种.

结束条件有两个, 一个是恰好走完了 39 个台阶, 另一个是走到了第 40 个台阶(正着走的情况下, 只剩下一个台阶时却迈了两步)或者走到了第 -1 个台阶(倒着走的情况下, 只剩下一个台阶的时候却迈了两步).

正着走: 可以认为是从楼梯下面往上面走;
倒着走: 可以认为是从楼梯上面往下面走;
正着走和倒着走的效果是一样的 (例如当”楼梯”是水平的”斑马线”的时候).

使用递归实现深搜的函数大致形式如下:

递归函数f(...){
    if(...){ //本层递归函数结束条件 1
        /* code */
    }else if (...) { //本层递归函数结束条件 2
        /* code */
    }else{
        递归函数f(...)//可能的步骤 1
        递归函数f(...)//可能的步骤 2
    }
}

在具体使用递归解决深搜问题的时候, 不同的思路和方法的最终实现方式会有些差别, 具体情况可以参考如下 4 个程序 (每个程序都可以独立解决”第39级台阶”这个问题).

程序 1 如下:

#include<iostream>
#include<stdio.h>
using namespace std;
int ans; //用于保存所有可能的走法
void f(int n, int step){//n: 剩下的阶梯数, step: 已走的步数

/*剩下的台阶数是负数 (如果最后只剩下一个台阶却走了两步
会导致产生剩下负数个台阶的情况), 这是不可能发生的,
因此退出 f() 函数.*/
    if(n<0){//判断边界条件, 函数出口 1

        return;
/*在 void 函数中使用"return"可以出发函数的强制结束,
类似于循环结构中的 "break", 在这里"return"用于退出
本层深度遍历, 回到上一个未被遍历的节点继续之后的深度遍历.
*/

    }
    if(n==0&&step%2==0){//判断边界条件, 函数出口 2
        ans++;
        return;
    }

/*尝试每一种可能的结果("n-1"和"n-2")并触发
下一步的递归操作 ("n-1,step+1"和"n-2,step+1")
*/
    f(n-1,step+1); //下一步可能的走法 1
    f(n-2,step+1); //下一步可能的走法 2
}
int main(){
    f(39,0);
    cout << ans << endl;
    return 0;
}

上面的程序是倒着计算(倒着走楼梯)的, 也可以按照正着计算(正着走楼梯)的方法写程序, 程序 2 如下:

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

int sum=0;

void f(int n, int step){

        if(n==39&&step%2==0){
            sum++;
            return;
        }

        if(n>39){
            return;
        }

        f(n+1,step+1);
        f(n+2,step+1);

    }

int main(){
    f(0,0);
    cout<<sum<<endl;
    return 0;
}

为了使逻辑上更清晰一些, 可以对上面的程序 2 做以下修改, 修改后得到的程序 3 如下:

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

int sum=0;

void f(int n, int step){

        if(n==39&&step%2==0){
            sum++;
            return;
        }else if(n>39){
            return;
        }else{
            f(n+1,step+1);
            f(n+2,step+1);
        }

    }

int main(){
    f(0,0);
    cout<<sum<<endl;
    return 0;
}

当然, 递归函数除了可以使用没有返回值的 “void f()” 来定义, 也可以使用有返回值的”int f()”来定义, 例如程序 4:

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

int sum=0;

int f(int n, int step){

        if(n==39&&step%2==0){
            sum++;
            return sum;
        }else if(n>39){
            return -1;
        }else{
            f(n+1,step+1);
            f(n+2,step+1);
            return 0;
        }

    }

int main(){
    f(0,0);
    cout<<sum<<endl;
    return 0;
}

Excerpt-21 March, 2019

One

It was many and many a year ago,

In a kingdom by the sea,

That a maiden there lived whom you

May know

By the name of ANNABEL LEE;

And this maiden she lived with no other thought

Than to love and be loved by me.

I was a child and she was a child,

In this kingdom by the sea,

But we loved with a love that was more than love —

I and my Annabel Lee —

With a love that the winged seraphs of heaven

Coveted her and me.

Two

It doesn’t interest me

What you do for a living.

I want to know

What you are ache for

And if you dare to dream

Of meeting your heart’s longing.

It doesn’t interest me

How old you are

I want to know

If you will risk

Looking like a fool

For love

For your dream

For the adventure of being alive

I want to know

If you can sit with pain

Mine or your own

Without moving to hide it

Or fade it

Or fix it.

It doesn’t interest me

Who you know

Or how you came to be here

I want to know if you will stand

In the center of the fire

With me

And not shrink back.

Three

Your children are not children.

They are the sons and daughters of Life’s longing for itself.

They come through you but not from you,

And though they are with you yet they belong not to you.

You may give them your love but not your thoughts,

For they have their own thoughts.

You may house their bodies but not their souls,

For their souls dwell in the house of tomorrow,

Which you cannot visit, not even in your dreams.