算法设计与分析习题答案1-6章

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[]=\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;