根据提供的实验报告，我们可以将其中的关键知识点归纳如下：
### 最大公约数实验
#### 欧几里得算法
**核心思想**：
欧几里得算法（也称为辗转相除法）是一种高效的求解两数最大公约数的方法。其基本原理是基于这样一个事实：两数的最大公约数等于其中较小数和两数相除余数的最大公约数。
**代码实现**：
```cpp
#include<iostream.h>
using namespace std;
int CommonFactor(int m, int n) {
int r = m % n;
while (r != 0) {
m = n;
n = r;
r = m % n;
}
return n;
}
int main() {
int a, b;
cout << "请输入两个整数：";
cin >> a >> b;
cout << a << "和" << b << "的最大公约数是：" << CommonFactor(a, b) << endl;
return 0;
}
```
#### 连续整数检测法
**核心思想**：
该方法通过从较小的整数开始，逐个检查是否能够同时整除两个数来找出最大公约数。这种方法效率较低，但易于理解。
**代码实现**：
```cpp
#include<iostream.h>
using namespace std;
int min(int a, int b) {
return (a <= b) ? a : b;
}
int gcd(int m, int n) {
int t;
for (t = min(m, n); t > 0; t--) {
if (m % t == 0 && n % t == 0)
return t;
}
}
int main() {
int a, b;
cout << "请输入两个整数：";
cin >> a >> b;
cout << a << "和" << b << "的最大公约数是：" << gcd(a, b) << endl;
return 0;
}
```
#### 分解质因数法
**核心思想**：
该方法首先将两个数分解成质因数的形式，然后找出共同的质因数并计算出它们的乘积作为最大公约数。
**代码实现**：
```cpp
#include<iostream.h>
using namespace std;
int decompose(int num, int p[]) {
int i = 2, count = 0;
while (i <= num) {
while (num % i == 0) {
p[count++] = i;
num /= i;
}
i++;
}
return count;
}
int CommonFactor(int m, int n) {
int a[100], b[100], c[100];
int la = decompose(m, a);
int lb = decompose(n, b);
int i = 0, j = 0, k = 0;
while (i < la && j < lb) {
if (a[i] == b[j]) {
c[k++] = a[i];
i++; j++;
} else if (a[i] < b[j]) {
i++;
} else {
j++;
}
}
int N = 1;
for (i = 0; i < k; i++)
N *= c[i];
return N;
}
int main() {
int a, b;
cout << "请输入两个整数：";
cin >> a >> b;
cout << a << "和" << b << "的最大公约数是：" << CommonFactor(a, b) << endl;
return 0;
}
```
### 字符串匹配实验
#### BF算法
**核心思想**：
BF(Brute Force)算法是一种最简单的字符串匹配算法，通过逐个比较目标字符串中的字符与模式字符串中的字符来确定是否存在匹配。
**代码实现**：
```cpp
#include<iostream.h>
using namespace std;
int BF(char S[], char T[]) {
int i = 1, j = 1, k = 0;
while (S[0] - i + 1 >= T[0]) {
k = i;
while (j <= T[0] && S[i] == T[j]) {
i++; j++;
}
if (j > T[0]) break;
i = k + 1;
j = 1;
}
if (j > T[0]) return i - j + 1;
else return 0;
}
int main() {
int returnS;
cout << "请输入字符串S:\n";
cin >> (S + 1);
cout << "请输入字符串T:\n";
cin >> (T + 1);
cout << "BF算法的结果：";
cout << BF(S, T) << endl;
return 0;
}
```
#### KMP算法
**核心思想**：
KMP(Knuth-Morris-Pratt)算法是一种改进的字符串匹配算法，它通过预先计算模式串的部分匹配表(next 数组)来避免不必要的回溯，从而提高匹配效率。
**代码实现**：
```cpp
#include<iostream.h>
using namespace std;
int next[100] = {0};
void GetNext(char T[], int next[]) {
next[1] = 0;
int j = 1, k = 0;
while (j < T[0]) {
if ((k == 0) || (T[j] == T[k])) {
j++; k++;
next[j] = k;
} else {
k = next[k];
}
}
}
int KMP(char S[], char T[]) {
int i = 1, j = 1;
while (T[0] - j <= S[0] - i && j <= T[0]) {
if (j == 0 || S[i] == T[j]) {
i++; j++;
} else {
j = next[j];
}
}
if (j <= T[0]) return 0;
else return i - j + 1;
}
int main() {
int returnS;
cout << "请输入字符串S:\n";
cin >> (S + 1);
cout << "请输入字符串T:\n";
cin >> (T + 1);
cout << "KMP算法的结果：";
cout << KMP(S, T) << endl;
return 0;
}
```
#### BM算法
**核心思想**：
BM(Boyer-Moore)算法利用了模式串中最后一个字符的信息以及坏字符规则，通过计算模式串中每个字符在模式串末尾出现的位置，来决定下一次比较的起始位置，从而实现快速匹配。
**代码实现**：
```cpp
#include<iostream.h>
using namespace std;
int dist(char c) {
int i = 1;
while (T[i] != c && T[i] != '\0') i++;
if (i >= T[0]) return T[0];
else return T[0] - i;
}
int BM(char S[], char T[]) {
int i = T[0], j;
while (i <= S[0]) {
j = T[0];
while (j > 0 && S[i] == T[j]) {
j--;
i--;
}
if (j == 0) return i + 1;
else i = i + dist(S[i]);
}
return 0;
}
int main() {
int returnS;
cout << "请输入字符串S:\n";
cin >> (S + 1);
cout << "请输入字符串T:\n";
cin >> (T + 1);
cout << "BM算法的结果：";
cout << BM(S, T) << endl;
return 0;
}
```
以上代码片段展示了三种不同的最大公约数算法及三种常用的字符串匹配算法的实现方式，这些算法不仅有助于理解计算机科学中的基本概念，还能帮助学生掌握C语言编程的基本技巧。
grayren2013-01-19报告很完整 建议下载
