编程珠玑 第一章 习题解答

于 2012年05月21日 发布在 算法&&ACM 跳到评论
编程珠玑虽然说给了习题的题目和答案,而且也比较详尽,但是鉴于以前看书有答案的往往看的不是太仔细,以至于很多东西都没有搞清楚,所以我决定把习题都记录下来。这样有助于我研究题目,解决问题。
第一章简单来说就介绍了个用bitmap排序的实例,从思维上给了我们思考问题的另一个角度。
1.c语言的话可以用qsort,但是感觉qsort的比较函数的定义较为复杂,还是推荐用c++中的sort。

int main(void){
    vector v;
    for( int i = 0; i < 100; i++ )
        v.push_back( rand() );
    sort( v.begin(), v.end() );
    for( int i = 0; i < 100; i++ )
        cout << v[i] << endl;
    return 0;
}


c++中的set容器也可以实现排序的功能,当元素添加到集合中后,set可以自动排序。用迭代器从头到尾遍历就可以得到排序序列。参考:http://www.cplusplus.com/reference/stl/set/

python中列表有sort方法。

list = [3,4,5,6,7]

list.sort()

2.位向量的实现就是用比特位0,1来表示一些特定信息,通常是用数组,每个int中包含32个bits,当我们定位某个位置时,先确定索引是在哪个int中,然后再确定int中的那个位对应索引。我用c语言和c++中的类实现了位向量。我不帖出来了,在github上,https://github.com/fookwood/fkcode/tree/master/bitvector,排版看起来不行= =。。。

c++中有现成的bitset,我猜实现原理应该和以上差不多。

3.位图的实现我用了三种,一个是c语言的(简称cvec),一个是c++的(简称cppvec),还有时c++现成的bitset(简称bitset)。系统排序用的是sort命令,加上-n选项。排序用了c的qsort,c++的sort和c++的set。下面是运行时间。

cvec  1.737 1.001

cppvec 1.769 1.033

bitset 2.644 1.908

系统sort命令 5.290 4.554

qsort 2.081 1.345

sort 2.802 2.066

set 5.921 5.185

输入输出的时间是0.736s。左右分别为带输入输出和不带的。

可以看出两种语言位图的实现都是效率最高的,c++中的bitset,set,sort虽然效率上差了点,但是实现上非常方便,而且能保证一定的正确性。系统的排序实在方便,一句命令就可以搞定( sort -n < in -o out ).

4.生成[0,n)的之间k个不重复的随机整数。

#include<iostream>
#include<cstdlib>
#include<algorithm>
#include<cstdio>
using namespace std;
const int N = 10000000;
const int K = 10000000;
int randint( int l, int r ){
    return rand() % ( r-l ) + l;
}
int a[ N ];
int main(void){
    for( int i = 0; i < N; i++ )
        a[i] = i;
    for( int i = 0; i < K; i++ ){
        swap( a[i], a[ randint(i,N) ] );
        printf("%d\n",a[i]);
    }
    return 0;
}

如果要想生成这样一个数组,可以直接从头到尾循环,每个数根随机位置交换值就可以。

5.可以将输入文件分成两分,第一份保存[0,5000000)的数,第二个文件保存[5000000,10000000)的数字,然后分别进行排序,所用内存就可以降到1MB以内。如果我们把文件分成k份(每份都存一定区间的数),那么就可以在n的时间,n/k的空间内完成排序。标准答案中说可以在nk时间n/k空间内完成,我对于nk的时间不太明白,把输入文件扫描,然后把数字保存到相应文件,扫一遍应该就可以了。

6.每个整数最多出现10次,那么保存每个数字信息的空间不再是1bit了,可以用4bits来保存,可以类比第五题,可以分成4份,在n/4的空间内完成。同样,当保存数字信息的量变化时,分成更多份,就可以在更小的空间内完成。

7.

数出现超过一次?

当第二次更新的时候,相应位已经是1了,这个时候提示错误。

当输入小于0或者大于等于n?

当输入数字时候对其进行范围判断,忽略或者提示错误。

不是数值?

忽略

8.题目描述中排序包含区号么。。。用一种效率稍逊的算法就是每个区号建立一个set,查找时候的效率是O(logN)的。有木有谁又更好的办法。

9.本题值得一说。

初始化空间需要大量时间,不过我们的应用只需要其中一点点空间,比如1000000的位图,我们只用到其中的10位,怎样节省时间?题目中提示,可以用额外的正比于向量大小的空间。我当时直接看的答案,到晚上搜了搜才看懂。

解决方法使用了两个额外的向量,from和to,变量top。如果对i位置进行初始化,进行一下步骤:
from[i] = top; to[top]=i;data[i] = 0;top++;
from[i]=top的目的是将i在to中的索引放入to中,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位置是否被初始化过。

10.类似于取快递,根据电话号码的最后一位或者最后两位进行分类,类似于哈希的思想,用顺序遍历来处理碰撞。不能用开头的原因是很多电话号码的前面都是一样的,比如手机号码都是以1开头的。而且最后一位的分布比较随机、均匀。

11.= =答案竟然说飞鸽传书。

12.铅笔? T.T ….

本文共有 8条评论 | 沙发:文章评论

  1. cgangee说道:

    飘过,膜拜。。。

  2. 名字说道:

    楼主啊第6题 分为四份 是根据什么来分啊 :?:

  3. 李江说道:

    第五题,每次读取时,判断读到的数字是否是本次排序范围之内的,如果是,就排序,否则就丢弃读到的这个数字,也不需要把大文件分割成小文件,不存在分割这个事情,,每趟排序都需要读取n个 数据,所以时间开销是nk,
    我大概想到的为代码:
    #define N 10000000
    #define k 5
    #define RANGE N/K
    int array[1+range/32];
    for(i=0;i<k;i++)
    {
    while(scanf("%d",&currentNum)!=EOF)
    {
    if(i*RANGE<=currentNum<=(i+1)*RANGE)
    {
    排序;
    输出到文件;
    }
    }
    }

    • 陈祖杰说道:

      你的这个思路个人感觉有点问题,遇到不在i*RANGE<=currentNum<=(i+1)*RANGE的数字丢弃不进入排序,那被丢弃的数什么时候被排序,目测应该没有第二次机会输入了吧。

  4. 匿名说道:

    第八题可以用第六题的方法,只不过是用3个bit来存信息,000代表无,001代表800, 010代表另一个,100代表另另一个,当800时 | 001,同样 其他 |010 和 100,就可以判断这个号是否存在,并且都有哪些存在.如111代表三个都有。

  5. 飞飞一世界说道:

    你好!第四题,生成[0,n)的之间k个不重复的随机整数。
    int randint( int l, int r ){
    return rand() % ( r-l ) + l;
    }
    这个代码是返回l到r-1直接的任意数字,前后都是闭区间。
    这样的话,在主函数里面如下,第二次循环的时候会不会重复呢?
    int main(void){
    for( int i = 0; i < N; i++ )
    a[i] = i;
    for( int i = 0; i < K; i++ ){
    //这里。我怎么感觉randint那个函数后面再加个1,才不会重复呢。
    swap( a[i], a[ randint(i,N) ] );
    printf("%d\n",a[i]);
    }
    return 0;
    }
    求指正,谢谢。

留下评论!

:wink: :twisted: :roll: :oops: :mrgreen: :lol: :idea: :evil: :cry: :arrow: :?: :-| :-x :-o :-P :-D :-? :) :( :!: 8-O 8)