基于Java的四种算法设计（1.螺钉和螺母问题 2.九宫格问题 3.最大总和问题 4.地图着色问题）

资源下载地址：https://download.csdn.net/download/sheziqiong/86168456
资源下载地址：https://download.csdn.net/download/sheziqiong/86168456

1. 进一步加强学生的算法思维训练，培养学生的分析动手能力。

2. 巩固理论课程学习的常用算法设计方法及分析方法。

3. 学会为一些简单的综合实际问题设计算法。

4. 加强算法时间空间复杂性分析能力。

5. 进一步锻炼和加强学生的程序设计能力。

1. 利用所学的算法分析与设计理论知识，独立完成所选的题目；

2. 建立模型：为所选题目建立数学模型；

3. 数据结构设计：用数据结构表达模型；

4. 算法设计：在数结构的基础上设计解决问题的算法；

5. 算法分析：分析所设计算法的时间空间复杂度，说明算法的可行性。

6. 算法实现：用程序设计语言实现算法，并进行测试。

撰写的课程设计报告中应记录模型建立、数据结构、算法描述，算法时间、空间复杂度分析、算法正确性、程序执行的结果等。

基本思想：

通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据都要小，然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列。

原理：

设要排序的数组是A[0]……A[N-1]，首先任意选取一个数据（通常选
用数组的第一个数）作为关键数据，然后将所有比它小的数都放到它左边，所有比它大的数都放到它右边，这个过程称为一趟快速排序。值得注意的是，快速排序不是一种稳定的排序算法，也就是说，多个相同的值的相对位置也许会在算法结束时产生变动。

特点：

• 不稳定

• 快速排序过程中不会产生有序子序列，但每一躺排序后都有一个元素放在其最终位置上

• 每次选择的关键值可以把数组分为两个子数组的时候，快速排序算法的速度最快，当数组已经是正序或逆序时速度最慢；

• 递归次数与每次划分后得到的分区的处理顺序无关；

• 对n个关键字进行快速排序，最大递归深度为n，最小递归深度为log2n；

基本思想：

深度优先搜索属于图算法的一种，英文缩写为DFS即DepthFirstSearch.其过程简要来说是对每一个可能的分支路径深入到不能再深入为止，而且每个节点只能访问一次

原理：

从某个状态开始，不断地转移状态直到无法转移，然后退回到前一步的状态，继续转移到其他状态，如此不断重复。

特点：

• 一般不能保证找到最优解；

• 当深度限制不合理时，可能找不到解，可以将算法改为可变深度限制；

• 方法与问题无关，具有通用性；

• 属于图搜索方法。

基本思想：

动态规划程序设计是对解最优化问题的一种途径、一种方法，而不是一种特殊算法。不像搜索或数值计算那样，具有一个标准的数学表达式和明确清晰的解题方法。动态规划程序设计往往是针对一种最优化问题，由于各种问题的性质不同，确定最优解的条件也互不相同，因而动态规划的设计方法对不同的问题，有各具特色的解题方法，而不存在一种万能的动态规划算法，可以解决各类最优化问题。

原理：

把多阶段过程转化为一系列单阶段问题，利用各阶段之间的关系，逐个求解

特点：

• 最优子结构性质。如果问题的最优解所包含的子问题的解也是最优的，我们就称该问题具有最优子结构性质（即满足最优化原理）。最优子结构性质为动态规划算法解决问题提供了重要线索。

• 无后效性。即子问题的解一旦确定，就不再改变，不受在这之后、包含它的更大的问题的求解决策影响。

• 子问题重叠性质。子问题重叠性质是指在用递归算法自顶向下对问题进行求解时，每次产生的子问题并不总是新问题，有些子问题会被重复计算多次。动态规划算法正是利用了这种子问题的重叠性质，对每一个子问题只计算一次，然后将其计算结果保存在一个表格中，当再次需要计算已经计算过的子问题时，只是在表格中简单地查看一下结果，从而获得较高的效率

基本思想：

回溯法在问题的解空间树中，按深度优先策略，从根结点出发搜索解空间树。搜索至解空间树任一点时，先判断该点是否包含问题的解，如果肯定不包含(剪枝过程)，则跳过对该结点为根的子树的搜索，逐层向其祖先结点回溯，否则，进入该子树，继续按深度优先策略搜索。 原理：

回溯算法实际上一个类似枚举的搜索尝试过程，主要是在搜索尝试过程中寻找问题的解，当发现已不满足求解条件时，就“回溯”返回，尝试别的路径。回溯法是一种选优搜索法，按选优条件向前搜索，以达到目标。但当探索到某一步时，发现原先选择并不优或达不到目标，就退回一步重新选择，这种走不通就退回再走的技术为回溯法，而满足回溯条件的某个状态的点称为“回溯点”。

特点：

回溯法一个显著特征是在搜索过程中动态产生问题的解空间，在任何时间，算法只保存从根结点到当前扩展结点的路径。

题目描述

假设有n 个直径各不相同的螺钉以及n 个相应的螺母。我们一次只能比较一对螺钉和螺母，来判断螺母是大于螺钉、小于螺钉还是正好适合螺钉。然而，我们不能拿两个螺母做比较，也不能拿两个螺钉做比较。我们的问题是要找到每一对匹配的螺钉和螺母。

通过对问题的分析，拟采用分治法来解决该问题。由于题目要求“不能拿两个螺母做比较，也不能拿两个螺钉做比较”，因此每次比较的时候只能用一个螺母和螺钉进行比较。我们考虑首先从螺母堆中随机选定一个螺母(记为M)，将此螺母与所有的螺钉逐个进行比较。比较过程中，将较小的螺钉放在一堆(记为DA)，将较大的螺钉放在另一堆(记为DB)，同时可以确定与选定螺母M匹配的螺钉(记为D)，这样就找到了一对匹配的螺母和螺钉（M-D）。然后，将螺钉D与其余的螺母逐个进行比较。同样地，在比较过程中，将较小的螺母放在一堆(记为MA)，将较大的螺母放在另一堆(记为MB)。这样就将原问题划分为两个小规模的子问题：（1）螺母堆MA与螺钉堆DA,（2）螺母堆MB与螺钉堆DB。类似地，可以递归地对两个子问题进行求解，最终找到所有匹配的螺母和螺钉对。

记螺钉和螺母对的个数为n,即匹配的螺钉和螺母个数分别为n。

我们将上述分析过程和解决的思路进一步归纳为以下步骤：

1. 随机从n个螺母中选定一个螺母，将此螺母与所有螺钉逐个比较，可以将螺钉分为较小的一堆和较大的另一堆。同时确定了与选定螺母匹配的一个螺钉。
2. 将匹配了的螺钉与其余的螺母进行比较，也可以将螺母分为较小的一堆和较大的另一堆。
3. 较小的螺母堆与螺钉堆构成一个子问题，较大的螺母堆与螺钉堆构成另一个子问题。分别对两个子问题重复步骤（1）、（2）。通过分析，我们发现解决该问题的思路和快速排序极其相似。因此，以下考虑基于快速排序的思路来设计算法。

首先用两个数组A[0…n-1]和B[0…n-1]（列表）分别存储螺钉序列和螺母序列。螺钉和螺母的大小都分别用数字1到n表示，数字相同表示螺钉和螺母匹配。

算法 Sort(A[l…r],B[l…r])

if l 
算法 Partition(A[l…r],B[l…r])
 
P=A[l];
//声明临时数组C，长度为r-l+1
i=0; j=r-l;
for k=l: r
if B[k]
P
  C[j]=B[k];j=j-1;
    end
C[i]=P;
B=C;
i=0; j=r-l;
for k=l: r
if A[k]
P
  C[j]=A[k];j=j-1;
    end
C[i]=P;
A=C;
return i;
 
2.3 算法实现与复杂度分析 
数据结构：数组a和b
 
实现步骤：
 
传入参数，数组a、b，整形变量left、right
用第left个螺帽来区分螺钉
然后同时反过来用第left+1个螺钉来区分螺帽
递归调用快速排序，直到所有螺钉、螺帽全部匹配成功
 
实现技巧：每趟排序时可以用某一个螺钉或者螺母来作为另一个数组排序的标准来划分成组
 
算法复杂度
 
时间复杂度：O（n*logn）
空间复杂度：O（n）
 
2.4 程序实现及运行结果分析 
程序实现的详细完整过程：
 
 
用数组a和b分别表示螺帽和螺钉的尺寸数组
 
 
调用快速排序算法，将a、b两个参数传进去开始匹配
 
 
第一次选出一枚螺钉与所有螺帽比较，并将比此螺钉大的螺帽放到左侧，比此螺钉 小的螺帽放到右侧，同时也选出了与之正好对应的螺帽。
 
 
用与之正好对应的螺帽把螺钉分为比此螺帽大的，和比此螺帽小的。
 
 
重复III和IV，直到螺帽与螺钉实现一一对应
 
 
运行结果及测试分析：
 
原始结果：
 
 
改变螺钉（或螺帽）数目：
 
 
改变数组中螺钉（或螺母）顺序：
 
 
分析：
 
该算法程序能较好的解决螺钉螺母问题，但是算法稳定度不高，因此该程序还需要很多优化的地方。
 
三、九宫格问题 
题目描述
 
将1-9的数字填入下图表格中，使得每一行每一列以及对角线上的和都相等。
 
?
?
?
?
?
?
?
?
?
3.1 问题分析与解决思路 
通过对问题的分析，可以抽象成无向连通图的遍历来解决该问题。由于题目要求“将1-9的数字填入3*3的表格中，使得每一行每一列以及对角线上的和都相等”（即每一行每一列及对角线的和为15），所以想到用深度优先的算法来解决问题，从第一个格子开始填1，然后深度优先填剩下的格子，直到找到正确的组合。
 
3.2 模型建立与算法描述 
抽象化九宫格为数组a[3][3]，访问标志为数组jdg[10]，符合要求的解为数组b[100][3][3]。
 
我们将上述分析过程和解决的思路进一步归纳为以下步骤：
 
 
初始化九宫格为全0，访问标志全为0。
 
 
从第一个格子开始填数，后面继续不重复的填数。
 
 
每次填完9个数，判断是否每一行每一列以及对角线上的和都相等（即每一行每一列及对角线的和为15），若是则保存，不是则回到上一个回溯点遍历。
 
 
打印结果。
 
 
通过分析，我们发现解决该问题的思路和深度优先极其相似。因此，以下考虑基于深度优先的思路来设计算法。
 
算法伪代码描述 
算法 dfs(int n)
 
dfs（int n）
		for i<-1 i to 10 do		
			if jdg[i]=0
				flag<-true;
			else
				flag<-false;
			if flag
				a[n/3][n%3]<-i;
				jdg[i]<-1;
				dfs(n+1);
				jdg[i]<-0;
return i;
 
3.3 算法实现与复杂度分析 
数据结构：数组a[3][3]，jdg[10]， b[100][3][3]。
 
实现步骤：
 
 
设置深度递归条件
 
 
找到一种满足的结果，并保存下来
 
 
给访问数组赋值，并递归调用深度优先算法知道得到所有正确的九宫格结果
 
 
实现技巧：每趟递归时可以打印深度优先遍历的过程方便以后的分析
 
算法复杂度
 
时间复杂度：O（n^2）
 
3.4 程序实现及运行结果分析 
程序实现的详细完整过程：
 
 
设置访问数组jdg，九宫格数组a，及解集合数组b，判断标志flag，解计数变量count。
 
 
初始化访问数组全为0，初始化九宫格数组全为0
 
 
打印深度求解过程。
 
 
打印正确解集合。
 
 
运行结果及测试分析：
 
 
结果分析：
 
该算法程序能较好的解决数塔问题，但是如果行列数目较大的话，程序复杂度将大大增加，运行效率将会减小，该程序还需要很多优化的地方。而且算法一般不能保证找到最优解，且当深度限制不合理时，可能找不到解，可以将算法改为可变深度限制；
 
四、最大总和问题 
题目描述
 
将正整数排成等边三角形（也叫数塔），三角形的底边有个数，下图给出了的一个例 子。从三角形顶点出发通过一系列相邻整数（在图中用正方形表示），如何使得到达底边 时的总和最大？
 
4.1 问题分析与解决思路 
通过对问题的分析，拟采用动态规划法来解决该问题。由于题目要求“从三角形顶点出发通过一系列相邻整数（在图中用正方形表示），如何使得到达底边 时的总和最大”，因此使用二维数组来存放数字三角形，然后使用D（x,y）来表示第x行第y个数字（x，y从1开始算），使用MaxSum（x，y）表示从D（x，y）到底边的各条路径中，最佳路径的数字和。因此，此问题就转换为求MaxSum（1,1），这时，首先想到的就是可以使用简单的递归思想来求解，D（x，y）出发，下一步只能走D（x+1，y）或者D（x+1，y+1）。所以，对于N行的三角形，可以写出下面的递归算式：
 
 if(x==N)
	 	MaxSum(x,y)=D(x,y)
	 else
	 	MaxSum(x,y)=Max(MaxSum(x+1,y),MaxSum(x+1,y+1))+D(x,y)。
 
4.2 模型建立与算法描述 
记数塔为数组data,距离数组为数组dt，方向数组为dr。
 
我们将上述分析过程和解决的思路进一步归纳为以下步骤：
 
 
使用二维数组data来存放数字三角形。
 
 
然后使用D（x,y）来表示第x行第y个数字（x，y从1开始算）。
 
 
使用MaxSum（x，y）表示从D（x，y）到底边的各条路径中，最佳路径的数字和。
 
 
问题就转换为求MaxSum（1,1）。
 
 
通过分析，我们发现解决该问题的思路和动态规划极其相似。因此，以下考虑基于动态规划的思路来设计算法。
 
算法伪代码描述 
for i <- 1 to n do
for j <- 1 to j do
					if dt[i+1][j] > dt[i+1][j+1]
						dt[i][j] <- dt[i][j] + dt[i+1][j]
						dr[i][j] <- 0
					else
						dt[i][j] <- dt[i][j] + dt[i+1][j+1]
						dr[i][j] <- 1
for(i  <- 1;i to n-1 do 
				print(data[i][j])
				j <- j + dr[i][j]
		print(data[n][j])
 
4.3 算法实现与复杂度分析 
数据结构：数组data，dt， dr。
 
实现步骤：
 
 
输入数塔所有元素，包括数塔行数及每行的各个数塔值
 
 
初始化方向向下走
 
 
打印最原始的数塔、距离以及方向数组
 
 
动态规划计算最大和
 
 
实现技巧：每次计算时可以打印每一步的数塔、距离以及方向数组以观察算法过程。
 
算法复杂度
 
时间复杂度：O（n^2）
 
4.4 程序实现及运行结果分析 
程序实现的详细完整过程：
 
 
输入数塔元素的行数及数塔每行的元素
 
 
打印初始的数塔、距离以及方向数组
 
 
动态规划地递推计算每一步的最大累计和。
 
 
打印路线。
 
 
打印最终最大累计和结果
 
 
运行结果及测试分析：
 
初始结果：（以下的变化都是相对这种结果）
 

 
 
改变行数：
 
 
 
结果分析：
 
算法虽然能够正确的找到最大累计和和路线，但是，这个算法存在重复计算的问题，而且效率不好，因为存在子问题重叠性质。子问题重叠性质是指在用递归算法自顶向下对问题进行求解时，每次产生的子问题并不总是新问题，有些子问题会被重复计算多次。动态规划算法正是利用了这种子问题的重叠性质，对每一个子问题只计算一次，然后将其计算结果保存在一个表格中，当再次需要计算已经计算过的子问题时，只是在表格中简单地查看一下结果，从而获得较高的效率
 
五、地图着色问题 
已知中国地图，对各省进行着色，要求相邻省所使用的颜色不同，并保证使用的颜色 总数最少。
 
5.1 问题分析与解决思路 
通过对问题的分析，拟采用回溯递归来解决该问题。由于题目要求“相邻省所使用的颜色不同”，因此将地图抽象成无向连通图G=（V，E）和m种不同的颜色。用这些颜色为图G的各顶点着色，每个顶点着一种颜色。问题转换成求是否有一种着色法使G中每条边的2个顶点着不同颜色。这个问题是图的m可着色判定问题。
 
5.2 模型建立与算法描述 
记各地图板块的轮廓点横坐标为数组outline_x, 纵坐标为数组outline_y，将城市抽象成无向连通图的各点后对应的邻接矩阵为metrix，多边形数组Polygon。
 
我们将上述分析过程和解决的思路进一步归纳为以下步骤：
 
 
回溯法的递归描述框架Backtrack设计图的m着色算法，用图的邻接矩阵a表示无向连通图G= (V,E)。
 
 
若（i，j）属于图G=（V，E）的边集E，则a[i][j] = 1，否则a[i][j]=0，。
 
 
整数 1,2，…m用来表示m种不同颜色。顶点i所着的颜色用x[i]表示。数组x[1:n]是问题的解向量。问题的解空间可表示为一颗高度为n+1的完全m叉树，解空间树的第i(1<=i<=n)层中每一结点都有m个儿子，每个儿子相应于x[i]的m个可能的着色之一。第n+1层结点均为叶结点。
 
 
通过分析，我们发现解决该问题的思路和回溯递归极其相似。因此，以下考虑基于回溯递归的思路来设计算法。
 
算法伪代码描述 
if current<=n 
			for i<-0 i to 4 do
				province[current]<-i
				Graphics g <- mc.getGraphics()
				mc.fillColor(g, current, i)
				if isOK(province) 
					current++
					j <- color(province,n)
					if j==-1 
						current--
						province[current]<--1
					if current>n  return 1
		if i>=4  return -1;
		return 1;
 
5.3 算法实现与复杂度分析 
数据结构：数组metrix，Polygon
 
实现步骤：
 
 
遍历，确认当前城市能否被染色
 
 
开始着色
 
 
递归到下一个城市进行着色
 
 
若当前城市不可被着某色就进行回溯
 
 
所有城市递归着色完成则终止递归
 
 
实现技巧：可以设置时延来控制动画演示的时间延时，以达到单步运行展示的目的
 
时间复杂度：O（n*(m^n)），m指所用颜色种类总数，n指城市数
 
5.4 程序实现及运行结果分析 
程序实现的详细完整过程：
 
 
初始化34个城市
 
 
面板布局，设置背景，设置各种控件的尺寸大小并添加进面板指定位置
 
 
用户设置颜色。
 
 
用户根据所需点击面板上的对应的功能按钮，实现相应的算法功能展示。
 
 
运行结果及测试分析：
 
静态地图着色
 
 
动画展示地图着色：
 

 
 
分析：
 
该算法程序能较好形象地解决地图着色问题，但是在某些城市递归时会不断循环碰壁而消耗大量的时间，导致一个低效率的运行结果，因此该程序还需要很多优化的地方。
 
资源下载地址：https://download.csdn.net/download/sheziqiong/86168456
 资源下载地址：https://download.csdn.net/download/sheziqiong/86168456
                
                
                
        
        

  
    
      
        
      
      
        
          暑期编程PK赛
          
        
        得CSDN机械键盘等精美礼品！