4 / 37
if ((n ~= fix(n))||(n<0)) error('n 必须为非负整数！ ！'); end %计算阶乘 if n==0 x=1; else x = factorial(n-1)*n; end end function x=fibonacci(n) %%求斐波那契数列 %%输入：正整数 n %输出：斐波那契数列中第 n 个数 %例外处理 if ((n ~= fix(n))||(n<1)) ！'); error('n 必须为正整数！ end %计算 if n==1||n==2 x = 1; else x = fibonacci(n-1)+fibonacci(n-2); end end
3 / 37
error('A 和 B 必须同时为方阵！ ！'); end if (a_row ~= b_list) error('方阵 A 与 B 的维数必须相等！ ！'); end %矩阵相乘运算 n=a_row; X=zeros(n,n);%初始化 X for i=1:n for j=1:n for k=1:n X(i,j)=X(i,j)+A(i,k)*B(k,j); end end end end
测试:
x = gcd(123,234) x= 3
二、 验证给定数组中的所有元素是否唯一
代码：
function x=UniqueElements(A) %% 验证给定数组中的所有元素是否唯一 %输入：一个数组 1xN 矩阵 A
2 / 37
%输出：1--该数组所有元素唯一 % 0--该数组所有元素不唯一 x = 1; N = size(A,2); for i = 1:(N-1) for j=(i+1):N if A(i) == A(j) x = 0; break; end end end end
算法设计与分析实验报告
说明：本实验报告的算法全部用 Matlab 实现
目录： 一、求最大公约数的欧几里得算法 二、验证给定数组中的所有元素是否唯一 三、计算两个 N 阶矩阵的乘积 四、递归算法（阶乘、Fibonacci 数列） 五、KMP 模式匹配算法 六、Huffman 编码 七、图的遍历（深度优先搜索算法 DFS、广度优先搜索算法 BFS） 八、Dijkstra 算法、Kruskal 算法和 Prim 算法 九、排序算法（选择、冒泡、归并、快速、插入） 十、二叉树的三序遍历（前序、中序、后序）
测试:
>> t='this is a kmp string matching test string'; >> p='string';
1 / 37
一、 求最大公约数的欧几里得算法
代码：
function x = gcd(m,n) %% 求最大公约数的欧几里得算法 %输入：两个整数 m, n %输出：m，n 的最大公约数 x if (m ~= fix(m))||(n ~=fix(n)) error('两个输入变量必须为整数！ ！'); end if (m~=0)&&(n~=0) while n~=0 r = mod(m,n); m = n; n = r; end x = m; else error('两个输入变量均不能为零！ ！'); end end
测试:
A=[1 2 3 4]; B=[5 6 7 8]; X = MatrixMultiplication(A,B) X= 19 43 22 50
四、 递归算法（阶乘、Fibonacci 数列）
代码：
function x=factorial(n) %%求正整数 n 的阶乘 %%输入：正整数 n %输出：n 的阶乘 x=n*(n-1)*(n-2)*...*3*2*1 %例外处理
测试:
x=UniqueElements([2 0 1 1 0 5 1 5 2 7]) x= 0 >> x=UniqueElements([1 3 5 7 8 9 2 Fra bibliotek]) x= 1
三、 计算两个 N 阶矩阵的乘积
代码：
function X = MatrixMultiplication(A,B) %%计算两个 N 阶矩阵的乘积 %%输入：两个 N 阶矩阵 A，B %输出：矩阵 A 与 B 的乘积 X %例外处理 [a_row,a_list]=size(A); [b_row,b_list]=size(A); if (a_row ~= a_list||(b_row~=b_list))
测试:
x=factorial(5) x= 120 x=fibonacci(1) x=
5 / 37
1 >> x=fibonacci(2) x= 1 >> x=fibonacci(3) x= 2 >> x=fibonacci(4) x= 3 >> x=fibonacci(5) x= 5 >> x=fibonacci(10) x= 55
五、 KMP 模式匹配算法
代码：
function KMP(T, P) %%KMP：此算法是一种改进的字符串匹配算法 %输入： % T--原字符串 % P--模式
6 / 37
%输出： % 返回所有匹配字符串第一个字符的下标 n = length(T); m = length(P); pi= Compute_Prefix(P); q = 0; for i = 1:n while ( (q > 0) && (P(q+1) ~= T(i) )) q = pi(q); end if P(q+1)==T(i) q = q + 1; end if q == m temp = i - m ; fprintf('Pattern occurs with shift %u.\n' ,temp); q = pi(q); end end end function pi = Compute_Prefix(P) %%KMP 函数的子函数 m = length(P); pi(1)=0; k = 0; for q = 2:m while ( (k>0) && (P(k+1) ~= P(q) )) k = pi(k); end if P(k+1) == P(q) k=k+1; end pi(q)=k; end end