柚子快报邀请码778899分享：中南民族大学软工算法考试
#2019年软工算法考试 整理：北忘山 关注公众号获取更多资料 [外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-5dN70Ppv-1578581536946)(./1578578869033.png)]
估计题目范围：期中+习题 ####首先是期中考试题目： [外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-gCIbpVgk-1578581536949)(./1578570652724.png)] ####还有不知道哪里来的重点 [外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-i5xWKCg8-1578581536950)(./1578578790339.png)]
###非递归分析的五步骤 （1）决定用哪个（哪些）参数表示输入规模 （2）找出算法的基本操作 （3）检查基本操作的执行次数是否只依赖于输入规模，如果它还依赖于一些其他的特性，则最差效率，平均效率以及最优效率需要分别研究 （4）建立一个算法基本操作执行次数的求和表达式 （5）利用求和运算的标准公式和法则来建立一个操作次数的闭合公式，或者至少确定它的增长次数。
###递归分析的五个步骤 （1）决定用哪个（哪些）参数表示输入规模的度量标准 （2）找出算法的基本操作 （3）检查一下，对于相同的规模的不同输入，基本操作的执行次数是否可能不同。如果有这种可能，则必须对最差效率、平均效率以及最优效率做单独研究 （4）对于算法基本操作的执行次数，建立一个递推关系以及相应的初始条件。 （5）解这个递推式，或者至少确定它的解的增长次数。
##计算a 的 n次方及时间T（n）O(nlogn)
###//蛮力法求a的n次方
int Power1(int a,int n)
{
int ans=1;
for(int i=0;i ans*=a; return ans; } ###//分治法求a的n次方 int Power2(int a,int n) { int ans=1; if (n==0) ans=1; else if(n==1) ans=a; else ans=Power2(a,n/2)*Power2(a,(n+1)/2); return ans; } ###//减治法求a的n次方 int Power3(int a,int n) { int ans=1; if (n==0) ans=1; else if(n==1) ans=a; else { ans=Power3(a,n/2); if(n%2==0) ans=ans*ans;//当n为偶数 else ans=ans*ans*a;//当n为奇数 } return ans; } [外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-fPfP2qgT-1578581536951)(./1578572372813.png)] ###汉诺塔问题 ####解法 解法的基本思想是递归。假设有A、B、C三个塔，A塔有N块盘，目标是把这些盘全部移到C塔。那么先把A塔顶部的N-1块盘移动到B塔，再把A塔剩下的大盘移到C，最后把B塔的N-1块盘移到C。 每次移动多于一块盘时，则再次使用上述算法来移动。 [外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-ozXU0Jqw-1578581536952)(./1578572918697.png)] ####程序源码 #include #include #include using namespace std; int n; char x,y,z; void mov(int n,char a,char c,char b) { if(n==0) return; mov(n-1,a,b,c); cout< mov(n-1,b,c,a); } int main() { cin>>n; cin>>x>>y>>z; mov(n,x,y,z); return 0; } ###螺钉螺母的匹配问题 （快速排序的变形）nlogn ####算法分析 螺母我就用nut表示，螺钉我就用bolt表示。 我是假设只有唯一一个匹配的，即nut数组与bolt一一对应。否则算法还需要有更大的更改。 1.在nut数组拿一个，可以把bolt数组分为比那个小的，比那个大的，还有一个匹配的3个部分。 2.在bolt中小的那堆那一个可以把nut分成比那个小的，比那个大的，还有一个匹配的3个部分。 3.这样可以发现，现在数组产生两对比配的螺母和螺钉和一队小的螺钉和螺母，一队大的螺钉和螺母。 [外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-gtO7gW4W-1578581536953)(./1578573180160.png)] 令数组内部的排列也是这样。一次调用后前两个是匹配的螺母和螺钉。后面给一个坐标，左边是小的，右边是较大的。 这样对较小的螺母和螺钉再调用一个次函数，即又可以产生两对匹配，和较小小和较大大的 ####代码实现 //分类函数 //n和b为两个数组 //left为左索引，right为右索引 void Fix(int *n, int *b, int left, int right) { if (left < right) { int tmp = n[left]; int i = left, j = right; while (i < j) { while (i < j&&b[i] < tmp) { i++; } while (i < j&&b[j] > tmp) { j--; } if (i < j) { swap(b[i], b[j]); } } b[i] = tmp; swap(b[left], b[i]); cout << "n+b:" << endl; Print(n); Print(b); cout << endl; //一趟下来，i=j的tmp的位置。以tmp为界限，左右分别是小于和大于它的元素 tmp = b[left + 1]; i = left + 1, j = right; while (i < j) { while (i < j&&n[i] < tmp) { i++; } while (i < j&&n[j] > tmp) { j--; } if (i < j) { swap(n[i], n[j]); } } n[i] = tmp; swap(n[left + 1], n[i]); cout << "n+b:" << endl; Print(n); Print(b); cout << endl; Fix(n, b, left + 2, i); Fix(n, b, i + 1, right); } } ###两个数组的公共元素问题 时间复杂度是 O(maxn(m,n)) #include #include int elements(int a[],int b[],int c[],int sizea,int sizeb) { //a 和 b分别是两个比较数组 //c是用来存放公共元素的数组 //sizea sizeb 则是两个数组的大小 //在这个地方可以用：a.length表示，而不用传入数组的大小 int pa=0; //指向a数组的指针 int pb=0; //指向b数组的指针 int count=0; //统计数量 while(pa { if (a[pa]>b[pb]) pb++; else if(a[pa] pa++; else { c[count++]=a[pa]; pa++; pb++; } } return (count); } int main(void) { int a[]={1,2,3,4,5,6,7,8,9}; int b[]={4,5,6}; int c[10]; int i,count; count = elements( a,b,c ,9,3); printf("相同的元素的个数是：%d\n",count); for(i=0;i printf("%4d\n",c[i]); system("pause"); return 0; } ##最小生成树-Prim算法 普里姆算法（Prim算法） ####算法简单描述 1).输入：一个加权连通图，其中顶点集合为V，边集合为E； 2).初始化：Vnew = {x}，其中x为集合V中的任一节点（起始点），Enew = {},为空； 3).重复下列操作，直到Vnew = V： a.在集合E中选取权值最小的边 b.将v加入集合Vnew中，将 4).输出：使用集合Vnew和Enew来描述所得到的最小生成树。 [外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-xnkZI2pu-1578581536956)(./1578574240722.png)][外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-JBJkNGBw-1578581536957)(./1578574246477.png)] [外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-05cbNxbt-1578581536958)(./1578574256627.png)][外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-9Wd0IUNV-1578581536959)(./1578574260253.png)] [外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-g9dEwjsJ-1578581536960)(./1578574265109.png)][外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-eh2HIb54-1578581536961)(./1578574268240.png)] [外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-MRte4c8C-1578581536962)(./1578574272946.png)][外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-4sDvaUo1-1578581536963)(./1578574276646.png)] [外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-C9dShjfd-1578581536964)(./1578574282115.png)][外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-tUpHPMYX-1578581536965)(./1578574285320.png)] ####简单证明prim算法 反证法：假设prim生成的不是最小生成树 1).设prim生成的树为G0 2).假设存在Gmin使得cost(Gmin) 3).将 4).这与prim每次生成最短边矛盾 5).故假设不成立，命题得证. ####代码 #include using namespace std; #define MAX 100 #define MAXCOST 0x7fffffff int graph[MAX][MAX]; int prim(int graph[][MAX], int n) { int lowcost[MAX];//i-max的距离 int mst[MAX];//表示i的起点是谁 int i, j, min, minid, sum = 0; for (i = 2; i <= n; i++) { lowcost[i] = graph[1][i]; mst[i] = 1; }//默认起点是1 mst[1] = 0; for (i = 2; i <= n; i++) { min = MAXCOST; minid = 0; for (j = 2; j <= n; j++) { if (lowcost[j] < min && lowcost[j] != 0) { min = lowcost[j]; minid = j; } }//找出距离1最近的点 cout << "V" << mst[minid] << "-V" << minid << "=" << min << endl; sum += min; lowcost[minid] = 0; for (j = 2; j <= n; j++) { if (graph[minid][j] < lowcost[j]) { lowcost[j] = graph[minid][j]; mst[j] = minid; } }//相当于利用mind作为新的起点来更新lowcost[]; } return sum; } int main() { int i, j, k, m, n; int x, y, cost; cin >> m >> n;//m=顶点的个数，n=边的个数 //初始化图G for (i = 1; i <= m; i++) { for (j = 1; j <= m; j++) { graph[i][j] = MAXCOST; } } //构建图G for (k = 1; k <= n; k++) { cin >> i >> j >> cost; graph[i][j] = cost; graph[j][i] = cost; } //求解最小生成树 cost = prim(graph, m); //输出最小权值和 cout << "最小权值和=" << cost << endl; return 0; } ####实例输入 6 10 1 2 6 1 3 1 1 4 5 2 3 5 2 5 3 3 4 5 3 5 6 3 6 4 4 6 2 5 6 6 ####实例输出 V1-V3=1 V3-V6=4 V6-V4=2 V3-V2=5 V2-V5=3 最小权值和=15 ###warshall算法 最短路径 算法推荐博客 ####定义概览 Floyd-Warshall算法（Floyd-Warshall algorithm）是解决任意两点间的最短路径的一种算法，可以正确处理有向图或负权的最短路径问题，同时也被用于计算有向图的传递闭包。Floyd-Warshall算法的时间复杂度为O(N3)，空间复杂度为O(N2)。 [外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-demICG12-1578581536966)(./1578574890960.png)] [外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-WdVOVcKi-1578581536971)(./1578574896401.png)] ####代码 #include int main() { int e[10][10],k,i,j,n,m,t1,t2,t3; int inf=99999999; //用inf(infinity的缩写)存储一个我们认为的正无穷值 //读入n和m，n表示顶点个数，m表示边的条数 scanf("%d %d",&n,&m); //初始化 for(i=1;i<=n;i++) for(j=1;j<=n;j++) if(i==j) e[i][j]=0; else e[i][j]=inf; //读入边 for(i=1;i<=m;i++) { scanf("%d %d %d",&t1,&t2,&t3); e[t1][t2]=t3; } //Floyd-Warshall算法核心语句 for(k=1;k<=n;k++) for(i=1;i<=n;i++) for(j=1;j<=n;j++) if(e[i][j]>e[i][k]+e[k][j] ) e[i][j]=e[i][k]+e[k][j]; //输出最终的结果 for(i=1;i<=n;i++) { for(j=1;j<=n;j++) { printf("%10d",e[i][j]); } printf("\n"); } return 0; } ###主定理的运用 [外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-harG2NZU-1578581536973)(./1578576929018.png)] ###增长次数比较 [外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-gmqmADsQ-1578581536976)(./1578577477553.png)] ###递归斐波那契 public static long method(int n) { if(n<2) { return 1; }else { long a=method(n-1) + method(n-2); return a; } } ###非递归斐波那契 private static int method2(int n) { // TODO Auto-generated method stub //a,b,c int a=1; int b=1; int c = 0; for(int i=1;i c=a+b; a=b; b=c; } return c; } ###Floyd算法 #include int main() { int e[10][10],k,i,j,n,m,t1,t2,t3; int inf=99999999; //用inf(infinity的缩写)存储一个我们认为的正无穷值 //读入n和m，n表示顶点个数，m表示边的条数 scanf("%d %d",&n,&m); //初始化 for(i=1;i<=n;i++) for(j=1;j<=n;j++) if(i==j) e[i][j]=0; else e[i][j]=inf; //读入边 for(i=1;i<=m;i++) { scanf("%d %d %d",&t1,&t2,&t3); e[t1][t2]=t3; } //Floyd-Warshall算法核心语句 for(k=1;k<=n;k++) for(i=1;i<=n;i++) for(j=1;j<=n;j++) if(e[i][j]>e[i][k]+e[k][j] ) e[i][j]=e[i][k]+e[k][j]; //输出最终的结果 for(i=1;i<=n;i++) { for(j=1;j<=n;j++) { printf("%10d",e[i][j]); } printf("\n"); } return 0; } ###排序算法 排序算法总结文章连接：点击即可 [外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-9Sj9gF6v-1578581536977)(./1578579539734.png)] ####冒泡排序(BubbleSort) ####基本思想： 两个数比较大小，较大的数下沉，较小的数冒起来。 ####过程： 比较相邻的两个数据，如果第二个数小，就交换位置。 从后向前两两比较，一直到比较最前两个数据。最终最小数被交换到起始的位置，这样第一个最小数的位置就排好了。 继续重复上述过程，依次将第2.3…n-1个最小数排好位置。 [外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-JNRrd4fe-1578581536978)(./1578579654701.png)] 冒泡排序 平均时间复杂度：O(n2) public static void BubbleSort(int [] arr){ int temp;//临时变量 for(int i=0; i for(int j=arr.length-1; j>i; j--){ if(arr[j] < arr[j-1]){ temp = arr[j]; arr[j] = arr[j-1]; arr[j-1] = temp; } } } } ####选择排序(SelctionSort) ####基本思想： 在长度为N的无序数组中，第一次遍历n-1个数，找到最小的数值与第一个元素交换； 第二次遍历n-2个数，找到最小的数值与第二个元素交换； 。。。 第n-1次遍历，找到最小的数值与第n-1个元素交换，排序完成。 ####过程： [外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-FC8ESCXf-1578581536979)(./1578579712012.png)] 选择排序 平均时间复杂度：O(n2) public static void select_sort(int array[],int lenth){ for(int i=0;i int minIndex = i; for(int j=i+1;j if(array[j] minIndex = j; } } if(minIndex != i){ int temp = array[i]; array[i] = array[minIndex]; array[minIndex] = temp; } } } ####插入排序(Insertion Sort) ####基本思想： 在要排序的一组数中，假定前n-1个数已经排好序，现在将第n个数插到前面的有序数列中，使得这n个数也是排好顺序的。如此反复循环，直到全部排好顺序。 ####过程： [外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-VHHpo9WR-1578581536980)(./1578579783948.png)] 插入排序 平均时间复杂度：O(n2) public static void insert_sort(int array[],int lenth){ int temp; for(int i=0;i for(int j=i+1;j>0;j--){ if(array[j] < array[j-1]){ temp = array[j-1]; array[j-1] = array[j]; array[j] = temp; }else{ //不需要交换 break; } } } } ####快速排序(Quicksort) ####基本思想：（分治） 先从数列中取出一个数作为key值； 将比这个数小的数全部放在它的左边，大于或等于它的数全部放在它的右边； 对左右两个小数列重复第二步，直至各区间只有1个数。 ####辅助理解：挖坑填数 初始时 i = 0; j = 9; key=72 由于已经将a[0]中的数保存到key中，可以理解成在数组a[0]上挖了个坑，可以将其它数据填充到这来。 从j开始向前找一个比key小的数。当j=8，符合条件，a[0] = a[8] ; i++ ; 将a[8]挖出再填到上一个坑a[0]中。 这样一个坑a[0]就被搞定了，但又形成了一个新坑a[8]，这怎么办了？简单，再找数字来填a[8]这个坑。 这次从i开始向后找一个大于key的数，当i=3，符合条件，a[8] = a[3] ; j-- ; 将a[3]挖出再填到上一个坑中。 数组：72 - 6 - 57 - 88 - 60 - 42 - 83 - 73 - 48 - 85 0 1 2 3 4 5 6 7 8 9 此时 i = 3; j = 7; key=72 再重复上面的步骤，先从后向前找，再从前向后找。 从j开始向前找，当j=5，符合条件，将a[5]挖出填到上一个坑中，a[3] = a[5]; i++; 从i开始向后找，当i=5时，由于i==j退出。 此时，i = j = 5，而a[5]刚好又是上次挖的坑，因此将key填入a[5]。 数组：48 - 6 - 57 - 88 - 60 - 42 - 83 - 73 - 88 - 85 0 1 2 3 4 5 6 7 8 9 可以看出a[5]前面的数字都小于它，a[5]后面的数字都大于它。因此再对a[0…4]和a[6…9]这二个子区间重复上述步骤就可以了。 <数组：48 - 6 - 57 - 42 - 60 - 72 - 83 - 73 - 88 - 85 0 1 2 3 4 5 6 7 8 9 平均时间复杂度：O(N*logN) public static void quickSort(int a[],int l,int r){ if(l>=r) return; int i = l; int j = r; int key = a[l];//选择第一个数为key while(i while(i j--; if(i a[i] = a[j]; i++; } while(i i++; if(i a[j] = a[i]; j--; } } //i == j a[i] = key; quickSort(a, l, i-1);//递归调用 quickSort(a, i+1, r);//递归调用 } ###利用选择排序 E,X,A,M,P,L,E ``` import java.util.Arrays; public class T { public static void main(String[] args) { char[] a = { ‘e’, ‘x’, ‘a’, ‘m’, ‘p’, ‘l’, ‘e’ }; quickSort(a); System.out.println(Arrays.toString(a)); } private static void quickSort(char[] a) { quickSort(a, 0, a.length - 1); } private static void quickSort(char[] a, int low, int high) { if (low < high) { int pivotPosition = partition(a, low, high); quickSort(a, low, pivotPosition - 1); quickSort(a, pivotPosition + 1, high); } } private static int partition(char[] a, int low, int high) { char pivot = a[low]; while (low < high) { while (low < high && a[high] >= pivot) { high–; } if (low < high) { a[low] = a[high]; low++; } while (low < high && a[low] <= pivot) { low++; } if (low < high) { a[high] = a[low]; high–; } } a[low] = pivot; return low; } } ###冒泡排序    #include } void arrout(int a[],int n){ int i; for(i=0;i ###背包问题 [动态规划](https://www.cnblogs.com/yun-an/p/11037618.html) [贪心算法](https://blog.csdn.net/practical_sharp/article/details/102257213) ###估计题目 [外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-q0PksZcr-1578581536981)(./1578581387910.png)] [外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-kcBdb7KU-1578581536982)(./1578581394276.png)] [外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-m7ubgl2X-1578581536983)(./1578581400006.png)] 柚子快报邀请码778899分享：中南民族大学软工算法考试
发表评论