- 博客(16)
- 收藏
- 关注
RSS订阅原创 圆排列问题
问题描述圆排列问题：给定n个圆的半径序列，将它们放到矩形框中，各圆与矩形底边相切，求具有最小排列长度的圆排列解析圆排列问题的解空间是一棵排列树。按照回溯法搜索排列树的算法框架，设开始时a=[r1,r2,……rn]是所给的n个元的半径，则相应的排列树由a[1:n]的所有排列构成。如图，对于圆排列的问题，相邻的两个圆之间不一定会相切，如上方的第二个图。如果有一个无限大的圆，那么这个矩形的长度就是这个圆的直径，如下图。调用递归函数，如果搜索到达叶子节点，生成这种排列顺序并计算长度，否则，搜索下个排列的
2020-06-15 19:58:55
631
原创 图的M着色
问题描述解析使用到了邻接矩阵 还有就是color数组，也是解题的关键，要明确color数组代表的含义：color[n],大小为n,下标肯定代表顶点，里面的值代表这个顶点放的是哪种颜色。 Traceback（t）的t代表某一个顶点，这个顶点具体放哪种颜色不知道，肯定有个for循环从第一种颜色到最后一种颜色都要试一下，那么color[t]里就放当前这种颜色。OK（t）判断一下，如果可以，traceback（t+1）。 OK（t）中，t顶点和哪些顶点有联系，我就去判断这些点放置的颜色有没有和我相
2020-06-15 18:25:42
142
原创 最优前缀码问题
问题描述给定字符集，求给字符集的最优前缀码解析设计typedef struct { unsigned int weight; unsigned int parent, lchild, rchild;}HTNode, * HuffmanTree;typedef char** HuffmanCode;void Select(HuffmanTree* HT, int n, int* s1, int* s2);void CreateHuffmanTree(HuffmanTree*
2020-05-23 12:01:01
567
原创 相容问题--贪心算法
问题描述解析下面是另外两种贪心算法无法实现最优的反例核心代码#include<stdio.h>typedef struct{ int s; int f;}l;int main(){ l list[100]; int n; scanf("%d",&n); for(int i=0;i<n;i++) { scanf("%d %d",...
2020-05-01 13:59:40
261
原创 LCS算法
LCS算法问题描述找出两个字符串的最长子序列串长度伪代码样例手推过程代码运行结果核心代码#include<stdio.h>#include<string.h>char s1[100],s2[100];int l1,l2;int c[100][100];lcs(int x,int y){ int i,j; c[0][y]=0; c[x][...
2020-04-24 19:13:41
189
原创 矩阵链乘法求最少的运算次数
矩阵链乘法求最少的运算次数问题描述解析手推过程代码求得结果伪代码算法复杂度核心代码int RecurMatrixChain(int p[],int i,int j) //矩阵链乘法递归实现 { if (i==j) { s[i][j]=i; m[i][j]=0; return m[i][j]; } int q; m[i][j]=1e5; s[i]...
2020-04-18 20:51:54
655
原创 投资问题
投资问题问题解析复杂度核心代码int f(int x,int y) //表示投资第y项目x元的收益{ if(y==1) { if(x>0) return x+10; else return 0; } else if(y==2) { if(x>1) return 5*x-5; else return 0; } ...
2020-04-13 20:38:15
391
原创 寻找第k小个元素：特定分治策略
寻找第k小个元素：特定分治策略问题描述在含n个元素的无序数列中寻找第k小的元素算法分析递归实现图2的运算，伪代码核心代码 int select(int arr[],int n,int l,int r,int k) { int num=r-l+1; int s=num/5; int i=0; int count=0; int mid; int j=0; ...
2020-04-04 17:00:17
441
原创 最近对问题（分治法）
最近对问题（分治法）问题在给定的n个二维点中求得一对点的最小距离解析首先对点对根据x轴从小到大排序 并将其分为大小为n/2的两个集合S1,S2，并且对S1,S2进行递归，则总集合点对最小距离可能有三种情况：1.两个点均在S1，min为S1的最短距离2.两个点均在S2，min为S2的最短距离3.一个点在S1，一个点在S2，那么这两个点x左边可能范围是中位点加减min（dS1,dS2）...
2020-03-29 16:24:27
461
原创 二分归并排序法
二分归并排序法问题描述二分归并排序：对n个不同的数构成的数组A[1…n]进行排序，其中n=2^k解析核心代码int mergearray(int a[], int left, int mid, int right, int temp[]) { int i = left; int j = mid + 1; int m = mid; int n = righ...
2020-03-17 19:56:25
228
原创 简单查找算法时间复杂度
查找算法时间复杂度问题描述写出两种检索算法：在一个排好序的数组T[1…n]中查找x，如果x在T中，输出x在T的下标j；如果x不在T中，输出j=0.按实验模板编写，“分析”部分仅给出复杂度结果即可。算法顺序查找：顺序查找也称为线形查找，属于无序查找算法。从数据结构线形表的一端开始，顺序扫描，依次将扫描到的结点关键字与给定值k相比较，若相等则表示查找成功；若扫描结束仍没有找到关键字等于k的...
2020-03-10 19:26:53
1121
原创 Dijkstra算法求两点最短路径
Dijkstra算法求两点最短路径问题描述对于下图使用Dijkstra算法求由顶点a到顶点h的最短路径，按实验报告模板编写算法。算法简介选取一个起始点加入集合A，剩余点加入集合B计算集合B中的点到初始点的距离dis[i]，（若不相邻的距离无穷大，否则为权值）选取最小的dis[i]，计为dis[x]，并将点x加入集合A更新和点x相邻的点y的dis值（dis[y]=MIN(dis[y...
2020-03-08 14:03:34
2065
原创 Floyd算法求有向图两点间最短距离
Floyd算法求有向图两点间最短距离问题描述用Floyd算法求解下图各个顶点的最短距离。写出Floyd算法的伪代码和给出距离矩阵（顶点之间的最短距离矩阵），按实验报告模板编写算法。算法描述在计算两点之间的最短路径时，如果两点之间存在其他的点，那么可以将最短路径的情况分为两类，经过某个点和不经过这个点。那么在求有向图中ab两点的最短路径时，遍历剩下的点，比较在a到b的路径中是经过Vi距离短...
2020-03-08 13:19:47
1056
原创 Prim和Kruskal算法实现最小生成树
最小生成树的两种算法1.问题描述在一给定的无向图G = (V, E) 中，(u, v) 代表连接顶点 u 与顶点 v 的边（即），而 w(u, v) 代表此边的权重，若存在 T 为 E 的子集（即）且为无循环图，使得的 w(T) 最小，则此 T 为 G 的最小生成树2.Prim算法Prim算法即加点法 将一个起始点加入集合V中，寻找与集合相连并且距离最近的点加入集合，要求不可形成回路，...
2020-03-01 16:59:55
227
空空如也
空空如也
TA创建的收藏夹 TA关注的收藏夹
TA关注的人