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 用固态的书写笔,如铅笔:) 赏 Wechat Pay Alipay 两栈实现队列 [Reprinting] C++ Files and Streams