第一章：算法及其描述、认识DevCpp

信息技术作为当今先进生产力的代表，已经成为我国经济发展的重要支柱和强国的战略支撑。特别是近年来随着人工智能的发展、大数据在日常生活中的应用，整个社会对于信息技术的依赖程度越来越高。在这种情况下，学习编程将对未来的工作、学习和生活具有更多的实际意义。

要学习程序设计，首先要了解编程解决问题的一般过程、编写程序所要用到的语言及用来编写程序的相关软件。

一、算法及其描述

著名计算机科学家、图灵奖获得者Niklaus曾经说过：算法+数据结构=程序。由此可见，算法在程序设计中具有非常重要的作用。要了解什么是程序，首先我们要了解什么是算法。下面来看一个具体的问题：

1、渡河问题

两个大人带两个小孩来到渡口渡河。渡口只有一条船，船一次最多只能渡过一个大人或两个小孩，他们四人都会划船，但都不会游泳。现在请你帮他们设计一个渡河的方案。
因为只有一条船，而且这一条船只能渡一个大人或两个小孩，所以我们可以通过小孩的往返来实现把所有人渡到对岸。其渡河方案为：

• 第一步：两个小孩同船渡过河去。
• 第二步：一个小孩划船回来。
• 第三步：一个大人划船渡过河去。
• 第四步：对岸的小孩划船回来。
• 第五步：两个小孩同船渡过河去。
• 第六步：一个小孩划船回来。
• 第七步：余下的一个大人独自划船渡过河去。
• 第八步：对岸的小孩划船回来。
• 第九步：两个小孩再同时划船渡过河去。

2、算法

在我们用程序解决问题的时候，通常要找到解决这个问题的方法和步骤，这就是算法。
上面渡河问题的渡河方案，就是一个解决方案，而非算法。

【例1】猜数游戏

张老师在自己的手心写了一个1〜100的数字（包含1和100)，现在请同学们来猜这个数字，要是同学猜的数字大了，老师会给出提示：猜大了；要是同学猜的数字小了，老师会给出提示：猜小了；要是正确，老师会给出提示：猜对了。谁猜的次数最少，谁获胜。
对于这个问题，我们可以按顺序猜，一种方法是我们从1开始猜到100，如果张老师手里的数字恰好是100，那我们需要猜100次。当然我们也可以从100开始猜到1，如果张老师手里的数字恰好是1，我们最多还是要猜100次。
当然，我们还可以随机猜，那么猜的次数就要看运气了。比如张老师手里的数字是57, 我们随机猜了80，那么张老师提示猜大了，我们随机猜了2,张老师提示猜小了，我们随机猜 了78,张老师提示猜大了……
上面的随机猜法，最多猜的次数通常会比我们按顺序最多猜的次数要小，因为当我们猜 80的时候，张老师提示猜大了，我们就不会再去猜80后面的数。那么，每一次随机猜哪个数，才能保证我们最多猜的次数最少呢？我们发现可以猜中间的数。比如张老师手里的数是57,我们可以这样猜：
第一步：我们猜1〜100中间的数50，张老师提示猜小了（我们猜了1次）；
第二步：我们猜51〜100中间的数75，张老师提示猜大了（我们猜了2次）；
第三步：我们猜51〜74中间的数62，张老师提示猜大了（我们猜了3次）；
第四步：我们猜51〜61中间的数56，张老师提示猜小了（我们猜了4次）；
第五步：我们猜57〜61中间的数59,张老师提示猜大了（我们猜了5次）；
第六步：我们猜57〜58中间的数57，张老师提示猜对了（我们猜了6次）；
第七步：输出猜的次数6。
进而，我们可以得出这个问题的算法：
第一步：设要猜的数为X，进入第二步；
第二步：设猜数范围的左边界为left=1，右边界为right=100，猜数次数n=0，进入第
三步;
第三步：我们猜left〜right中间的数mid，mid为left与right的和整除2，然后记录猜数的次数n增加1。如果mid小于x，我们进入第四步；如果mid大于x，我们进入第五步；如果 mid等于X，我们进入第六步。
第四步：将left改为mid+1，然后返回第三步。
第五步：将right改为mid-1，然后返回第三步。
第六步：输出猜数次数n，猜数结束。
从以上的问题可以看出，一个问题可能会有多个算法。如在上述问题中，有从小到大猜数的算法、从大到小猜数的算法和从中间开始猜数的算法。对于同一个问题，不同的算法，效率可能也不一样。如从中间猜数的算法，一般就要比从小到大按顺序猜数的算法要高效。

3、算法的特征

一个算法，要能最终通过计算机的程序来实现，通常这个算法要具有如下特性：
(1) 有穷性：即一个算法必须在执行有限步后可以结束，而且每一步都要在有限的时间内完成。如例1的算法，当我们猜1〜100的数字时，最多猜9次。
(2) 确定性：对于算法的每一步应该执行的操作，在算法中都应该有明确的规定。
(3) 可行性：算法中的每一步都必须可行，都可以通过基本操作运算能够实现。如例1 中的第一步可以通过基本赋值操作left=1、right=100来实现。
(4) 有输入：算法主要是用来解决具体问题的，对于待解决的问题我们一般要用具体的数值来表示。如例1，我们用1和100来表示猜数的范围。所以作为算法加工的数值，通常需要通过输入来实现。有些输入需要在算法执行中给出，而有些算法看似没有输入，实际上已经包含在代码中。
(5) 有输出：输出是指算法执行结束后得到的结果。如例1，最后要输出猜的次数n。

4、算法的描述-流程图

可以有许多方法来描述一个算法，如猜数游戏的算法，就是用生活中的语言文字来进行描述的，这种描述方式称为自然语言描述。下面我们重点来学习另外一种常见的用图形描述的方式——流程图。

(1) 流程图的基本符号及其对应的基本操作见表

(2) 流程图的应用

下面是用流程图来描述“猜数游戏”的算法。

此外，我们还可以用N-S图、伪代码来描述算法。每种描述方法各有自己的优缺点，如用自然语言描述算法通俗易懂，但容易具有歧义；而流程图描述算法清晰简洁，但画起来又比较麻烦。所以对于具体的问题，我们可以根据需要来选择合适的描述方式。

5、小节练习

1、新学期开学了，小胖想减肥，健身教练给小胖制订了两个训练方案。方案一：每次连续跑3公里可以消耗300千卡（耗时半小时）；方案二：每次连续跑5公里可以消耗600千卡 (耗时1小时）。小胖每周周一到周四能抽出半小时跑步，周五到周日能抽出一小时跑步。 另外，教练建议小胖每周最多跑21公里，否则会损伤膝盖。请问如果小胖严格执行教练的训练方案，并且不想损伤膝盖，每周最多跑步消耗（ ）千卡？（2019CSP-J入门级）
A. 3000 B. 2500 C. 2400 D. 2520

2、 —些数字可以颠倒过来看，例如0、1、8颠倒过来还是本身，6颠倒过来是9，9颠倒过来看是6，其他数字颠倒过来都不构成数字。类似的，一些多位数也可以颠倒过来看，比如106颠倒过来是901。假设某个城市的车牌只由5位数字组成，每一位都可以取0到9。请问这个城市最多有（ ）个车牌倒过来恰好还是原来的车牌？（2019CSP-J入门级）
A. 60 B. 125 C.75 D. 100

3、如果开始时计算机处于小写输入状态，现在有一只小老鼠反复按照CapsLock、字母键A、字母键S、字母键D、字母键F的顺序循环按键，即CapsLock、A、S、D、F、 CapsLock、A、S、D、F……屏幕上输出的第81个字符是字母（ ）。（2018年NOIP初赛普及组）
A. A B. S C. D D. a

4、2017年10月1日是星期日，1999年10月1日是（ ）。（2017年NOIP初赛普及组）
A.星期三 B.星期日 C.星期五 D.星期二

5、设计算法：输入一个整数，判定这个整数是奇数还是偶数。用流程图描述。

6、设计算法：输入一个整数，求出这个整数的因子个数，如输入12，那么12的因子有1、2、3、4、6、12—共6个，所以12的因子个数为6。用流程图来描述。

二、认识DevCpp

对于一个问题，设计好算法后，下面要解决的就是如何把这个算法转换成计算机能够操作的语句，这些语句如何去编写和调试。这就需要了解程序设计语言及编写程序的相关软件。

1、程序及程序设计语言

我们所说的程序，通常是指一组计算机能够操作的语句或指令。
就像我们写文章，要用具体的语言来描述一样，编写程序也要用具体的语言来实现。写文章或日常交流，我们有中文、英文、日文等。同样，编写程序的语言也有C++、Python、Java和 C语言等。
我们主要学习的语言是C++，用来实现C++语言编写程序的软件有很多，DevCpp就是一款常用的软件。

2、Dev-C软件的安装和使用

Dev-C的版本很多，目前用得比较多的版本是5.11，这是一款免费软件，可以直接从官网下载。下面视频演示的是在Windows系统中安装DevCpp5.11的过程。

3、小节练习

在DevCpp中创建一个“ex1.cpp”文件，在文件中输入以下的C++程序：

#include<bits/stdc++.h>
using namespace std;
int main(){
    const float pi=3.14;
    float r,c,s;
    cin>>r;
    c=2*pi*r;
    s=pi*r*r;
    cout<<c<<endl;
    cout<<s<<endl;
    return 0;
}

输入3后按回车键，观察输出的答案，然后尝试输入其他一些整数，猜想其运行结果。

三、初步认识并编程解决问题

利用计算机快速运算的性能，我们可以通过自己编写的程序来解决日常生活中的许多问题，如数据的计算、汇总、筛选、查询等。那么对于生活中的问题，如果要用程序来解决，应该如何来实现呢？下面通过一个具体的例子来说明编程解决问题的一般过程。

1、问题说明

上述的内容，我们通常称为问题描述。要用程序来解决这个问题，通常我们还要从问题描述中抽象出具体的数据，有些数据是确定的，如妈妈每个月给津津300元；有些数据是不确定的，需要我们从键盘输入。所以为了解决这个问题，在问题描述后，我们通常还要描述这个问题需要输入数据的格式。如上述问题，我们给出如下的输入数据格式：

一般，当问题描述和输入格式确定后，就可以来编写程序了，但最终问题的结果如何呈现，这里还涉及输出的格式问题。所以在输入格式确定后，还要给出输出的格式。如上述问题，我们给出如下的输出格式：

最后，为了具体地说明问题，一般还会给出这个问题的输入样例，以及和输入样例对应的输出样例，有时为了说明问题，我们可能会给出多组样例。如上述问题给出下面的两组输入、输出样例：

综上可以发现，为了说明一个问题，我们一般用问题描述、输入格式、输出格式，以及具体的输入样例和输出样例，来明确界定要编写的程序所需解决的具体问题。因为程序和算法的局限，有时我们还会对数据的范围进行单独的明确界定，如上述问题，我们界定妈妈每个月给津津的零花钱数是“一个小于350的非负整数”。

2、编程解决问题的过程

(1) 分析问题

主要是依据问题的描述、输入、输出数据，来分析输人数据和输出数据的关系，从而形成解决问题的策略，为下一步设计算法提供依据。例如在上述问题中，通过分析，我们发现首先要解决是否出现钱不够用的月份，这个只要通过计算上个月剩下的钱加上妈妈当月给的零花钱是否会小于该月的预算即可。其次，要计算津津到年末手中有多少钱，通过问题分析，我们发现年末津津手中的钱s，等于12月份结束津津手中剩下的钱x、存在妈妈那儿的 钱以及这些钱的利息三者之和。

(2) 设计算法

依据上述的问题分析，我们形成下面的算法

(3) 编写代码

算法仅仅是我们解决问题的方法和步骤，要用程序来解决问题，还需要把算法转换成符合C++语言规范的代码。依据上述算法，我们在DevCpp软件中创建一个文件，写出如下 C++代码：

#include<bits/stdc++.h>
#define n 12
using namespace std;
int main(){
    int a[n+10],x=0,s=0,y;
    for(int i=1;i<=n;i++) cin >> a[i];
    for(int i=1;i<=n;i++){
        x=x+300;
        if(x<a[i]){
            cout<<-i<< endl;
            return 0;
        }
        y=(x-a[i])/100*100;
        s=s+y;
        x=x-y-a[i];
    }
    s=s+s*20/100+x;
    cout<<s<<endl;
    return 0;
}

(4) 调试运行

最后，在DevCpp中编译运行这个程序。如果程序运行过程中出错，还需要借助DevCpp来修改和调试，直到运行出要求的正确结果。

3、小节练习

小凯叔叔的服装店今天有一批新货送达。这批货包括领带a条、围巾b条、背心c件和夹克d件。现在小凯的叔叔希望不出售单一的服装，而是出售两种类型的套装：
套装1：由一条领带和一件夹克组成；
套装2：包括一条围巾、一件背心和一件夹克。
套装1的单价为e，套装2的单价为f。
小凯的叔叔想知道这批货物最多可以销售多少钱。
请你就上述问题设计输入格式、输出格式、输入样例和输出样例。并用流程图表示出求解该问题的算法。

四、认识C++程序

C++是美国AT&T贝尔实验室在20世纪80年代初期发明并实现的。起初，C++是作为 C语言的增强版出现的，从给C语言增加类开始，不断地增加新特性。
多年来，不管程序设计语言如何变化，C++始终是最主流的编程语言之一。很多操作系统和应用软件的底层都需要用C++语言来编写。

1、C++语言的特点

(1) 语言简洁紧凑，使用灵活方便

C++语言一共有84个关键字和9种控制语句，程序书写自由，一般主要用小写字母表示。

(2) 运算符丰富

C++语言的运算符包含的范围很广泛，共有34个运算符。

(3) 数据类型丰富

C++语言的数据类型有：整型、实型、字符型、数组类型等等。

(4) 结构化语言

结构化语言的显著特点是代码及数据的分隔化，即程序的各个部分除了必要的信息交流外，彼此独立。

(5) 生成的代码质量高

C++语言在代码效率方面可以和汇编语言相媲美。

(6) 可移植性强

C++语言编写的程序很容易进行移植，在一个环境下运行的程序不加修改或少许修改就可以在完全不同的另外一个环境下运行。

2、C++程序结构

在介绍C++语言程序的结构之前，我们先来看一个简单的例子：

【例1】在屏幕上输出“ Hello,World! ”

#include<bits/stdc++.h>          // 将库文件bits/stdc++.h包含进来
using namespace std;             // 使用标准命名空间
int main(){                      // C++的主函数
    cout<<"Hello,World!"<<endl;  // 输出“Hello,World!”
    return 0;                    // 结束主函数
}

运行结果：Hello,World!
【说明】
(1) 程序中，以“//”开头的表示注释，“//”后的内容用以对语句进行说明，不参与程序的运行。
(2) #include
告诉编译器的预处理器，将bits/stdc++.h库文件包括在本程序中。这个头文件是万能头文件，包含了绝大多数我们使用的库文件。
(3) using namespace std
使用std(标准)名字空间。所谓名字空间是标准C++中的一种机制，用来控制不同类库的冲突问题。使用它可以在不同的空间内使用相同名字的类或者函数。
(4) int main()
为主函数(main function)的起始声明main()是所有C++程序运行的起始点。不管它是在代码的开头、结尾还是中间，此函数中的代码总是在程序开始运行时第一个被执行。所有C++程序都必须有一个main()。main后面跟了一对圆括号()，表示它是一个函数。C++ 中所有函数都有一对圆括号()，括号中可以有一些参数。注意，圆括号中即使什么都没有也不能省略。int表示该函数的返回值是整数。主函数main()中的内容，由一对花括号{}括起来。
(5) cout<<”Hello,World!”<<endl
cout是一个输出语句，告诉计算机把引号之间的字符串Hello,World!送到标准的输出设备(显示器)上。注意，cout的声明在头文件中，所以要想使用cout，必须将头文件包括在程序开始处，否则程序无法识别cout，导致出现语法错误。endl是C++语言的换行控制符，表示内容输出后，换行输出后续的内容。
(6) return 0
主函数main()的返回语句，一般是函数的最后一条可执行语句，即在main()函数中， 只要遇到return 0，即表示该函数已经执行结束，即使后面还有其他语句，也不会被执行。 return后面的数值0表示程序顺利结束，其他数表示有异常。

此外，在C++中，语句间以“;”为分隔符。为了方便阅读，在C++中一般一个语句占一行，但有时为了减少行数，也可以把多个语句写在一行。

结合例1的说明，下面我们再来看上一节的程序：

【例2】津津的储蓄计划

#include<bits/stdc++.h>                  // 将库文件包含进来
#define n 12                             // 宏定义，即将n定义为12，后面遇到n即表示12
using namespace std;                     // 使用标准命名空间
int main(){                                // C++的主函数
    int a[n+10],x=0,s=0,y;               //
    for(int i=1;i<=n;i++) cin >> a[i];   //
    for(int i=1;i<=n;i++){               //
        x=x+300;                         //
        if(x<a[i]){                      //
            cout<<-i<< endl;             //
            return 0;                    //
        }
        y=(x-a[i])/100*100;              //
        s=s+y;                           //
        x=x-y-a[i];                      //
    }
    s=s+s*20/100+x;                      //
    cout<<s<<endl;                       //
    return 0;                            //
}

【说明】