本文主要是介绍编程珠玑——第二章习题，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
1、考虑查找给定输入单词的所有变位词的问题。仅给定单词和字典的情况下，如何解决该问题？如果有一些时间和空间可以在响应任何查询之前预先处理字典，又会如何？
答：现给每个单词做标记，然后给予某一规则对标记之后的单词排序（标记相同的单词相邻），最后将标记相同的单词归到某一集合（写在一行或者输出到某一个文件）。
在查找某一个单词的变位词的时候，先按相同的规则得到标记，然后根据标记的值找到某一行（或某一个文件）。
在有预处理的情况下，可以将上述算法的第一步和第二步预先处理；查询的时候只需要根据单词得到标记，查询结果就行。（相当于copy了一份字典，并将copy的字典改造成可查询变位词的格式）。
2、给定包含4 300 000 000个32位整数的顺序文件，如何找出一个出现至少两次的整数？
答：1,2,3,3,4,5....这样的可以用二分查找
3、前面涉及了两个需要精巧代码来实现的向量旋转算法。将其分别作为独立的程序实现。在每个程序中，i和n的最大公约数如何出现？
答：
方法一：海豚算法
- void Shifting(char * pArry, int rotdistance, int len)
- {
- int i, j;
- char temp;
- int igcd = gcd(rotdistance, len);
- for (i = 0; i < igcd; i++)
- {
- temp = pArry[i];
- j = i;
- for (; ;)
- {
- int k = j + rotdistance;
- k %= len;
- if ( k == i)
- {
- break;
- }
- pArry[j] = pArry[k];
- j = k;
- }
- pArry[j] = temp;
- }
- }
方法二：块交换算法
- #include <iostream>
- using namespace std;
- //交换pArry[a...a+m-1]和pArry[b...b+m-1]
- void myswap(char *pArry, int a, int b, int m)
- {
- char temp;
- for (int i = 0; i < m; i++)
- {
- temp = pArry[a + i];
- pArry[a + i] = pArry[b + i];
- pArry[b + i] = temp;
- }
- }
- void Shifting(char * pArry, int rotdistance, int len)
- {
- if (rotdistance == 0 || rotdistance == len)
- {
- return;
- }
- int i, j, p;
- i = p = rotdistance;
- j = len - p;
- while (i != j)
- {
- if (i > j)
- {
- myswap(pArry, p - i, p, j);
- i -= j;
- }
- else
- {
- myswap(pArry, p - i, p + j - i, i);
- j -= i;
- }
- }
- myswap(pArry, p - i, p, i);
- }
- int _tmain(int argc, _TCHAR* argv[])
- {
- char arry[] = "abcdefghijklmn";
- int len = strlen(arry);
- Shifting(arry, 10, len);
- return 0;
- }
方法三：求逆算法
根据矩阵的转置理论，对于矩阵AB，要得到BA，则分别求A和B的转置A', B'，然后对(A'B')转置，即(A'B')' = BA。同理，可以得到另一种一维向量向左旋转的算法。将要被旋转的向量x看做两部分ab，这里a代表x中的前rotdistance个元素。首先对a部分进行反转，再对b部分进行反转，最后对整个向量x进行反转即可。
对于字符串“abcdefgh”, rotdistance = 3, len = 8:
reverse(1, rotdistance); //cbadefgh
reverse(rotdistance+1, len); //cbahgfed
reverse(1, len); //defghabc
- #include <iostream>
- using namespace std;
- //对字符串中第i个字符到第j个字符进行反转，i、j>=1
- void MyReverse(char * pArry, int i, int j)
- {
- int front = i;
- int tail = j;
- char temp;
- while (front != tail && front < tail)
- {
- temp = pArry[front - 1];
- pArry[front - 1] = pArry[tail - 1];
- pArry[tail - 1] = temp;
- ++front;
- --tail;
- }
- }
- //将字符串左旋转rotdistance个字符
- void Shifting(char * pArry, int rotdistance, int len)
- {
- if (rotdistance == 0 || rotdistance == len)
- {
- return;
- }
- MyReverse(pArry, 1, rotdistance);
- MyReverse(pArry, rotdistance + 1, len);
- MyReverse(pArry, 1, len);
- }
- int _tmain(int argc, _TCHAR* argv[])
- {
- char arry[] = "abcdefgh";
- int len = strlen(arry);
- Shifting(arry, 5, len);
- cout << arry << endl;
- return 0;
- }
4、几位读者指出，既然所有的三个旋转算法需要的运行时间都正比于n，杂技算法那的运行速度显然是求逆算法的两倍。杂技算法对数组中的每个元素进存储和读取一次。而求逆算法需要两次。在实际的计算机上进行实验以比较两者的速度差异，特别注意内存引用位置附近的问题。
答：可以将bc看做一个整体，然后运用向量旋转算法，得到bca。然后对bc运用向量旋转算法，得到cb。最后变换后的向量为即cba.
5、向量旋转函数将向量ab变为向量ba。如何将向量abc变为cba？（这对交换非相邻内存块的问题进行了建模）
6、XXX。。。。要查询名字Mike Lesk.而已按“LESK*M*”(也就是“5375^*6*”)，随后，系统会输出他的电话号码。这样的服务随处可见。现在的问题是，不同的名字可能具有相同的按键编码。在Lesk的系统中发生这种情况时，系统会询问永和更多的信息。给定一个大的名字文件（例如标准的大城市电话号码簿），如何定位这些“错误匹配”？（当Lesk在这种规模的电话号码簿上做实验时，他发现错误匹配发生的概率仅仅是0.2%）如何实现一个以名字的按键编码为参数，并返回所有可能的匹配名字的函数？？
7、程序员需要转置一个存储在磁带上的4000*4000的矩阵（每条记录的格式相同，为数十个字节）。最初提出的程序需要运行50个小时。程序员是如何将运行时间减少到半小时的？？
8、给定一个n元师叔集合，一个实数t和一个整数k，如何快速确定是否存在一个k元子集，其元素纸盒不超过t？？
9、顺序搜索和二分搜索代表了搜索时间和预处理时间之间的折中。处理一个n元表格时，需要执行多少次二分搜索才能弥补对表进行排序所消耗的预处理时间？
10、爱迪生要求某人计算一个空灯泡壳的容积。在使用测径仪和微积分进行数小时的计算后，他给出了答案——150立方厘米。而爱迪生在几秒钟之内就计算完毕并给出了“更
接近155”。他是如何实现的？？？
这篇关于编程珠玑——第二章习题的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
