Programming Pears: Exercises of Charpter 1

gaunthan Posted on Feb 13 2017

? Programming Exercises ? ? C++ ?

## Exercise 2
如何通过使用位逻辑（如与、或、移位）来实现位向量？

----------

下面给出的代码展示了怎么实现Bitmap：
```cpp
#ifndef BITMAP_H
#define BITMAP_H

#include <cstddef>
#include <stdexcept>

class Bitmap {
public:
    typedef unsigned char Byte;

Bitmap(std::size_t bitNums)
        : bitmap_(new Byte[(bitNums >> 3) + 1]()), bitNums_(bitNums) { }
    ~Bitmap() { delete[] bitmap_; }

void set(std::size_t i) { getByteOfBit(i) |= GetBitMask(i); }
    void clear(std::size_t i) { getByteOfBit(i) &= ~GetBitMask(i); }
    bool get(std::size_t i) const { return getByteOfBit(i) & GetBitMask(i); }
private:
    std::size_t size() const { return bitNums_; }

Byte& getByteOfBit(std::size_t i)
    {
        if(i >= size()) {
            throw std::range_error("Bit position out of range.");
        }
        return bitmap_[i >> 3];
    }
    Byte getByteOfBit(std::size_t i) const { return bitmap_[i >> 3]; }

static Byte GetBitMask(std::size_t i)
    {
        return (Byte)0x80 >> (i & 0x7);
    }

private:
    Byte* bitmap_;
    std::size_t bitNums_;
};

#endif // BITMAP_H
```

## Exercise 4
如何生成位于0至n-1之间的k个不同的随机顺序的随机整数？要求程序简短且高效。

----------

```cpp
#ifndef DIFF_RANDOM_GEN_H
#define DIFF_RANDOM_GEN_H

#include <random>
#include <ctime>
#include <memory>
#include <set>
#include <algorithm>
#include <iterator>

typedef std::size_t Number;
typedef std::vector<Number> NumVector;

class DiffRandomGen {
public:
    DiffRandomGen(Number min, Number max)
        : e_(std::time(0)), u_(min, max) { }

Number operator()()
    {
        while(true) {
            Number num = u_(e_);
            if(s_.find(num) == s_.end()) { // A new one.
                s_.insert(num);
                return num;
            }
        }
    }
private:
    std::default_random_engine e_;
    std::uniform_int_distribution<Number> u_;
    std::set<Number> s_;
};

inline std::shared_ptr<NumVector> GenDiffRandomNums(Number min, Number max,
                                             std::size_t num)
{
    std::shared_ptr<NumVector> pvec(new NumVector(num));
    DiffRandomGen gen(min, max);
    std::generate_n(pvec->begin(), num, gen);
    return pvec;
}

#endif // DIFF_RANDOM_GEN_H
```

上面方法并不满足题目要求……具体解决方案见[C语言 获取随机数](http://leanote.com/blog/post/5789969dab644135ea0107e0#title-7)。

## Exercise 5
我们描述的代码需要1.25M的空间，如果1MB空间是严格的边界，你又会推荐如何处理呢？你的算法的运行时间又是多少？

----------

由于空间不足，位图不能放下所有的数据。所以得分两批：

1. 先处理0 ~ 1M -1之间的数字；
2. 再处理1M ~ 1.25M 之间的数字。

位图同样初始化为容纳范围在0 ~ 1M之间的数据。算法开始读取数据文件，若该数大于等于1M，则追加入中间文件，否则，标记到位图中。读取够1M个数据，就把位图中的数据写到输出文件，然后把中间文件的数据加载到位图。注意，由于这部分数据都大于1M，因此需要先减去1M才能标记到位图中。同样的，这部分数据写到输出文件时每个数都要加上1M的值。这部分数据的数量是1.25M - 1M，因此位图的循环只需到1.25M这个数字即可。

这种方式相比原来，多了一个临时文件的读写过程，也多了一次位图排序过程。但第二次排序过程数据量是第一次的四分之一。

还有一种方式是不使用临时文件，而是读两次数据文件。

## Exercise 6
如果不是每个整数最多出现一次，而是最多出现10次。你又如何处理？你的解决方案如何随着可用存储空间总量的变化而变化？

----------

这种情况下，使用$\lceil log_210 \rceil = 4$个位来统计整数出现次数。因此，需要稍微改变一下原先的位图向量的设计。

至于第二问，综合练习5和练习6的解决方案即可。

## Exercise 7
如何处理输入中可能存在的重复数据，并调用错误处理函数？如果输入整数小于零或大于等于n呢？或者输入不是数值呢？方式很直接：
```cpp
for each i in the input file
    if isNotNumber(i) or i < 0 or i >= n
        call error handler
    if bit[i] = 1   // 重复出现的数字
        call error handler
    bit[i] = 1 
```

实际上，由于数据文件所含记录数可能多于规定的数量，因此还应该添加一个计数器，限制读取的记录数量。

## Exercise 8
如果限制可用空间为1MB，同时添加更多待排序的数据文件呢？如何将号码存储在一个集合中，要求可以实现非常快速的查找？

----------

~~这题显然多了一个要处理的因素：多个已排序文件之间的排序。因此，题目可以转化为外存多路归并排序。关于第二问，因为数据有序，所以使用二分查找即可。~~

由于区号是加到电话号码的最前面的，因此只要区号内的号码都是有序的，则非常容易实现几个区号时间的排序。我们先对每个区号对应的文件进行排序，方法用得是习题5里面提及的方案。然后我们可以创建一个映射关系`<zoneId, fd>`，对zoneId集进行排序即可。

至于第二问，由于数据集是有序的，因此把数据读取到内存后进行二分查找即可。

## Exercise 10
如果内存空间非常充足，那使用散列表是最好的选择，因为所有操作都能在常数时间内完成。否则，可以使用平衡二叉树，其提供平均对数时间的查找、插入和删除操作。

## Exercise 11

- 因特网？
- 无人机？
- 心电感应？ :)

没想到答案竟是飞鸽传底片……

## Exercise 12
用固态的书写笔，如铅笔:)