「荒原之梦考研数学」文章

clock() 函数是 C 标准库 time.h 中的一个函数, time.h 标准库中定义了各种涉及日期和时间的函数, 变量类型和宏. 其中, clock() 函数可以返回自程序开始执行到当前位置为止, 处理器走过的时钟打点数(即”ticks”, 可以理解为”处理器时间”). 在 VC++6.0 中, 每过千分之一秒(即 1 毫秒)则 clock() 函数的返回值加 1. 但是, 处理器的时钟打点数并不是一个人类可以直观感知的时间概念, 时钟打点数只描绘了该处理器在处理该问题时所耗费的”处理器时间”. 为了能将获取到的时间转换成便于人类理解且具有普遍性的”时 分 秒”的计时方式, 我们需要引入一个常量, 在 VC++6.0 中, 使用常量 CLOCKS_PER_SEC 来进行转换且 CLOCKS_PER_SEC=1000.
但是在不同的编译环境中, CLOCKS_PER_SEC 的数值可能是不同的. 在 Windows 10 中使用”Everything”这个程序在本机上搜索 stdio.h 可以看到我的这个计算机操作系统中存在”Emacs”, “CodeBlocks”和”Dev-cpp”三款编译器, 因此也就存在三套相互独立的 C 语言编译环境, 如图 1:

(下面以 Windows 10 下的 CodeBlocks 的编译环境为例, 查看在 C 语言的头文件中关于 CLOCKS_PER_SEC 的定义.)

在我的电脑上, CodeBlocks 的 C 语言头文件位于下面的位置:

C:\GreenSoftware\codeblocks-17.12mingw-nosetup\MinGW\include

在这个目录下找到 time.h 这个头文件, 可以在其中找到如下关于 CLOCKS_PER_SEC 的定义:

/*
 * Number of clock ticks per second. A clock tick is the unit by which
 * processor time is measured and is returned by 'clock'.
 */
#define    CLOCKS_PER_SEC  ((clock_t)1000)
#define    CLK_TCK     CLOCKS_PER_SEC

由上面的头文件中的定义可以知道, 常量 CLOCKS_PER_SEC 的值被定义为 1000, 变量类型为 clock_t.

为了验证, 我们可以在 Windows 平台上的 CodeBlocks 中运行如下 C++ 程序:

#include <iostream>
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
using namespace std;

int main()
{
    int i=10;
    clock_t start,finish;
    double Times, Times1;
    start=clock();
    while(i--){
        cout<<i<<endl;
    };
    finish=clock();
    Times=(double)(finish-start)/CLOCKS_PER_SEC;
    Times1=(double)(finish-start)/CLK_TCK;
    cout<<"start(时钟打点): "<<start<<endl;
    cout<<"finish(时钟打点): "<<finish<<endl;
    cout<<"CLOCKS_PER_SEC: "<<CLOCKS_PER_SEC<<endl;
    cout<<"CLK_TCK: "<<CLK_TCK<<endl;
    cout<<"运行时间(秒)(CLOCKS_PER_SEC): "<<Times<<endl;
    cout<<"运行时间(秒)(CLK_TCK): "<<Times1<<endl;

    return 0;
}

控制台的输出结果是:

9
8
7
6
5
4
3
2
1
0
start(时钟打点): 5
finish(时钟打点): 6
CLOCKS_PER_SEC: 1000
CLK_TCK: 1000
运行时间(秒)(CLOCKS_PER_SEC): 0.001
运行时间(秒)(CLK_TCK): 0.001

Process returned 0 (0x0)   execution time : 0.322 s
Press any key to continue.

根据上面的输出结果也可以证明在 Windows 平台上的 CodeBlocks 编译器中常量 CLOCKS_PER_SEC 的值被定义为 1000.

注: 在 VC++6.0 环境中, CLK_TCK 和 CLOCKS_PER_SEC 均被定义成 1000. 因此, 一般情况下, 在 Windows 环境中, 程序里使用 CLK_TCK 或者 CLOCKS_PER_SEC 的效果是一样的, 但是, 在 Linux 环境中只能使用 CLOCKS_PER_SEC.

Linux 下对于 CLOCKS_PER_SEC 这个常量的定义一般和 Windows 下是不同的.

Linux 下的 C 语言头文件通常都是放在 /usr/include 这个目录下.

(下面, 我将使用”Kali Linux 2019.1″进行本部分接下来的操作.)

在 /usr/include 目录下找到并打开 time.h, 在其中可以看到如下内容:

/* This defines CLOCKS_PER_SEC, which is the number of processor clock
   ticks per second, and possibly a number of other constants.   */
#include <bits/time.h>

在这个头文件里没有直接指明 CLOCKS_PER_SEC 的值, 而是选择包含了 bits/time.h 这个头文件. 于是, 我们在 /usr/include/x86_64-linux-gnu/bits 目录下找到 time.h 文件, 可以找到如下内容:

/* ISO/IEC 9899:1999 7.23.1: Components of time
   The macro `CLOCKS_PER_SEC' is an expression with type `clock_t' that is
   the number per second of the value returned by the `clock' function.  */
/* CAE XSH, Issue 4, Version 2: <time.h>
   The value of CLOCKS_PER_SEC is required to be 1 million on all
   XSI-conformant systems. */
#define CLOCKS_PER_SEC  ((__clock_t) 1000000)

由此我们知道, 在该 C 语言编译环境下, CLOCKS_PER_SEC 的值被定义成 1000000.

同样地, 在 Linux 下运行如下程序也可以看到当前编译环境下 CLOCKS_PER_SEC 的数值是多少:

#include <iostream>
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
using namespace std;

int main()
{
    int i=10;
    clock_t start,finish;
    double Times;
    start=clock();
    while(i--){
        cout<<i<<endl;
    };
    finish=clock();
    Times=(double)(finish-start)/CLOCKS_PER_SEC;
    cout<<"start(ticks): "<<start<<endl;
    cout<<"finish(ticks): "<<finish<<endl;
    cout<<"CLOCKS_PER_SEC: "<<CLOCKS_PER_SEC<<endl;
    cout<<"Total Times(s)(CLOCKS_PER_SEC): "<<Times<<endl;

    return 0;
}

运行后, 控制台的输出结果是:

9
8
7
6
5
4
3
2
1
0
start(ticks): 1124
finish(ticks): 1169
CLOCKS_PER_SEC: 1000000
Total Times(s)(CLOCKS_PER_SEC): 4.5e-05

另外, 在 time.h 这个 C 标准库中, 还定义了四个库变量, 其中库变量 clock_t 的作用是存储处理器时间, 因此, 在声明 clock() 函数的时候需要使用 clock_t 声明函数的返回值类型.

使用 clock() 计算程序中一个函数运行耗时的模板如下:

#include <stdio.h>

#include <time.h>
/*
导入 clock() 函数的头文件.
*/

clock_t start, stop;
/*
定义记录开始和结束时间的变量.
clock_t 是 clock() 函数的返回变量类型.
*/

double duration;
/*
记录函数运行时间, 单位为秒.
*/

int main(){

    start=clock();
/*
记录自 main() 函数被执行开始到本次 clock() 被调用一共走过了多少个 ticks.
*/

    MyFunction();//要进行计时的目标函数.

    stop=clock();
/*
记录自 main() 函数被执行开始到本次 clock() 被调用一共走过了多少个 ticks.
*/

    duration=((double)(stop-start))/CLOCKS_PER_SEC;
    //将时钟打点数转换成人类可以直观感知的时间秒数.

    /*
    不在测试范围内的操作写在这里, 例如输出 duration 的数值的操作等.
    */

    return 0;
}

题目

标题：等差素数列

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

题目

凑算式

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

​
（如果显示有问题，可以参见【图1.jpg】）
​
​
这个算式中A~I代表1~9的数字，不同的字母代表不同的数字。

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

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

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

题目分析

本题就是一个无重复全排列的问题, 在 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;
}

一、题目

生日蜡烛

某君从某年开始每年都举办一次生日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_1$ $q^{(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;
}

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

题目

煤球数目

有一堆煤球，堆成三角棱锥形。具体：
第一层放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