算法与控制结构

一个完成某种特定任务的过程，可分解成一组操作步骤，这组操作步骤即构成一个算法。

一、算法
    1.1 算法设计的方法
    1.2 算法结构
    1.3 条件
二、布尔类型
    2.1 布尔类型数据的基本概念
    2.2 关系运算符
    2.3 逻辑运算符
三、选择语句
    3.1 if—else语句的语法
    3.2 C++语句条件运算符
    3.3 switch-case语句
四、循环语句
    4.1 while语句
    4.2 do—while语句
    4.3 for语句
    4.4 逗号“,”运算符
    4.5 控制语句
五、算法设计与评价

一、算法

程序设计过程中，程序员将完成某种程序功能的过程，分解成一组可被计算机执行的操作步骤，这组操作步骤就叫算法。

1.1 算法设计的方法

1.2 算法结构

1.3 条件

选择结构和循环结构都需要用到条件，条件成立，我们称这个条件为真，否则称之为假，C++语言使用布尔类型来表达条件的真假，通过关系运算符构成的关系表达式来描述条件。还可以根据逻辑运算符构成的逻辑表达式来符合条件。

使用C++语言，将设计好的算法，编写成一组语句序列，这就是C++源程序，为了描述选择结构和循环结构的算法，C++分别提供了选择语句和循环语句。

二、布尔类型

2.1 布尔类型数据的基本概念

布尔（bool）类型：true、false，true和false都是关键字，可以定义布尔类型变量保存布尔型数据，一个布尔型变量占用1个字节，计算机只能存储数值数据，因此计算机内部以1表示true，0表示false。

#include <iostream>
using namespace std;

int main()
{
    bool x = true;//定义一个布尔型变量x，初始值化为true
    cout<<x<<endl;//显示变量x的值，true被显示为1
    
    int y; //再定义1个int型变量
    y=x;// 将布尔型变量x赋值给int型变量y，C++将自动转化类型，true被转换为1
    cout<<y<<endl;//显示y的值，结果为1
    
    x=5; //将int型变量5赋值给布尔型变量，5被转换为true，即非0转换为true，此时编译器会提示warning错误
    cout<<x<<endl;//显示变量x的值，true显示被显示为1
    
    return0;
}

在布尔型数据中，true和false是常量。除了赋值运算外，还可以对布尔类型的变量进行关系运算，或者是逻辑运算。

2.2 关系运算符

由关系运算符构成的表达式，就是关系表达式，关系表达式的作用就是比较两个数的大小，比较的结果是布尔类型，结果为true说明条件成立，为false说明条件不成立。

关系运算符 优先级 结合性
大于（>） 6 从左向右
大于等于（>=） 6 从左向右
小于（<） 6 从左向右
小于等于（<=） 6 从左向右
等于（==） 7 从左向右
不等于（!=） 7 从左向右

2.3 逻辑运算符

逻辑运算符用于判断复合条件是否成立。结果为布尔类型。

逻辑运算符 优先级 运算规则
与（&&） 11 双目运算符，真真为真、否则都为假，相当于并取的意思
或（||） 12 双目运算符，假假为假，否则都为真，相当于或的意思
非（!） 2 单目运算符，非假即真，非真即假，相当于求反的意思

参与逻辑运算的操作数必须是布尔类型，否则将自动转换，其他类型转为布尔类型的规则是，0转为false，非0转为true。

三、选择语句

算法中某些操作步骤，需要满足特定条件才能执行，比如求变量x的倒数，需要判断x不等于0是否成立，若成立进行算法运算，否则应提示错误信息。

句型：如果......，就......，否则,,,,,,

选择结构/分支结构：如果条件成立，则执行算法分支1，否则执行算法分支2

C++语言提供了2中选择语句句型：

3.1 if—else语句的语法

使用方法：

if(表达式)
{语句1;}
else
{语句2;}

语法说明：

/*实例一：求一个数的倒数*/
#include <iostream>
using namespace std;

int main()
{
    double x;
    cout<<"请输入一个数值："<<endl;
    cin>>x;

    if (x!=0) //判断条件
    /*条件成立，执行以下语句，有3条语句，所以不需大括号括起来*/
    {   
        double y;
        y = 1/x;
        cout<< "x的倒数为："<<y<<endl;
    }
    else
        cout<<"因为x的值等于0,0没有倒数"<<endl; //else只有1条语句，可以省略大括号
    return 0;
}

C++语言将一对大括号括起来的语句称为一条复合语句。C++还要一种特殊的语句，空语句，是由单个；组成的，计算机在执行空语句时不会执行任何操作，空语句也没有任何实际的用途，只是在某些特殊的语法场合需要空语句。

/*实例二：判断一个年份是不是闰年*/
#include <iostream>
using namespace std;

int main()
{
    int x;
    cout<<"请输入一个年份："<< endl;
    cin>>x;
    if ((x%100!=0 && x%4==0) || x%400==0) //复合条件判断语句，用括号括起来。
        cout<<x<<"是闰年";
    else
    cout<<x<<"不是闰年";

    return 0;
}

复合判断语句用在if后面，用括号括起来。可以多层嵌套。

/*求解符号函数*/
#include <iostream>
using namespace std;

int main()
{
    float x; //要判断的数
    cout<<"请输入一个实数："<<endl;
    cin>>x;

    int a; //用来保存结果

    if(x==0) //先判断0
    cout<<"0没有符号,值为："<<a;

    /*复合语句判断x的值，并确定a的值，最后输出提示性语句和a*/
    else
    {
        if(x<0) a=-1;
        else a=1;
    }
    cout<<a<<endl;
    return 0;
}

if_else可以多层嵌套，每个else自动的和上面最近的if配对，如果else配对错误，那么执行结果也是错误的。所以为了慎重起见，上层的if_else语句应对添加大括号，将下层的if_else语句括起来

良好的书写习惯可以提供代码的可读性，要合理利用空格、缩进、空行和注释，来区分语句的层次，说明语句的功能和用途。

if_else多层嵌套代码可读性低，C++还提供了一种更加直观简洁的写法if...else if_..._else，的书写方式，求解符号实例可以改造为：

#include <iostream>
using namespace std;

int main()
{
    float x; //要判断的数
    cout<<"请输入一个实数："<<endl;
    cin>>x;

    int a; //用来保存结果

    if(x==0) a=0;
    else if(x>0) a=1;
    else a=-1;

    cout<<a<<endl;
  
    return 0;
}

if-else if-else语法：

if(表达式1) 语句1;
else if(表达式2) 语句2;
......
else if(表达式n) 语句n;
else 语句n+1

#include <iostream>
using namespace std;

int main()
{
    int x;
    cout <<"请输入一个数字："<< endl;
    cin >> x;
    if(x == 1) cout <<"Today is Monday!"<<endl;
    else if (x==2) cout <<"Today is Tuesday!"<<endl;
    else if (x==3) cout <<"Today is Thursday!"<<endl;
    else if (x==4) cout <<"Today is Wednesday!"<<endl;
    else if (x==5) cout <<"Today is Friday!"<<endl;
    else if (x==6) cout <<"Today is Saturday!"<<endl;
    else if (x==7) cout <<"Today is Sunday!"<<endl;
    else cout<<"数值超出1-7的范围"<<endl;

    return 0;
}

3.2 C++语句条件运算符

符号标识：由问号和冒号组成“?:”

在程序设计中，如果条件成立，则执行算法分支1，否则执行算法分支2，双分的if-else支结构，可以通过条件运算符来实现简单的分支结构。语法规则如下：

表达式1 ? 表达式1 : 表达式2

语法说明：

int a =5, b = 10, c;a>b ? a:b //这是一个条件表达式，结果为10，数据类型为int型
cout(a>b ? a:b); //显示表达式的结果
c = a>b ? a:b; //将结果赋值给int型变量c

实列：

#include <iostream>
using namespace std;
int main(){
    int a=5,b=10,c;
    a>b ? a:b;
    cout<<c<<endl;
    c= (a>b ? a:b);
        return 0;
}

3.3 switch-case语句

分支结构算法中，有一类特殊的算法，某一表达式结果，可分成若干种情况，每一种情况，只写一种算法分支，C++语言提供了switch-case结果来描述这种多分支结果。语法形式比if-else更加简洁直观。

语法：

switch(表达式)
{
    case 常量表达式1:语句1;
    case 常量表达式2:语句2;
        ......
    case 常量表达式n:语句n;
    default:语句n+1;
}

说明：

实例一：有break语句跳出比对的情况

/*有break语句的情况*/
#include <iostream>
using namespace std;
int main(){
    int x;
    cout<<"请输入一个标识星期几的数值：";
    cin>>x;
    switch (x) //下列的case语句会根据switch中x的值进行比较
    {
        case 1:cout<<"Today is Monday!"<<endl ; break;
        case 2:cout<<"Today is Tuesday!"<<endl ; break; 
       case 3:cout<<"Today is Thursday!"<<endl ; break;
        case 4:cout<<"Today is Wednesday!"<<endl ; break;
        case 5:cout<<"Today is Friday!"<<endl ; break;
        case 6:cout<<"Today is Saturday!"<<endl ; break;
        case 7:cout<<"Today is Sunday!"<<endl ; break;
        default: cout<<"input error"<<endl;
    }
    //每个case语句只要是执行了cout语句，程序功能就已经完成
    //使用break语句中途跳出switch语句，继续执行switch语句的下一条语句，即return语句
    return 0;
}

实例二：无break的情况

#include <iostream>
using namespace std;
int main(){
    int mouth;
    cout<<"请输入一个标识月份的数值：";
    cin>>mouth;    switch (mouth)
    {
        case 1:
        case 3:
        case 5:
        case 7:
        case 8:
        case 10:
        case 12:cout<<"这个月是大月，有31天"<<endl; break;
        case 4:
        case 6:
        case 9:
        case 11:cout<<"这个月是小月，只有30天"<<endl; break;
        case 2:cout<<"2月天数为28天，闰年29天"<<endl; break;
        default: cout<<"input error"<<endl;
    }
        return 0;
}

若多个case的语句一样，可以共用语句。

四、循环语句

有些算法，在满足特定条件下，将重复执行某些操作步骤，这种结构称之为循环结构，循环结构就是在条件成立时，重复执行某个操作，否则结束循环。

循环4要素：循环变量、初始值、循环条件、循环体

循环语句：while语句、do—while语句、for语句

实例分析：求奇数数列1,3,5.......2n-1的前N项累加和，公式\sum^{N}_{n=1}{2n-1}，奇数数列前N项的和，是一个重复累积的过程，累加起点就是n=1时，累加条件是n<=N，直到这个条件不成立。

4.1 while语句

语法：

while(表达式)
    语句

/*求奇数数列1,3,5.......2n-1的前N项累加和*/
#include <iostream>
using namespace std;
int main(){
    int N,sum=0,n=1; //定义变量，并将用于保存结果的sum初始化为0，开始的n初始化为1
    cout<<"请输入计算的值：";
    cin>>N; //获取前N项
    while (n<=N)
    {
        sum += 2*n-1; // 等价于sum=sum+2*n-1,
        n++; //执行完上一条语句，将n自增1。该条语句用于跳出循环，使得循环条件n<=N趋于false
    }
     cout<<"前"<<N<<"项的累积结果为："<<sum<<endl; //跳出循环后，执行本条语句，显示变量sum
    return 0;
}

4.2 do—while语句

do—while语句是先执行循环体，在判断条件。语法如下：

do
  语句
while(表达式);

/*求奇数数列1,3,5.......2n-1的前N项累加和*/
#include <iostream>
using namespace std;
int main(){
    int N,sum=0,n=1;
    cout<<"请输入计算的值：";
    cin>>N;
    do
    {
        sum += 2*n-1;
        n++;
    }
    while (n<=N);
    cout<<"前"<<N<<"项的累积结果为："<<sum<<endl;
    return 0;
}

4.3 for语句

for语句语法：

for(表达式1;表达式2;表达式3)
    语句

/*求奇数数列1,3,5.......2n-1的前N项累加和*/
#include <iostream>
using namespace std;
int main(){
    int N,n,sum=0;
    cout<<"请输入计算的值：";
    cin>>N;
    for(n=1;n<=N;n++) //集中用3个表达式来指定n=1，循环条件n<=N,以及修改循环条件中的变量N，使得循环趋向于false
    sum += 2*n-1; //表达式n<=N为true时执行的语句
    cout<<"前"<<N<<"项的累积结果为："<<sum<<endl;
    return 0;
}

4.4 逗号“,”运算符

逗号运算符，可以将多个表达式链接在一起，构成一个复合的逗号表达式，

表达式1, 表达式2, ......, 表达式n

实例说明：

int a,b,c;
a=5, b=10, c=a+b; //依次执行，所以a=5, b=10, c=15，计算机会将最后的表达式计算结果（c=a+b）作为该表达式的结果，故结果为15
cout<<(a,b,c); //显示逗号表达式的结果，结果为15

编写程序时，可以将多个表达式语句用逗号运算符连接起来，构成一个长的表达式语句，使得程序更加紧凑，利用逗号运算符改写求奇数列前N项的累积和程序。

/*求奇数数列1,3,5.......2n-1的前N项累加和*/
#include <iostream>using namespace std;
int main(){
    int N,n,sum;
    cout<<"请输入计算的值：";
    cin>>N;
    for(n=1,sum=0;n<=N;n++) //集中用3个表达式来指定n=1，循环条件n<=N,以及修改循环条件中的变量N，使得循环趋向于false
    sum += 2*n-1; //表达式n<=N为true时执行的语句
    cout<<"前"<<N<<"项的累积结果为："<<sum<<endl;
    return 0;
}

4.5 控制语句

计算机通常是按照语句的书写顺序执行程序的，而某些语句，会造成执行顺序的跳转，例如选择语句和循环语句，造成程序执行顺序跳转的语句，统称为控制语句。

五、算法设计与评价

程序设计中，算法应当时可实现的，算法应当能被计算机执行，算法应当完成某种功能，具有使用价值，因此，我们设计的算法应对具有以下5个特性：

如何评判一个算法的优劣，是通过算发杂程度和内存占用量，这是评价一个算法优劣的基本标准。

最后的实例：求反正切（arctan）函数的算法设计，计算机只能进行算术运算，关系运算，逻辑运行等基本运算，不能直接运行对数函数这一类的复杂运算，此类复杂运算，需要分解成基本运算进行求解。

arctan = x-\left(\frac{x^3}{3}\right)+\left(\frac{x^5}{5}\right)-\left(\frac{x^7}{7}\right)...+\left(\frac{x^{2n+1}}{2n+1}\right)

公式化解为：arctan(x) = \sum^{\infty}_{n=0}(-1)^n\frac{x^{2n+1}}{2n+1}，其中记f(n)=\frac{x^{2n+1}}{2n+1}

分子：a(0)=x, a(n+1)=a(n)*x^2

分母：b(0)=1, b(n+1)=b(n)+2

那么：f(n)=a(n)/b(n)


大
中
小
上
一
章
下
一
章
↓
∨