编程珠玑 第三章 习题解答

为什么我看完这一章不知道该写啥?。。整体来看是比较基础的。

1.if-else语句的每个分支的形式都差不多,我们可以用数组来使循环简单一点。数组中每个点表明一个阶段,用level[i]表示阶段i的起始点,tax[i]表示阶段i的税率,用have [i]表示这个阶段已经有的税收,然后得到收入后二分到相应的阶段,计算税收。

2.不知所云(用递归实现应该很简单,不用数组的话代码量会比较大)。

3.这个不会,看了答案了。这个方法的精髓就是把重复出现n次的字符用 n+‘字符’来表示,重复出现的行用同样的方法可以得到。这个方法给了我很大的启示,以前没有思路的一道题目,瞬间来了灵感。
(更多…)

继续阅读 →

编程珠玑 第二章 习题解答

这一章很奇葩啊。。书中B问题在一面的时候被问到,C在笔试的时候是第一大题(当时写了好多)。

1.在给定单词和字典的情况下,遍历字典,计算每个的标签,然后与给定的单词的标签比较。可以预处理的话就好说了,将所有单词按照标签排序,然后可以用equal_range求出区间,O(logN)。

2.可以类比如何找出没有出现的整数。43 0000 0000 大于int的表示范围。可以先扫面一遍,把第一位为0的和第一位为1的放到两个不同的文件中,看哪个文件里面的数多,就开始处理这个文件,把第二位的0和1的数字放到两个文件中,看哪个的数字多,依此类推,最后肯定得到一个数,他出现了不止一次。

3.我实现了两个算法。gao函数是那个杂技算法,gaogao是块交换算法。经过简单的测试还没有发现什么问题。n和len的最大公约数就是置换的次数。

#include<iostream>
#include<string>
#include<algorithm>
using namespace std;
int gcd( int a, int b ){
return b==0?a:gcd(b, a%b);
}
int gao( int *start, int *end, int n ){
int len = end - start;
int d = gcd( n, len );
for( int i = 0; i < d; i++ ){
int t = *(start+i);
int next = i;
while( (next+n)%len != i ){
*(start+next) = *(start+(next+n)%len);
next = (next+n)%len;
}
*(start+next) = t;
}
}

(更多…)

继续阅读 →

编程珠玑 第一章 习题解答

编程珠玑虽然说给了习题的题目和答案,而且也比较详尽,但是鉴于以前看书有答案的往往看的不是太仔细,以至于很多东西都没有搞清楚,所以我决定把习题都记录下来。这样有助于我研究题目,解决问题。
第一章简单来说就介绍了个用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;
}

(更多…)

继续阅读 →