问题描述

在一个路口设置一个探测器，通过通信线路连接到计算机。

• 路口每通过一辆汽车，探测器向计算机发出一个车辆信号，
• 探测器每隔单位时间发出一个时钟信号，
• 观测结束向计算机发出结束信号。

问题求解：

• 接收探测器发出的信号，
• 统计出观测的时长、
• 在观测时长内通过的车辆总数、以及两辆车之间最大的时间间隔。
• 最后输出结果

抽象模型

通常，我们遇到的现实世界中的问题都是采用自然语言描述的。当问题比较复杂时，其语义就会比较模糊。因此，我们需要采用数学语言来为之建立抽象模型，明确问题的确切含义。

典型的问题求解方式：

• 问题 \(\Rightarrow\) 抽象模型 \(\Rightarrow\) 模型中求解 \(\Rightarrow\) 对解的解释（问题的解）
  • 当问题模型很简单时，比如：\(y=f(x)\)，就可以直接得到解。
  • 当问题比较复杂时，我们可以试图采用迭代的方式用小问题的解来构造大问题的解：\(S_{i+1}=f(S_{i}), i=0, 1, ...\)

如何表示问题中的各种信号？

• 一种方法：
  
  • v表示车辆信号
  • t表示时间信号
  • e表示结束信号
• 这样就是一串v、t、e，比如：
  
  • vvtttvvvtvtvtttvvvvvtvtvtvtve。
• 也可以分别用0、1、#来表示车辆、时间、结束信号，这样就可以用一串01并以#结束来表示观测过程
  
  • 00101001010101001010#。

问题和模型之间的对应关系

• 接收探测器发出的信号
  
  • 问题中：观测到的一连串信号，\(\Rightarrow\) 模型中：由0和1构成并以#结束的符号串
• 统计出观测的时长
  
  • 问题中：观测时长，\(\Rightarrow\) 模型中：符号串中 ’1‘ 的个数
• 在观测时长内通过的车辆总数
  
  • 问题中：观测到的车辆数，\(\Rightarrow\) 模型中：符号串中 ’0‘ 的个数
• 两辆车之间的时间间隔
  • 问题中：两辆车之间的时间间隔，\(\Rightarrow\) 模型中：两个'0'中间连续 ’1‘ 的个数

进一步思考

其实就是问题描述中的一些不明确的东西，需要明确一下，或者作出一些合理的假设。

1. 如何计算间距？这里有一个语义问题需要解决：
   
   • 如果没有车，这个间距怎么计算？
     
     • 1111111#
   • 如果只有一辆车，这个间距怎么计算？
     
     • 1111101#
   • 假设：没有车辆经过的全部时间理解为车辆之间的时间间隔是合理的。
2. 还有：输入数据是一次性读取，如何保存？还是读一个信号处理一个？为什么要这样？
   
   • 如果一个数据读入后只需要使用一次，就不应该保存在计算机中。学会读取一个字符处理一个字符。整个解题思路是迭代过程。
   • 当前面读取的数据以后还会用到，此时，就需要保存起来。

问题的模型

基于以上分析，如果我们用0、1、#来表示车辆、时间、结束信号，则问题的模型就是

• 一连串的0和1，并以#结束
  
  • 一次具体的观测：00101001010101001010#
  • 任意一次观测：\(a_1a_2...a_{n-1}a_n\)，其中\(a_i=0,1,\#\) 

这个串可短可长。所以，我们需要采用迭代方式来求解了。

• 用串的长度表示问题的大小，长串由短串添加一个个信号构成。
  
  • \(P_i\) 表示问题 \(a_1a_2...a_{i-1}a_i\)
  • \(P_{i+1}\) 表示问题 \(a_1a_2...a_{i}a_{i+1}\)

模型中求解

为了在模型中求解，我们需要知道大问题的解和小问题的解之间的关系。

• \(S_i\)表示\(P_i:a_1a_2...a_{i-1}a_i\)的解，
• \(S_{i+1}\)表示\(P_{i+1}:a_1a_2...a_{i}a_{i+1}\)的解。

数学上：\(S_{i+1}\)和\(S_i\)之间是什么关系？关键因素是末尾添加的字符\(a_{i+1}\).

1. 问题的解\(S_i\)中包含哪些东西？
   • 问题的解应该包括：观测时长、车辆数量、车辆之间最大间隔。
     • \(duration_i, vehicles_i, longestInterval_i\)
   • 还有，随着问题变大，末尾的信号可能会产生更大的间隔，所以需要暂时保留一个末尾的间隔
     
     • \(tailInterval_i\)
2. \(S_{i+1}\)和\(S_i\)之间的关系。取决于末尾添加的信号是什么？注意：以下\(=\)可不是C语言中的赋值号，而是纯粹数学意义上的相等！
   • 当\(a_{i+1}='0'\)时，即检测到车辆，此时车辆数会增加、但是观测时长不变。另外，新的车辆使得原先末尾的间隔结束，开始新的间隔，即新的间隔应该为0，而最长间隔不变。所以：
     
     • \(duration_{i+1} = duration_i\)
     • \(vehicles_{i+1} = vehicles_{i}+1\)
     • \(tailInterval_{i+1}=0\)
     • \(longestInterval_{i+1}=longestInterval_i\)
   • 当\(a_{i+1}='1'\)时，即检测到时间信号，此时观测时长会增加、但是车辆数不变。另外，新的时间信号使得原先末尾的间隔会变长，同时最长间隔也可能会变长。所以：
     
     • \(duration_{i+1} = duration_i+1\)
     • \(vehicles_{i+1}= vehicles_{i}\)
     • \(tailInterval_{i+1}=tailInterval_{i}+1\)
     • \(longestInterval_{i+1}=\max\{longestInterval_i, tailInterval_{i+1}\}\)
   • 当\(a_{i+1}='\#'\)时，即检测到结束信号，此时所有观测值均不变，且\(S_i\)即为最终解。所以：
     
     • \(duration_{i+1} = duration_i\)
     • \(vehicles_{i+1}= vehicles_{i}\)
     • \(tailInterval_{i+1}=tailInterval_{i}\)
     • \(longestInterval_{i+1}=longestInterval_i\)
3. 最小问题的解呢？即迭代的初始状态是什么？
   • 最小问题即空串。那么所有的观测值均应为0
     • \(duration_0=0\)
     • \(vehicles_0=0\)
     • \(tailInterval_0=0\)
     • \(longestInterval_0=0\)
   • 这个其实就是循环结构之前的初始化。或者说初始化的本质是大小为0的问题的解。

NS图

经过以上分析，问题求解的基本步骤就是：初始问题的解、以迭代方式更新解、输出解。

我们采用自顶向下逐步求精的方法，一层层向下展开细节，从而给出问题求解的NS图。这里只给出最终最底层的NS图，但是从图中所用线条粗细可以看出层次结构。

勘误：上图中step2.2.2应位于迭代框内。因为画图排版太麻烦了，就不重画了。

算法的伪代码描述

• 数学模型中的问题求解，只是列出问题的解和子问题的解之间的关系式，一种静态关系。
• 而实际求解的算法则是：从大小为 \(i\) 的问题的解出发，经过动态Action（通常是赋值语句）更新状态来完成计算，找出大小为 \(i+1\) 的问题的解；通过不断迭代方式，使得\(i\)从\(0\)一直到\(n\)为止，即可获得最终解。 

算法的说明：

1. 算法中一些观测量：用\(duration\)表示观测时长，用\(vehicles\)表示车辆数，用\(longestInterval\)表示最长间隔，用\(tailInterval\)表示末尾的间隔。
2. 算法采用迭代方式求解，利用问题\(P_i\)的解\(S_i\)来求问题\(P_{i+1}\)的解\(S_{i+1}\)。初始问题\(P_0\)的解为\(S_0\)。

伪代码算法：

1. 初始问题\(P_0\)的解\(S_0\)：\(duration，vehicles，longestInterval，tailInterval\)置0；
2. 读取下一个信号（字符），用\(signal\)表示；
3. 如果\(signal\)是\(\#\)，则转向第9步；
4. 如果\(signal\)是\(0\)，则转向第5步，否则（即为1）转向第7步；
5. 即检测到车辆：
   1. 车辆数\(vehicles\)加一，
   2. \(tailInterval\)置0；
6. 转到第2步；
7. 即检测到时间信号：
   1. 观测时长\(duration\)加一，
   2. \(tailInterval\)加一，
   3. 将\(longestInterval\)设置为\(longestInterval\)和\(tailInterval\)的最大值；
8. 转到第2步；
9. 打印输出：\(duration，vehicles，longestInterval\)；
10. 结束。 

编码

基于上述算法，伪代码/流程图，可以着手编码工作。

•  代码级的设计包括：变量名命名、变量类型设计、状态变量设计
  • 变量名命名采用英文单词，以及camel命名方式；
  • 读入的信号用signal变量存放，类型为char；
  • 三个观测量命名为duration，vehicles，longestInterval，
  • 临时变量tailInterval表示末尾间隔长度。
  • 我们假设这些数量值均位于int的表示范围中，因此，这些变量的类型均为int。
• 完整的C语言代码
  • https://onlinegdb.com/KZrbylLpx

#include <stdio.h>

int main()
{
    char signal;
    int duration, vehicles, longestInterval, tailInterval;

    // Initialization, solution for P0: empty srting
    duration = 0;
    vehicles = 0;
    longestInterval = 0;
    tailInterval = 0;

    // iteration for next solution
    scanf("%c", &signal);
    while (signal != '#')
    {
        if (signal == '0')
        {
            // in case of a vehicle observed
            vehicles++;
            tailInterval = 0;
        }
        else
        {
            // in case of time signal observed
            duration++;
            tailInterval++;
            if (tailInterval > longestInterval)
            {
                longestInterval = tailInterval;
            }
        }
        scanf("%c", &signal);
    }

    // print out the solution
    printf("Observation duration: %d\n", duration);
    printf("Number of vehicles observed: %d\n", vehicles);
    printf("Longest interval between vehicles: %d\n", longestInterval);

    return 0;
}

测试用例

• 语义定义
  • 特殊串的语义如何定义
  • 主要是间隔的定义
• 边界测试
  • 长度为0（除了最后一个#）
    • #
    • 0，0，0
  • 全1
    • 1111111111#
    • 10，0，10
  • 全0
    • 0000000000#
    • 0，10，0
  • 一个0
  • 一个1
  • 两个0之间一串1
  • 两个1之间一串0
  • 0和1交替的串
  • 有两串1，长度一样
  • 有两串1，前长后短，或者前短后长
  • 随意

总结

• 这是一个典型的采用迭代方式解题的全过程，需要强调的是其中的各种设计技术。
  • 问题描述
    • 分析与假设
  • 数学建模
  • 模型中求解
  • 迭代算法：伪代码、流程图、程序代码
  • 测试用例

进一步讨论

• 如果车辆之间的间隔必须是两辆车之间的间隔，该如何处理？
  • 考虑一下人是如何处理这种情况的？需要一个状态变量，即前面检测到车辆了没有？把思路细化就可以得到计算机的算法了。希望大家能自己完成这一改变。
• 问题、建模、求解过程中，一切都是按正常逻辑展开的。但是，在程序实现以及实际部署运行中，就有可能出现各种意外。比如，输入中可能出现非法字符。因此，我们需要修改条件分支中的else子句为else if以处理当signal==‘1’的情况，避免非法字符被当作‘1’，因为这样会得到错误的结果。更新后的代码为：
  • https://onlinegdb.com/WGhhfs9I2 
  • 这样，当输入中出现非法字符时，程序会退出运行，并返回1。

You have no rights to post comments