算法设计与分析实验报告完整版修订版

简介：
《算法设计与分析实验报告》提供了关于计算机科学中核心课程——算法设计与分析的全面实践指导。该版本经过修订，包含了最新的研究和优化方法，旨在帮助学生深入理解并掌握复杂问题的有效解决方案，通过一系列精心设计的实验加强理论知识的应用能力。 根据提供的实验报告，我们可以将其中的关键知识点归纳如下： ### 最大公约数实验 #### 欧几里得算法 **核心思想**： 欧几里得算法（也称为辗转相除法）是一种高效的求解两数最大公约数的方法。其基本原理是基于这样一个事实：两个整数的最大公约数等于其中较小的整数和较大整数除以较小整数所得余数的最大公约数。 **代码实现**： ```cpp #include 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 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 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 using namespace std; int BF(char S[], char T[]) { int i = 1, j = 1; while (S[0] - i + 1 >= T[0]) { bool match = true; for (; j <= T[0]; ++j) { if (T[j] != S[i++]) break; } if (match) return i - j + 1; else --i, ++j; } return 0; } int main() { int returnS; cout << 请输入字符串S:\n; cin >> (S + 1); cout << 请输入字符串T:\n; cin >> (T + 1); cout << BF算法的结果：\n << BF(S, T) << endl; return 0; } ``` #### K