第二章习题

• 2.6.1 考虑查找给定输入单词的所有变位词问题。仅给定单词和字典的情况下，如何解决该问题？如果有一些时间和空间可以在响应任何查询之前预处理字典，又会如何？

• 2.6.2 给定包含4 300 000 000 个32位整数的顺序文件，如何找出一个出现至少两次的整数？

  思考：仿照查找缺失一个的二分查找，每次取二分之后的数据多的一端。

• 2.6.3 前面涉及了两个需要精巧代码来实现的向量旋转算法。将其分别作为独立的程序实现。在每个程序中，i 和 n 的最大公约数如何出现?

  • 杂技算法：

#include <stdio.h>
#include <string.h>

char *reverse(char str[], int r, int n);
int gcd(int i, int j);

int main(void)
{
    char str[] = "abcdefgh";
    int rotdist = 3;
    int len = strlen(str);
    
    char *res = reverse(str, rotdist, len);
    printf("Reverse Results:%s\n", res);
    return 0;
}

// ”杂技“算法旋转向量
char *reverse(char str[], int rotdist, int n)
{
    int gcd_num = gcd(rotdist,n);
    int j,k;
    char t;
    for(int i=0; i<gcd_num; i++){
        t = str[i];
        j = i;
        while(1){
            k = j + rotdist;
            if (k >= n)
                k -= n;
            if (k == i)
                break;
            str[j] = str[k];
            j = k;
            
        str[j] = t;
        }
    }
    return str;
}

// ”更相减损术“求最大公约数
int gcd(int i, int j)
{
    while(i != j){
        if(i > j)
            i -= j;
        else
            j -= i;
    }
    return i;
    
}

• 求逆算法

#include<stdio.h>
#include<string.h>

char* reverse(char str[], int start, int end);

int main(void)

{

    char str[]="abcdefgh";
    printf("Row String:%s \n",str);
    int rotdist = 3;
    int len = strlen(str);
    char* res = reverse(str, 0, rotdist -1);
    res = reverse(res, rotdist, len-1);
    res = reverse(res, 0, len-1);
    printf("Results:%s \n",res);

    return 0;
}
 
 char* reverse(char str[], int start, int end)
 {
     char tmp;
     while(start < end){
         tmp = str[start];
         str[start] = str[end];
         str[end] = tmp;
         
         start++;
         end--;
     }
     return str;
 }

• 20世纪70年代末期，贝尔实验室开发出了“用户操作的电话号码簿辅助程序”，该程序允许雇员使用彼岸准的按键电话在公司号码簿中查找电话号码。要查找该系统设计者的名字Mike Lesk，可以按“LESK*M*”(也就是5375*6*)，随后，系统会输出他的电话号码。这样的服务现在随处可见。该系统中出现的一个问题是，不同的名字可能具有相同的按键编码。在Lesk的系统中发生这种情况时，系统会询问用户更多的信息。给定一个大的名字文件（例如标准的大城市电话号码簿），如何定位这些“错误匹配”呢？（当Lesk在这种规模的电话号码簿上做实验时，他发现错误匹配发生的概率仅仅是0.2%）。如何实现一个以名字的按键编码为参数，并返回所有可能的匹配名字的函数？