[数据结构与算法]Ad Hoc类问题求解案例

Ad Hoc类问题

前言：在程序设计竞赛的试题中，有这样一类试题，解题不能套用现成的算法，也没有模式化的求解方法，而是需要编程者自己设计算法来解答试题，这类试题被称作Ad Hoc类试题，也被称为杂题.

• 一方面，Ad Hoc类试题能够比较综合地反映编程者的智慧、知识基础和创造性思维的能力；
• 另一方面，求解Ad Hoc类试题的自创的算法只针对某个问题本身，探索该问题的独有性质，是一种专为解决某个特定的问题或完成某项特定的任务而设计的算法，因此Ad Hoc类试题的求解算法一般不具备普适意义和可推广性。

求解Ad Hoc类问题的方法多样，但按照数理分析和思维方式的角度，大致可分两大类：

1. 机理分析法：采用顺向思维方式，从分析内部机理出发，顺推出求解算法
2. 统计分析法：采用逆向思维方式，从分析部分解出发，倒推出求解算法

机理分析法实验范例

Factstone Benchmark

试题来源：Waterloo local 2005.09.24

题目描述：

Amtel宣布，到2010年，它将开发出128位处理器的计算机；到2020年，它将开发出256位计算机；以此类推，Amtel实行每十年就将芯片字长长度翻一番的战略。（在此前，Amtel于2000年开发了64位计算机；在1990年，开发了32位计算机；在1980年，开发了16位计算机；在1970年，开发了8位计算机；并首先在1960年开发了4位计算机。）
Amtel使用新的标准检查等级——Factstone——来宣传其新处理器的大大提高的能力。 Factstone等级被定义为这样的最大整数n，使得n！可以表示为一个计算机的字的无符号整数（比如1960年的4位计算机可表示3！=6，而不能表示4！=24）。

输入：

输入给出若干测试用例。每个测试用例一行，给出年份y。在最后一个测
试用例后，在最后一行给出0。

输出：

对于每个测试用例，输出一行，给出Factstone等级。

示例：

Sample Input

1960
1981
0

Sample Output

3
8

题解分析：

采用顺向思维方式去分析题目，给定一个年份 => 求解出处理器的字大小 k位=> 计算出最大的n使得n!成为一个符合字的大小$2^k?1$的无符号整数，即：
$$n!<2^k?1$$
假定当年位 Y 年，则其处理器的字的位数为 $K=2^{2+?(Y?1960)/10?}$,得到K位二进制数的最大的无符号整数是$2^K?1$，则求n的方法有两种：

1. 直接求取，但是方法及其容易溢出且速度慢
2. 采用对数计算：${\log }_{2}n!={\log }_{2}n+{\log }_2(n?1)+...+{\log }_{2}1\le K$来计算n。显然，方法2效率高一些。

算法实现：计算Y年字的位数K，累加${\log }_{2}i$，直到数字超过K为止，此时i-1即位Factstone等级。

#include<iostream>
#include<bits/stdc++.h>
#include<cmath>
using namespace std;
int main()
{
    float Y;
    while(1){
        cin>>Y;
        if(Y == 0) break;
        unsigned long long K = pow(2,2+(unsigned long long)((Y-1960)/10));
        double i = 1;
        double n = log2(i);
        while(n <= K){
            n += log2(++i);
        }
        cout<<i-1<<endl;
    }
    getchar();
    return 0;
}

统计分析法实验范例

当我们在一时得不到事物特征机理的情况下，我们可以先通过手算或者编程等方法测试得到一些数据，即问题的部分解，再利用数理统计知识对数据进行处理，从而得到最终的数学模型。

Ants

试题来源：Waterloo local 2004.09.19

题目描述：

一只蚂蚁军队在长度为l厘米的横竿上走，每只蚂蚁的速度恒定，1cm/s。当一只行走的蚂蚁到达横杆终点的时候，它就立即掉了下去；当两只蚂蚁相遇的时候，他们就调转头，并开始往相反的方向走。我们知道蚂蚁在横杆上原来的位置，但是不知道蚂蚁行走的方向。请您计算所有蚂蚁从横杆上掉下去的最早可能时间和最晚可能时间。

输入：

输入的第一行给出一个整数，表示测试用例个数。每个测试用例首先给出两个整数：横竿的长度（以厘米为单位）和在横竿上的蚂蚁的数量n。接下来给出n个整数，表示每只蚂蚁在横竿上从左端测量过来的位置，没有特定的次序。所有输入数据不大于1000000，数据间用空格分隔。

输出：

对于输入的每个测试用例，输出用一个空格分隔的两个数，第一个数是所有的蚂蚁掉下横竿的最早可能的时间（如果它们的行走方向选择合适），第二个数是所有的蚂蚁掉下横竿的最晚可能的时间。

试题解析：

每只蚂蚁都有2种爬行方向，那么1000000只蚂蚁的爬行方式组合就达到了$2^{1000000}$种，这是一个天文数字，因此不可能逐个枚举蚂蚁的爬行方式。

我们先研究蚂蚁较少时的情况：

2只蚂蚁的其中一个情况：

4只蚂蚁的情况：

显然，当蚂蚁越来越多的时候，情况就越加复杂。而题解的瓶颈就是蚂蚁相遇的情况。

假如出现这种情况：蚂蚁永远不会相遇，即所有的向左走的蚂蚁都在向右走的蚂蚁的左边，那么很容易得出算法时间复杂度O(n)

让我们再看下两只蚂蚁的例子，能否假设两只蚂蚁再相遇后，忽略对方，各自继续朝着自己的方向走？如图所示：

这就相当于忽略了相遇这一事件，也就是说可以假设这些蚂蚁即使相遇了也不理采对方而是继续走着自己的路。这样，每只蚂蚁掉落所用的时间就只有两个取值：一个是向左右所用的时间，一个是向右走所用的时间。

由此得出，设
$$l_i为蚂蚁i在横杆上从左端过来测量的位置(1\le i\le n)$$
设little和big为n只蚂蚁掉下横杆的最早和最晚可能时间，则
l i t t l e = m i n 1 ≤ i ≤ n { l i , L ? l i } little = {\underset { 1\leq i \leq n} {min} }\{l_i,L-l_i\} little=1≤i≤nmin?{li?,L?li?}

b i g = m a x 1 ≤ i ≤ n { l i , L ? l i } big = {\underset { 1\leq i \leq n} {max} }\{l_i,L-l_i\} big=1≤i≤nmax?{li?,L?li?}