习题3
1． 假设在文本\中查找模式\，写出分别采用BF算法和KMP
算法的串匹配过
//BF算法
#include
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 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 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 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