一．
40亿个随机排列的32位整数的顺序文件，找出一个不在文件中的32位整数。在具有足够内存的情况下，如何解决？如果有几个外部的“临时”文件可用，但是仅有几百个字节的内存，又该如何解决？
1内存足够大就可以采取第一章中所介绍的Bitmap结构进行存储，然后遍历就可找到不存在的32位整数。
2 我们把文件中的32位整数看成二进制的表示，然后在内存允许的范围内读取数据，按照下图进行探测，把数据分成两类分别存入文件1和文件2。然后读入其他部分的数据按照同样地方法进行划分存入文件1文件2，经过第一次处理32位的二进制数据开头为0的全部存到了文件1，开头为1的全部存入了文件2.。
多次读取一共读入了40亿个数据，文件1和文件2中肯定有至少一个文件的数据个数小于等于20亿个，假设这个文件是文件1。由于整个文件中有不存在的32位整数，那么在文件1中肯定能找到至少一个不存在的数据。（如果文件1数据的个数等于文件2数据的个数，那么文件1和文件2都能找到不存在的32位数据，如果文件1的数据个数小于文件2的数据个数，那么在文件1中肯定能找到不存在的32位数据）。
下一次就把文件1作为读入数据进行同样地划分，不断地进行同样的探测就会找到不存在的32 位数据。
二．
将一个n元一维向量向左旋转i个位置。例如，当n=8且i=3时，向量abcdefg旋转为defgabc，能否使用数十个额外字节的存储空间，在正比于n的时间内完成向量的旋转。
1 常规思路首先将向量的前i个元素复制到一个临时数组中，然后将余下的n-i个元素向左移动i个位置，然后将最初的i个元素从临时数组中复制到x中余下的位置。但是这种方法使用i个额外的位置，产生了巨大的空间消耗。
2.首先将x[0]保存在temp中，然后将x[i]移动到x[0] x[2i]移动到x[i], x[3i]移动到x[2i]（每次下标+i，不一定是二倍），以此类推如果x的下标大于n了就把下标转换成x%n，继续循环。直到所有的元素都被移动过。
#include <stdio.h>
const int n = 10;
const int r = 3;
int x[n] ={1,2,3,4,5,6,7,8,9,10};
int gcd(int a, int b)
{
return !b ? a : gcd(b, a%b);
}
int main()
{
for(int i = 0; i < gcd(n, r); i++)
{
int temp = x[i];
int j = i;
while(1)
{
int k = j + r;
if(k >= n) k -= n;
if(k == i) break;
x[j] = x[k];
j = k;
}
x[j] = temp;
}
printf("将一维向量1 2 3 4 5 6 7 8 9 10 左移3个位置后为\n");
for(int i = 0; i < n; i++) printf("%d ", x[i]);
printf("\n");
return 0;
}
3.旋转向量 x 其实就是交换向量 ab 的两段，得到向量 ba ，这里 a 代表 x 的前 i 个元素， b 代表后边的元素。假设 a 比 b 短，将 b 分为 b1 ， b2 ；其中 b2 与 a 的元素个数相同。交换 a 和 b2 ， (a)(b1)(b2) 向量即变为了 (b2)(b1)(a) ，此时 a 已经到了最终的位置。前边的 (b2)(b1) 又构成了相同的结构，相同的方法继续交换，递归调用最后成功左移 i 个位置。
#include <stdio.h>
const int n = 10;
const int r = 3;
int x[n] ={1,2,3,4,5,6,7,8,9,10};
void swap(int *a, int *b, int s)
{
int temp;
while(s--)
{
temp = *a;
*a = *b;
*b = temp;
a++, b++;
}
}
void rot(int *base, int m, int n)
{
if(0 == (m %= n)) return;
n -= m;
if(m < n)
{
swap(base, base+n, m);
rot(base, m, n);
}
else if(m > n)
{
swap(base, base+m, n);
rot(base+n, m-n, m);
}
else
{
swap(base, base+m, m);
}
}
int main()
{
rot(x, r, n);
printf("将一维向量1 2 3 4 5 6 7 8 9 10 左移3个位置后为\n");
for(int i = 0; i < n; i++)
{
printf("%d ", x[i]);
}
printf("\n");
return 0;
}
4
利用手的翻转，一张图清晰描述这个最简洁的算法，原理就是这个公式(arbr)r=ba。
Reverse(0, i-1); cbadefgh
Reverse(i, n-1); cbahgfed
Reverse(0, n-1); defghabc
#include <stdio.h>
const int n = 10;
const int r = 3;
int x[n] ={1,2,3,4,5,6,7,8,9,10};
void reverse(int a[], int start, int end)
{
while(start < end)
{
int temp = a[start];
a[start] = a[end];
a[end] = temp;
start++, end--;
}
}
void roca(int a[], int k, int m)
{
reverse(a, 0, k-1);
reverse(a, k, m-1);
reverse(a, 0, m-1);
}
int main()
{
roca(x, r, n);
printf("将一维向量1 2 3 4 5 6 7 8 9 10 左移3个位置后为\n");
for(int i = 0; i < n; i++)
{
printf("%d ", x[i]);
}
printf("\n");
return 0;
}
三.
在一个词典中找出所有的变位词，例如 pots stop tops互为变位词，因为一个单词可以通过改变其他单词中字母的顺序得到其他单词。
1 暴力方法，一个单词全排列，然后对每一个排列遍历词典。
2 我们可以把首先遇到的单词，进行排序。例如pans排序后变为anps，我们现在就把anps作为单词pans的标记，然后当在遇到snap，也将anps标记为anps。也就是将所有只以字母a n p s组成的单词都标记为anps。遇到的其他单词也已相同的方法进行标记。然后再对所有的标记进行排序，就可以肯容易得到一组变位词。具体方法请看图
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define MAX 100 // 假设单词长度不超过100
#define maxNum 20000
typedef struct T
{
char word[MAX];
char sig[MAX];
}T;
T t[maxNum];
char oldsig[MAX];
int flag = 0;
int cmp(const void *a, const void *b)
{
return *(char *)a - *(char *)b;
}
int cmp1(const void *a, const void *b)
{
return strcmp( (*(T *)a).sig, (*(T *)b).sig );
}
int main()
{
freopen("dict.txt", "r", stdin);
int i = 0;
while(scanf("%s", t[i].word) != EOF)
{
strcpy(t[i].sig, t[i].word);
qsort(t[i].sig, strlen(t[i].sig), sizeof(char), cmp);
i++;
}
int sum = i;
qsort(t, sum, sizeof(t[0]), cmp1);
strcpy(oldsig, " ");
for(int j = 0; j < sum; j++)
{
if(strcmp(oldsig, t[j].sig) != 0 && flag > 0) printf("\n");
strcpy(oldsig, t[j].sig);
flag++;
printf("%s ", t[j].word);
}
printf("\n");
return 0;
}
习题选解
1 如果允许提前处理那就进行二分查找，节省时间。
2 模仿寻找缺失整数的算法。
5 (arbrcr)r = cba
7 给每个元素按行列加上标号，然后先按列排序，再按行排序