编程珠玑——第一章习题解答

    今天看了《编程珠玑》的第一章，通过参考前辈的和自己编程，实现了“磁盘文件排序”的两种方法，现在记录下该章的课后习题，希望通过这个过程，可以让自己有所长进。

第一题  
    如果不缺内存，如何使用一个具有库的语言来实现一种排序算法以表示和排序集合？
解答：
    首先，C++有实现排序的库函数：sort，该函数实现的是快速排序；另外，C++的容器map和set均可以实现排序，由于map和set的实现是红黑树，所以具有自动排序功能，当然，这个需要数据不能重复；
    下面为了复习下快速排序的实现，重新实现了一遍，代码如下所示。

int Partition(int *array, int left, int right)
{
    int priot = array[left];    //浠ョ?涓?涓?厓绱犱綔涓轰富鍏?
    int first = left;
    int last = right;
    while(first < last)
    {
        while(first < last && array[last] >= priot)
        {
            last--;
        }
        Swap(&array[first], &array[last]);
        while(first < last && array[first] <= priot)
        {
            first++;
        }
        Swap(&array[first], &array[last]);
    }
    return first;
}

void QuickSort(int *array, int first, int last)
{
    if(array == NULL)
    {
        return;
    }
    if(first < last)
    {
        int priot = Partition(array, first, last);
        QuickSort(array, first, priot - 1);
        QuickSort(array, priot + 1, last);
    }

第二题
    如何使用位逻辑（例如与、或、移位）来实现位向量？
解答：
    代码如下所示。

//如何使用位逻辑运算(例如与、或、移位)来实现位向量
/* Copyright (C) 1999 Lucent Technologies */
/* From 'Programming Pearls' by Jon Bentley */

/* bitsort.c -- bitmap sort from Column 1
* Sort distinct integers in the range [0..N-1]
* 排序在0到N-1范围内的无重复整数
*/

#include <stdio.h>

#define BITSTEPWORD 32     //表示一个整型含有32个位
#define SHIFT  5        //单次位移量
#define MASK 0x1F        //掩码
#define NUM  10000000    //表示1000万个整数
int array[1 + NUM / BITSTEPWORD];//使用整型数组模拟定义1000万个位的数组

/*功能：设置位数组中的从0开始的第i位为1
 *参数：需要设置为1的位
 */
void set(int i)
{
    array[i >> SHIFT] |= (1 << (i & MASK));
}

/*
 *功能：设置位数组中的从0开始的第i位为0
 *参数：需要设置为0的位
 */
void clr(int i)
{
    array[i >> SHIFT] &= ~(1 << (i & MASK));
}
 /*
  *功能：取出从0开始的第i位的值，用于检测
  */
void test(int i)
{
    return array[i >> SHIFT] & (i << (i & MASK));
}

int main(void)
{
    int i;
    clear();
    for( i = 0; i < 100; i++ )
        set( i*2 );
    for( i = 0; i < 200; i++ )
        printf("%d",test(i) ? 1:0 );
    puts("");
    return 0;
}

    实现方法说明：
    i >> SHIFT：将i向右移动5位，相当于将i除以32位。因为一个int是32位，所以结果表示i在第几个int数组成员中；
    举例说明：如果i是34，则结果是1，也就是从0开始的第1个int数组成员。
    1 << (i & MASK)：使用掩码留下i的低5位再左移动1位，相当于除以32所得的余数再左移动1位。因为第一是0，所以结果都需要左移动1位。结果中1所在的位表示i在该int数组成员的第几位上。
    接着上例继续说明，如果i是34，则i & MASK是2，二进制表示是10，再向左移动1位，得到100，也就反映出此时从0开始的第2位是1。
    
第四题
    如何生成小于n且没有重复的k个整数的问题。最简单的方法是、就是使用前k个正整数。这个极端的数据集合将不明显的改变位图方法的运行时间，但是可能会歪曲系统排序的运行时间。如何生成位于0至n-1之间的k个不同的随机顺序的随机整数？
解答：
    实现方法一，代码如下所示。

//方法一
int array[n + 1];
void make_data(int n)
{
    if(n <= 0)
    {
        return;
    }
    for(int i = 0; i < n; i++)
    {
        array[i] = i + 1;
    }

    for(int i = 0; i < n; i++)
    {
        int ii = (rand() * RAND_MAX + rand()) % n;
        int jj = (rand() * RAND_MAX + rand()) % n;
        swap(array[ii], array[jj]);
    }
}

    实现方法二，代码如下所示。

/* Copyright (C) 1999 Lucent Technologies */
/* From 'Programming Pearls' by Jon Bentley */

/* bitsortgen.c -- gen $1 distinct integers from U[0,$2) */

#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#define MAXN 2000000
int x[MAXN];

int randint(int a, int b)
{    return a + (RAND_MAX * rand() + rand()) % (b + 1 - a);
}

int main(int argc, char *argv[])
{
    int i, k, n, t, p;
    srand((unsigned) time(NULL));
    k = atoi(argv[1]);
    n = atoi(argv[2]);
    for (i = 0; i < n; i++)
        x[i] = i;
    for (i = 0; i < k; i++)
    {
        p = randint(i, n-1);
        t = x[p];
        x[p] = x[i];
        x[i] = t;
        printf("%dn", x[i]);
    }
    return 0;
}

    上述两种方法没有什么本质的不同，都是生成n个正整数，然后对其位置进行随机的交换。

第五题
    那个程序员说他又1MB的可用存储空间，但是我们概要描述的代码需要1.25MB的空间。他可用不费力气的索取到额外的空间。如果1MB空间是严格的边界，你会推荐如何处理呢？
解答：
    可用多路归并排序进行解决。
    例如：我们可以将输入文件分成两个部分，第一部分保存[1,5000000]之间的数，第二个文件保存[5000001,10000000]的数字，然后分别进行排序，所用的内存就可以降到1MB以内。如果把文件分为k份（每份都保存一定区间的数），那么就可以再O(n)的时间内，n/k的空间内完成排序。

第六题
    如果那个程序员说的不是每个整数最多出现一次，而是每个整数最多出现10次，你又如何建议他呢？你的解决方案如何随着可用存储空间总量的变化而变化呢？
解答：
    如果每个整数最多出现10次，那么我们可以用4位（半个字节）来统计每个整数的出现次数。可以利用问题5中的方法，利用10000000/2个字节的空间遍历一次来完成对整个文件的排序。当保存的数字量变化时，分成更多的份，就可以再更小的空间内完成，如10000000/2k的空间内。

第8题
    当那个程序员解决该问题的时候，美国所有的免费电话的区号是800。现在免费电话的区号包括800、877和888，而且还在增多。如何在1MB空间内完成对所有这些免费电话的号码的排序？如何将免费电话号码存储在一个集合中，要求可以实现非常快速的查找以判定一个给定的免费电话号码是否可用或者已经存在？
解答：
    这个问题没有给出答案，网上有的答案是这样的：每个区号建立一个set，查找的时候效率是O(logn)。
    我想的是进行排序的时候，可以把800、877和899的区号分别提取出来，然后分别进行排序，最后在归并到一个结果文件中。
    不知道有没有更好的办法。

第九题
    使用更多的空间来换取更少的运行时间存在一个问题：初始化空间本身需要消耗大量的时间。说明如何设计一种技术，在第一次访问向量的项时将其初始化为0。你的方案应该使用常量时间进行初始化和向量访问，使用的额外空间应正比于向量的大小。因为该方法通过进一步增加空间减少初始化的时间，所以仅在空间很廉价、时间很宝贵且向量很稀疏的情况下才考虑。
解答：
    解决的方法是使用两个额外的向量：from和to，还有一个变量top。如果对i位置进行初始化，进行以下步骤：
    from[i] = top;
    to[top] = i;
    data[i] = 0;
    top++;
    from[i] = top的目的是将i在to中的索引放入from中；
    to[top] = i意思是这个top位置对应的是i，这时data就可以做相应的操作，然后top右移动。
    判断一个位置是否初始化过的条件是：from[i] < top && to[from[i]] == i，from[i] < top的意思是from[i]对应的to中的位置已经被处理过了，但是from[i]可能是随机值，也会小于top，这时候就需要第二个条件了，to[from[i]] == i的意思是：to[from[i]]所指向的位置就是i，这种方式确保了i位置是否被初始化过。
    《这个我得好好的理解理解，标记一下》

第十题
    在成本低廉的隔日送达时代之前，商店允许顾客通过电话订购商品，并在几天后上门自取。商店数据库使用客户的电话号码作为其检索的主关键字（客户知道他们的电话号码，并且这些关键字几乎都是唯一的）。你如何组织商店的数据库，以允许高效的插入和检索操作？
解答：
    根据电话号码的最后两位作为客户的哈希索引，进行分类，当顾客打电话下订单的时候，它被放置在一个合适的位置。然后当顾客抵达进行检索商品时，营业员按顺序检索订单，这是经典的解决哈希冲突的解决方法：通过顺序检索。电话号码的最后两位数字是相当随机的，而电话号码的前两位作为索引行不通，因为很多电话号码的前两位是相同的。

第十一题
    飞鸽传书+网络传输（还有打印机），囧啊

第十二题
    载人航天需要在外太空的极端环境下实现书写。民间盛传美国国家航天局花费100万美元研发了一种特殊的钢笔来解决这个问题。那么前苏联如何解决这个问题的？
解答：
     According to the urban legend, the Soviets solved their problem with a pencil（铅笔）, of course. For background on the true story, learn about the Fisher Space Pen company. The company was founded in 1948, and its writing instruments have been used by the Russian Space Agency, underwater explorers, and Himalayan climbing expeditions.
    擦，用铅笔。


    参考：
    
    
    
    感谢！！