算法设计与分析（第2版） 王红梅 胡明 习题答案

习题3

1． 假设在文本\中查找模式\，写出分别采用BF算法和KMP

算法的串匹配过

//BF算法

#include using namespace std;

int BF(char S[], char T[]) {

int index = 0; int i = 0, j = 0; while ((S[i] != '\\0') && (T[j] != '\\0')) {

if (S[i] == T[j]) { i++; j++; } else { ++index; i = index; j = 0; } }

if (T[j] == '\\0') return index + 1; else return 0; }

int main() { char s1[19]=\

char s2[7]=\

cout<< BF( s1, s2) <

//KMP算法

#include using namespace std;

void GetNext(char T[ ], int next[ ]) //求模式T的next值 {

int i, j, len; next[0] = -1;

for (j = 1; T[j]!='\\0'; j++) //依次求next[j] {

for (len = j - 1; len >= 1; len--) //相等子串的最大长度为j-1 { for (i = 0; i < len; i++) //依次比较T[0]~T[len-1]与T[j-len]~T[j-1] if (T[i] != T[j-len+i]) break; if (i == len) { next[j] = len; break; } }//for if (len < 1)

next[j] = 0; //其他情况，无相等子串 }//for }

int KMP(char S[ ], char T[ ]) //求T在S中的序号 {

int i = 0, j = 0;

int next[80]; //假定模式最长为80个字符 GetNext(T, next);

while (S[i] != '\\0' && T[j] != '\\0') {

if (S[i] == T[j]) {

i++; j++; }

else { j = next[j]; if (j == -1) {i++; j++;}

} }

if (T[j] == '\\0') return (i - strlen(T) +1); //返回本趟匹配的开始位置 else return 0; }

int main() { char s1[]=\ char s2[]=\

cout<

return 0; }

2.分式化简。设计算法，将一个给定的真分数化简为最简分数形式。例如，将6/8化简为3/4。

#include using namespace std;

int main() {

int n;//分子 int m;//分母

int factor;//最大公因子 int factor1;

cout<<\输入一个真分数的分子与分母： \ cin>>n>>m;

int r = m % n;//因为是真分数 所以分母一定大于分子 factor1=m; factor=n; while (r != 0) {

factor1 =factor; factor = r;

r = factor1% factor; }

cout<<\输出该真分数的最简分数： \return 0; }

3. 设计算法，判断一个大整数能否被11整除。可以通过以下方法：将该数的十进制表示

从右端开始，每两位一组构成一个整数，然后将这些数相加，判断其和能否被11整除。例如，将562843748分割成5,62,84,37,48，然后判断(5+62+84+37+48)能否被11整除 //将一个大整数看成一个数组

//数组的奇数位对应数的10倍加上数组偶数对应数的本身 //验证结果能否被11整除

#include using namespace std;

int main() { int a[9]={5,6,2,8,4,3,7,4,8}; int result=0; //result为题目要求的各位之和 for(int i=0;i!=9;++i) { if(i%2==0) result+=a[i]; //i 为偶数位时，结果加上其对应数组数的本身 else result+=a[i]*10; //i 为奇数位时，结果加上对应数组数的10倍 } if(result==0) cout<<\该整数能被11整除\ else

cout<<\该整数不能被11整除\ return 0; }

4. 数字游戏。把数字 1,2,?,9这9个数字填入以下含有加、减、乘、除的四则运算式中，使得该等式成立。要求9个数字均出现一次且仅出现一次，且数字1不能出现在乘和除的一位数中（即排除运算式中一位数为1的平凡情形）。

??×?＋???÷?－?? = 0