分类： 编程开发

冒泡排序算法的排序过程

（以下排序过程按照大数位于小数右边的规则展开说明，按照大数位于小数左边的规则进行的冒泡排序与此过程类似）

1. 首先进行第 1 次遍历，选取整个队列 (队列长度为 N) 的第 1 个数字 (记为 a)，和紧邻 a 后的数字 (记为 b) 比较大小，如果 a 大于 b, 则交换 a 与 b 的位置，此后，a 继续和紧邻 a 后的数字 c 比较；如果 a 小于 b, 则丢下 a, 拿起 b, 并和紧邻 b 后的后的数字比较大小。经过这一轮比较，当比较到整个队列结束时，一共进行了 N-1 次比较，此时，整个队列中最大的数字排在了整个队列的最后；
2. 现在进行第 2 次遍历，此时只需要遍历除了第 1 次遍历后得到的数列的最后一个数之外的 N-1 个数字，即需要比较 N-2 次，得到整个数列第 2 大的数字排在上一轮排序得到的最大的数字的左边；
3. 依照前面两步所示的规则继续进行第 3, 4, 5, …, N-1 轮循环就完成了整个排序过程。

以数列 [3,2,5,1,2] 为例，冒泡排序的过程如下：

第 1 轮第 1 次比较：[2,3,5,1,2];
第 1 轮第 2 次比较：[2,3,5,1,2];
第 1 轮第 3 次比较：[2,3,1,5,2];
第 1 轮结束：[3,2,1,2,5];
第 2 轮结束：[2,1,2,3,5];
第 3 轮结束：[1,2,2,3,5];
第 4 轮结束：[1,2,2,3,5].

下面这个动图很好的演示了冒泡排序的整个过程：
（该动图使用 VisuAlgo 制作，来自：https://visualgo.net/）

C++ 实现的冒泡排序算法

递归实现

#include <iostream>
using namespace std;

int * mp(int a[], int start, int end){
    if(start<end){
/*
使用start和end这两个变量定义递归的边界条件，
start表示数组的起始位置，end表示数组的结束
位置，每次循环结束时，end都会减1，因此当start
不再小于end的时候，就代表整个数组都被遍历了，
即递归操作完成。
*/
        int temp = 0;
        for(int i = 0; i <= 8; i++){
            if(a[i]>a[i+1]){
                temp = a[i];
                a[i] = a[i+1];
                a[i+1] = temp;
            }
        }
    end --;
    mp(a,start,end);
    }
    return a;
}

int main(){
    int start = 0;
    int end = 9;
    int a[10] = {7,6,2,1,5,6,4,0,8,5};
    int *p;
    p = mp(a,start,end);

    for(int j = 0; j <=8; j++){
        cout << *(p+j) << " ";
    }
    return 0;
}

运行后输出的结果：

0 1 2 4 5 5 6 6 7
Process returned 0 (0x0)   execution time : 0.085 s
Press any key to continue.

非递归实现

双层 for 循环实现的冒泡排序（无改进）

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

int main(){
    int nums[10]={7,6,2,1,5,6,4,0,8,5};
    int temp=0;
    for(int i=0;i<=8;i++){
/*有10个数字的队列首次遍历需要比较9次，之后，
每次遍历需要比较的数字的个数都比上一次少1个。
这层循环用于确定需要遍历的队列的长度。*/
        for(int j=0;j<8-i;j++){
/*从队列第 1 个数字开始，比较到不需要比较的最后
一个数字为止，这层循环用于确定需要比较的具体的
数字。*/
            if(nums[j]>nums[j+1]){
/*如果前一个数大于后一个数，则交换两个数的位置，
把大的数字放到后面。*/
                temp = nums[j+1];
                nums[j+1]= nums[j];
                nums[j] = temp;
            }
        }
    }
    for(int z=0;z<=8;z++){
        cout<<nums[z]<<" ";
    }
    return 0;
}

上面这个程序的时间复杂度为：O(n^2^), 空间复杂度为：O(1).

双层 for 循环实现的冒泡排序（使用位置交换标志位进行改进）

我们首先对上面“双层 for 循环实现的冒泡排序（无改进）”中给出的程序做一些改变，使其能打印出每一轮排序的结果，程序如下：

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

int main(){
    int nums[10]={7,6,2,1,5,6,4,0,8,5};
    int temp=0;
    for(int i=0;i<=8;i++){
        for(int j=0;j<8-i;j++){
            if(nums[j]>nums[j+1]){
                temp = nums[j+1];
                nums[j+1]= nums[j];
                nums[j] = temp;
            }
        }
        cout<<i<<"#:"<<" ";
        for(int z=0;z<=8;z++){
        cout<<nums[z]<<" ";
    }
    cout<<endl;
    }
    return 0;
}

运行上面的程序后可以得到如下结果：

0#: 6 2 1 5 6 4 0 7 8
1#: 2 1 5 6 4 0 6 7 8
2#: 1 2 5 4 0 6 6 7 8
3#: 1 2 4 0 5 6 6 7 8
4#: 1 2 0 4 5 6 6 7 8
5#: 1 0 2 4 5 6 6 7 8
6#: 0 1 2 4 5 6 6 7 8
7#: 0 1 2 4 5 6 6 7 8
8#: 0 1 2 4 5 6 6 7 8

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

通过上面的运行结果可以看出第 6 轮循环结束时排序其实已经完成，之后的 7, 8 轮排序得出的结果和第 6 轮排序得出的结果完全一致。我们可以通过在程序中添加“位置交换标志位”来避免无用的排序，即一旦发现某一轮循环结束之后没有任何一个元素的位置发生了改变，就认为此时排序已经完成，不需要进行接下来的排序。
使用“位置交换标志位”改进后的程序如下：

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

int main(){
    int nums[10]={7,6,2,1,5,6,4,0,8,5};
    int temp=0;
    bool SwapFlag = true;
/*
定义位置交换标志变量
当发生位置交换时置为 true
未发生位置交换时置为 false
*/
    for(int i=0;i<=8&&SwapFlag==true;i++){
            SwapFlag=false;
/*
每开始一轮排序时都将标志位复位
(初始默认本轮不会出现交换)
*/
        for(int j=0;j<8-i;j++){
            if(nums[j]>nums[j+1]){
                SwapFlag=true;
/*
只要在一轮排序中发生了一次交换
则标志位置为 true
*/
                temp = nums[j+1];
                nums[j+1]= nums[j];
                nums[j] = temp;
            }
        }
        cout<<i<<"#:"<<" ";
        for(int z=0;z<=8;z++){
        cout<<nums[z]<<" ";
    }
    cout<<endl;
    }
    return 0;
}

输出结果如下：

0#: 6 2 1 5 6 4 0 7 8
1#: 2 1 5 6 4 0 6 7 8
2#: 1 2 5 4 0 6 6 7 8
3#: 1 2 4 0 5 6 6 7 8
4#: 1 2 0 4 5 6 6 7 8
5#: 1 0 2 4 5 6 6 7 8
6#: 0 1 2 4 5 6 6 7 8
7#: 0 1 2 4 5 6 6 7 8

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

可以看到，经过改进之后，在使用相同的源代码逻辑和同一组数据的情况下，排序次数减少了 1 次。

---

更改记录：

1. 2019 年 05 月 29 日 17 时 17 分，在“冒泡排序算法的排序过程”中新增了一张演示冒泡排序的动图（图 1）并添加了有关说明。

EOF

预备知识

指针函数

C++ 中指针函数的基本形式：

函数类型 * 函数名 (参数数据类型 参数1, 参数数据类型 参数 2,...){
    执行体 1;
    执行体 2;
    ...
}

例如下面这个函数就是一个指针函数：

int * a(int b[], int c){
    cout<<"Hello";
    return b;
}

指针函数的返回值是一个指针，在 main() 函数中调用该指针函数的时候，可以使用一个同类型的指针来接收。指针函数的作用之一就是解决一个函数中存在多个返回值的时候，如何返回这多个数值的问题。

静态变量

C++ 中的变量，大致可以分为（该分类不严格，仅供参考）“全局变量”、“局部变量”、“静态变量”、“全局静态变量（或称“静态全局变量”）”、“局部静态变量（或称“静态局部变量”）”和指针变量等。局部变量是存放在内存的堆区的，一旦一个函数执行完毕，则编译器就会自动释放这部分内存，该局部变量也随之消失。全局变量和静态变量都是存放在数据区（也称“全局区”或者“静态区”）的，该区域的内容可以被全局共享，在整个程序结束时，由系统自动释放。

指针变量用来存放指针，而指针就是一块内存的地址，因此，指针变量存放的就是一个内存地址。指针变量也是一个变量，是变量就需要使用内存空间存放，需要使用内存空间就需要分配内存并获取内存地址，因此，指针变量本身也是有内存地址的，存放指针变量的内存地址又指向了它存放的内存地址。指针变量的定义形式一般如下：

基类型 *指针变量名称;

在函数中定义的变量都是局部变量（在一个程序的所有函数之外定义的变量称为“全局变量”），但是我们要返回这个变量供其他函数（例如 main() 函数）使用，这个时候就需要使用“局部静态变量”来达到这个目的。

局部静态变量的定义方法就是在定义的局部变量之前加上 static 关键字。

具体实现方法

C++ 中不允许把一个数组或者多个数值作为一个整体返回，也就是说，对于 C++ 中的任何一个函数， 其返回值只能是 0 个或者 1 个单独的数字，不能是一个数组或者多个数字。不过，我们可以结合使用指针和数组（由于数组在内存中是使用一块连续的区域存储的，因此，只要知道了一个数组中第一个元素的地址并且知道了这个数组的长度，那么就可以找到和处理整个数组）来达到返回多个数值的目的。

概括地说，至少有以下三种方法：

方法一

返回一个指针指向数组中第一个元素的地址，在已知数组中第一个元素的地址和数组长度的情况下，可以唯一确定一个数组。

示例程序如下：

#include <iostream>
using namespace std;

/*
定义一个返回指针的函数用于返回数组
*/
int * ReturnMyArr(){
    static int MyArr[5] = {0,1,2,3,4};
/*
C++ 不支持在函数外面返回局部变量的地址
因此，这里定义为 static 变量
*/

    return MyArr;
}

int main(){
    int *p;
/*
定义一个整数型指针
*/

    p = ReturnMyArr();
/*
将数组的第一个元素值在内存中
的地址赋值给指针变量p
*/

/*
通过指针p打印数组
*/
    for(int i = 0; i < 5; i++){
        cout << *(p+i) << " ";
    }
}

方法二

方法二其实没有返回数组，自然也没有涉及 return, 但是方法二同样可以对数组进行处理，并使 main() 函数获取到处理后得到的新数组。

方法二的主要原理就是把待处理的数组的第一个元素的地址作为参数传入用于处理该数组的函数，被处理后的数组写入到了内存中，main() 函数从内存中读取经过处理后的数组，这样就达到了返回多个数值的效果。

示例程序如下：

#include <iostream>
using namespace std;

/*
把指针变量作为形式参数输入函数
该指针指向的是数组 a[] 中第一
个元素的地址
函数 ReturnMyArr() 的作用是对数
组 a[] 进行操作，操作的结果就写
入到了内存中，可以被 main() 函数
使用，不需要有返回值，因此使
用 void
*/
void ReturnMyArr(int *p){

/*
使用指针逐个指向数组 a[] 的每一
个元素，将她们都赋值为 0
*/
    for(int j=0; j<3; j++){
        *(p + j) = 0;
    }
}

int main(){
    int i = 0;
    int a[3] = {1,2,3};

/*
将数组 a[] 以实参的形式传入函数
ReturnMyArr()
*/
    ReturnMyArr(a);

/*
循环打印
*/
    while(i < 3){
        cout << a[i] << " ";
        i++;
    }
}

运行结果如下：

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

方法三

这里也可以不借助局部静态变量和指针实现对数组的返回。我们可以把变量定义在 main() 函数中，之后将这些变量作为参数传入指针函数。由于这些变量是定义在 main() 函数中的，因此只要 main() 函数没有结束，即使指针函数结束了，这些参数也不会由于内存回收而被销毁。

示例程序如下：

#include <iostream>
using namespace std;

int * ReturnMyArr(int a[]){
    for(int i = 0; i < 3; i++){
        a[i] = 0;
    }
/*
对数组 a[] 重新赋值
*/

    return a;
}

int main(){
    int a[3] = {1,2,3};
    int *p;
    p = ReturnMyArr(a);

    for(int i = 0; i <= 2; i++){
        cout << *(p+i) << " ";
    }

    return 0;
}

运行结果如下：

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

如果我们不想改变数组 a[] 的数值，也可以新增一个数组 b[] 用于保存数组 a[] 经过指针函数计算后的结果。

示例程序如下：

#include <iostream>
using namespace std;

int * ReturnMyArr(int a[], int b[]){
    for(int i=0; i <= 2; i++){
        b[i] = a[i];
    }
    return b;
}

int main(){
    int a[3] = {1,2,3};
    int b[3];
    int *p;
    p = ReturnMyArr(a,b);

    for(int i = 0; i <= 2; i++){
        cout << *(p+i) << " ";
    }
    return 0;
}

运行结果如下：

1 2 3
Process returned 0 (0x0)   execution time : 0.194 s
Press any key to continue.

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

题目

标题：李白打酒

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

一天，他提着酒壶，从家里出来，酒壶中有酒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

题目

标题：切面条

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

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

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

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

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

题目分析

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

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

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

通过使用 Windows 系统中的”画图”工具绘制出前 4 种情况(如果时间充裕的话可以在得出结果后绘制第 5 种情况以验证对规律的猜测是否正确), 如图 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 次.
本题的关键是正确地找出数列中的多个数值, 如果只找出前三个数值则本题很可能会得出错误的结果.

题目

标题：啤酒和饮料

啤酒每罐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

题目

题目标题: 第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;
}

题目

标题: 马虎的算式

小明是个急性子，上小学的时候经常把老师写在黑板上的题目抄错了。

有一次，老师出的题目是：36 x 495 = ?

他却给抄成了：396 x 45 = ?

但结果却很戏剧性，他的答案竟然是对的！！

因为 36 * 495 = 396 * 45 = 17820

类似这样的巧合情况可能还有很多，比如：27 * 594 = 297 * 54

假设 a b c d e 代表1~9不同的5个数字（注意是各不相同的数字，且不含0）

能满足形如： ab * cde = adb * ce 这样的算式一共有多少种呢？

请你利用计算机的优势寻找所有的可能，并回答不同算式的种类数。

满足乘法交换律的算式计为不同的种类，所以答案肯定是个偶数。

答案直接通过浏览器提交。
注意：只提交一个表示最终统计种类数的数字，不要提交解答过程或其它多余的内容。

题目分析

预备知识:
乘法交换律: a * b = b * a

该题目可以整理成以下几点:

• 将三位数中间的数字拿出来放到两位数的中间, 更换前后两数的乘积相等.
• 因为有 5 个不同的数字, 每个数字都可能取 1 到 9 不同的数字(不包括 0), 因此使用 5 层 for 循环, 将每个数字都从 1 尝试到 9, 看看是否满足 “ab * cde = adb * ce” 这样的形式.

使用编程解决问题的主要思路就是让程序一步步的满足所有题目给出的条件, 然后就可以通过一片片的循环得到最终的结果.

要满足的条件和对应的编程实现如下:

• 需要有 5 个数字, 每个数字都是从 1 到 9 -> 5 个 for 循环
• 5 个数字要各不相同 : if 判断, 每多出一个数字(每增加一层循环)都要判断这个数字是否与已有的数字相同, 只有与已有的数字不相同才继续向下循环.

解题程序如下:

#include<iostream>
#include<stdio.h> //不加这个不能使用 printf()函数
using namespace std;

int main(){
    int ans = 0;
    for (int a=1; a<10; a++){
        for (int b=1; b<10; b++){
            if(b!=a){
                for (int c=1; c<10; c++){
                    if(c!=a&&c!=b){
                        for(int d=1; d<10; d++){
                            if(d!=a&&d!=b&&d!=c){
                                for(int e=1; e<10; e++){
                                    if(e!=a&&e!=b&&e!=c&&e!=d){
                                        //判断是否满足 ab * cde = adb * ce
                                        if((a*10+b)*(c*100+d*10+e)==(a*100+d*10+b)*(c*10+e)){
                                            //为了验证结果是否正确, 可以将所有可能的结果都打印出来, 随机抽取几个手动验算
                                            printf("((%d*10+%d)*(%d*100+%d*10+%d)==(%d*100+%d*10+%d)*(%d*10+%d))=%d\n",a,b,c,d,e,a,d,b,c,e,(a*100+d*10+b)*(c*10+e));
                                            ans++;
                                        }
                                    }
                                }
                            }
                        }
                    }
                }
            }
        }
    }
    cout << ans << endl;
    return 0;
}

正确答案是:

142