Categories
不学无术 木有技术

第二章 啊哈！算法

原文见：

http://blog.csdn.net/silenough/article/details/7040028

 
A. 给定一个最多包含40亿个随机排列的32位整数的顺序文件，找出一个不在文件中的32位整数(在文件中至少缺少一个这样的数—为什么？)。在具有足够内存的情况下，如何解决该问题？如果有几个外部的“临时”文件可用，但是仅有几百字节的内村，又该如何解决该问题？
因为2^32 大于40亿，所以文件中至少缺失一个整数。我们从表示每个整数的32位的视角来考虑二分搜索，算法的第一趟（最多）读取40亿个输入整数，并把起始位为0的整数写入一个顺序文件，把起始位为1的整数写入另一个顺序文件。这两个文件中，有一个文件最多包含20亿个整数，接下来将该文件用作当前输入并重复探测过程，但这次探测的是第二个位。如果原始的输入文件包含n个元素，那么第一趟将读取n个整数，第二趟最多读取n/2个整数，第三趟最多读取n/4个整数，依次类推，所以总的运行时间正比于n。
如果内存足够，采用位图技术，通过排序文件并扫描，也能够找到缺失的整数，但是这样做会导致运行时间正比于nlog(n).
1. 考虑查找给定输入单词的所有变位词的问题。仅给定单词和字典的情况下，如何解决该问题？如果有一些时间和空间可以在响应任何查询之前预先处理字典，又会如何？
首先计算给定单词的标识，若果不允许预处理，那么久只能顺序读取整个文件，计算每个单词的标识，并于给定单词的标识进行比较。
 

  1. //压缩一个单词，形成其标识,设定单词中相同字母不会超过99个
  2. void compress(char * pWord, int len, char * pFlag)
  3. {
  4.     sort(pWord, pWord+len); //对单词进行排序
  5.     int i = 0;
  6.     int nCount;            //计数重复字母的个数
  7.     char chCount[3];       //存放整数到字符的转换值，整数最大为99
  8.     while (*pWord != ‘’)
  9.     {
  10.         char chTemp = *pWord;
  11.         char *pTemp = pWord + 1;
  12.         nCount = 1;
  14.         while (true)
  15.         {
  16.             if (chTemp == *pTemp++)
  17.             {
  18.                 ++nCount;
  19.             }
  20.             else
  21.             {
  22.                 *(pFlag + i++) = *pWord;
  23.             //  ++i;
  24.                 memset(chCount, ‘’, 3);
  25.                 _itoa(nCount, chCount, 10);
  26.                 if (nCount >= 10)
  27.                 {
  28.                     *(pFlag + i++) = *(chCount + 0);
  29.                 //  i++;
  30.                     *(pFlag + i++) = *(chCount + 1);
  31.                 //  ++i;
  32.                 }
  33.                 else
  34.                 {
  35.                     *(pFlag + i++) = *(chCount + 0);
  36.                 //  ++i;
  37.                 }
  38.                 pWord = pWord + nCount;
  39.                 break;
  40.             }
  41.         }
  42.     }
  43. }

如果允许进行预处理，我们可以在一个预先计算好的结构中执行二分查找，该结构中包含按标识排序的(标识，单词)对。
2. 给定包含4300 000 000 个32位整数的顺序文件，如何找出一个出现至少两次的整数？
 方法一：
二分搜索通过递归搜索包含半数以上整数的子区间来查找至少出现两次的单词。因为4300000000  > 2^32，所以必定存在重复的整数，搜索范围从[0, 2^32）开始，中间值mid为2^31，若区间[0, 2^31)内的整数个数大于2^31个，则调整搜索区间为[0, 2^31)，反之则调整搜索区间为[2^31， 2^32)，然后再对整个文件再遍历一遍，直到得到最后的结果。这样一共会有log2(n)次的搜索，每次遍历n个整数（每次都是完全遍历），总体的复杂度为o(nlog2(n))。
 

  1. #include <iostream>
  2. using namespace std;
  4. int pow2(int n)   //求2的n次幂
  5. {
  6.     int i;
  7.     int r = 1;
  8.     for (i = 0; i < n; i++)
  9.     {
  10.         r *=2;
  11.     }
  12.     return r;
  13. }
  16. int _tmain(int argc, _TCHAR* argv[])
  17. {
  18.     int arr[] = {4,2,5,1,6,3,8,0,7,6,11,12,14,9,15,10,13};
  19.     int len = sizeof(arr) / sizeof(int);
  21.     int nCount = 0;
  22.     int bit = 4;
  23.     int low = 0;
  24.     int high = pow2(bit);
  25.     int mid = (low +high) / 2;
  26.     int i;
  28.     while (low <= high )
  29.     {
  30.         mid = (low + high) / 2;  //取中间值
  31.         nCount = 0;
  33.         for (i = 0; i < len; i++)    //计数[low, mid）范围内整数的个数
  34.         {
  35.             if (arr[i] < mid && arr[i] >= low)
  36.             {
  37.                 ++nCount;
  38.             }
  39.         }  //end for
  41.         if (nCount == 0)     //若nCount为0，则mid即为重复的整数
  42.         {
  43.             cout << mid<<endl;
  44.             break;
  45.         }
  46.         else
  47.         {
  48.             if (nCount > (mid – low))  //若大于mid与low的差值,
  49.             {                          //表明重复的整数落在区间[low, mid）
  50.                 high = mid;        //缩小区间
  51.             }
  52.             else
  53.             {
  54.                 low = mid;
  55.             }  //end if
  56.         } //end if （） else（）
  57.     }  //end while
  58. }

 
   方法二：
 

  1. #include <iostream>
  2. #include <algorithm>
  3. using namespace std;
  5. int _tmain(int argc, _TCHAR* argv[])
  6. {
  7.     int arr[] = {4,2,5,1,7,3,8,0,7,6,11,12,14,9,15,10,13};
  8.     int len = sizeof(arr) / sizeof(int);
  10.     sort(arr, arr + len);   //先进行排序
  11.     int i;
  12.     int increase = arr[0];
  13.     for (i = 0; i < len; i++)
  14.     {
  15.         if (arr[i] > (i + increase))
  16.         {
  17.             increase += (arr[i] – i – increase);
  18.             continue;
  19.         }
  21.         if (arr[i] < (i + increase))
  22.         {
  23.             cout << arr[i] << endl;
  24.             break;
  25.         }
  26.     }
  27. }

3. 前面涉及了两个需要精巧代码来实现的向量旋转算法，将其分别作为独立的程序实现。在每个程序中，i和n的最大公约数如何实现？
采用辗转相除法求两个整数的最大公约数。
 

  1. int gcd(int a, int b)
  2. {
  3.     int temp;
  4.     if (a < b)  //使a始终为最大数
  5.     {
  6.         temp = a;
  7.         a = b;
  8.         b = temp;
  9.     }
  11.     while (b != 0)
  12.     {
  13.         temp = a % b;
  14.         a = b;
  15.         b = temp;
  16.     }
  17.     return a;
  18. }

 
 
方法一：海豚算法
 

  1. void Shifting(char * pArry, int rotdistance, int len)
  2. {
  3.     int i, j;
  4.     char temp;
  5.     int igcd = gcd(rotdistance, len);
  6.     for (i = 0; i < igcd; i++)
  7.     {
  8.         temp = pArry[i];
  9.         j = i;
  10.         for (; 😉
  11.         {
  12.             int k = j + rotdistance;
  13.             k %= len;
  14.             if ( k == i)
  15.             {
  16.                 break;
  17.             }
  18.             pArry[j] = pArry[k];
  19.             j = k;
  20.         }
  21.         pArry[j] = temp;
  22.     }
  23. }

方法二：块交换算法
 

  1. #include <iostream>
  2. using namespace std;
  4. //交换pArry[a…a+m-1]和pArry[b…b+m-1]
  5. void myswap(char *pArry, int a, int b, int m)
  6. {
  7.     char temp;
  8.     for (int i = 0; i < m; i++)
  9.     {
  10.         temp = pArry[a + i];
  11.         pArry[a + i] = pArry[b + i];
  12.         pArry[b + i] = temp;
  13.     }
  15. }
  17. void Shifting(char * pArry, int rotdistance, int len)
  18. {
  19.     if (rotdistance == 0 || rotdistance == len)
  20.     {
  21.         return;
  22.     }
  24.     int i, j, p;
  25.     i = p = rotdistance;
  26.     j = len – p;
  28.     while (i != j)
  29.     {
  30.         if (i > j)
  31.         {
  32.             myswap(pArry, p – i, p, j);
  33.             i -= j;
  34.         }
  35.         else
  36.         {
  37.             myswap(pArry, p – i, p + j – i, i);
  38.             j -= i;
  39.         }
  40.     }
  41.     myswap(pArry, p – i, p, i);
  42. }
  44. int _tmain(int argc, _TCHAR* argv[])
  45. {
  46.     char arry[] = “abcdefghijklmn”;
  47.     int len = strlen(arry);
  48.     Shifting(arry, 10, len);
  49.     return 0;
  50. }

方法三：求逆算法
根据矩阵的转置理论，对于矩阵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
 

  1. #include <iostream>
  2. using namespace std;
  4. //对字符串中第i个字符到第j个字符进行反转，i、j>=1
  5. void MyReverse(char * pArry, int i, int j)
  6. {
  7.     int front = i;
  8.     int tail = j;
  9.     char temp;
  10.     while (front != tail && front < tail)
  11.     {
  12.         temp = pArry[front – 1];
  13.         pArry[front – 1] = pArry[tail – 1];
  14.         pArry[tail – 1] = temp;
  15.         ++front;
  16.         –tail;
  17.     }
  18. }
  20. //将字符串左旋转rotdistance个字符
  21. void Shifting(char * pArry, int rotdistance, int len)
  22. {
  23.     if (rotdistance == 0 || rotdistance == len)
  24.     {
  25.         return;
  26.     }
  27.     MyReverse(pArry, 1, rotdistance);
  28.     MyReverse(pArry, rotdistance + 1, len);
  29.     MyReverse(pArry, 1, len);
  30. }
  32. int _tmain(int argc, _TCHAR* argv[])
  33. {
  34.     char arry[] = “abcdefgh”;
  35.     int len = strlen(arry);
  36.     Shifting(arry, 5, len);
  37.     cout << arry << endl;
  38.     return 0;
  39. }

 
5. 向量旋转函数将向量ab变为ba。如何将向量abc变成cba？(这个交换非相邻内存块的问题进行了建模)
可以将bc看做一个整体，然后运用向量旋转算法，得到bca。然后对bc运用向量旋转算法，得到cb。最后变换后的向量为即cba.
 

  1. //交换pArry[a…a+m-1]和pArry[b…b+m-1]
  2. void myswap(char *pArry, int a, int b, int m)
  3. {
  4.     char temp;
  5.     for (int i = 0; i < m; i++)
  6.     {
  7.         temp = pArry[a + i];
  8.         pArry[a + i] = pArry[b + i];
  9.         pArry[b + i] = temp;
  10.     }
  12. }

 
 

  1. //对向量pArry中起始于ibegainPos位置的irotdistance-ibegainPos个元素
  2. //与起始于ibegainPos+irotdistance位置到位置iendPos之前的元素进行交换
  3. void SuccessiveSwap(char * pArry, int ibegainPos, int irotdistance, int iendPos)
  4. {
  5.     int i, j;
  6.     i = irotdistance – ibegainPos;
  7.     j = iendPos – irotdistance;
  9.     while (i != j)
  10.     {
  11.         if (i > j)
  12.         {
  13.             myswap(pArry, irotdistance – i, irotdistance, j);
  14.             i -= j;
  15.         }
  16.         else
  17.         {
  18.             myswap(pArry, irotdistance – i, irotdistance + j – i, i);
  19.             j -= i;
  20.         }
  21.     }
  22.     myswap(pArry, irotdistance – i, irotdistance, i);
  23. }

6. 如何实现一个以名字的按键编码为参数，并返回所有可能的匹配名字的函数
用按键编码标识每一个名字，并根据标识排序，然后顺序读取排序后的文件并输出具有不同名字的相同标识。为了检索出给定按钮编码的名字，可以使用一种包含编码标识和其他数据的结构。然后对该结构排序，使用二分搜索查询按键编码。
7. 转置一个存储在磁带上的4000×4000的矩阵(每条记录的格式相同，为数十个字节)。如何将运行的时间减少到半个小时？
给每条记录插入列号和行号，然后调用系统的磁带排序程序先按列排序再按行排序，最后使用另一个程序删除列号和行号。
8. 给定一个n元实数集合、一个实数t和一个整数k，如何快速确定是否存在一个k元子集，其元素之和不超过t？
对n元实数集合先进行排序，然后计算前k个元素的和既可以确定是否存在这样一个子集。若采用快速排序，时间复杂度为nlog10(n)。
9. 顺序搜素和二分搜索代表了搜索时间和预处理时间之间的折中。处理一个n元表格时，需要执行多少次二分搜索才能弥补对表进行排序所消耗的预处理时间？
对于顺序搜索，搜索k次的时间复杂度为O(kn);若采用二分搜索则需要先排序，则二分搜索的时间复杂度为O(nlog10(n)+log2(n))
变位词程序的实现
 

  1. //对从文件中读入的每个单词调用qsort库函数排序，输出到新的文件中
  2. void mysign(FILE * pFile1, FILE * pFile2)
  3. {
  4.     char word[20];
  5.     char sig[20];
  7.     pFile1 = fopen(“..file1.txt”, “r”);
  8.     if ( NULL == pFile1)
  9.     {
  10.         cout << “Open file1 error!” << endl;
  11.         return ;
  12.     }
  14.     pFile2 = fopen(“..file2.txt”, “w”);
  15.     if (NULL == pFile2)
  16.     {
  17.         cout << “Open file2 error!” << endl;
  18.         return ;
  19.     }
  20.     while (!feof(pFile1))
  21.     {
  22.         memset(word, ‘’, 20);
  23.         memset(sig, ‘’, 20);
  24.         fscanf(pFile1, “%s”, word);
  25.         strncpy(sig, word, strlen(word));
  26.         qsort(sig, strlen(sig), sizeof(char), charcomp);
  27.         fprintf(pFile2, “%s   %sn”, sig, word);
  28.     }
  29.     fclose(pFile1);
  30.     fclose(pFile2);
  31. }


 
 
使用sort程序将具有相同标识的单词归拢到一起，形成一个新的文件。最后调用squash()函数将具有相同变位词的单词在同一行输出。
 

  1. //将具有相同变位词的单词在同一行输出
  2. void squash()
  3. {
  4.     FILE * pFile3 = fopen(“..file3.txt”, “r”);
  5.     if ( NULL == pFile3)
  6.     {
  7.         cout << “Open file3 error!” << endl;
  8.         return ;
  9.     }
  11.     FILE * pFile4 = fopen(“..file4.txt”, “w”);
  12.     if (NULL == pFile4)
  13.     {
  14.         cout << “Open file4 error!” << endl;
  15.     }
  17.     char word[20];
  18.     char sig[20];
  19.     char oldsig[20];
  20.     int linenum = 0;
  21.     memset(oldsig, ‘’, 20);
  22.     while (!feof(pFile3))
  23.     {
  24.         memset(word, ‘’, 20);
  25.         memset(sig, ‘’, 20);
  26.         fscanf(pFile3, “%s %s”, sig, word);
  28.         if (strncmp(sig, oldsig, strlen(sig)) != 0 )
  29.         {
  30.             fprintf(pFile4, “n”);
  31.         }
  32.         strncpy(oldsig, sig, strlen(sig));
  33.         fprintf(pFile4, “%s “, word);
  34.     }
  35.     fclose(pFile3);
  36.     fclose(pFile4);
  37. }

Leave a Reply

Your email address will not be published. Required fields are marked *

This site uses Akismet to reduce spam. Learn how your comment data is processed.