1.熟悉C/C++语言的集成开发环境;
2.掌握算法的概念;
3.了解问题的求解方法;
4.理解递归思想,学会编写递归。
实验原理:
将模式对准文本的前m个字符从左往右进行比对,如果其中有一个字符不匹配,模式往右移动一位继续下一个m个字符的比对。最坏的情形是模式须移动n-m+1次,每次移动模式之前,做足m次比对才发现不匹配。因此,在最坏情况下,该算法属于Θ(nm)。
检查匹配串的第一个字符与文本串的第一个字符是否相匹配,我们通过比较文本串的和匹配串的第一个字符来开始,如果他们不匹配我们移向文本串的第二个字符。再比较匹配串的第一个字符和文本串第二个字符。如果他们不匹配我们继续向前移动,直到我们遇到一个相匹配的或直到我们到达文本串的最后。
实验代码:
#include<iostream> #include<string> #include<algorithm> using namespace std; int StringMatch(string T,string s) { int n = T.size(); //文本长度 int m = s.size(); //模式长度 for (int i = 0; i < n - m; i++) //只需比较前n-m个字符 { int j = 0; while (j < m&&s[j] == T[i + j]) //查找符合的 j++; if (j == m) //匹配成功返回模式在文本中的开始位置 return i; } return -1; //否则返回-1 } int main() { string T, P; cout << "请输入字符串文本:" <<endl; cin >> T; cout << "请输入待查字符串,寻找位置:" <<endl; cin >> P; //输入一个标准文本和一个待查字符串 cout << StringMatch(T, P) << endl; //调用函数,输出查找结果 return 0; }
实验测试:
1.编译运行
2.数据测试:
①以hjdjgs54621ahgd545和1ah为测试,成功找到
②以hsgdh54和sdga为测试,返回-1,未找到
算法复杂度分析:
该方法又称暴力搜索,也是最容易想到的方法。预处理时间 O(0),匹配时间复杂度O(N*M)。主要过程:从原字符串开始搜索,若出现不能匹配,则从原搜索位置+1继续。
实验原理:
比较x和a的中间元素a[mid],若x=a[mid],则x在L中的位置就是mid;如果x<a[mid],则x在a[mid]的前面;如果x>a[mid],则x在a[mid]的后面。无论在哪部分查找x,其方法都和在a中查找x一样,只不过是查找的规模缩小了。
实验代码:
#include <iostream> using namespace std; int binary_search(int arr[], int length, int K); //折半查找函数声明 int main() { int i,k; int arr[10]; //定义待查找数组 cout << "请输入长度为10的整型数组:" << endl; for(i=0;i<10;i++) cin >> arr[i]; //获取用户输入作为数组值 cout << "请输入查找键K:" << endl; cin >> k; //用户输入查找键K int id = binary_search(arr, 10, k); //调用折半查找函数 cout << "id:" << id << endl; //输出下标 return 0; } int binary_search(int arr[], int length, int K) //折半查找函数定义 { int n = length; int l = 0; int r = n - 1; //获取数组长度n,以及首尾位置 l,r while(l <= r){ int m = (int) (l+r) / 2; //定义m为中间位置 if(K == arr[m])return m; //如果碰巧K等于中间值,直接返回 else if(K < arr[m]) r = m-1; else l = m+1; //否则继续比较前后位置 } return -1; }
实验测试:
1.编译运行
2.数据测试
①以2 4 8 12 46 48 78 79 81 83和81为测试,成功找到
②以2 4 8 12 46 48 78 79 81 83和56为测试,返回-1,未找到
算法复杂度分析:
输入规模:n
基本操作:三路数值比较
复杂度:
实验原理:
鸡翁一值钱五:公鸡五文一只;
鸡母一值钱三:母鸡三文一只;
鸡雏三值钱一:小鸡三只一文;
百钱买百鸡:100文钱买鸡。
设鸡翁x只,鸡母y只,鸡雏z只,所以5x+3y+1/3z = 100,x+y+z = 100
且x,y,z为整数, 0 <= x <= 100, 0 <= y <= 100, 0 <= z <= 100
如果用解方程的方式解这道题需要进行多次猜解,计算机的一个优势就是计算速度特别暴力并且无怨无悔,所以我们可以欺负她、蹂躏她!因此我们用穷举法的方式来解题,需要 1013 次猜解,但对于计算机来说,小 CASE!
分析:
这是一个很简单的for循环查找判断题。三种鸡均为整型,公鸡,母鸡不会出问题,但这鸡雏却会出现问题,在C中如果a 为int型,那么a/3等等仍然
为int型,假设a为2 则a/3输出的结果为0;a为4输出为1…所以要对鸡雏单独加一个判定条件(k % 3 == 0)。如果不想输出这么多次,可以把i,j,k拿到外边。如果想更进一步,及用宏定义来表示三种鸡型和它们的数量。先假设一只公鸡的数量最多是100/5=20,也就是公鸡最多的数量是20只,母鸡的数量最多为100/3=33(取整),小鸡的话因为最多只能有100只,所以小鸡最多的数量为100。
实验代码:
//暴力破解版 #include <stdio.h> int main() { int i, j, k; //定义对三种鸡型的循环变量 printf("穷举法的方式来解题,计算机计算结果:\n\n"); for(i=0;i<=(100/5);i++ ) //鸡翁最多20只 for(j=0;j<=(100/3);j++) //鸡母最多33只 for(k=0;k<=100;k++ ) //鸡雏最多100只 { if(5*i+3*j+k/3==100&&k%3==0&&i+j+k==100) //如果数量满足百元买百鸡,则输出该配合 { printf("鸡翁%2d只,鸡母%2d只,鸡雏%2d只\n", i, j, k); } } return 0; }
实验测试:
算法复杂度分析:
穷举法,使用三重循环,是最没有效率的算法。时间复杂度O(n ^ 3),循环要执行1000000次,穷举法时间复杂度太高,可以进行适当的优化。如果小鸡的数量可以直接通过母鸡的数量和公鸡的数量算出来,算法简化成了二重循环,算法的时间复杂度为O(n ^ 2)。算法其实还可以继续优化成O(n),通过数学的方法,我们可以列出题目的方程组,设公鸡为x,母鸡为y,小鸡为z
换成参数方程:
根据题目定义域,列方程:
最后,算法被优化成了O(n),并且整个循环只要执行3次。
从一开始的穷举法需要执行1000000次,再到现在的只需要执行3次。