南京邮电大学算法设计实验报告——动态规划法
- 格式:docx
- 大小:86.45 KB
- 文档页数:12
TSP问题算法实验报告指导教师:****名:***学号:**********提交日期:2015年11月目录总述 (2)动态规划法 (3)算法问题分析 (3)算法设计 (3)实现代码 (3)输入输出截图 (6)OJ提交截图 (6)算法优化分析 (6)回溯法 (6)算法问题分析 (6)算法设计 (7)实现代码 (7)输入输出截图 (9)OJ提交截图 (9)算法优化分析 (10)分支限界法 (10)算法问题分析 (10)算法设计 (10)实现代码 (10)输入输出截图 (15)OJ提交截图 (15)算法优化分析 (15)总结 (16)总述TSP问题又称为旅行商问题,是指一个旅行商要历经所有城市一次最后又回到原来的城市,求最短路程或最小花费,解决TSP可以用好多算法,比如蛮力法,动态规划法…具体的时间复杂的也各有差异,本次实验报告包含动态规划法,回溯法以及分支限界法。
动态规划法算法问题分析假设n个顶点分别用0~n-1的数字编号,顶点之间的代价存放在数组mp[n][n]中,下面考虑从顶点0出发求解TSP问题的填表形式。
首先,按个数为1、2、…、n-1的顺序生成1~n-1个元素的子集存放在数组x[2^n-1]中,例如当n=4时,x[1]={1},x[2]={2},x[3]={3},x[4]={1,2},x[5]={1,3},x[6]={2,3},x[7]={1,2,3}。
设数组dp[n][2^n-1]存放迭代结果,其中dp[i][j]表示从顶点i经过子集x[j]中的顶点一次且一次,最后回到出发点0的最短路径长度,动态规划法求解TSP问题的算法如下。
算法设计输入:图的代价矩阵mp[n][n]输出:从顶点0出发经过所有顶点一次且仅一次再回到顶点0的最短路径长度1.初始化第0列(动态规划的边界问题)for(i=1;i<n;i++)dp[i][0]=mp[i][0]2.依次处理每个子集数组x[2^n-1]for(i=1;i<n;i++)if(子集x[j]中不包含i)对x[j]中的每个元素k,计算d[i][j]=min{mp[i][k]+dp[k][j-1]};3.输出最短路径长度。
第1篇一、实验目的1. 理解动态规划的基本思想和方法。
2. 掌握动态规划在解决实际问题中的应用。
3. 提高编程能力和算法设计能力。
二、实验内容本次实验主要涉及以下四个问题:1. 斐波那契数列2. 最长公共子序列3. 最长递增子序列4. 零钱找零问题三、实验原理动态规划是一种在数学、管理科学、计算机科学、经济学和生物信息学等领域中使用的,通过把原问题分解为相对简单的子问题的方式求解复杂问题的方法。
动态规划的基本思想是将一个复杂问题分解成若干个相互重叠的子问题,然后按照子问题的顺序逐个求解,最后将这些子问题的解合并成原问题的解。
四、实验步骤及代码实现1. 斐波那契数列斐波那契数列是指这样一个数列:1, 1, 2, 3, 5, 8, 13, 21, ...,其中每个数都是前两个数的和。
```cppinclude <iostream>using namespace std;int Fibonacci(int n) {if (n <= 1) {return 1;}int fib[n+1];fib[0] = 1;fib[1] = 1;for (int i = 2; i <= n; i++) {fib[i] = fib[i-1] + fib[i-2];}return fib[n];}int main() {int n;cout << "请输入斐波那契数列的项数:" << endl;cin >> n;cout << "斐波那契数列的第 " << n << " 项为:" << Fibonacci(n) << endl;return 0;}```2. 最长公共子序列给定两个序列A和B,找出它们的公共子序列中长度最长的序列。
```cppinclude <iostream>using namespace std;int LCSLength(string X, string Y) {int m = X.length();int n = Y.length();int L[m+1][n+1];for (int i = 0; i <= m; i++) {for (int j = 0; j <= n; j++) {if (i == 0 || j == 0)L[i][j] = 0;else if (X[i-1] == Y[j-1])L[i][j] = L[i-1][j-1] + 1;elseL[i][j] = max(L[i-1][j], L[i][j-1]);}}return L[m][n];}int main() {string X = "AGGTAB";string Y = "GXTXAYB";cout << "最长公共子序列长度为:" << LCSLength(X, Y) << endl; return 0;}```3. 最长递增子序列给定一个序列,找出它的最长递增子序列。
动态规划实验报告动态规划实验报告一、引言动态规划是一种常用的算法设计方法,广泛应用于计算机科学和运筹学等领域。
本实验旨在通过实际案例,探究动态规划算法的原理和应用。
二、实验背景动态规划算法是一种通过将问题分解为子问题,并存储子问题的解来解决复杂问题的方法。
它通常适用于具有重叠子问题和最优子结构性质的问题。
三、实验目的1. 理解动态规划算法的基本原理;2. 掌握动态规划算法的实现方法;3. 分析动态规划算法在实际问题中的应用。
四、实验过程本实验选择了经典的背包问题作为案例进行分析。
背包问题是一个组合优化问题,给定一个背包的容量和一系列物品的重量和价值,如何选择物品放入背包,使得背包中物品的总价值最大化。
1. 确定状态在动态规划算法中,状态是问题的关键。
对于背包问题,我们可以将状态定义为背包的容量和可选择的物品。
2. 确定状态转移方程状态转移方程是动态规划算法的核心。
对于背包问题,我们可以定义一个二维数组dp[i][j],表示在背包容量为j的情况下,前i个物品的最大总价值。
则状态转移方程可以表示为:dp[i][j] = max(dp[i-1][j], dp[i-1][j-w[i]] + v[i])其中w[i]表示第i个物品的重量,v[i]表示第i个物品的价值。
3. 初始化边界条件在动态规划算法中,边界条件是必不可少的。
对于背包问题,边界条件可以定义为当背包容量为0时,无论物品如何选择,总价值都为0。
4. 递推求解根据状态转移方程和边界条件,我们可以通过递推的方式求解问题。
具体步骤如下:- 初始化dp数组;- 逐行逐列计算dp数组的值,直到得到最终结果。
五、实验结果与分析通过实验,我们得到了背包问题的最优解。
同时,我们还可以通过分析dp数组的取值,了解到每个状态下的最优选择。
这为我们提供了在实际问题中应用动态规划算法的思路。
六、实验总结本实验通过对动态规划算法的实际案例进行分析,深入理解了动态规划算法的原理和应用。
动态规划法动态规划法(Dynamic Programming)是一种常用的算法思想,主要用于解决具有重叠子问题性质和最优子结构性质的问题。
动态规划法通过把问题分解为更小的子问题,并将子问题的解存储起来,以避免重复计算,从而提高了算法的效率。
动态规划法有两个核心概念:状态和状态转移方程。
在动态规划过程中,我们需要定义状态,即问题的子问题解,以及状态之间的关系,即状态转移方程。
动态规划法的一般步骤如下:1. 定义问题的子问题:将问题划分为更小的子问题,并明确子问题的解是什么。
2. 定义状态:将问题的子问题解抽象为状态,即用一个变量或者数组表示子问题的解。
3. 定义状态转移方程:根据子问题的关系,定义状态之间的转移方程,即如何根据已知的子问题解计算出更大的问题的解。
4. 缓存子问题解:为了避免重复计算,我们需要将已经计算过的子问题解存储起来,以便后续使用。
5. 递推计算:通过状态转移方程和缓存的子问题解,逐步计算出更大的问题的解,直到计算出最终的问题解。
动态规划法的关键在于找到正确的状态转移方程和合理的存储子问题解的方式。
有些问题的状态转移方程比较容易找到,比如斐波那契数列,每个数都是前两个数的和;而有些问题的状态转移方程可能比较复杂,需要通过观察问题的特点和具体分析来确定。
动态规划法的时间复杂度通常为O(n),其中n 表示问题规模。
由于利用了子问题的解,避免了重复计算,因此动态规划法相对于暴力求解法能够大大提高算法的效率。
但是,动态规划法的空间复杂度通常较高,需要存储大量的子问题解,因此在实际应用中需要权衡时间和空间的消耗。
总的来说,动态规划法是一种非常灵活且强大的算法思想,能够解决许多复杂的问题,特别适用于具有重叠子问题性质和最优子结构性质的问题。
通过正确定义状态和状态转移方程,并结合缓存子问题解和递推计算,我们可以高效地求解这类问题,提高算法的效率。
第1篇一、实验背景与目的随着计算机技术的飞速发展,算法在计算机科学中扮演着至关重要的角色。
为了加深对算法设计与分析的理解,提高实际应用能力,本实验课程设计旨在通过实际操作,让学生掌握算法设计与分析的基本方法,学会运用所学知识解决实际问题。
二、实验内容与步骤本次实验共分为三个部分,分别为排序算法、贪心算法和动态规划算法的设计与实现。
1. 排序算法(1)实验目的:熟悉常见的排序算法,理解其原理,比较其优缺点,并实现至少三种排序算法。
(2)实验内容:- 实现冒泡排序、快速排序和归并排序三种算法。
- 对每种算法进行时间复杂度和空间复杂度的分析。
- 编写测试程序,对算法进行性能测试,比较不同算法的优劣。
(3)实验步骤:- 分析冒泡排序、快速排序和归并排序的原理。
- 编写三种排序算法的代码。
- 分析代码的时间复杂度和空间复杂度。
- 编写测试程序,生成随机测试数据,测试三种算法的性能。
- 比较三种算法的运行时间和内存占用。
2. 贪心算法(1)实验目的:理解贪心算法的基本思想,掌握贪心算法的解题步骤,并实现一个贪心算法问题。
(2)实验内容:- 实现一个贪心算法问题,如活动选择问题。
- 分析贪心算法的正确性,并证明其最优性。
(3)实验步骤:- 分析活动选择问题的贪心策略。
- 编写贪心算法的代码。
- 分析贪心算法的正确性,并证明其最优性。
- 编写测试程序,验证贪心算法的正确性。
3. 动态规划算法(1)实验目的:理解动态规划算法的基本思想,掌握动态规划算法的解题步骤,并实现一个动态规划算法问题。
(2)实验内容:- 实现一个动态规划算法问题,如背包问题。
- 分析动态规划算法的正确性,并证明其最优性。
(3)实验步骤:- 分析背包问题的动态规划策略。
- 编写动态规划算法的代码。
- 分析动态规划算法的正确性,并证明其最优性。
- 编写测试程序,验证动态规划算法的正确性。
三、实验结果与分析1. 排序算法实验结果:- 冒泡排序:时间复杂度O(n^2),空间复杂度O(1)。
TSP问题算法实验报告指导教师:季晓慧姓名:辛瑞乾学号: 1004131114 提交日期: 2015年11月目录总述 (2)动态规划法 (3)算法问题分析 (3)算法设计 (3)实现代码 (3)输入输出截图 (6)OJ提交截图 (6)算法优化分析 (6)回溯法 (6)算法问题分析 (6)算法设计 (7)实现代码 (7)输入输出截图 (9)OJ提交截图 (10)算法优化分析 (10)分支限界法 (10)算法问题分析 (10)算法设计 (10)实现代码 (11)输入输出截图 (15)OJ提交截图 (16)算法优化分析 (16)总结 (16)总述TSP问题又称为旅行商问题,是指一个旅行商要历经所有城市一次最后又回到原来的城市,求最短路程或最小花费,解决TSP可以用好多算法,比如蛮力法,动态规划法…具体的时间复杂的也各有差异,本次实验报告包含动态规划法,回溯法以及分支限界法。
动态规划法算法问题分析假设n个顶点分别用0~n-1的数字编号,顶点之间的代价存放在数组mp[n][n]中,下面考虑从顶点0出发求解TSP问题的填表形式。
首先,按个数为1、2、…、n-1的顺序生成1~n-1个元素的子集存放在数组x[2^n-1]中,例如当n=4时,x[1]={1},x[2]={2},x[3]={3},x[4]={1,2},x[5]={1,3},x[6]={2,3},x[7]={1,2,3}。
设数组dp[n][2^n-1]存放迭代结果,其中dp[i][j]表示从顶点i经过子集x[j]中的顶点一次且一次,最后回到出发点0的最短路径长度,动态规划法求解TSP问题的算法如下。
算法设计输入:图的代价矩阵mp[n][n]输出:从顶点0出发经过所有顶点一次且仅一次再回到顶点0的最短路径长度1.初始化第0列(动态规划的边界问题)for(i=1;i<n;i++)dp[i][0]=mp[i][0]2.依次处理每个子集数组x[2^n-1]for(i=1;i<n;i++)if(子集x[j]中不包含i)对x[j]中的每个元素k,计算d[i][j]=min{mp[i][k]+dp[k][j-1]};3.输出最短路径长度。
第1篇一、实验目的通过本次实验,掌握常见算法的设计原理、实现方法以及性能分析。
通过实际编程,加深对算法的理解,提高编程能力,并学会运用算法解决实际问题。
二、实验内容本次实验选择了以下常见算法进行设计和实现:1. 排序算法:冒泡排序、选择排序、插入排序、快速排序、归并排序、堆排序。
2. 查找算法:顺序查找、二分查找。
3. 图算法:深度优先搜索(DFS)、广度优先搜索(BFS)、最小生成树(Prim算法、Kruskal算法)。
4. 动态规划算法:0-1背包问题。
三、实验原理1. 排序算法:排序算法的主要目的是将一组数据按照一定的顺序排列。
常见的排序算法包括冒泡排序、选择排序、插入排序、快速排序、归并排序和堆排序等。
2. 查找算法:查找算法用于在数据集中查找特定的元素。
常见的查找算法包括顺序查找和二分查找。
3. 图算法:图算法用于处理图结构的数据。
常见的图算法包括深度优先搜索(DFS)、广度优先搜索(BFS)、最小生成树(Prim算法、Kruskal算法)等。
4. 动态规划算法:动态规划算法是一种将复杂问题分解为子问题,通过求解子问题来求解原问题的算法。
常见的动态规划算法包括0-1背包问题。
四、实验过程1. 排序算法(1)冒泡排序:通过比较相邻元素,如果顺序错误则交换,重复此过程,直到没有需要交换的元素。
(2)选择排序:每次从剩余元素中选取最小(或最大)的元素,放到已排序序列的末尾。
(3)插入排序:将未排序的数据插入到已排序序列中适当的位置。
(4)快速排序:选择一个枢纽元素,将序列分为两部分,使左侧不大于枢纽,右侧不小于枢纽,然后递归地对两部分进行快速排序。
(5)归并排序:将序列分为两半,分别对两半进行归并排序,然后将排序好的两半合并。
(6)堆排序:将序列构建成最大堆,然后重复取出堆顶元素,并调整剩余元素,使剩余元素仍满足最大堆的性质。
2. 查找算法(1)顺序查找:从序列的第一个元素开始,依次比较,直到找到目标元素或遍历完整个序列。
现代控制理论学习报告动态规划法1、概述:动态规划(dynamic programming)是运筹学的一个分支,是求解决策过程最优化的数学方法。
20世纪50年代初美国数学家R.E.Bellman等人在研究多阶段决策过程(multistep decision process)的优化问题时,提出了著名的最优化原理(principle of optimality),把多阶段过程转化为一系列单阶段问题,利用各阶段之间的关系,逐个求解,创立了解决这类过程优化问题的新方法——动态规划。
本文简要介绍了动态规划的基本概念,并通过一个实例说明其在现实生活中的应用。
2、基本思想:动态规划算法通常用于求解具有某种最优性质的问题。
在这类问题中,可能会有许多可行解。
每一个解都对应于一个值,我们希望找到具有最优值的解。
其基本思想也是将待求解问题分解成若干个子问题,先求解子问题,然后从这些子问题的解得到原问题的解。
与分治法不同的是,适合于用动态规划求解的问题,经分解得到子问题往往不是互相独立的。
若用分治法来解这类问题,则分解得到的子问题数目太多,有些子问题被重复计算了很多次。
如果我们能够保存已解决的子问题的答案,而在需要时再找出已求得的答案,这样就可以避免大量的重复计算,节省时间。
动态规划的实质是分治思想和解决冗余,因此,动态规划是一种将问题实例分解为更小的、相似的子问题,并存储子问题的解而避免计算重复的子问题,以解决最优化问题的算法策略。
该方法主要应用于最优化问题,这类问题会有多种可能的解,每个解都有一个值,而动态规划找出其中最优(最大或最小)值的解。
若存在若干个取最优值的解的话,它只取其中的一个。
但是首先要保证该问题的无后效性,即无论当前取哪个解,对后面的子问题都没有影响.在求解过程中,该方法也是通过求解局部子问题的解达到全局最优解,但与分治法和贪心法不同的是,动态规划允许这些子问题不独立,(亦即各子问题可包含公共的子子问题)也允许其通过自身子问题的解作出选择,该方法对每一个子问题只解一次,并将结果保存起来,避免每次碰到时都要重复计算。
实验二动态规划算法一、实验目的与要求1、熟悉最长公共子序列问题的算法;2、初步掌握动态规划算法;二、实验题若给定序列X={x1,x2,…,xm},则另一序列Z={z1,z2,…,zk},是X的子序列是指存在一个严格递增下标序列{i1,i2,…,ik}使得对于所有j=1,2,…,k有:zj=xij。
例如,序列Z={B,C,D,B}是序列X={A,B,C,B,D,A,B}的子序列,相应的递增下标序列为{2,3,5,7}。
给定2个序列X和Y,当另一序列Z既是X的子序列又是Y的子序列时,称Z 是序列X和Y的公共子序列。
给定2个序列X={x1,x2,…,xm}和Y={y1,y2,…,yn},找出X和Y的最长公共子序列。
三.(1)实验源代码://最长公共子序问题://问题描述: 若给定序列X={x1,x2,…,xm},则另一序列Z={z1,z2,…,zk},//是X的子序列是指存在一个严格递增下标序列{i1,i2,…,ik}使得对于所有j=1,2,…,k有:zj=xij。
//例如,序列Z={B,C,D,B}是序列X={A,B,C,B,D,A,B}的子序列,相应的递增下标序列为{2,3,5,7}。
//给定2个序列X和Y,当另一序列Z既是X的子序列又是Y的子序列时,称Z 是序列X和Y的公共子序列。
//给定2个序列X={x1,x2,…,xm}和Y={y1,y2,…,yn},找出X和Y的最长公共子序列。
#include<bits/stdc++.h>using namespace std;#define max 1000//注意:这里使用的char数组,可以按字符输出,若改为string类型,//执行printf("%c",A[m-1])就会报错;char A[100],B[100]; //输入的两个串a和b//这里定义全局变量可以不赋值0,因为全局变量自动赋值0;int c[max][max]; //记录最长公共子序的长度;int b[max][max]; //记录状态号;void LCS(int m,int n){if(m==0||n==0){return;else if(b[m][n]==1){LCS(m-1,n-1);printf("%c",A[m-1]);}else if(b[m][n]==2){m=m-1;LCS(m,n);}else if(b[m][n]==3){n=n-1;LCS(m,n);}}void LCS_length(int m,int n){for(int i=1;i<=m;i++){for(int j=1;j<=n;j++){if(A[i-1]==B[j-1]){c[i][j]=c[i-1][j-1]+1;b[i][j]=1;}else if(c[i-1][j]>=c[i][j-1]){c[i][j]=c[i-1][j];b[i][j]=2;}else{c[i][j]=c[i][j-1];b[i][j]=3;}}}}{printf("请输入两个待测的字符串:\n");scanf("%s",&A);scanf("%s",&B);int m=strlen(A); //m为A串长度;int n=strlen(B); //n为B串长度;LCS_length(m,n);printf("其最长公共子序的长度为:%d\n",c[m][n]);printf("其最长公共子序为:");LCS(m,n);return 0;}(2)运行结果为:(3)算法思路:最长公共子序列的结构有如下表示:设序列X=<x1, x2, …, x m>和Y=<y1, y2, …, y n>的一个最长公共子序列Z=<z1, z2, …, z k>,则:1.若x m=y n,则z k=x m=y n且Z k-1是X m-1和Y n-1的最长公共子序列;2.若x m≠y n且z k≠x m ,则Z是X m-1和Y的最长公共子序列;3.若x m≠y n且z k≠y n,则Z是X和Y n-1的最长公共子序列。
实验报告2.2(递归法)学号:201208070103 姓名:陈明班级:智能1201第16 周课程名称算法设计与分析实验课时 2实验项目整数因子分解问题实验时间2015年1月10日实验目的对于给定的正整数n,计算n共有多少种不同的分解式。
实验环境Eclipse Luna, Java JDK1.7, Windows 8.1实验内容(算法、程序、步骤和方法)一、算法策略动态规划法。
把1~number的约数预先存起来,需要用得时候,直接在前面取得。
二、算法设计(步骤)1)把number的约数全部计算出来,存储在factor数组里面。
2)使用快速排序法QuickSort把factor按升序排序3)使用动态规划法。
把0~number的分解式的个数存在recordNum数组里面。
三、复杂度分析1)时间复杂度:首先时计算约数因子,其次是快速排序,最后是动态规划,这三步伟主要耗时。
故时间复杂T(n)=O(n)+O(n*log n)+O(k) (其中k为number 的约数个数,故为常数级别)。
故T(n)<O(n*log n)+ O(n*log n)=2 O(n*log n)故该算法的时间复杂度为 O(n*log n)2)空间复杂度:O(n)1)从控制台console输入数字,java封装类Scanner获得输入流;2)获得的数字,赋值给number数据记录和计算1)number=12时:2)number=11时:结论(结果)3)number=888888时:小结1)动态规划法相对于递归法来说,当输入规模很大时,应该考虑动态规划法;2)进行两个种方法的对比:Number=888888动态规划法:递归法:T(动态规划)=30毫秒,T(递归策略)=263毫秒显然,从耗时上来看,动态规划法要优于递归策略!指导老师评议成绩评定:指导教师签名:。
一、实验目的本次实验旨在通过实际操作,加深对算法理论知识的理解,提高算法设计与分析能力,培养解决实际问题的能力。
通过实验,使学生掌握以下内容:1. 理解常见算法的基本原理和实现方法;2. 掌握算法设计与分析的常用方法;3. 能够运用算法解决实际问题。
二、实验内容本次实验选择了以下两个算法进行实现和分析:1. 冒泡排序算法;2. 快速排序算法。
三、实验过程1. 冒泡排序算法(1)算法原理冒泡排序是一种简单的排序算法,它重复地遍历要排序的数列,一次比较两个元素,如果它们的顺序错误就把它们交换过来。
遍历数列的工作是重复地进行,直到没有再需要交换,也就是说该数列已经排序完成。
(2)实现步骤① 初始化一个布尔变量 swapped,用于判断是否发生交换;② 遍历数组,比较相邻的两个元素,如果前者大于后者,则交换它们的位置;③ 如果在一轮遍历中没有发生交换,则说明数组已经排序完成,退出循环;④ 重复步骤②和③,直到数组排序完成。
(3)代码实现```pythondef bubble_sort(arr):n = len(arr)for i in range(n):swapped = Falsefor j in range(0, n-i-1):if arr[j] > arr[j+1]:arr[j], arr[j+1] = arr[j+1], arr[j]swapped = Trueif not swapped:breakreturn arr```2. 快速排序算法(1)算法原理快速排序是一种分而治之的排序算法。
基本思想是:通过一趟排序将要排序的数据分割成独立的两部分,其中一部分的所有数据都比另一部分的所有数据要小,然后再按此方法对这两部分数据分别进行快速排序,整个排序过程可以递归进行,以此达到整个数据变成有序序列。
(2)实现步骤① 选择一个基准值(pivot),可以是数组的第一个元素、最后一个元素或中间元素;② 将数组分为两部分,一部分是小于基准值的元素,另一部分是大于基准值的元素;③ 对这两部分数据分别进行快速排序;④ 递归执行步骤①至③,直到数组排序完成。
算法实现程序设计报告一.问题描述输入N个点的坐标,判断这N个点能否构成一个凸多边形。
二.课题分析根据2点确定一条直线的原理,即y-y1/x-x1=y2-y1/x2-x1;移向得x(y2-y1)+y(x1-x2)-x1y2+x2y1, 设t= x(y2-y1)+y(x1-x2)-x1y2+x2y1,假如可组成凸多边形,且假设两点是图多边形一边,则把其他N-2点带入, 得到的t必均为正或均为负.由此可判断任意2点是否为凸多边形的一条边.由任意点开始寻找能够与其组成边的点,若按顺序能够找到N点则其为凸多边形,反之则不能.三.设计思路输入N个点,用二维数组存储这N个点, 定义real函数判断N个点是否能构成凸多边形,从第一个点开始能够找到N条满足函数tt的边则为图多边形.tt 为判断2点能否够成图多边形边的函数.四.处理流程图#include<stdio.h>#define N 4int tt(int p[][2],int a,int b){int temp[N],k=0;int t;int i;int j;for(i=0;i<N;i++){if(i==a||i==b){continue;}t=p[i][0]*(p[b][1]-p[a][1])+(p[a][0]-p[b][0])*p[i][1]-p[a][0]*p[b][1]+p[b][0]*p[a][1]; if(t==0)return 0;elseif(t>0)temp[k++]=1;elsetemp[k++]=-1;}for(j=1;j<k;j++){if(temp[0]!=temp[j]) return 0;}return 1;}int real(int p[][2]){int flag[N],m=0;int i,j;for(i=0;i<N;i++){flag[i]=0;}for( i=0;i<N;i++){for(j=1;j<N;j++){if(flag[j]) continue;if(tt(p,m,j)){flag[m]=1;m=j;break;}}}flag[m]=1;for(i=0;i<N;i++){if(flag[i]==0)return 0;}if(tt(p,0,m)) return 1;return 0;}void main(){int p[N][2];int i;printf("请输入这N个点坐标:\n");for(i=0;i<N;i++){printf("第%d个点坐标:",i+1);scanf("%d,%d",&p[i][0],&p[i][1]);printf("%d,%d\n",p[i][0],p[i][1]);}if (real(p))printf("能");elseprintf("不能");}六.程序测试记录:第一次:欢迎使用,本系统尚在试用阶段,有问题请与作者联系!请选择您的登陆方式( 1 :管理员 2 :普通用户)请输入您的用户名: zhaoyan请输入您的密码:haiyang您的用户名或密码有误,无法登陆!Press any key to continue第二次:欢迎使用,本系统尚在试用阶段,有问题请与作者联系! 请选择您的登陆方式( 1 :管理员 2 :普通用户)请输入您的用户名: yinjuan请输入您的密码:09005512请选择你要的操作:1:输入点的坐标2.运行程序3.判断能否构成凸多边形4:删除数据5:退出系统七.课程设计总结:算法实现的程序设计课是学校安排的自己动手的程序设计!自己发现问题、解决问题,使我对C和C++的操作有了进一步的掌握。
算法分析与设计实验报告实验题目: 动态规划算法的设计与实现1、实验目的通过本实验,掌握动态规划算法的设计的基本思想,进一步提高学生的编程能力。
2、实验内容:给定n个矩阵{A1,A2,…,A n},其中A i与A i+1就是可乘的,i=1,2…,n-1。
如何确定计算矩阵连乘积的计算次序,使得依此次序计算矩阵连乘积需要的数乘次数最少。
3、源程序if (t<u) //返回t,k中较小的值,并记录断点处k{ u=t; s[i][j]=k;} }return u; }int Look(int i,int j) //备忘录计算最优值{ if (m[i][j]>0){ return m[i][j]; }if (i == j) return 0;int u=Look(i, i)+Look(i+1,j)+p[i-1]*p[i]*p[j]; s[i][j]=i;for (int k=i+1; k<j;k++){ int t=Look(i,k)+Look(k+1,j)+p[i-1]*p[k]*p[j]; //递归if (t<u){ u=t; //从k处断开,分别求得每次的数乘次数s[i][j]=k; //返回t,k中较小的值,并记录断点处k} } m[i][j]=u;return u; }void Traceback(int i,int j) { //输出矩阵结合方式,加括号输出if(i == j) //只有一个矩阵,直接输出{ cout<<"A"<<i; }else if(i+1 == j) //两个矩阵,加括号输出{ cout<<"(A"<<i<<"A"<<j<<")"; }else{ cout<<"("; Traceback(i,s[i][j]); //递归,从最得到最优解的地方s[i][j]处断开Traceback(s[i][j]+1,j);cout<<")"; } }void main(){ cout<<"输入矩阵个数:n=";cin>>n; cout<<"输入第一个矩阵行数与第一个到第n个矩阵的列数:"; for(int i=0;i<=n;i++){ cin>>p[i]; } cout<<endl; cout<<"请选择解决矩阵连乘问题的方法:"<<endl; cout<<"1、动态规划算法"<<endl; cout<<"2、直接递归算法"<<endl; cout<<"3、备忘录算法"<<endl;cout<<"0、退出、、、"<<endl;cout<<endl;cout<<"请选择算法:";cin>>q; cout<<endl;while(q!=0){ switch(q){case 1: matrixChain(); cout<<"动态规划算法解决矩阵连乘问题:"<<endl; cout<<"最优计算次序为:";Traceback(1,n); cout<<endl; cout<<"矩阵连乘的最优数乘次数为:"<<m[1][n]<<endl; //最终解值为m[1][n]break;case 2: Recur(0,n); cout<<"直接递归算法解决矩阵连乘问题:"<<endl;cout<<"最优计算次序为:";Traceback(1,n);cout<<endl; cout<<"矩阵连乘的最优数乘次数为:"<<m[1][n]<<endl; //最终解值为m[1][n]break;case 3: Look(1,n); cout<<"备忘录算法解决矩阵连乘问题:"<<endl;cout<<"最优计算次序为:";Traceback(1,n);cout<<endl; cout<<"矩阵连乘的最优数乘次数为:"<<m[1][n]<<endl; //最终解值为m[1][n]break;case 0:q=0; break; }cout<<endl; cout<<"请选择解决矩阵连乘问题的方法:"<<endl; cout<<"1、动态规划算法"<<endl; cout<<"2、直接递归算法"<<endl; cout<<"3、备忘录算法"<<endl;cout<<"0、退出、、、"<<endl;cout<<"请选择算法:";cin>>q;cout<<endl; }cout<<endl; }5、结论动态规划算法设计通常有四个步骤:1.找出最优解的性质,并刻画其结构特征。