程序设计基础笔记

1.入门知识

程序的基本结构和程序的输出

我们使用到的头文件有两种：
cmath iostream头文件：C++ 语言头文件；
stdio.h math.h头文件：C 语言头文件。
以下是最基本的程序，分别使用 C++ 与 C 语言。

#include <iostream> //预编译命令。因为代码要用 cout, endl
#include <cmath>    //预编译命令。因为代码要用 sin,cos,tan 函数
using namespace std;  //使后续cout,endl等命令不必写成std::cout,std::endl

int main() // 主函数
{ // 主函数开始
    // 计算三角函数式并输出
    cout << sin(20.0 / 180 * 3.14159) *
        cos(20.0 / 180 * 3.14159) -
        cos(10.0 / 180 * 3.14159) /
        tan(10.0 / 180 * 3.14159)
        << endl;
    return 0;
} // 主函数结束

#include <stdio.h> // 或 #include <cstdio>，前者是C语言风格的头文件
#include <math.h>  // 或 #include <cmath>，前者是C语言风格的头文件

int main()
{
    printf("%f\n", sin(20.0 / 180 * 3.14159) * cos(20.0 / 180 * 3.14159) -
        cos(10.0 / 180 * 3.14159) / tan(10.0 / 180 * 3.14159));
    return 0;
}

对于不同的输出函数cout和printf，使用方法也不同，以后我们统一使用cout。以下是两种函数的格式控制与语法。

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

int main()
{
    cout << 'A' << 'b' << "__THU__" << "DCS, THU, Beijing"
        << "Hello, World" << endl
        << "\t------------\n";
    cout << "\t************" << endl;
    cout << "2018.09.17\n";

    printf("%c%c%s%s%s\n\t------------\n", 'A', 'b', "__THU__", "DCS, THU, Beijing", "Hello, World");
    printf("\t************\n");
    printf("2018.09.17\n");
    
    return 0;
}

其他注记

define可以用来定义变量，如圆周率等。

#include <iostream> // cout, endl
#include <cmath>    // sin,cos,tan
using namespace std;
#define PI 3.141592653589793238462

int main()
{
    cout << sin(20.0 / 180 * PI) *
        cos(20.0 / 180 * PI) -
        cos(10.0 / 180 * PI) /
        tan(10.0 / 180 * PI)
    << endl;
    return 0;
}

iomanip头文件可以用来控制cout格式。

#include <iostream>
#include <iomanip>
using namespace std;

int main()
{
    cout << fixed << setprecision(4) << 1 / 5.0 << endl;
    cout << fixed << setprecision(4) << 1.0 / 5 << endl;
    return 0;
}

2.代数思维

实例引入2

我们用以下问题作为引入。
我们国家在天气预报等日常生活中，通常是使用摄氏温度来表示温度高低（冷热）的。但还有一些国家是使用华氏温度来表示温度的。这两种温度体系之间存在如下换算关系：
celsius = (5/9) * (fahrenheit - 32)
请你编写一个温度转换工具，能将用户输入的任意华氏温度转换为对应的摄氏温度。

对于这道题我们需要处理输入，输出，代数运算。

#include <iostream>
using namespace std;
int main()
{
    double fahrenheit;
    cout << "Enter a degree in Fahrenheit: ";
    cin >> fahrenheit;
    double celsius = (5.0 / 9) * (fahrenheit - 32);
    cout << "Fahrenheit " << fahrenheit << " is "
        << celsius << " in celsius" << endl;
    return 0;
}

这里涉及到的重要思想是变量。我们先了解变量的一些知识。

大小，地址和指针

sizeof()函数输出变量的size。

#include <iostream>
using namespace std;

int main()
{
    int i;
    short s;
    char c;
    double d;
    cout << sizeof(int) << ' ' << sizeof(i) << endl;    // 输出 4 4
    cout << sizeof(short) << ' ' << sizeof(s) << endl;  // 输出 2 2
    cout << sizeof(char) << ' ' << sizeof(c) << endl;   // 输出 1 1
    cout << sizeof(double) << ' ' << sizeof(d) << endl; // 输出 8 8
    return 0;
}

这里我们介绍&运算符，用来取变量地址。

#include <iostream>
using namespace std;

int main()
{
    int a = 13;
    cout << "a = " << a << ' ' << endl;
    cout << "&a = " << &a << ' ' << sizeof(&a) << endl;
    a += 4;
    cout << "a = " << a << ' ' << endl;
    cout << "&a = " << &a << ' ' << endl;
    double d = 1.2;
    cout << "&d = " << &d << ' ' << sizeof(&d) << endl;
    return 0;
}

接下来我们介绍指针。指针是特殊的变量，可以将地址值赋予指针。

#include <iostream>
using namespace std;

int main()
{
    int a = 13;
    int* ptr; // 定义一个可以保存整数类型单元地址值的变量，其名为ptr
    ptr = &a; // 将变量a所在内存单元的地址值赋给指针变量ptr
    cout << "&a = " << &a << ' ';
    cout << ptr << endl; // 输出指针变量ptr自己所在单元中保存的数值（即a的地址值）
    return 0;
}

如下是对指针性质的探究。

#include <iostream>
using namespace std;

int main() 
{
    int a = 13;
    int* ptr;
    ptr = &a;
    cout << "&a = " << &a << ' ' << ptr << endl;
    cout << "a = " << a << ' ' << *ptr << endl;

    a += 4;
    cout << "a = " << a << ' ' << *ptr << endl;
    *ptr = 23; // 向所指内存单元写入新值
    cout << "a = " << a << ' ' << *ptr << endl;

    return 0;
}

布尔变量，关系运算符

布尔变量取值只有false和true。关系运算符通常返回布尔变量。
这里的boolalpha函数可以以true/false来输出布尔。

#include <iostream>
using namespace std;

int main()
{
    cout << boolalpha; // 以true/false来输出布尔值 
    cout << "(3 > 5 ) " << (3 > 5) << endl;
    cout << "(3 < 5 ) " << (3 < 5) << endl;
    cout << "(3 == 5) " << (3 == 5) << endl;
    cout << "(3 != 5) " << (3 != 5) << endl;
    cout << "(3 <= 5) " << (3 <= 5) << endl;
cout << "(3 >= 5) " << (3 >= 5) << endl;

    return 0;
}

实例2

问题1：判断数的奇偶

这里我们需要使用if-else语句。满足if内布尔表达式则执行if后方语句，否则执行else后方语句。

#include <iostream>
using namespace std;

int main()
{
    int a;
    cin >> a;

    if (a % 2 == 0)
        cout << "Even" << endl;
    else
        cout << "Odd\n";

    return 0;
}

问题2：计算二次方程的根
对于一元二次方程 $ax^2+bx+c=0$ ，方程中的系数由用户在运行时输入。试编程根据用户输入的系数a,b,c求解方程的根。
要求：如果没有实数根，则输出“无实数根”；如果有实数根且不相等，则输出两个根，中间用一个空格隔开；如果实数根相等，则输出一个根的值。

#include <iostream>  // cin, cout
#include <cmath>     // sqrt
using namespace std;

int main()
{
    double a, b, c;
    double delta;
    cin >> a >> b >> c;  //输入a值时，要判断a不能为0更加严谨
    delta = b * b - 4 * a * c;
    if (delta < 0)
    {
        cout << "无实数根" << endl;
    }
    if (delta == 0)
    {
        cout << -b / (2 * a) << endl;
    }
    if (delta > 0)
    {
        if (a > 0)
        {
            cout << (-b + sqrt(delta)) / (2 * a) << ' '
                << (-b - sqrt(delta)) / (2 * a) << endl;
        }
        else
        {
            cout << (-b - sqrt(delta)) / (2 * a) << ' '
                << (-b + sqrt(delta)) / (2 * a) << endl;
        }
    }
    return 0;
}

3.逻辑思维

实例引入3

问题：逻辑判断
清华附中有四位同学A、B、C、D，其中一位做了好事，不留名，表扬信来了之后，校长问这四位是谁做的好事。
A说：不是我。
B说：是C。
C说：是D。
D说：他胡说。
已知：三个人说的是真话，一个人说的是假话。现在请你根据这些信息，编写程序找出做了好事的人。

如果使用暴力解法，代码会变成这样：

#include <iostream>
using namespace std;

int main()
{
    char thisman = 'A' - 1;
    int sum;

    /// A
    thisman++;
    sum = (thisman != 'A') + (thisman == 'C')
        + (thisman == 'D') + (thisman != 'D');
    if (sum == 3)
    {   // 如果3句话为真，则输出当前可能性所假定的人为做好事者
        cout << "做好事者为" << thisman << endl;
        return 0;
    }

    /// B
    thisman++;
    sum = (thisman != 'A') + (thisman == 'C')
        + (thisman == 'D') + (thisman != 'D');
    if (sum == 3)
    {   // 如果3句话为真，则输出当前可能性所假定的人为做好事者
        cout << "做好事者为" << thisman << endl;
        return 0;
    }

    /// C
    thisman++;
    sum = (thisman != 'A') + (thisman == 'C')
        + (thisman == 'D') + (thisman != 'D');
    if (sum == 3)
    {   // 如果3句话为真，则输出当前可能性所假定的人为做好事者
        cout << "做好事者为" << thisman << endl;
        return 0;
    }

    /// D
    thisman++;
    sum = (thisman != 'A') + (thisman == 'C')
        + (thisman == 'D') + (thisman != 'D');
    if (sum == 3)
    {   // 如果3句话为真，则输出当前可能性所假定的人为做好事者
        cout << "做好事者为" << thisman << endl;
        return 0;
    }

    cout << "找不出做好事者" << endl; // 输出无解信息
    return 0;
}

这样子代码变得十分冗长。

for循环

我们可以采用for循环语句进行优化。for语句能在满足表达式时重复执行语句，执行后对变量进行操作。

#include <iostream>
using namespace std;

int main()
{
    char thisman = 'A' - 1;
    int sum;
    for (int i = 0; i < 4; i++)
    {
        thisman++;
        sum = (thisman != 'A') + (thisman == 'C')
            + (thisman == 'D') + (thisman != 'D');

        if (sum == 3)
        {   // 如果3句话为真，则输出当前可能性所假定的人为做好事者
            cout << "做好事者为" << thisman << endl;
            return 0;
        }
    }
    cout << "找不出做好事者" << endl; // 输出无解信息
    return 1; // 返回1表示题目无解
}

实际上，我们可以用标志变量来判断是否有解：

#include <iostream>
using namespace std;

int main()
{
    int g = 0;     // 初始化为0，表示“无解”
    for (int k = 0; k < 4; k++) // k是循环控制变量
    { // for 循环体开始
        char thisman = 'A' + k;
        int sum = (thisman != 'A') + (thisman == 'C')
            + (thisman == 'D') + (thisman != 'D');

        if (sum == 3)
        {   // 如果3句话为真，则输出当前可能性所假定的人为做好事者
            cout << "做好事者为" << thisman << endl;
            g = 1; // 有解标志置1，表示找到解了
        }
    } // for 循环体结束

    if (g != 1)
    {
        cout << "找不出做好事者" << endl; // 输出无解信息
    }

    return 0;
}

如果问题解是唯一的，实际上我们不需要等待循环结束，我们可以使用break语句跳出循环：

#include <iostream>
using namespace std;

int main()
{
    int g = 0;                  // 声明变量为整数类型，初始化为0
    for (int k = 0; k < 4; k++)      // 循环从k为0到3，
    {

        if (((k != 0) + (k == 2) + (k == 3) + (k != 3)) == 3)
        {
            cout << "做好事者为" << char('A' + k) << endl;  // 输出做好事者
            g = 1;              // 让有解标志置1
            break;              //终止循环
        }
    }
    if (g != 1)                 // 则输出无解信息
    {
        cout << "找不出做好事者" << endl;
    }
    return 0;
}

二进制位运算

二进制位运算是一种很有用的技巧。以下程序是经典二进制猜数字游戏中输出各卡片上数字的程序，运用了位运算：

#include <iostream>
using namespace std;

int main()
{
    for (int m = 0; m < 7; m++)
    {
        cout << "CARD " << m << endl;
        for (int i = 1; i <= 100; i++) /// 获得指定位置bit值
            if (i & (1 << m)) 
                cout << i << ' ';
        cout << endl << endl; /// 每张卡片输出之间空一行
    }
    return 0;
}

实例3

问题：
某地刑侦大队对涉及六个嫌疑人的一桩疑案进行分析，以下内容叙述的是刑侦队搜集到的线索和情报：
A、B 至少有一人作案；
A、E、F 三人中至少有两人参与作案；
A、D 不可能是同案犯；
B、C 或同时作案，或与本案无关；
C、D 中有且仅有一人作案；
如果 D 没有参与作案，则 E 也不可能参与作案。
请你编写程序，将作案人找出来。

我们介绍表达式_(bool)_?_(value)_:_(value2)_的用法，?前表达式为真时返回:前的值，否则返回后值。

#include <iostream>
using namespace std;

int main()
{
    int cc1, cc2, cc3, cc4, cc5, cc6;
    for (int A = 0; A <= 1; A++)
        for (int B = 0; B <= 1; B++)
            for (int C = 0; C <= 1; C++)
                for (int D = 0; D <= 1; D++)
                    for (int E = 0; E <= 1; E++)
                        for (int F = 0; F <= 1; F++)
                        { /// 最内层循环, 最后一个人
                            cc1 = A || B;
                            cc2 = !(A && D);
                            cc3 = (A && E) || (A && F) || (E && F);
                            cc4 = (B && C) || (!B && !C);
                            cc5 = (C && !D) || (D && !C);
                            cc6 = D || !E;
                            if (cc1 + cc2 + cc3 + cc4 + cc5 + cc6 == 6)
                            {
                                cout << "A:" << (A == 1 ? "是罪犯" : "不是罪犯") << endl;
                                cout << "B:" << (B == 1 ? "是罪犯" : "不是罪犯") << endl;
                                cout << "C:" << (C == 1 ? "是罪犯" : "不是罪犯") << endl;
                                cout << "D:" << (D == 1 ? "是罪犯" : "不是罪犯") << endl;
                                cout << "E:" << (E == 1 ? "是罪犯" : "不是罪犯") << endl;
                                cout << "F:" << (F == 1 ? "是罪犯" : "不是罪犯") << endl;
                            }
                        }
    return 0;
}

问题2：
输入一个年份（2023-2050），输出这一年的日历。
格式如下：

01        1  2  3  4  5
    6  7  8  9 10 11 12
   13 14 15 16 17 18 19
   20 21 22 23 24 25 26
02 27 28 29 30 31  1  2
    3  4  5  6  7  8  9
   10 11 12 13 14 15 16
   17 18 19 20 21 22 23
03 24 25 26 27 28  1  2
......

#include <iostream>
using namespace std;

int main()
{
    // 用户输入年份
    cout << "Please input year (2023-2050): ";
    int year;
    cin >> year;
    if (year < 2023 || year > 2050) 
  {
        cout << "Error! Not in range [2023..2050]\n";
        return 1;
    }
    // 计算天数
    int cnt = 0;
    for (int y = 2023; y < year; y++)
        cnt += (y % 400 == 0 || y % 4 == 0 && y % 100 != 0) ? 366 : 365;
    // 已知2023.01.01是星期日，计算1月1日是星期几 
    int w = cnt % 7; // 1: Mon, 2: Tue, 3: Wed, 4: Thu, 5: Fri, 6: Sat, 0: Sun 
    if (w == 0) w = 7; // 调整一下，方便后续处理1月份的前导空白

    // 开始输出指定年份的日历
    cout << "01"; // Jan.
    // 输出年前空白（上一年在第一周里所占天数）
    for (int day = 0; day < w - 1; day++) cout << "   ";
    // 输出各月日历
    for (int month = 1; month <= 12; month++) 
  {
        int lastday = (month == 4 || month == 6 || month == 9 || month == 11) ? 30 : 31;
        if (month == 2) 
        lastday = (year % 400 == 0 || year % 4 == 0 && year % 100 != 0) ? 29 : 28;
        for (int day = 1; day <= lastday; day++, w++) 
    {
            printf("%3d", day); // 右对齐，3字符宽，不足补空格
            if (w % 7 == 0) 
      {
                if (lastday - day < 7 && month < 12)
                    printf("\n%02d", month + 1); // 01 ~ 11 月日历最后一行要特殊处理，右对齐，2字符宽，不足补0
                else
                    printf("\n  "); // 一般情况是显示空格
            }
        }
    }
    // 至此，已完成所有日期的输出
    cout << endl;
    return 0;
}

4.函数思维

函数

函数能够将一段有特定功能的代码封装到函数中，这样声明函数后就能更方便的调用。

#include <iostream>
using namespace std;

int add(int a, int b)
{
    return a + b;
}

int main()
{
    cout << add(3, 4);
    return 0;
}

例如我们将计算三角形面积的面积的方法封装为函数：

#include <iostream>
using namespace std;

float TriangleArea(float base, float height)
{
    float area;
    area = 0.5 * base * height;
    return area;
} ///先计算并保存，最后返回结果

int main()
{
    int base, height;
    cin >> base >> height;
    cout << TriangleArea(base, height) << endl;
    return 0;
}

关于函数有几个重要概念：形式参数，实在参数及地址，用下面的代码加以说明：

#include <iostream>
using namespace std;

float TriangleArea(float base, float height)
{
    cout << "In TriangleArea(): " << endl;
    cout << " base @ " << &base << ", height @ " << &height << endl;
    float area;
    area = 0.5 * base * height;
    return area;
}

int main()
{
    int base, height;
    cout << "In main(): " << endl;
    cout << " base @ " << &base << ", height @ " << &height << endl;
    cin >> base >> height;
    cout << TriangleArea(base, height) << endl;
    return 0;
}

实例4

问题1：判断质数

#include <iostream> // cout
#include <cmath>    // sqrt
using namespace std;

bool IsPrime(int); // 子函数声明。相对于主函数main，用户自定义函数均可被称为“子”函数

int main() {
    int n = 0;
    cout << "请输入一个整数：n=";
    cin >> n;

    // 用实参n调用子函数，子函数返回值作为if语句的分支条件
    if (IsPrime(n))
        cout << n << "是质数" << endl;
    else
        cout << n << "不是质数" << endl;
    return 0;
}

bool IsPrime(int n) {
    for (int k = 2; k <= sqrt(n); k++)
        if (n % k == 0) return false; // n 能被k整除，返回false
    return true; // n 不能被k整除，返回true
}

问题2：
输出所有ASCII码对应的“字符”及其内存中的二进制表示（由0和1组成的串）。
一行输出4个字符，字符之间用一个空格隔开
在输出各字符时，格式要求如下：
ASCII码的十进制值二进制串字符
例如：75 01001011 K
十进制数占三个字符宽，不够宽时在后面补空格。

这里我们有获取某整数某个二进制位上的值的小技巧。

#include <iostream>
using namespace std;

void out_int_with_sp(int i)
{
    cout << i;
    if (i < 10)
        cout << "  ";
    else if (i < 100)
        cout << ' ';
}

int get_bit(int n, int pos)
{
    int mask = (1 << pos);
    int bit = (n & mask) >> pos;
    return bit;
}

void output_bit(int n, int pos)
{
    int bit = get_bit(n, pos);
    cout << bit;
}

void out_char_bin(int n)
{
    for (int i = 7; i >= 0; i--)
        output_bit(n, i);
}

int main()
{
    for (int i = 0; i < 128; i++)
    {
        out_int_with_sp(i);
        cout << ' ';
        out_char_bin(i);
        cout << ' ' << char(i);
        if (i % 4 == 3)
            cout << endl;
        else
            cout << ' ';
    }
    return 0;
}

4-7
问题：
编写程序，找出2－100以内的全部 $4n＋1$ 型质数，输出这些质数并统计输出它们的数目，其中 $n$ 为正整数。

这里我们介绍continue语句，用于跳过当前循环的后续语句，而不是直接跳出循环。

#include <iostream>
#include <cmath>
using namespace std;

bool IsPrime(int n) {
    bool ans = true;
    for (int k = 2; k <= sqrt(n); k++)
        if (n % k == 0) {
            ans = false;
            break;
        }
    return ans;
}

int main() {
    int Count = 0;
    for (int i = 2; i <= 100; i++) {
        if (!IsPrime(i)) 
            continue;
        if ((i - 1) % 4 != 0) 
            continue;
        cout << i << endl;
        Count++;
    }
    cout << "Count = " << Count << endl;
    return 0;
}

5.数据组织与处理

数组

数组，顾名思义是一组数。基本性质可见以下代码：

#include <iostream>
using namespace std;

int main()
{
    int array[10];
    char message[10];
    double salary[10];
    cout << "sizeof(int[10])    = " << sizeof(array)
        << ", sizeof(int)*10    = " << sizeof(int) * 10 << endl;
    cout << "sizeof(char[10])   = " << sizeof(message)
        << ", sizeof(char)*10   = " << sizeof(char) * 10 << endl;
    cout << "sizeof(double[10]) = " << sizeof(salary)
        << ", sizeof(double)*10 = " << sizeof(double) * 10 << endl;
    return 0;
}

实际上在某些意义下，数组与指针是等价的。

#include <iostream>
using namespace std;

int main()
{
    int array[10], * ptr;
    ptr = array;
    cout << "ptr   = " << ptr << ", ptr + 1   = " << ptr + 1 << endl;
    cout << "array = " << array << ", array + 1 = " << array + 1 << endl;
    for (int i = 0; i < 10; i++)
        if (i % 2 == 0) *(array + i) = i * 2;
        else ptr[i] = i * 2;
    for (int i = 0; i < 10; i++)
        cout << "array[" << i << "]:\t"
        << ptr[i] << ' ' << *(ptr + i) << ' '
        << array[i] << ' ' << *(array + i) << endl;
    return 0;
}

实例5.1

问题1：
某电视台举办歌手大奖赛，邀请了7名评委给歌手打分。在计算歌手的平均得分时，为了公平起见，要把这些评委给出的最高分、最低分都去掉，只将剩下的5名评委给出的评分进行平均。
请你编写程序来完成这个任务。设评委给分区间为0~100分。

#include <iostream>
using namespace std;

int main()
{
    int score[7];

    // 1. 先完成所有输入和保存
    for (int i = 0; i < 7; i++)
        cin >> score[i];

    // 2. 然后再进行统计计算
    int min = 100, max = 0;
    double avg = 0.0;
    for (int i = 0; i < 7; i++) {
        if (min > score[i])
            min = score[i];
        if (max < score[i])
            max = score[i];
        avg += score[i];
    }
    avg -= (max + min);
    avg /= 5;

    cout << "avg = " << avg << endl;
    return 0;
}

实际上这样子声明的数组长度必须为确定值。如果长度不确定，我们可以使用vector。

#include <iostream>
#include <vector>
using namespace std;

int main() {
    int N; cin >> N;
    vector<int> score(N);

    // 1. 先完成所有输入和保存
    for (int i = 0; i < N; i++)
        cin >> score[i];

    // 2. 然后再进行统计计算
    int min = 100, max = 0;
    double avg = 0.0;
    for (int i = 0; i < N; i++) {
        if (min > score[i])
            min = score[i];
        if (max < score[i])
            max = score[i];
        avg += score[i];
    }
    avg -= (max + min);
    avg /= (N - 2);

    cout << "avg = " << avg << endl;
    return 0;
}

问题2：
输出未知长度序列的特定元素的和
若该元素满足下列条件才能被选中求和：
能被3或5整除；
小于1000；
这个数之前没有出现-1.

这里我们介绍另一种循环语句：while循环，只有当括号内表达式结果为真才会执行循环。
vector.push_back将元素置于容器尾，vector.size()给出容器大小。

#include <iostream>
#include <vector>
using namespace std;

int main()
{
    vector<int> list;
    while (1)
    {
        int x;
        cin >> x;
        if (x == -1)
            break;
        list.push_back(x);
    }
    int sum = 0;
    for (int i = 0; i < list.size(); i++)
    {
        int x = list[i];
        if (((x % 3 > 0) && (x % 5 > 0)) ||
            (x >= 1000))
            continue;
        sum += x;
    }
    cout << sum;
    return 0;
}

问题3：筛法寻找质数
输出小于100的质数
筛法是另一种重要的筛选质数的方法。依次在对应范围内排除掉质数的倍数即可。

#include <iostream> // cin, cout
#include <cmath> // sqrt
using namespace std;

void FindPrimes(int* array, int n) {
    for (int d = 2; d <= sqrt(n); d++) {
        if (array[d] == 0) {
            for (int k = d + d; k <= n; k += d)
                array[k] = 1;
        }
    }
}

int main() 
{
    int prime[101] = { 1, 1 };
    FindPrimes(prime, 100);
    for (int i = 2; i <= 100; i++)
        if (prime[i] == 0)
            cout << i << ' ';
    cout << endl;

    return 0;
}

问题4：查找元素
查找一个元素是否在一个有序数组中
这里我们介绍折半查找法，即排序后每次将数组折半查找。这与后面分治算法的思想有联系。

#include <iostream>  // cin, cout
#include <iomanip>   // setw – 设置显示宽度
using namespace std;

int BinarySearch(int AA[], int Key, int low, int high)
{
    int middle = 0;
    while (low <= high) 
    {
        middle = (low + high) / 2;
        if (Key == AA[middle])
            return middle;
        else if (Key < AA[middle])
            high = middle - 1;
        else
            low = middle + 1;
    }
    return -1; // 数组中没有Key
}

int main() 
{
    const int NUM = 100; // NUM是整型常量
    int a[NUM]; // 数组大小可以使用整型常量
    for (int i = 0; i < NUM; i++) 
    {
        a[i] = i * i + 1;
        cout << setw(4) << a[i] << ((i + 1) % 10 == 0 ? '\n' : ' ');
    }

    int searchKey;
    cout << "请输入一个待查正整数: ";
    cin >> searchKey;

    int b = 0;
    b = BinarySearch(a, searchKey, 0, NUM - 1);

    if (b != -1)
        cout << "查到该数在数组中为: a[" << b << "]\n";
    else
        cout << "数组中无此数!\n";

    return 0;
}

问题5：对数组排序
我们这里介绍最简单的冒泡排序。从前向后遍历比较相邻两个元素，若位置不对则对换。

#include <iostream> // cout
using namespace std;

int main() {
    int a[6] = { 1, 8, 3, 2, 4, 9 }; // 测试样例

    for (int i = 1; i <= 5; i++) // 遍数=个数-1
        for (int j = 0; j < 6 - i; j++) {
            if (a[j] < a[j + 1]) {
                int tmp = a[j];
                a[j] = a[j + 1];
                a[j + 1] = tmp;
            }
        }

    for (int i = 0; i < 6; i++)
        cout << a[i] << ' ';
    cout << endl;

    return 0;
}

问题6：
A、B、C、D、E 五人合伙夜间捕鱼，凌晨时都疲惫不堪，各自在湖边的树丛中找地方睡着了。日上三竿，A第一个醒来，他将鱼平分作五份，把多余的一条扔回湖中，拿自己的一份回家去了。B第二个醒来，也将鱼平分为五份，扔掉多余的一条，只拿走自己的一份。接着 C、D、E 依次醒来，也都按同样的办法分鱼。
问：这五个人至少合伙捕到多少条鱼？每个人醒来后，看到的鱼数分别是多少条？
我们这里介绍do-while循环用法，与while类似，只不过现在是先执行后判断。

#include <iostream>
using namespace std;

int main() {
    // 记录每人醒来后看到的鱼数
    int i = 0, fish[6] = { 1, 1, 1, 1, 1, 1 };
    do {
        fish[5] = fish[5] + 5; // 让E看到的鱼数增5
        for (i = 4; i >= 1; i--) {
            if (fish[i + 1] % 4 != 0)
                break;
            else
                fish[i] = fish[i + 1] / 4 * 5 + 1;
        }
    } while (i >= 1); // 当 i>=1 继续做do循环

    for (i = 1; i <= 5; i++)
        cout << fish[i] << endl;
    return 0;
}

string

string是一种特殊的数组，C++中可以直接使用数据类型string。以下代码注释部分是C语言的写法。

#include <iostream> // cout
// #include <cstring>  // strlen, strcat, strcmp, strcpy
#include <string> // string
using namespace std;

int main()
{
    // char str1[50] = "BeiJing";
    string str1 = "Beijing";
    // cout << "str1 length: " << strlen(str1) << endl; // 字符串的长度
    cout << "str1 length: " << str1.length() << endl; // 字符串的长度    
    // strcat(str1, ", Tsinghua!"); // 拼接两个字符串
    str1 += ", Tsinghua!";    
    // cout << "---> " << str1 << " ==> str1 length: " << strlen(str1) << endl;
    cout << "---> " << str1 << " ==> str1 length: " << str1.length() << endl;    
    // cout << "Tsinghua > Peking? "                 // 比较两个字符串的字典序大小
    //      << strcmp("Tsinghua", "Peking") << endl; // 相等时返回 0
    cout << "Tsinghua > Peking? "                            // 比较两个字符串的字典序大小
        << (string("Tsinghua") > string("Peking")) << endl; // 相等时返回 0
    // char str2[100];              // 要注意有足够的空间
    string str2;
    // strcpy(str2, "THIS YEAR, "); // 复制字符串
    str2 = "THIS YEAR, ";
    // strcat(str2, str1);
    str2 += str1;
    cout << "str2 = " << str2 << endl;
    return 0;
}

实例5.2

问题1：
某日某地，发生了一起严重交通事故，肇事司机逃跑了！
目击者对交警说：肇事汽车的号码为4位完全平方数，且数字从左到右一个比一个大。
请你编写程序，帮交警算出肇事车的号码。

常规解法如下：

#include <iostream>
using namespace std;

void find_it()
{
    for (int i = 32; i < 100; i++)
    {
        int n = i * i;
        if (((n / 1000) < (n / 100 % 10)) &&
            ((n / 100 % 10) < (n / 10 % 10)) &&
            ((n / 10 % 10) < (n % 10)))
            cout << "肇事汽车号码为" << n << endl;
    }
}

int main()
{
    find_it();
    return 0;
}

单纯闲来无事用数组自然也可以。

#include <iostream>
using namespace std;

void find_it()
{
    for (int i = 32; i < 100; i++)
    {
        int n = i * i;
        char code[5];
        sprintf_s(code, "%d", n); // 把整数转成数字字符数组，再进行比较。
        if (code[0] < code[1] && code[1] < code[2] && code[2] < code[3])
            cout << "肇事汽车号码为" << n << endl;
    }
}

int main()
{
    find_it();
    return 0;
}

多维数组

多维数组顾名思义拥有多个维度。
比如我们计算3*3矩阵相乘，可以用二维数组：

#include <iostream>
using namespace std;

int main() 
{
    cout << "Input m[][]:" << endl;
    int m[3][3];
    for (int i = 0; i < 3; i++)
        for (int j = 0; j < 3; j++)
            cin >> m[i][j];

    cout << "Input n[][]:" << endl;
    int n[3][3];
    for (int i = 0; i < 3; i++)
        for (int j = 0; j < 3; j++)
            cin >> n[i][j];

    int r[3][3];

    for (int i = 0; i < 3; i++)
        for (int j = 0; j < 3; j++)
            r[i][j] = m[i][0] * n[0][j] +
            m[i][1] * n[1][j] +
            m[i][2] * n[2][j];

    cout << "m[][] * n[][] = " << endl;

    for (int i = 0; i < 3; i++) {
        for (int j = 0; j < 3; j++)
            cout << r[i][j] << ' ';
        cout << endl;
    }

    return 0;
}

实例5.3

问题1：
电视歌手大奖赛开赛报名时，由于人数较多，一些参赛信息需要及时录入计算机并用计算机进行管理。其中，有一个很重要的工作是：要按选手姓名（汉语拼音）排序后编号，以决定选手比赛的顺序。
请你编程实现对姓名拼音串按英文字典顺序排序的程序。
为测试程序，假定共有10名选手，选手姓名拼音最长不超过20个英文字符，且中间无空格。

解法一：我们采用二维字符数组。

#include <iostream>
#include <cstring>
using namespace std;

int main()
{
    char namelist[10][20]; // 二维字符数组！
    for (int i = 0; i < 10; i++)
    {
        cout << "Input #" << i << " singer's name: ";
        cin >> namelist[i];
    }

    for (int i = 0; i < 9; i++)         // 轮(遍,趟)数=元素数目-1
        for (int j = 0; j < 9 - i; j++) // 比较数=总轮数–当前轮次
            if (strcmp(namelist[j], namelist[j + 1]) > 0)
            {
                char tmp[20];
                strcpy_s(tmp, namelist[j]);
                strcpy_s(namelist[j], namelist[j + 1]);
                strcpy_s(namelist[j + 1], tmp);
            }

    for (int i = 0; i < 10; i++)
        cout << i << ' ' << namelist[i] << endl;
    return 0;
}

解法二:我们使用string，vector，直接使用sort函数进行排序。

#include <iostream>  // cout
#include <string>    // string
#include <vector>    // vector
#include <algorithm> // sort
using namespace std;

int main()
{
    vector<string> namelist(10); // 10个歌手的名字数组（向量）
    for (int i = 0; i < 10; i++)
    {
        cout << "Input #" << i << " singer's name: ";
        cin >> namelist[i];
    }
    sort(namelist.begin(), namelist.end()); // 将向量"头部"和"尾部"传入排序函数
    for (int i = 0; i < 10; i++)
        cout << i << ' ' << namelist[i] << endl;
    return 0;
}

实际上sort函数相当好用。可以用来数组排序：

#include <iostream>     // cout
#include <algorithm> // sort
using namespace std;

int main()
{
    int array[] = {1, 3, 99, 10, 20, 42, 14, 86, 36};
    int num = sizeof(array) / sizeof(array[0]); ///  计算数组元素数量的小技巧
    sort(array, array + num);
    for (int i = 0; i < num; i++)
        cout << array[i] << ' ';
    cout << endl;
    return 0;
}

若名字中含有空格，我们可以使用getline函数读取整行。

#include <iostream>
#include <string>
using namespace std;

int main()
{
    string str1;
    getline(cin, str1);
    cout << "INPUT1 = [" << str1 << "]." << endl;

    char str2[100];
    cin.getline(str2,99);//指定最大长度
    cout << "INPUT2 = [" << str2 << "]." << endl;

    return 0;
}

问题2：
以整数数组排序为例，程序询问用户排序准则，从小到大时，输入1；从大到小时，输入2。程序根据用户的输入，输出指定的排序结果。
这里我们使用函数指针数组来简化代码：

#include <iostream>
using namespace std;

void bubble1(int data[], int num) 
{
    for (int i = 0; i < num - 1; i++)
        for (int j = 0; j < num - 1 - i; j++)
            if (data[j] > data[j + 1]) 
            {
                int tmp = data[j];
                data[j] = data[j + 1]; data[j + 1] = tmp;
            }
}

void bubble2(int data[], int num) /// 拷贝粘贴，稍作修改
{ 
    for (int i = 0; i < num - 1; i++)
        for (int j = 0; j < num - 1 - i; j++)
            if (data[j] < data[j + 1]) 
            {
                int tmp = data[j];
                data[j] = data[j + 1]; data[j + 1] = tmp;
            }
}

int main() 
{
    /// 使用指向函数的指针，函数指针数组（也称为“函数跳转表”）
    void (*pf[2])(int*, int) = { bubble1, bubble2 };
    /// <<<--- 这可能是C/C++语言中最令人困惑的语法形式了！
    int data[] = { 8, 4, 7, 9, 3, 5, 1 };
    int ans = 0;
    cin >> ans;
    pf[ans - 1](data, 7);

    for (int i = 0; i < 7; i++) 
        cout << data[i] << ' ';
    cout << endl;
    return 0;
}

实际上我们也可以在函数参数中使用函数指针：

#include <iostream>
using namespace std;

void bubble(int data[], int num, bool (*op)(int, int)) 
{
    for (int i = 0; i < num - 1; i++)
        for (int j = 0; j < num - 1 - i; j++)
            if (op(data[j], data[j + 1])) 
            {
                int tmp = data[j];
                data[j] = data[j + 1];
                data[j + 1] = tmp;
            }
}

bool op1(int a, int b) 
{
    return a > b; 
}
bool op2(int a, int b) 
{ 
    return a < b; 
}

int main() 
{
    bool (*pf[2]) (int, int) = { op1, op2 }; /// 称pf数组为“函数跳转表”

    int data[] = { 8, 4, 7, 9, 3, 5, 1 };
    int ans = 0;
    cin >> ans;
    bubble(data, 7, pf[ans - 1]);

    for (int i = 0; i < 7; i++)
        cout << data[i] << ' ';
    cout << endl;
    return 0;
}

结构体与函数

我们引入结构体这种数据类型。一个结构体中可以定义不同类型的元素，将他们统合起来就成了结构体。

#include <iostream> // cout
#include <cstring>  // stcpy
using namespace std;

struct package
{
    char msg[4];
    int v1, v2;
};

package transfer(package data)
{
    cout << "&data= " << &data << ", value = "
        << data.msg << ' ' << data.v1 << ' ' << data.v2 << endl;
    package tmp;
    strcpy_s(tmp.msg, data.msg);
    tmp.v1 = data.v1 + 1;
    tmp.v2 = data.v2 + 2;
    cout << "&tmp = " << &tmp << ", value = "
        << tmp.msg << ' ' << tmp.v1 << ' ' << tmp.v2 << endl;
    return tmp;
}

int main()
{
    package pkg = { "ABC" }, res;
    cout << "&pkg = " << &pkg << ", value = "
        << pkg.msg << ' ' << pkg.v1 << ' ' << pkg.v2 << endl;
    res = transfer(pkg);
    cout << "&res = " << &res << ", value = "
        << res.msg << ' ' << res.v1 << ' ' << res.v2 << endl;
    return 0;
}

实例5.4

问题1：
根据《XX大学出售新建职工住宅实施办法》的规定，特批人员按下述原则进行排队：
1、按照票数多少排序；
2、票数相同的按职务等级排序；
3、职务相同的按来校时间排序；
4、来校时间相同按任职时间排序；
5、任职时间相同的，按出生年月日排序。
请你编写程序，完成下列人员的排队（序）。

姓名,票数,职务等级,来校时间,任职时间,出生时间
zhangsan, 48, 1, 2008, 2006, 1967
lisi,     50, 2, 2009, 2008, 1970
wangwu,   48, 1, 2008, 2006, 1966
zhaoliu,  50, 2, 2008, 2008, 1968
qianjiu,  35, 3, 2011, 2011, 1972

#include <iostream>  // cout
#include <algorithm> // sort
using namespace std;

struct person 
{
    char xingming[20];
    int  piaoshu;
    int  zhiwu_dengji;
    int  laixiao_shijian;
    int  renzhi_shijian;
    int  chusheng_shijian;
};

void output(person p) 
{
    cout << p.xingming << ": " << p.piaoshu << ", "
        << p.zhiwu_dengji << ", " << p.laixiao_shijian << ", "
        << p.renzhi_shijian << ", " << p.chusheng_shijian << endl;
}

void Swap(person* first, person* second) 
{
    person p;
    p = *first;
    *first = *second;
    *second = p;
}

bool person_cmp(person a, person b)
{
    if (a.piaoshu < b.piaoshu) return true;
    if (a.piaoshu > b.piaoshu) return false;

    if (a.zhiwu_dengji < b.zhiwu_dengji) return true;
    if (a.zhiwu_dengji > b.zhiwu_dengji) return false;

    if (a.laixiao_shijian > b.laixiao_shijian) return true;
    if (a.laixiao_shijian < b.laixiao_shijian) return false;

    if (a.renzhi_shijian > b.renzhi_shijian) return true;
    if (a.renzhi_shijian < b.renzhi_shijian) return false;

    if (a.chusheng_shijian > b.chusheng_shijian) return true;
    if (a.chusheng_shijian < b.chusheng_shijian) return false;

    return true;
}

void bubble(person* a, int num)
{
    for (int j = 0; j < num - 1; j++)
        for (int i = 0; i < num - 1 - j; i++)
            if (person_cmp(a[i], a[i + 1]))
                Swap(&(a[i]), &(a[i + 1]));
}

int main()
{
    person array[5] = { {"zhangsan", 48, 1, 2008, 2006, 1967},
                       {"lisi",      50, 2, 2009, 2008, 1970},
                       {"wangwu",    48, 1, 2008, 2006, 1966},
                       {"zhaoliu",   50, 2, 2008, 2008, 1968},
                       {"qianjiu",   35, 3, 2011, 2011, 1972} };
    sort(array, array + 5, person_cmp);
    for (int i = 0; i < 5; i++) output(array[i]);
    return 0;
}

问题2：约瑟夫环
n 只猴子围成一圈，顺时针方向从 0 到 n-1 编号。之后从 0 号开始沿顺时针方向让猴子按 1，2，…，m 依次报数。凡报到 m 的猴子，都让其出圈，取消其候选资格。不停地按顺时针方向逐一让报出 m 的猴子出圈，最后剩下那只就是猴王。
请你编写程序模拟这个过程。要求按取消候选资格的次序，依次输出被淘汰猴子的编号，以及最后剩下的猴王编号。

实际上可以想象将一个数组“首尾相接”形成“环形数组”来解决。

#include <iostream>
#include <vector>
using namespace std;

int main()
{
    int n, m;
    cout << "请输入猴子总数: ";
    cin >> n;
    cout << "请输入报数间隔: ";
    cin >> m;
    // 根据猴子总数创建相应长度的向量，各元素值均为0
    vector<int> ring(n);
    int idx = 0;

    for (int i = 0; i < n; i++)
    {
        int cnt = 0;
        while (1)
        {
            cnt++;
            // 1. 寻找能够报数cnt的位置
            while (ring[idx] == 1)
            {
                idx++;
                idx %= n;
            }
            // 2. 若报数为m，则停止报数
            if (cnt == m) break;
            // 3. 当前位置已安全报数，转下一位置
            idx++;
            idx %= n;
        }
        ring[idx] = 1;// 标记报数为m的猴子
        cout << idx << ' '; // 输出报数为m的猴子位置（从0编号）
    }

    cout << "---> 猴王位置为 " << idx << endl;
    return 0;
}

文件的读写

有些时候我们需要对其他文件进行操作。
我们先介绍打开文件：

#include <iostream>
#include <fstream>
using namespace std;

int main() {
    char fname[20];
    cout << "Please input file name:";
    cin >> fname;

    ifstream input;
    input.open(fname);
    if (input)
        cout << "Open " << fname << " OK\n";
    else
        cout << fname << " not found!\n";
    input.close();

    return 0;
}

接下来我们需要读取文件内容：

#include <fstream>      // ifstream
#include <iostream>     // cout
using namespace std;
// file open, read one word and close
// move file-pointer and read some chars from file
void test2()
{
    ifstream in("log.txt");
    /// 文件指针从文件尾向文件头方向移动4个字节
    in.seekg(-4, ios_base::end); /// 文件开头用ios_base::beg, 当前位置用ios_base::cur
    char word[5];
    in >> word;  /// 从移动后的位置开始读取一个字符串
    cout << "Last 4 chars = " << word << endl;
    in.close();
}

int main()
{
    test2();
    return 0;
}

进一步我们需要写入文件：

#include <fstream>  // ofstream
using namespace std;

// file open, output and close
void test1() 
{
    ofstream out;
    out.open("log.txt"); // 如文件存在，则清除其内容
    out << "Hello, world!" << endl;
    out.close();
}

// append
void test2() 
{
    ofstream out;
    out.open("log.txt", ios::app); // 在原文件内容后面添加新内容
    out << "THU " << endl << "CST##";
    out.close();
}

// 主函数中对上述各种文件操作进行测试
int main() 
{
    test1();
    getchar();
    test2();
    return 0;
}

读写中还有一种特殊的形式：二进制读写，即以二进制的方式读取与写入。

#include <iostream>
#include <fstream>
#include <cstring>
using namespace std;

// write binary data
void w_test_1()
{
    ofstream out;
    out.open("log3.txt", ios::binary);
    float f = 3.4f;
    out.write(reinterpret_cast<char *>(&f), sizeof(f)); /// &f 需要被转换成 char*
    // 等价于 out.write((char*)(&f), sizeof(f));
    out.close();
}

// read binary data
void r_test_1()
{
    ifstream in;
    in.open("log3.txt", ios::binary);
    float f;
    in.read(reinterpret_cast<char *>(&f), sizeof(f)); /// &f 需要被转换成 char*
    // 等价于 in.read((char*)(&f), sizeof(f));
    cout << "f = " << f << endl;
    in.close();
}

// write binary struct
void w_test_2()
{
    struct S
    {
        int a, b;
        char info[10];
    } data; /// 定义结构类型和结构变量

    ofstream out;
    out.open("log4.txt", ios::binary);
    data.a = 3;
    data.b = 45;
    strcpy(data.info, "THU");
    out.write(reinterpret_cast<char *>(&data), sizeof(data));
    out.close();
}

// read binary struct
void r_test_2()
{
    struct S
    {
        int a, b;
        char info[10];
    } data; /// 定义结构类型和结构变量

    ifstream in;
    in.open("log4.txt", ios::binary);
    in.read(reinterpret_cast<char *>(&data), sizeof(data));
    cout << data.a << ' ' << data.b << ' ' << data.info << endl;
    in.close();
}

int main()
{
    r_test_1();
    w_test_1();
    r_test_2();
    w_test_2();
    return 0;
}

实例5.5

问题1：
老师给小明布置了一道有特殊要求的计算题：将10000个自然数进行累加（不要求以自然数序输入），数据是老师提供的，打印在纸上，要求手工输入给程序。
注意：因为数据量巨大，可能需要好几天才能完成 …小明不干活时，程序是要求退出的（因为要关机）。
输入0表示老师询问中间结果，程序输出累计结果。输入-1表示结束本轮输入，程序退出。
要求：不能将中间结果输出到屏幕上。
针对以上场景，我们可以采用文件读写的方式：

#include <iostream>
#include <fstream>
using namespace std;

int main()
{
    int last_cnt = 0, last_res = 0;  // 后面从文件读数据可能失败，因此需要在定义时进行初始化
    ifstream status("tmp.res");
    if (status)
        status >> last_cnt >> last_res; // 若文件不存在，则不会更新这两个变量的值
    status.close();
    for (; last_cnt < 10000;)
    {
        int data;
        cout << "input " << last_cnt << "-th number:";
        cin >> data; // 变量data既可能是用户要计算的数据，也可能是用户的“操作指令”
        if (data == 0) // 操作指令：要求输出当前结果
        {
            cout << "current result = " << last_res << endl;
            continue;
        }

        if (data == -1) // 操作指令：结束当前计算任务，保存中间结果
        {
            cout << "bye-bye" << endl;
            ofstream fout("tmp.res");
            fout << last_cnt << ' ' << last_res;
            fout.close();
            break;
        }

        // 若执行到这里，则既没有continue, 也没有break，表明输入不是指令，在是需要累加的数
        last_res += data;
        last_cnt++;
    }

    if (last_cnt == 10000)
        cout << "Finished! Final result = " << last_res << endl;
    return 0;
}

问题2：
对一篇英文文章中出现的单词进行统计，输出各个单词出现次数。
例如，设某个文本文件的内容为：

If you are editing several files in emacs, each in its own buffer, each buffer has its own point location. A buffer that is not currently displayed remembers where point is in case you display it again later.

则程序应该输出：

If 1
you 1
are 1
editing 1
several 1
files 1
in 3
...
again 1
later 1

这里的文字从文件中读取。

#include <iostream>
#include <fstream>
#include <cstring>
#include <vector>
using namespace std;

struct word_count 
{
    char word[20];
    int count;
};

int main() 
{
    int num = 0;
    vector<word_count> wd_cnt(100);
    char file_name[10];
    cout << "Please input file name:";
    cin >> file_name;
    fstream fin;
    fin.open(file_name);
    while (!fin.eof()) 
    {
        char word[20];    
        fin >> word;
        bool found = false;

        char* last_char = word + strlen(word) - 1;
        if (*last_char == '.' || *last_char == ',')
            *last_char = '\0';

        if (fin.eof())
            break;

        for (int i = 0; i < num; i++) 
        {
            if (strcmp(word, wd_cnt[i].word) == 0) 
            {
                wd_cnt[i].count++;
                found = true;
                break;
            }
        }

        if (!found) 
        {
            strcpy_s(wd_cnt[num].word, word);
            wd_cnt[num].count = 1;
            num++;
        }
    }

    fin.close();
    for (int i = 0; i < num; i++)
        cout << wd_cnt[i].word << ' '
        << wd_cnt[i].count << endl;
    return 0;
}

问题3：
期中考试结束了。班主任孔老师让助教王小二从各科老师处拿到了全班学生的成绩。孔老师想通过计算班上每个学生的学分绩，统计班级平均分、最高分、最低分，得到班级成绩各分数段人数情况（也称直方图）。
请你跟王小二一起来完成这个任务吧。已知课程有三门：几何与代数、离散数学、一元微积分。
各科成绩保存在不同的文本文件中，存储格式为：文件每一行对应一名学生，包含学生姓名、学号、成绩（整数）。
各课程的成绩文件、学分为：
几代：g.txt，4 学分
离散：d.txt，3 学分
微积：m.txt，4 学分

#include <iostream>
#include <fstream>
#include <cstring>
using namespace std;

struct OneGrade // 单科成绩
{
    char name[20];
    long int id;
    int score;
};

struct AllGrade // 综合成绩
{
    char name[20];
    long int id;
    int m_score, g_score, d_score;
};

int read_from(char fname[20], OneGrade score_array[40])
{
    int idx = 0; // student index
    ifstream fin;
    fin.open(fname);
    while (!fin.eof())
    {
        char name[20];
        long int id;
        int score;
        fin >> name >> id >> score;
        strcpy_s(score_array[idx].name, name);
        score_array[idx].id = id;
        score_array[idx].score = score;
        idx++;
    }
    fin.close();
    return idx;
}

int main()
{
    int stu_num = 0; // 学生总人数
    char m_file[20], g_file[20], d_file[20];
    OneGrade m_grade[40], g_grade[40], d_grade[40];
    AllGrade mgd_grade[40];

    memset(mgd_grade, 0, sizeof(mgd_grade));
    float max_gpa, min_gpa, avg_gpa;
    int hist[6]; // 六个分数段：不及格，~70, ~80, ~90, ~100, 100

    cout << "input m_grade file:";
    cin >> m_file;
    stu_num = read_from(m_file, m_grade);

    cout << "input g_grade file:";
    cin >> g_file;
    read_from(g_file, g_grade);

    cout << "input d_grade file:";
    cin >> d_file;
    read_from(d_file, d_grade);

    for (int i = 0; i < stu_num; i++)
    {
        strcpy_s(mgd_grade[i].name, d_grade[i].name);
        mgd_grade[i].id = d_grade[i].id;
        mgd_grade[i].d_score = d_grade[i].score;
    } // 完成一门课程的成绩复制

    for (int i = 0; i < stu_num; i++)
    {
        for (int j = 0; j < stu_num; j++)
        {
            if (mgd_grade[j].id == g_grade[i].id)
            {
                mgd_grade[j].g_score = g_grade[i].score;
                break;
            }
        }
    }

    for (int i = 0; i < stu_num; i++)
    {
        for (int j = 0; j < stu_num; j++)
        {
            if (mgd_grade[j].id == m_grade[i].id)
            {
                mgd_grade[j].m_score = m_grade[i].score;
                break;
            }
        }
    }

    max_gpa = 0;
    min_gpa = 100;
    avg_gpa = 0;
    memset(hist, 0, sizeof(hist));

    for (int i = 0; i < stu_num; i++)
    {
        float gpa = (mgd_grade[i].m_score * 4.0 +
                     mgd_grade[i].g_score * 4.0 +
                     mgd_grade[i].d_score * 3.0) /
                    11;
        if (gpa > max_gpa)
            max_gpa = gpa;
        if (gpa < min_gpa)
            min_gpa = gpa;
        avg_gpa += gpa; // 先累加求和，循环结束后再除以人数
        if (gpa < 60)
            hist[0]++; // [ 0, 60)
        else
            hist[int(gpa) / 10 - 5]++;
    } // for

    avg_gpa /= stu_num;
    cout << "MAX GPA = " << max_gpa << endl;
    cout << "MIN GPA = " << min_gpa << endl;
    cout << "AVG GPA = " << avg_gpa << endl;
    cout << "[0..59], [60..69], [70..79], [80..89], [90..99], 100\n";
    for (int i = 0; i < 6; i++)
        cout << "HIST[" << i << "]: " << hist[i] << endl;
    return 0;
}

问题4：
基于波形拼接算法的语音合成：利用事先录制好的样例语音template.wav（标准WAV文件，二进制文件），以及配套标注文件（纯文本文件），根据用户输入的数字串（假定均为合法数字），依次从样例语音文件中抽取相应数字对应的语音片段，将它们拼接到一起，保存到一个新的标准WAV格式文件中。要求提供程序运行参数来指定数字串，或运行时询问用户需要合成的数字串。
标注文件template_label_sample_point.txt的格式为：每一行包含3列，分别表示数字、在语音数据中的起始位置（以采样样本为单位）、发音时间持续长度（以采样样本为单位）。例如：

1 2	`1 7296 9600 2 17840 7760`

#include <cstring>  // strlen
#include <fstream>  // ifstream, ofstream
#include <iostream> // cin, cout
using namespace std;

char TEMPLATE_WAV_FILE[] = "template.wav";
char TEMPLATE_WAV_LABEL_FILE[] = "template_label_sample_point.txt";
char OUTPUT_WAV_FILE[] = "output.wav";
struct WavHead {
    char riff_id[4];           //! 标识串"RIFF"
    long size0;                //波形块的大小
    char wave_fmt[8];          //! 标识串"WAVEfmt "
    long size1;                //格式块的大小
    short fmttag;              //波形编码格式
    short channel;             //音频数据的声道数
    long sampl;                //音频采样率
    long bytepersecblockalign; //每秒音频需要记录的字节数
    short blockalign;          //存储一个采样需要的字节数
    short bitpersamples;       //每个采样的二进制位数
    char data[4];              //! 标识串"data"
    long datasize;             //数据块大小
};

bool str_equal(char* a, const char* b, int len)
{
    for (int i = 0; i < len; i++)
    {
        if (a[i] != b[i])
            return false;
    }
    return true;
}

bool is_valid_fmt(WavHead* phead) // 结构体变量的指针！
{
    // 文件格式检查
    if (!str_equal(phead->riff_id, "RIFF", 4) ||
        !str_equal(phead->wave_fmt, "WAVEfmt", 7) ||
        !str_equal(phead->data, "data", 4))
    {
        cout << "Invalid wav format" << endl;
        return false;
    }
    // 数据格式检查
    if (phead->channel != 1)
    {
        cout << "Only support channel = 1, now channel = " << phead->channel << endl;
        return false;
    }
    if (phead->bitpersamples != 16)
    {
        cout << "Only suport bitpeprsamples = 16, now bitpersamples = "
            << phead->bitpersamples << endl;
        return false;
    }
    return true;
}

// 通过指针参数phead返回文件头信息，通过函数返回值(short*)返回全部音频数据
short* load_wav(char* wav_file, WavHead* phead)
{
    ifstream fin(wav_file, ios::binary);
    fin.read((char*)phead, sizeof(WavHead));
    short* pdata = new short[phead->datasize / sizeof(short)];
    fin.read((char*)pdata, phead->datasize);
    fin.close();
    return pdata;
}

void load_labels(char* label_file, int* start_sample, int* len_samples)
{
    ifstream fin(label_file);
    int num;
    while (fin >> num)
        fin >> start_sample[num] >> len_samples[num];
    fin.close();
}

// 检查输入数字串是否合法
bool is_valid_input(char* target)
{
    char digit;
    while (digit = *target++)
    {
        // 方法二：if (digit < '0' || digit > '9')
        // 方法三：使用 isdigit(digit) 函数进行判断（#include <ctype.h>)
        if (!(digit >= '0' && digit <= '9'))
        {
            cerr << "Invalid input " << digit << endl;
            return false;
        }
    }
    return true;
}

int main()
{
    WavHead head;
    short* pdata = load_wav(TEMPLATE_WAV_FILE, &head); // 读入语音数据
    int start_sample[10], len_samples[10];
    load_labels(TEMPLATE_WAV_LABEL_FILE, start_sample, len_samples); // 读入文本标签
    char target[100];
    cout << "Please input digits (length < 100): ";
    cin >> target;
    if (!is_valid_input(target))
        return -1;
    //! 用【语音拼接法】合成指定数字串的语音文件 -->
    int target_len = strlen(target);
    ofstream fout(OUTPUT_WAV_FILE, ios::binary);  // WAV文件是二进制的文件

    // <1> 写入WAV文件的头结构：先计算语音数据长度，准备好WAV文件的头结构
    head.datasize = 0;
    for (int i = 0; i < target_len; i++)
        head.datasize += len_samples[target[i] - '0'] * sizeof(short);
    fout.write((char*)&head, sizeof(WavHead));

    // <2> 依次写入数字串中各位数字对应的语音数据
    for (int i = 0; i < target_len; i++)
    {
        int num = target[i] - '0'; // 从数字字符得到数字值
        fout.write((char*)(pdata + start_sample[num]), sizeof(short) * len_samples[num]);
    }
    fout.close();
    delete[] pdata;

    cout << "Speech for " << target << " saved in " << OUTPUT_WAV_FILE << endl;
    return 0;
}

链表

循环链表是一种比较好的处理约瑟夫环的方式，每个节点包含自身的内容和指向下个节点的指针。

#include <iostream>
using namespace std;

struct monkey
{
    int num;
    monkey* next;
}*head,*tail;

void create(int nn) {
    monkey* p, * q;

    p = new monkey;
    p->num = 1;
    p->next = NULL;

    head = p;  // 全局变量head为链表头，赋值为p
    q = p;     // 局部变量q为当前链表尾，赋值为p
    for (int i = 2; i <= nn; i++) {
        p = new monkey;
        p->num = i;
        p->next = NULL;// 链表尾部指向空
        q->next = p;   // 将p结点加到链表尾部
        q = p;         // 让q指向链表尾部结点
    }
    tail = q; // 全局变量tail为链表尾
    tail->next = head; // 链表尾部指向链表头，形成了“循环链表”！
}

int main()
{
    int length;
    cin >> length;
    create(length);
    return 0;
}

6.减治思想

减而治之就是减治思想。

递归函数

如果一个函数运行时需要调用他自己，这样的函数就叫做递归函数。例如如下函数用来计算正整数的阶乘：

#include <iostream>
using namespace std;

int fact(int n) 
{
    if (n == 1)           /// 终止条件
        return 1;         /// 直接返回

    return n * fact(n - 1); /// n * (n-1)!
}   /// 自己调用自己的函数，被称为递归函数

int main() 
{
    cout << "fact(3) = " << fact(3) << endl;
    return 0;
}
/// 函数改变实参调用自己求解正整数的阶乘

实例6

问题1：
请编写程序，输出N*N的数字方阵，将1~N*N的自然数逆时针旋转填充到矩阵中。下面是一个6*6的矩阵完成填充后的示意图。

1 20 19 18 17 16
2 21 32 31 30 15
3 22 33 36 29 14
4 23 34 35 28 13
5 24 25 26 27 12
6  7  8  9 10 11

#include <iostream>
#include <iomanip>
using namespace std;

int m[6][6] = { {0} };

void Show()
{
    for (int i = 0; i < 6; i++) {
        for (int j = 0; j < 6; j++)
            cout << setw(2) << m[i][j] << ' ';
        cout << endl;
    }
}

void Fill(int num, int begin, int size) {
    if (size == 0) return;

    if (size == 1) {
        m[begin][begin] = num;
        return;
    }

    for (int j = 0; j < size - 1; j++)
    {
        m[begin + j][begin] = num + j;
        m[begin + size - 1][begin + j] = size - 1 + num + j;
        m[begin + size - 1 - j][begin + size - 1] = 2 * (size - 1) + num + j;
        m[begin][begin + size - 1 - j] = 3 * (size - 1) + num + j;
    }

    Fill(num + 4 * (size - 1), begin + 1, size - 2);
}

int main() 
{
    Fill(1, 0, 6);
    Show();

    return 0;
}

问题2：
计算组合数 C(m, n)

#include <iostream>
using namespace std;

int C(int m, int n)
{
    if (m < 0 || n < 0 || m < n)
        return 0;
    if (m == n) return 1;
    if (n == 1) return m;
    return C(m - 1, n) + C(m - 1, n - 1);
}

int main()
{
    cout << "C(6,2) = "
        << C(6, 2) << endl;
    return 0;
}

问题3：
计算斐波那契数列
我们在这里使用备忘录的技巧。如果计算过一些值，我们将他们储存起来，再次计算时就不需要重复计算了。这能将时间复杂度换为空间复杂度。

#include <iostream>
using namespace std;

int FIB[20] = { 0 }; /// 这个变量被称为“备忘录”，存储已计算的结果

int fib(int n)
{
    if (FIB[n])
        return FIB[n]; /// 若已计算过，直接查“备忘录”返回结果（也称“查表”）
    if (n < 2)
        FIB[n] = n;  // 保存到备忘录中
    else
        FIB[n] = fib(n - 1) + fib(n - 2);  // 保存到备忘录中
    return FIB[n];
}

int main()
{
    for (int i = 1; i <= 12; i++)
        cout << fib(i) << ' ';
    cout << endl;
    return 0;
}

问题4：
汉诺塔问题

#include <iostream>
using namespace std;

int step = 1;  // 记录操作步骤的次序

// 函数功能：将n只盘子，从A柱借助B柱移到C柱，输出操作步骤
void move(int n, char A, char B, char C) {
    if (n == 1) { // 如果n为1，则为直接可解结点
        cout << "[" << step << "] move 1# from " << A
            << " to " << C << endl;
        step++;
    }
    else {
        move(n - 1, A, C, B);
        //直接可解结点，输出操作步骤的文字说明信息
        cout << "[" << step << "] move " << n
            << "# from " << A << " to " << C << endl;
        step++;
        move(n - 1, B, A, C);
    }
}

int main() {
    int n;
    cout << "盘数n = ";
    cin >> n;
    cout << "在3根柱子上移" << n << "只盘的步骤为: " << endl;
    move(n, 'A', 'B', 'C');
    return 0;
}

7.分治思想

分而治之就是分治思想。

从排序算法说起

选择排序：选择数组中元素最小的元素，与第一位交换，然后递归。

#include <iostream>
using namespace std;

void select_sort(int A[], int n) {
    // 1. 检查递归是否中止
    if (n == 1) return;

    // 2. 查找最小元素
    int smallest = 0;
    for (int i = 1; i < n; i++)
        if (A[i] < A[smallest]) smallest = i;

    // 3. 将最小元素与A[0]交换（如果需要的话）
    if (smallest) {
        int tmp = A[0];
        A[0] = A[smallest];
        A[smallest] = tmp;
    }

    // 4. 对剩余数组继续使用选择排序
    select_sort(A + 1, n - 1);
}

int main() {
    int A[] = { 5, 2, 6, 1, 7, 3, 4 };  // just for test

    int num = sizeof(A) / sizeof(A[0]);

    select_sort(A, num);

    for (int i = 0; i < num; i++) cout << A[i] << ' ';
    cout << endl;

    return 0;
}

归并排序：将数组拆分为两个子数组分别排序，递归分治，最后合并。

#include <iostream>
using namespace std;

void merge_sort(int A[], int start, int end) {
    /// 1. 递归中止条件
    if (start == end - 1) return;

    /// 2. 对两个子数组分开排序
    int mid = (end + start) / 2;
    merge_sort(A, start, mid);
    merge_sort(A, mid, end);

    /// 3. 合并有序子数组中的元素
    /// 3.1 分配临时空间存放合并元素
    int* tmp = new int[end - start];
    /// 3.2 依次取出子数组的元素，进行合并
    int left_idx = start, right_idx = mid, i = 0;
    while (left_idx < mid && right_idx < end) {
        if (A[left_idx] < A[right_idx])
            tmp[i++] = A[left_idx++];
        else
            tmp[i++] = A[right_idx++];
    }

    /// 3.3 如果有子数组元素没有取完，则全部并入临时空间
    while (left_idx < mid)  
        tmp[i++] = A[left_idx++]; /// 先左
    while (right_idx < end) 
        tmp[i++] = A[right_idx++];/// 后右

    /// 3.4 从临时空间复制回返回数组中
    for (int i = 0, idx = start; i < end - start; i++, idx++)
        A[idx] = tmp[i];

    /// 3.5 释放临时空间
    delete[] tmp;
}

int main() {
    int A[] = { 5, 2, 6, 1, 7, 3, 4 };  // just for test

    int num = sizeof(A) / sizeof(A[0]);

    merge_sort(A, 0, num);

    for (int i = 0; i < num; i++) cout << A[i] << ' ';
    cout << endl;

    return 0;
}

快速排序：选取特定元素，将比其大和比其小的元素分别置于两侧，随后递归分治。

快速排序1

#include <iostream>   
using namespace std;

int a[] = { 5, 2, 6, 1, 7, 3, 4 };  /// 全局数组变量

void sort(int z, int y) {
    if (z >= y) return;

    int zz = z, yy = y, k = a[z], m = 0;
    do {
        /// scan from right to left
        while ((zz < yy) && (a[yy] > k)) yy--;
        if (zz < yy) a[zz++] = a[yy];

        /// scan from left to right
        while ((zz < yy) && (a[zz] <= k)) zz++;
        if (zz < yy) a[yy--] = a[zz];
    } while (zz != yy);
    m = zz;   /// 找到了分区点，记录到m中
    a[m] = k; /// 完成分区操作（数值k归位）

    sort(z, m - 1);
    sort(m + 1, y);
}

int main() {
    int len = sizeof(a) / sizeof(a[0]);
    sort(0, len - 1);

    for (int i = 0; i < len; i++)
        cout << a[i] << ' ';
    cout << endl;

    return 0;
}

快速排序2（去掉全局变量，调整函数接口）

#include <iostream>        // cout
using namespace std;

void sort(int array[], int low, int high) {
    if (low >= high) return;

    int z = low, y = high, k = array[z];
    do {
        /// scan from right to left
        while ((z < y) && (array[y] > k)) y--;
        if (z < y) array[z++] = array[y];

        /// scan from left to right
        while ((z < y) && (array[z] <= k)) z++;
        if (z < y) array[y--] = array[z];
    } while (z != y);
    array[z] = k;

    sort(array, low, z - 1);
    sort(array, z + 1, high);
}

int main() {
    int a[] = { 5, 2, 6, 1, 7, 3, 4 };
    int len = sizeof(a) / sizeof(a[0]);

    sort(a, 0, len - 1);

    for (int i = 0; i < len; i++)
        cout << a[i] << ' ';
    cout << endl;

    return 0;
}

9-5
快速排序3（暴力分区）

#include <iostream> // cout
using namespace std;

void quick_sort(int *array, int len)
{
    if (len <= 1)
        return;
    /// 按最坏可能，为两个子数组分配空间
    int *left = new int[len], *right = new int[len];
    /// 设置两个子数组长度的初值（为零）
    int left_len = 0, right_len = 0;
    /// 1. 拆分
    int key = array[0]; /// 选第0个元素为基准值
    for (int i = 1; i < len; i++)
    { /// 将剩余各数进行分区
        if (array[i] <= key)
            left[left_len++] = array[i];
        if (array[i] > key)
            right[right_len++] = array[i];
    }
    /// 2. 对子数组进行排序
    quick_sort(left, left_len);
    quick_sort(right, right_len);
    /// 3. 合并子数组，先左后右
    int idx = 0;
    for (int i = 0; i < left_len; i++)
        array[idx++] = left[i];
    array[idx++] = key;
    for (int i = 0; i < right_len; i++)
        array[idx++] = right[i];
    /// 释放空间
    delete[] left;
    delete[] right;
}

int main()
{
    int a[] = {5, 2, 6, 1, 7, 3, 4};
    int len = sizeof(a) / sizeof(a[0]);

    quick_sort(a, len);

    for (int i = 0; i < len; i++)
        cout << a[i] << ' ';
    cout << endl;

    return 0;
}

9-6
快速排序4（双向同步）

#include <iostream> // cout
using namespace std;

void quick_sort(int *p, int n)
{
    if (n <= 1)
        return;
    int t = p[n - 1], left = 0, right = n - 2; /// 尾部元素作基准
    do
    {
        for (; right >= left; left++)
            if (p[left] > t)
                break;
        for (; right >= left; right--)
            if (p[right] < t)
                break;
        if (right >= left)
            swap(p[left], p[right]);
    } while (right >= left);
    swap(p[left], p[n - 1]); /// 将基准元素交换到它该去的位置
    quick_sort(&p[0], left);
    quick_sort(&p[left + 1], n - left - 1);
}

int main()
{
    int a[] = {5, 2, 6, 1, 7, 3, 4};
    int len = sizeof(a) / sizeof(a[0]);

    quick_sort(a, len);

    for (int i = 0; i < len; i++)
        cout << a[i] << ' ';
    cout << endl;

    return 0;
}

实例7

问题1：
一条小溪尺寸不大，青蛙可以从左岸跳到右岸，左岸有一石柱L，面积只容得下一只青蛙落脚，同样右岸也有一石柱R，面积也只容得下一只青蛙落脚。有一队青蛙从尺寸上一个比一个小。我们将青蛙从小到大，用1，2，…，n编号。
规定：初始时这队青蛙只能趴在左岸的石头L上，按编号一个落一个，小的落在大的上面。不允许大的在小的上面。
在小溪中有S个石柱，有y片荷叶，规定溪中的柱子上允许一只青蛙落脚，如有多只同样要求按编号一个落一个，大的在下，小的在上，而且必须编号相邻。对于荷叶只允许一只青蛙落脚，不允许多只在其上。对于右岸的石柱R，与左岸的石柱L一样允许多个青蛙落脚，但须一个落一个，小的在上，大的在下，且编号相邻。
当青蛙从左岸的L上跳走后就不允许再跳回来；同样，从左岸L上跳至右岸R，或从溪中荷叶或溪中石柱跳至右岸R上的青蛙也不允许再离开。
问: 在已知溪中有s根石柱和y片荷叶的情况下，最多能跳过多少只青蛙？

这本质上是个数学问题。

#include <iostream>
using namespace std;

int Jump(int S, int y) {
    if (S == 0) return y + 1;
    return 2 * Jump(S - 1, y);
}

int main() {
    int S, y, sum;

    cout << "ÇëÊäÈëÊ¯ÖùÊýS=";
    cin >> S;
    cout << "ÇëÊäÈëºÉÒ¶Êýy=";
    cin >> y;

    sum = Jump(S, y);
    cout << "Jump(" << S << "," << y << ") = 2" << sum << endl;
    return 0;
}

问题2：
请你编写一个程序，输出九连环的操作步骤
1.只有第一个环可以自由上下，前两个环可同时上下
2.想要卸下某个环，就必须满足两个条件:
第一、这个环的前一个环要留在杆上;
第二、其他前面的环都不在上面。
装跟卸的方法、条件一样，倒推过来就行。

#include <iostream>
using namespace std;

// 设置正的初始状态为“在线上（为1）”
int ring[10] = { 1,1,1,1,1,1,1,1,1,1 };

// 上或下使用同一个函数（递归实现）
void ChangeTo(int pos, int dst) {
    if (ring[pos] == dst) return;

    // 1. 
    ChangeTo(pos - 1, 1);

    // 2.
    for (int idx = pos - 2; idx > 0; idx--) ChangeTo(idx, 0);

    // 3.
    ring[pos] = dst;

    // 4.
    cout << pos << "-->" << dst << " [";
    for (int i = 1; i < 9; i++) cout << ring[i] << ", ";
    cout << ring[9] << "]\n";
}

int main() {
    // 0. 从9到1按顺序将环取下（置为0）
    for (int i = 9; i > 0; i--) ChangeTo(i, 0);
    return 0;
}

8.枚举思想

实例8

问题1：
从楼上到楼下一共有 h 级台阶，若每一步有三种走法（步幅）：
走一级台阶；
走二级台阶；
走三级台阶。
请给出所有可能的下楼方案。每个方案包括：共要多少步？每一步走几级台阶？请用递归算法求解。

#include <iostream> // cout
using namespace std;

// 方案细节记录在take中，方案数用num累计
int take[100], num = 0;

void Try(int i, int s)
{
    for (int j = 3; j > 0; j--)
    {
        if (i >= j)
        {
            take[s] = j; // 记录第s步走j个台阶
            if (i == j)
            {          // 如果已经到了楼下
                num++; // 则方案数加1
                cout << "方案" << num << ": ";
                for (int k = 1; k <= s; k++)
                    cout << take[k];
                cout << endl;
            }
            else                   // 尚未走到楼下
                Try(i - j, s + 1); // 再试剩下的台阶
        }
    }
}
// 有i级台阶，从第s步开始

int main()
{
    cout << "请输入楼梯台阶数h(<100)：";
    int h;
    cin >> h; // 输入楼梯的台阶数

    Try(h, 1); // 从第h级，开始下第一步

    cout << "总方案数：" << num << endl;

    return 0;
}

问题2：
在半张中国象棋的棋盘上，一只马从左下角跳到右上角，只允许往右跳，不允许往左跳，问能有多少种跳步方案。
要求：输出方案数和各方案的具体跳法。

解法一（常规）

#include <iostream> // cout
using namespace std;

int dx[] = {1, 2, 2, 1}, dy[] = {2, 1, -1, -2};
int num, path[100][2];

void Jump(int x, int y, int step)
{
    // 是否到达目标？
    if ((x == 8) && (y == 4))
    {
        num++; // 方案数加1
        cout << num << ": ";
        for (int i = 0; i < step; i++) // 从起点开始输出各步的坐标
            cout << "(" << path[i][0] << ", " << path[i][1] << ") ";
        cout << endl;

        return;
    }
    // 遍历四种跳步方向
    for (int k = 0; k < 4; k++)
    {
        int x1 = x + dx[k], y1 = y + dy[k];

        // 若(x1, y1)不可行，则放弃当前测试，转至下一个跳步方案
        if ((x1 < 0) || (x1 > 8) || (y1 < 0) || (y1 > 4))
            continue;

        path[step][0] = x1;
        path[step][1] = y1;

        /// 从(x1, y1)出发到目标点，有多少种跳法？--- 问题性质相同，规模缩小：递归！
        Jump(x1, y1, step + 1);
    }
}

int main()
{
    // 初始方案数置0
    num = 0;

    // 从位置(0,0)出发，第0步
    Jump(0, 0, 0);

    return 0;
}

解法二（结构体数组）

#include <iostream> // cout
using namespace std;

struct position
{
    int x, y;
};
position dxy[4] = {{1, 2}, {2, 1}, {2, -1}, {1, -2}};
position start_pos = {0, 0}, goal_pos = {8, 4};
position path[100];
int num;

void Jump(position pos, int step)
{
    // 是否到达目标？
    if ((pos.x == 8) && (pos.y == 4))
    {
        num++; // 方案数加1
        cout << num << ": ";
        for (int i = 0; i < step; i++) // 从起点开始输出各步的坐标
            cout << "(" << path[i].x << ", " << path[i].y << ") ";
        cout << endl;
        return;
    }

    // 遍历四种跳步方向
    for (int k = 0; k < 4; k++)
    {
        position next_pos = {pos.x + dxy[k].x, pos.y + dxy[k].y};
        // 检查next_pos是否可行？
        if ((next_pos.x < 0) || (next_pos.x > 8) ||
            (next_pos.y < 0) || (next_pos.y > 4))
            continue;

        // 记录方案！结构变量可以直接赋值！
        path[step] = next_pos;

        // 从next_pos出发到目标位置，有多少种跳步方案？【递归】
        Jump(next_pos, step + 1);
    }
}

int main()
{
    num = 0;            // 初始方案数置0
    Jump(start_pos, 0); // 跳第一步
    return 0;
}

问题3：
有编号分别为 0、1、2、3、4 的五本书，准备分给A、B、C、D、E五个人。请你写一个程序，输出所有的分书方案，要求每个分书方案都能让每个人都皆大欢喜（即每人都分到感兴趣的书）。假定这5个人对5本书的阅读兴趣如下表（1表示喜欢，0表示不喜欢）：

  0  1  2  3  4
A 0, 0, 1, 1, 0
B 1, 1, 0, 0, 1
C 0, 1, 1, 0, 1
D 0, 0, 0, 1, 0
E 0, 1, 0, 0, 1

一种重要的想法是回溯算法：当方案不满足条件时进行回溯处理。

#include <iostream> // cout
using namespace std;

/// 读者与书本的编号都是基于0的
int like[5][5] = {{0, 0, 1, 1, 0},
                  {1, 1, 0, 0, 1},
                  {0, 1, 1, 0, 1},
                  {0, 0, 0, 1, 0},
                  {0, 1, 0, 0, 1}};
int num;         /// 方案数
int assigned[5]; /// assigned[book_id] = reader_id，值为-1表示没有被分配

void Try(int reader)
{
    /// 递归中止条件：所有读者均已分配合适书籍
    if (reader == 5)
    {
        num++;
        cout << "第" << num << "个方案（5本书的读者编号）: ";
        for (int i = 0; i < 5; i++)
            cout << assigned[i] << ' ';
        cout << endl;
        return;
    }
    /// 逐一为每本书找到合适的读者
    for (int book = 0; book < 5; book++)
    {
        /// 是否满足分书条件
        if ((like[reader][book] != 1) || assigned[book] != -1)
            continue;
        /// 记录当前这本书的分配情况
        assigned[book] = reader;
        /// 从下一位读者开始，分配剩余书籍的所有方案
        Try(reader + 1);
        /// 尝试下一种分书方案前，需要将本次分配的书退还（回溯），即恢复“未分配”状态
        assigned[book] = -1;
    }
}

int main()
{
    // 设置分书方案数初始值为0
    num = 0;

    /// 设置书本初始状态为未分配
    for (int book = 0; book < 5; book++)
        assigned[book] = -1;

    /// 从第0个读者开始，寻找所有分书方案
    Try(0);

    return 0;
}

另一种解法（不回溯）

#include <iostream> // cout
using namespace std;

int like[5][5] = {{0, 0, 1, 1, 0},
                  {1, 1, 0, 0, 1},
                  {0, 1, 1, 0, 1},
                  {0, 0, 0, 1, 0},
                  {0, 1, 0, 0, 1}};
int num; /// 方案数

/// 分配方案：记录5本书分别分给谁（用户编号)
struct assign_state
{
    int assigned[5];
} state;

void Try(int reader, assign_state state)
{
    /// 递归中止条件：所有读者均已分配合适书籍
    if (reader == 5)
    {
        num++;
        cout << "第" << num << "个方案（5本书的读者编号）: ";
        for (int i = 0; i < 5; i++)
            cout << state.assigned[i] << ' ';
        cout << endl;
        return;
    }
    /// 逐一为每本书找到合适的读者
    for (int book = 0; book < 5; book++)
    {
        /// 是否满足分书条件
        if (like[reader][book] != 1 || state.assigned[book] != -1)
            continue;

        /// 记录当前这本书的分配情况
        assign_state next_state = state; /// 初始化新的状态变量
        next_state.assigned[book] = reader;

        /// 从下一位读者开始，求解分配剩余书籍的所有方案
        Try(reader + 1, next_state); /// 不需要回溯了!  开启平行宇宙！
    }
}

int main()
{
    num = 0; // 分书方案数初始值
    for (int book = 0; book < 5; book++)
        state.assigned[book] = -1;
    Try(0, state); // 从第0个人（A）开始分书
    return 0;
}

问题4：
在国际象棋的棋盘上，放置8个皇后（棋子），使皇后两两之间互不攻击。

自然可以采用暴力算法（利用next_permutation全排列）

#include <iostream>
#include <algorithm>
using namespace std;

bool CanAttack(int q[9], int pos1, int pos2)
{
    if (abs(pos1 - pos2) == abs(q[pos1] - q[pos2]))
        return true;
    return false;
}

bool IsSafe(int q[9])
{
    for (int i = 2; i <= 8; i++)
        for (int j = 1; j <= i - 1; j++)
            if (CanAttack(q, i, j))
                return false;
    return true;
}

int main()
{
    int q[9], num = 0;
    // int q = {0, 1, 2, 3, 4, 5, 6, 7, 8};
    for (int i = 1; i <= 8; i++)
        q[i] = i;
    do
    {
        if (IsSafe(q))
        {
            num++;
            cout << num << ": ";
            for (int i = 1; i <= 8; i++)
                cout << q[i] << ' ';
            cout << endl;
        }
    } while (next_permutation(q + 1, q + 9));

    return 0;
}

枚举+递归解法（回溯）

#include <iostream>
using namespace std;

int Num;        // 方案数
int Q[9];       // 8个皇后所占用的行号
bool S[9];      // S[1]~S[8]，当前行是否安全
bool L[17];     // L[2]~L[16]，(i-j)对角线是否安全
bool R[17];     // R[2]~R[16]，(i+j)对角线是否安全
const int OFFSET = 9;    // 用来统一数组下标范围[2,3,...,16]

void Try(int col) {
    /// 递归中止条件：所有列均已放上皇后了
    if (col == 9) {
        Num++;

        cout << "方案" << Num << "：";
        for (int k = 1; k <= 8; k++) cout << Q[k] << " ";
        cout << endl;

        return;
    }

    /// 依次尝试当前列的 8 行位置
        /// 依次尝试当前列的 8 行位置
    for (int row = 1; row <= 8; row++) {
        /// 判断拟放置皇后的位置是否安全
        if (!S[row] || !R[col + row] ||
            !L[col - row + OFFSET]) continue;

        /// 记录位置信息（行号)
        Q[col] = row;

        /// 修改三个方向的安全性标记
        S[row] = false;
        L[col - row + OFFSET] = false;
        R[col + row] = false;

        /// 递归尝试放下一列
        Try(col + 1);

        /// 回溯：恢复三个方向原有安全性
        S[row] = true;
        L[col - row + OFFSET] = true;
        R[col + row] = true;
    }

}

int main() {
    Num = 0;
    for (int i = 0; i < 9; i++)  S[i] = true;
    for (int i = 0; i < 17; i++) L[i] = R[i] = true;

    Try(1);     /// 从第1列开始放皇后

    return 0;
}

枚举+递归解法（不回溯）

#include <iostream>
using namespace std;

int Num;        // 方案数

struct place_state {
    int Q[9];           // 8个皇后所占用的行号
    bool S[9];          // S[1]~S[8]，当前行是否安全
    bool L[17];         // L[2]~L[16]，(i-j)对角线是否安全
    bool R[17];         // R[2]~R[16]，(i+j)对角线是否安全
};

const int OFFSET = 9;   // 调整一三象限对角线数组的下标范围

void Try(int col, place_state state) {

    /// 递归中止条件：所有列均已放上皇后了
    if (col == 9) {
        Num++;

        cout << "方案" << Num << "：";
        for (int k = 1; k <= 8; k++) cout << state.Q[k] << " ";
        cout << endl;

        return;
    }
    /// 依次尝试当前列的 8 行位置
        /// 依次尝试当前列的 8 行位置
    for (int row = 1; row <= 8; row++) {
        /// 判断拟放置皇后的位置是否安全
        if (!state.S[row] ||
            !state.R[col + row] || !state.L[col - row + OFFSET]) continue;

        /// 记录位置信息（行号）
        place_state next_state = state;
        next_state.Q[col] = row;

        /// 修改三个方向的安全性标记
        next_state.S[row] = false;
        next_state.L[col - row + OFFSET] = false;
        next_state.R[col + row] = false;

        /// 从下一列开始放置剩余皇后：递归【同性质问题】
        Try(col + 1, next_state); /// next_state可视为问题的初始设置
    }
}

int main() {
    place_state state;
    for (int i = 0; i < 9; i++)  state.S[i] = true;
    for (int i = 0; i < 17; i++) state.L[i] = state.R[i] = true;

    Try(1,state);     /// 从第1列开始放皇后

    return 0;
}

9.动态规划

实例9

问题1：
编写一个程序，在一个给定的数字串中插入 K 个乘号，使总的乘积最大。

#include <iostream>
#include <iomanip>
using namespace std;

const int s = 3215125; /// 示例数据
int D[7][7] = {0};     /// 大小与示例数据有关

void InitD()
{
    D[0][6] = s;
    int s1 = 1000000;
    for (int i = 1; i <= 6; i++)
    {
        D[i][6] = D[i - 1][6] % s1;
        s1 = s1 / 10;
    }

    for (int i = 0; i <= 6; i++)
        for (int j = 5; j >= i; j--)
            D[i][j] = D[i][j + 1] / 10;
}

int Q[7][7][3] = {0}; /// 大小与示例数据有关

int P(int left, int right, int k)
{
    if (k == 0)
        return D[left][right];
    int max = 0;
    if (Q[left][right][k] == 0)
    {
        for (int i = left; i <= right - k; i++)
        {
            int x = D[left][i] * P(i + 1, right, k - 1);
            if (x > Q[left][right][k])
                max = x;
        }
        Q[left][right][k] = max;
    }
    return Q[left][right][k];
}

int main()
{
    InitD();
    cout << P(0, 6, 3) << endl;
    return 0;
}

问题2：
某公司购买长钢条，将它切割为若干短钢条后再出售。下表是公司制定的不同长度钢条价格表。假定切割工序是没有成本支出的，希望给出最佳的切割方案。
（给定一段长为 $n$ 的钢条和一个价格表 $p(i), i = 1, 2, 3, ..., n$ ，求切割钢条的最佳方案，使得销售收益 $r(n)$ 最大。）

方法一：枚举+递归算法

#include <iostream>
using namespace std;

const int p[] = {0, 1, 5, 8, 9, 10, 17, 17, 20, 24, 30}; /// 价格表示例
int r[11] = {0};                                         /// 示例数据最长为10

int cut(int n)
{
    if (n == 0)
        return 0;
    if (r[n])
        return r[n];
    int max = 0;
    for (int i = 1; i <= n; i++)
    {
        int val = p[i] + cut(n - i);
        if (val > max)
            max = val;
    }
    return r[n] = max;
}

int main()
{
    cout << cut(7) << endl; /// 7为测试示例长度
    return 0;
}

方法二：枚举+递推算法

#include <iostream>
using namespace std;

const int p[] = {0, 1, 5, 8, 9, 10, 17, 17, 20, 24, 30};
int r[11] = {0}; /// 示例数据最长为10

int cut(int n)
{
    for (int j = 1; j <= n; j++)
    {
        int max = 0;
        for (int i = 1; i <= j; i++)
        {
            int val = r[j - i] + p[i];
            if (val > max)
                max = val;
        }
        r[j] = max; // 长度j的最佳方案
    }
    return r[n]; /// 从1递推到n求出的结果
}

int main()
{
    cout << cut(7) << endl;
    return 0;
}

问题3：
P是出发点，从P到A，求最短路径。要求：只能向上或向右前进。

G 3 D 1 B 2 A
1   2   2   3
K 3 H 4 E 5 C
4   1   2   4
N 2 L 1 I 4 F
2   2   3   4
P 3 O 2 M 3 J

采用递推求解

#include <iostream>
using namespace std;

int min(int a, int b)
{
    if (a <= b)
        return a;
    else
        return b;
}

int main()
{
    const int h[4][3] = {{3, 2, 3}, {2, 1, 4}, {3, 4, 5}, {3, 1, 2}}; // 水平方向上的道路距离
    const int v[3][4] = {{2, 2, 3, 4}, {4, 1, 2, 4}, {1, 2, 2, 3}};   // 垂直方向上的道路距离
    int p[4][4] = {{0}};

    for (int j = 1; j < 4; j++) // 纵轴上的点
        p[0][j] = p[0][j - 1] + h[0][j - 1];
    for (int i = 1; i < 4; i++) // 横轴上的点
        p[i][0] = p[i - 1][0] + v[i - 1][0];
    for (int i = 1; i < 4; i++) // 内部的点
        for (int j = 1; j < 4; j++)
            p[i][j] = min((p[i - 1][j] + v[i - 1][j]),
                          (p[i][j - 1] + h[i][j - 1]));

    cout << "from P to A is " << p[3][3] << endl;
    // 输出每个路口对P点的最小距离
    for (int i = 3; i >= 0; i--)
    {
        for (int j = 0; j <= 3; j++)
            cout << p[i][j] << ' ';
        cout << endl;
    }
    return 0;
}

11-6
问题4：
给定n个矩阵的序列（矩阵链） $A_1, A_2, ..., A_n$ ，其中矩阵 $A_i$ 的大小为 $P_{i-1} \times P_i$ ，
在计算它们的乘积 $A1A2...An$ 时，可以用括号来明确计算次序。因为矩阵运算满足结合律，所以任何一种加括号的方法都能得到相同的计算结果。然而，不同的加括号方法，对乘积运算的代价（标量乘法的次数）所产生的影响却是不同的。
请编程求解最优的加括号方案，使得通过添加括号明确计算次序后，矩阵链乘法所需的标量乘法次数最少。
注意：因为要求有明确的计算次序，所以各个矩阵乘法运算都要求有括号。

采用递推求解，递推输出

#include <iostream>
using namespace std;

int p[100] = {30, 35, 15, 5, 10, 20, 25};
int n = 6; /// 矩阵数量, n<100
/// 最小代价为m[i][j]，最佳分割点s[i][j]保存最优值m[i][j]对应的分割点
int m[100][100], s[100][100];

void matrix_chain()
{
    for (int i = 1; i <= n; i++)
        m[i][i] = 0;
    /// 子矩阵链从短到长逐步增长，递推求解最优计算代价
    for (int len = 2; len <= n; len++)
    { /// len是矩阵链的长度
        for (int i = 1; i <= n - len + 1; i++)
        {
            int j = i + len - 1; /// 满足子矩阵链长度为len要求

            m[i][j] = 100000; /// 初始值
            for (int k = i; k < j; k++)
            {
                int q = m[i][k] + m[k + 1][j] + p[i - 1] * p[k] * p[j];
                if (q < m[i][j])
                {
                    m[i][j] = q;
                    s[i][j] = k; /// 保存最佳分割点 k
                }
            }
        }
    }
}

/// 递归输出括号方案
void print_optimal_parens(int i, int j)
{
    if (i == j) /// 若只有一个矩阵，则不加括号，直接显示
        cout << 'A' << i;
    else
    {
        cout << '(';                          /// 若有多个矩阵，则需要加括号
        print_optimal_parens(i, s[i][j]);     /// i..k
        print_optimal_parens(s[i][j] + 1, j); /// k+1..j
        cout << ')';
    }
}

int main()
{
    matrix_chain();
    print_optimal_parens(1, 6); /// A1 A2 ... A6
    cout << endl;

    return 0;
}

10.多步决策

实例10

问题1：
目标：将东岸的3人3鬼通过一只小船安全转移到西岸，希望摆渡次数尽可能少。
任务：编写程序，求出一种渡河方案。
条件：
船的容量有限，一次最多只能坐2人（或2鬼或1人1鬼）。
无论是在河的东岸还是在河的西岸，一旦鬼数多于人数，则人将被鬼吃掉。
怎样渡河的大权掌握在人的手中。

#include <iostream>
#include <iomanip>
using namespace std;

// 定义描述渡河状态东岸人数与鬼数的结构类型。R: 状态中的人数, G: 状态中的鬼数
struct state
{
    int R, G;
};

state s[20];     // 结构数组：记录渡河时的状态转移过程
int d[20] = {0}; // 整数数组：记录状态转移过程决策号（1-5），元素设初值0，表示“决策待定”
int k;           // 当前状态号，从1开始编号

// 摆渡策略(数组)
state op[6] = {{0, 0}, // 不使用0下标元素，设置为全零。
               {2, 0},
               {1, 0},
               {1, 1},
               {0, 1},
               {0, 2}}; // 摆渡策略从下标1开始

// 渡河状态转移函数
void transfer_state()
{
    k = 1;      // 当前状态编号，1表示初始状态
    s[1].R = 3; // 初始状态时东岸有3人
    s[1].G = 3; // 初始状态时东岸有3鬼
    int fx;     // 摆渡方向，-1为东向西，1为西向东

    do
    {
        if (k % 2 == 1)
            fx = -1; // 若k为奇数，表明是从东岸到西岸摆渡
        else
            fx = 1; // 若k为偶数，表明是从西岸到东岸摆渡
        int i;      // 决策号
        /// 从当前状态出发，依次尝试所有状态转移决策（决策号从1到5）
        for (i = d[k] + 1; i <= 5; i++)
        {                                  // 试探采用哪个决策能安全地从状态k出发到下一状态
            int u = s[k].R + fx * op[i].R; // 按第i号策略走1步之后，东岸的人数
            int v = s[k].G + fx * op[i].G; // 按第i号策略走1步之后，东岸的鬼数

            if (u > 3 || v > 3 || u < 0 || v < 0)
                continue;                               //(1) 越界，舍弃当前决策
            bool AQ = (u == 3) || (u == 0) || (u == v); // 判断是否安全
            if (!AQ)
                continue; //(2) 不安全，舍弃当前决策

            bool CHF = false; // 判断选用当前摆渡策略后到达的“新状态”是否重复？
            // 查历史信息（倒序），只应考虑摆渡方向一致的状态（状态号间隔为2）
            for (int j = k - 1; j >= 1; j -= 2) // (u, v)对应状态s[k+1]
                if (s[j].R == u && s[j].G == v)
                    CHF = true; // 若人鬼数一致，则是重复状态
            if (CHF)
                continue; //(3) 重复，则舍弃当前决策i，继续(continue)尝试下一决策

            d[k] = i; // 记录从当前状态k转移到下一状态k+1所选择的摆渡决策号
            k++;      // 按策略渡河，状态号加1（变更为下一状态了）
            s[k].R = u;
            s[k].G = v;

            break; // 已找到一个决策，跳出(break)FOR循环，**暂停**尝试其他策略
        }

        if (i > 5)
            d[k--] = 0; // 决策都失败了，改当前状态为未决策，退回前一状态
    } while (!(s[k].R == 0 && s[k].G == 0)); // 目标是东岸既无人又无鬼
}

void display()
{
    for (int i = 1; i <= k; i++)
        cout << setw(2) << i
             << ": (" << s[i].R << "," << s[i].G << ")"        /// 状态内容
             << " choice = " << d[i]                           /// 决策号
             << " {" << op[d[i]].R << "," << op[d[i]].G << "}" /// 决策内容
             << endl;
}

int main()
{
    transfer_state();
    display();
    return 0;
}

在上一问基础上，我们进一步优化程序，求出所有的渡河方案，没有多余的重复步骤。

#include <iostream>
using namespace std;

struct position
{
    int x, y;
};

// 不同决策对应的状态坐标变化
position dxy[] = {{1, 1}, {0, 1}, {2, 0}, {1, 0}, {0, 2}};

// 起始状态，结束状态
position start_pos = {3, 3}, goal_pos = {0, 0};

// 决策序列的记录
position path[100];
int num; // 总的方案数

/// 记录出现次数，防止重复!!!
int pos_cnt[2][4][4] = {{{0}}};

bool IsEq(position pos1, position pos2)
{
    return (pos1.x == pos2.x) && (pos1.y == pos2.y);
}

bool IsDone(position pos)
{
    return IsEq(pos, goal_pos);
}

bool IsValid(position pos, int step)
{
    bool v, s, r;
    int dir = step % 2; /// 0: from left to right; 1: from right to left

    /// 1. 合法性检查
    v = (pos.x >= 0) && (pos.x <= 3) && (pos.y >= 0) && (pos.y <= 3);

    /// 2. 安全性检查
    s = (pos.x == pos.y || pos.x == 0 || pos.x == 3); /// 根据游戏规则推导出来

    /// 3. 重复性检查
    r = pos_cnt[dir][pos.x][pos.y] == 0; /// 根据算法特点推导出来的

    return v && s && r;
}

void SetCount(position pos, int step, int cnt)
{
    int dir = step % 2; /// 0: from East to West; 1: from West to East
    pos_cnt[dir][pos.x][pos.y] = cnt;
}

position GetNewPos(position pos, int k, int step)
{
    int dir = (step % 2 == 0) ? -1 : 1; /// 次序决定方向，方向决定加减 !!!
    /// 通过引入方向变量，使下面的新坐标计算公式成为通用的，对两个方向均适用【代数思维】
    position next_pos = {pos.x + dir * dxy[k].x, pos.y + dir * dxy[k].y};
    return next_pos;
}

void LogStep(position pos, int step)
{
    path[step] = pos;
}

void OutStep(position pos)
{
    cout << "(" << pos.x << ", " << pos.y << ") ";
}

void OutAll(int step)
{
    for (int i = 0; i <= step; i++)
        OutStep(path[i]);
    cout << endl;
}

void Jump(position pos, int step)
{
    if (IsDone(pos))
    {          // 是否到达目标？
        num++; // 方案数加1
        cout << num << ": ";
        OutAll(step); // 输出方案
        return;
    }

    // 遍历N种方案
    for (int k = 0; k < sizeof(dxy) / sizeof(dxy[0]); k++)
    {
        position next_pos = GetNewPos(pos, k, step);
        if (!IsValid(next_pos, step + 1))
            continue; // next_pos是否可行？

        SetCount(next_pos, step + 1, 1); // 设置次数!!!
        LogStep(next_pos, step + 1);     // 记录方案
        Jump(next_pos, step + 1);        // 走下一步
        SetCount(next_pos, step + 1, 0); // 清除次数!!!（回溯）
    }
}

int main()
{
    num = 0;                   // 初始方案数置0
    SetCount(start_pos, 0, 1); // 起点，第0步，第1次（到达）
    LogStep(start_pos, 0);     // 记录起点
    Jump(start_pos, 0);        // 从起点出发，走第0步
    return 0;
}

笔记

#程序设计

程序设计基础笔记

http://imtdof.github.io/2024/10/31/程序设计基础笔记/

作者

UncleBob

发布于

2024年10月31日

许可协议

大学物理（2）笔记-电磁学上一篇

ODE笔记-一阶ODE 下一篇