一、三个问题
1、给定一个最多包含40亿个随机排列的32位整数的顺序文件，找出一个不在文件中的32位整数。分别考虑在有足够内存或有几个外部临时文件可用，但仅有几百字节的内存的情况下，如果解决问题；
2、将一个n元一维向量向左旋转i个位置，例如，当n=8且i=3时，向量abcdefgh旋转为defghabc；
3、给定一个英语字典，找出其中的所有变位词集合。例如，“pots”、“stop”、“tops”互为变位词，因为每个单词都可通过改变其他单词中字母的顺序来得到。
二、问题解决
1、对于第一个问题，如果内存足够，则可以采用第（1）节中的位图技术，使用536870912个8位字节形成位图来表示已看到的整数，然而，若仅有几百字节，则考虑使用二分搜索技术来解决。为了采用二分搜索技术，必须定义一个范围、在该范围内表示元素的方式以及用来确定哪一半范围存在缺失整数的探测方法。
我们采用已知包含至少一个缺失元素的一系列整数作为范围，并使用包含所有这些整数在内的文件表示这个范围。通过统计中间点之上和之下的元素来探测范围：或者上面或者下面的范围具有之多全部范围的一半元素。由于整个范围中有一个缺失元素，因此我们所需的那一半范围中必然也包含缺失的元素。这些就是解决问题的二分搜索算法所需的主要思想。
2、对于第二个问题，我们将问题看做是把数组ab转换成ba，同事假定我们拥有一个函数可以将数组中特定部分的元素求逆。从ab开始，首先对a求逆，得到a'b，然后对b求逆，得到a‘b’，最后整体求逆，得到（a‘b’）‘，此时就恰好是ba了。具体做法如下面代码所示：
reverse(0,i-1); //cbadefgh reverse(i,n-1); //cbahgfed reverse(0,n-1); //defghabc
3、对于第三个问题，可以通过标识字典中的每一个词，使得在相同变位词类中的单词具有相同的标识。然后将所有具有相同标识的单词集中在一起。这将原始的变位词问题简化为两个问题：选择标识和集中具有相同标识的单词。
对于标识。当使用等价关系来定义类时，定义一种标识使得类中的每一项都具有相同的标识，而该类以外的其他项则没有该标识。可使用一个计数来代表重复的次数，例如（1）mississippi可以写成i4m1p2s4或者1省略就是i4mp2s4，也可（2）使用一个包含26个整数的数组来表示每个字母出现的次数。
以下是变位词程序的实现：
int charcmp(char *a,char *b)
{
return *a - *b;
}
#define WORDMAX 100
int main(void)
{ char word[WORDMAX],sign[WORDMAX];
while(scanf(%s,word) != EOF)
{ strcpy(sign,word);
qsort(sign,strlen(sign),sizeof(char),charcmp); //排序单词内的字符
printf("%s %s\n",word,sign);
}
return 0;
}
//输出相同签名的 变位词 到单行squash
int main()
{ char word[WORDMAX],sign[WORDMAX],oldsign[WORDMAX];
int linenum = 0;
while(scanf("%s %s",word,sign) != EOF)
{ oldsign = sign;
if(strcmp(sign,oldsign) != 0 && linenum > 0) //判断是否sig与oldsig（其上一次的值）不同
printf("\n");
strcpy(oldsign,sign);
linenum++;
printf("%s ",word);
}
printf("\n");
return 0;
}
sign < dictionary | sort | squash > gramlist