XXXX大学
算法设计与分析课程设计报告
院（系）:
年级：
姓名：
专业：计算机科学与技术
研究方向：互联网与网络技术
指导教师：
X X X X 大学
目录
题目1 电梯调度 (1)
1.1 题目描述 (1)
1。2 算法文字描述 (1)
1。3 算法程序流程 (4)
1.4 算法的程序实现代码 (8)
题目2 切割木材 (10)
2.1题目描述 (10)
2。2算法文字描述 (10)
2.3算法程序流程 (11)
2.4算法的程序实现代码 (15)
题目3 设计题 (17)
3.1题目描述 (17)
3.2 输入要求 (17)
3.3输出要求 (17)
3.4样例输入 (17)
3.5样例输出 (17)
3.6测试样例输入 (17)
3。7测试样例输出 (18)
3。8算法实现的文字描述 (18)
3。9算法程序流程 (19)
3.10算法的程序实现代码 (20)
算法分析与设计课程总结 (23)
参考文献 (24)
题目1 电梯调度
1。1 题目描述
一栋高达31层的写字楼只有一部电梯,其中电梯每走一层需花费4秒，并且在每一层楼停靠的时间为10秒，乘客上下一楼需要20秒,在此求解最后一位乘客到达目的楼层的最短时间以及具体的停靠计划.例如:此刻电梯停靠需求为4 5 10(有三位乘客,他们分别想去4楼、5楼和10楼），如果在每一层楼都停靠则三位乘客到达办公室所需要的时间为3*4=12秒、4*4+10=26秒、4＊9+2＊10=56秒,则最后一位乘客到达办公室的时间为56秒，相应的停靠计划为4 5 10均停靠。对于此测试用例电梯停靠计划方案：4 10,这样到第4楼的乘客所需时间为3*4=12秒,到第5楼的乘客所需时间为3*4+20=32秒,到第10楼的乘客所需时间为9*4+10=46秒，即最后到达目的楼层的顾客所需时间为46秒.
输入要求：
输入的第1行为整数n f1 f2 … fn，其中n表示有n层楼需要停靠,n=0表示没有更多的测试用例，程序终止运行。f1 f2 … fn表示需要停靠的楼层（n 〈=30，2<=f1 输出要求： 对于每一个测试用例,第1行输出最后一位乘客到达目的楼层所需时间,第2行输出停靠次数和相应的停靠方案，每一个数字用一个空格隔开。 1.2 算法文字描述 程序实现的算法思想，将待求解问题分解成若干个子问题,先求解子问题，然后从这些子问题的解得到远问题的解.与分治法不同的是，适合用动态规划发求解的子问题往往不是相互独立。若用分治法求解这类问题，则分解的子问题数目太多，以至于最后解决原问题需要耗费指数时间。然而，不同子问题的数目常常是多项式量级。在分治法求解时,有些子问题被重复计算了许多次。如果能够保存已解决的子问题的答案，而在需要时在找出以求得的答案,就可以避免大量重复计算，从而得到多项式时间算法.为了达到这个目的，可以采用一个表来记录所有已解决的子问题的答案。不管子问题以后是否被使用，只要他被计算过，就将其结果填入表中。动态规划算法适合求解最优化问题，设计动态规划算法的具体步骤如下：○，1找出最优解的性质，并刻画其结构;错误!递归地定义最优值；错误!以自底向上的方式计算最优值；错误!根据计算最优值时得到的信息，构造最优解. 例如：给定金额n以及1，2，5分硬币，求找n的最少硬币数。 对于大于1分的找零理所当然可以找零1分，大于2分和5分的找零与此类似，那么找零时就有三种选择，即找零后剩余金额为n-1，n-2，n-5，这三种选择总的找零数最少的方案即为所求解的方案。显然，最终的找零方案与执行当前选择后剩余的金额的找零相关，即金额n的最优找零方案包含了金额n—1，n-2，n—5的最优找零方案，于是可得如下状态转移方程: 具体的求解过程： 初始化F（1)=1，F（2），F（5）=1 F(1) 1 F（2） 1 F(3）min｛F（2）+1,F（1)+1}=2 F（4) min{F(2）+1，F（3）+1｝=2 F（5) 1 F（6）min｛F（1）+1,F（4)+1,F(1)+1｝ =2 … F（n）min｛F(n—1)+1，F（n-2)+1，F （n—5）+1｝ 算法设计思路及求解过程 思路:题目所描述的整个过程是“并行的”,而且所有人到达各自楼层的用时只与最晚到达的人有关.由于去各个楼层的具体数目对结果没有影响,所以可以将“电梯还剩i个人”表述成“电梯里面的乘客还要去i个楼层”.电梯从第1层开始向上运行，任意时刻的状态都可以由“电梯当前所处楼层"和“电梯里面都有哪些乘客确定”，初始状态为“电梯在1楼”和“所有乘客都在电梯上". 在电梯运行的每一个阶段都需要作出相应的决策，哪些乘客乘坐电梯到目的层，哪些乘客选择爬楼梯到达目的地.决策后,电梯里面的乘客被分成两部分:乘客留在电梯里面继续上升；乘客离开电梯走楼梯到达。求当前状态下电梯里面的乘客所有人到达目的所需要的最短时间，只需要找到一个最优决策，使得下电梯的乘客和留在电梯中的乘客最晚到达时间越短越好，这个最短时间就是当前状态 下的最优解。如果假设决策后留在电梯里面的乘客到达各自楼层所需要的时间为T1，离开电梯的各自到达目的地所需时间为T2,则min ｛max （T1,T2）｝就是当前状态的最优解，其中T1可以由“当前层数+1”和“决策后剩下的人”确定的状态得到;T2则为下电梯走楼梯到达目的走楼梯最多的那一位乘客所花时间. 如果去第k 层的乘客选择在当前楼层下电梯，那么第1，2…k -1层的乘客也应该选择在此时下电梯（如图 1所示），这样就可以得到当前决策下的一个最优解。 为了进一步处理停靠请求，对楼层按从高到低进行排序,并以此进行编号，如此可以避免在求解过层中处理不连续的请求,如：4，5,10。使用i ，j 两个参数表示电梯当前的状态，即电梯在第i 层，电梯中有j 位乘客. 综上所述，可得如下状态转移方程 : f （i ，j)表示电梯在第i 层楼时，电梯中j 个人都到达目的地所需要的最短时间. 具体求解过程： 第一步：计算初始状态f （topFloor ，1)，f(topFloor,2），…，f(topFloor,n ）； 第二步：根据状态转移方程计算f （i,j)； 1 无论电梯当前位于何处 2 n k … 3 … 第k 楼的乘客选择在 此下电梯 k-1 k 层以下的乘客此刻都应离开电梯 图 1 解题结论 第三步：根据计算最优值时记录的信息求解最优解. 1。3 算法程序流程 图 2 Input函数流程图 图 4 main函数流程图 图 3 solve函数流程图 图 5 calculate函数流程图 图7 tLeave函数流程图 图 6 tStay函数流程图 1。4 算法的程序实现代码 ＃include ＃include # include #include # include #include〈vector〉 using namespace std; const int maxN=30,maxF=31; // 电梯上一层楼所需时间，电梯每次停靠时长,人走一层楼所需时间 const int ve=4，st=10，vw=20; int n,f［maxN+1］； //数据读取 bool input(）｛ cin〉〉n; if(n==0) return false; // 注意：f［1.。.n］中楼层数从高到低排列 for(int i=n;i〉=1；i——） cin>〉f[i]; return true； ｝ int dp［maxF+1］［maxN+1］,nextJ［maxF+1]［maxN+1]； // 目前电梯在第currF层, 第L层到第R层乘客离开电梯 // 函数返回这些离开电梯的乘客中最晚到达目的层所需时间 int tLeave(int currF，int l，int r）{ if(l>r) return 0； // 仅需考虑两端, 无论此刻电梯在何处, 第l—r层花时间最多的 // 一定是离电梯当前所在楼层最远的乘客 return max（abs（currF-f［l]),abs(currF—f[r］)）*vw; ｝ // 现在电梯在第i层，电梯里面本来有j位乘客，离开电梯的乘客剩下jj位int tStay(int i,int j，int jj)｛ // 没有乘客离开,电梯不停 if（j==jj ｜| i==1) return dp［i+1］[jj] +ve; // 所有人都离开电梯 else if（jj==0) return 0； // 一般情况，电梯在第i层停靠 else return dp［i+1］［jj]+ve+st; } // void calculate(）｛ // 边界：电梯在顶楼时所有人都必须下电梯 int topFloor=f[1］; for（int j=1;j〈=n；j++）{ // 1,j表示停靠请求的编号,编号越小表示编号停靠楼层越高 dp［topFloor］[j]=tLeave(topFloor,1,j）; ｝ for（int i=topFloor-1；i>=1;i—-）｛ // i表示电梯此刻所在位置 for（int j=1;j<=n；j++）{ dp［i][j］=numeric_limits for（int jj=0;jj<=j;jj++）｛ // 计算离开电梯的人和留在电梯里面的人中到达目的地最晚的 int tmp=max（tStay（i,j,jj），tLeave（i，jj+1，j））; // 在此求解花费时间最短的乘客 if(dp[i］[j］>tmp) ｛ dp[i][j］=tmp； // jj以前的乘客均离开电梯 nextJ[i］[j]=jj; } ｝ ｝ } cout〈〈dp[1]［n]〈 ｝ // 重构最优解 void rebuildSolution（）｛ vector int j=nextJ［1][n］，topFloor=f[1］； for(int i=2;i<=topFloor；i++）｛ if(nextJ[i］[j]！=j)｛ stops。push_back(i)； j=nextJ[i]［j]； if（j==0) break; } ｝ cout〈〈stops。size()； for(int i=0；i〈stops。size（）;i++){ cout〈<” "〈〈stops[i]； ｝ cout〈〈endl； ｝ void solve（）{ memset（dp，0,sizeof(dp))； memset（nextJ，0,sizeof(nextJ）); calculate（）; rebuildSolution（）； } 题目2 切割木材 2。1题目描述 一个木匠从木材公司买了一批木材,每块木材的长度均相同，但由于制作家具时所需的木块长度各不相同，因此需要把这些木材切割成长度不同的木块。同时每次切割时由于锯子本身有一定的宽度，因此每切割一次就会浪费掉一些木料。请设计一个程序使木匠能够用最少的木材切割出所需的木块。 输入描述: 输入有若干个测试样例,每个测试样例占一行。每行由若干个整数构成，第一个整数为所购买的木块的长度L(0 输出描述： 每个测试样例输出一行，为一个整数N，表示制作家具时需要购买的木块的数量。 样例输入: 1000 100 250 250 500 650 1000 1000 50 200 250 250 500 650 970 样例输出： 3 4 2。2算法文字描述 此题目是装载问题的一个变种，与装载问题不同的是此问题没有给出“船”数量，但是给出了船的载重量，因此仍旧可以借鉴解装载问题的思路，即让每一根原材料可以切出更多符合要求的木料，类似于装载问题中“将第一艘轮船尽可能地装满”,即保证切割以后剩余的原材料是最少的。算法具体描述如下：Step 1：声明求解结果变量res=0，剩余未切割木料数量count=n，当前已切割木料长度和cw=0，目前最大切割长度bestW=0，求解标记数组visited［n]，当前最优求解数组nVisited［n]，问题求解状态记录数组res_arr［n]，锯口宽度sw； Step 2:当剩余未切割木料数量count大于0时，利用回溯法进行最大子集 和求解。当i〈n-1时，搜索左子树的条件:当前节点未被访问且cw+data［i］〈=w+sw，访问左子树时第i层相应节点时将相应访问标记visited［i］置为true，递归搜索该节点的左子树；递归搜索右子树时，将当前节点访问标记visited[i]置为false； Step 3:当i>n—1时，获得一种切割方案，若此次求解结果优于已得求解结果,即bestW〈cw，使用nVisited数组记录当前求解状态，同时更新bestW的值； Step 4:利用回溯法完成1次木料切割后，更当前问题求解状态res_arr数组，根据最新的求解状态更新未切割木料数量count，同时res++，若count=0则求解结束,否则重复2，3，4直至count=0。 2。3算法程序流程 图8 main函数流程图 图9 input函数流程图 图10 solve函数流程图 图11 backtrack函数流程图 2。4算法的程序实现代码 # include ＃include ＃include〈cstring〉 ＃define MAX_SAMPLE_LENGTH 50 /＊回溯法求解*/ int* in=(int ＊)malloc(MAX_SAMPLE_LENGTH＊sizeof(int）)； int＊data=(int ＊）malloc(MAX_SAMPLE_LENGTH*sizeof（int)）; bool＊visited=(bool *)malloc(MAX_SAMPLE_LENGTH＊sizeof(bool）); bool* nVisited=(bool *)malloc(MAX_SAMPLE_LENGTH*sizeof（bool））; bool＊res_arr=（bool ＊)malloc(MAX_SAMPLE_LENGTH＊sizeof(bool))；int w; // 原材料长度 int n；// 数据元素个数 int sw；// 锯口宽度 int cw；// 当前已锯木头长度和 int res；// 求解结果 int bestW; // 当前求解最大值 bool input(）｛ bool flag=true; //初始化数据保存数组 memset(in，0，MAX_SAMPLE_LENGTH＊sizeof(int））； memset（visited，false，MAX_SAMPLE_LENGTH*sizeof（bool)）； memset(res_arr,false，MAX_SAMPLE_LENGTH＊sizeof(bool)）; memset(nVisited，false,MAX_SAMPLE_LENGTH＊sizeof（bool))； // 记录输入数据个数 n=0； // 读取数据—原材料(木头)长度 scanf(”%d”，&w）; if(0==w) flag=false； // 锯口宽度 scanf("%d"，&sw); while（flag){ scanf(”%d”，data+n)； n++； char ch=getchar()； if（ch==’\n') break; ｝ return flag； } void backtrack（int i,int k){ if（i〉n-1）{ if（bestW // 记录最优值 bestW=cw； // 记录当前最优解 for(int i=0;i nVisited［i]=visited［i]; ｝ } return ; } // 进入右子树条件 if(!res_arr［i]＆&cw+data[i]+k＊sw〈=w){ // 记录当前已锯木头数量 k++； // 进入右子树实际操作 cw+=data[i]； // 访问标记 visited［i]=true; backtrack（i+1,k)； cw-=data［i]； k-—; } visited［i］=false; backtrack(i+1，k）； ｝ int solve(int＊data,int n）｛ res=0；// 求解结果初始化 int count=n； while（count>0)｛ // 初始化，cw当前已锯木头长度和, // count剩余未锯木头数量，bestW本次求解最大长度和 cw=0，count=0，bestW=0； backtrack（0,0)； for(int i=0；i // 更新待解决问题状态 if（！res_arr［i]） res_arr［i］=nVisited[i］; // 剩余未求解元素个数 if(!res_arr［i]) count++； } // 记录求解结果 res++; } return res; } int main(）｛ while（input（)){ solve（data，n)； printf（”\n％d\n"，res）; ｝ } 题目3 设计题 3。1题目描述 给定一个数塔，如图12所示.在此数塔中，从顶部出发，在每一节点可以选择向左走还是向右走，一直走到底层。请找出一条路径，使路径上的数值和最大。 图12 数塔 3.2 输入要求 第一行输入一个整数n,n表示数塔的层数,第2,…，n+1行为数塔对应节点的数值。 3。3输出要求 第一行输出路径数值和,第二行输出具体路径. 3.4样例输入 5 13 11 12 40 7 16 6 14 15 8 12 7 13 24 11 3。5样例输出 91 (1,1)-〉(2,1）-〉(3,1）—>（4，2）-〉(5,3） 3。6测试样例输入 11 9 8 12 10 7 4 1 5 23 19 17 8 21 12 16 32 25 24 28 31 27 8 5 9 10 11 13 15 3。7测试样例输出 113 (1,1)—〉（2,1)—〉（3,2）—〉（4，3）->（5,3)->（6,4)—〉(7，5) 3。8算法实现的文字描述 动态规划采用自底向上逐层分阶段决策 1)第1次决策，针对第4层 如果最优路径经过6，则从第4层到第5层应该经过12，则第4+第5层的最大路径为6+12=18 如果最优路径经过14，则从第4层到第5层应该经过13，则第4+第5层的最大路径为13+14=27 …… 这样实际上将5阶数塔变为4阶数塔问题了。 2)逐层向上递推,最后得到问题的最优解 根据题意，待处理的数据规模同数塔的层数有关，同时数据节点的个数与层数相同，所以可以使用二维数组data存储待处理节点数值，只有一半的节点有数值,实际上是一个下三角矩阵.可以较为容易地得到问题状态转移方程: Step 1:声明变量数塔层数n，待处理数据节点数值数组data［n][n]，结果（状态）数组d[n]［n］; Step 2：输入数塔层数n，维数组data和d分配内存空间； Step 3：初始化第n层结果（状态)数组值； Step 4：根据状态转移方程求解d(i,j)，其中i从n-1到1，j从1到i; Step 5：输出d(1，1）; Step 6：根据数组d求解具体路径并输出。 实验报告题目 实验一递归与分治策略 一、实验目的 1．加深学生对分治法算法设计方法的基本思想、基本步骤、基本方法的理解与掌握； 2．提高学生利用课堂所学知识解决实际问题的能力； 3．提高学生综合应用所学知识解决实际问题的能力。 二、实验内容 设计一个递归和分治算法，找出数组的最大元素，找出x在数组A中出现的次数。 三、实验要求 （1）用分治法求解…问题； （2）再选择自己熟悉的其它方法求解本问题； （3）上机实现所设计的所有算法； 四、实验过程设计（算法设计过程） 1.设计一个递归算法，找出数组的最大元素。 2.设计一个分治算法，找出x在数组A中出现的次数。 3.写一个主函数，调用上述算法。 五、实验结果分析 （分析时空复杂性，设计测试用例及测试结果） 时间复杂性：最好情况下，O(n) 最坏情况下：O(nlog(n) 空间复杂性分析：O(n) 六、实验体会 通过写递归与分治策略实验，更加清楚的知道它的运行机理，分治法解题的一般步骤：（1）分解，将要解决的问题划分成若干规模较小的同类问题；（2）求解，当子问题划分得足够小时，用较简单的方法解决；（3）合并，按原问题的要求，将子问题的解逐层合并构成原问题的解。做实验重在动手动脑，还是要多写写实验，才是硬道理。 七、附录：（源代码） #include"stdio.h" #define ElemType int int count(ElemType a[],int i,int j,ElemType x) { int k=0,mid; //k用来计数，记录数组中x出现的次数if(i==j) { if(a[i]==x) k++; return k; } else { mid=(i+j)/2; k+=count(a,i,mid,x); k+=count(a,mid+1,j,x); } return k; } ElemType Maxitem(ElemType a[],int n) { ElemType max=a[n-1],j; if(n==1) { max=a[n-1]; return max; } else { XXXX大学 算法设计与分析课程设计报告 院（系）： 年级： 姓名： 专业：计算机科学与技术 研究方向：互联网与网络技术 指导教师： X X X X 大学 目录 题目1 电梯调度 (1) 1.1 题目描述 (1) 1.2 算法文字描述 (1) 1.3 算法程序流程 (4) 1.4 算法的程序实现代码 (8) 题目2 切割木材 (10) 2.1题目描述 (10) 2.2算法文字描述 (10) 2.3算法程序流程 (11) 2.4算法的程序实现代码 (15) 题目3 设计题 (17) 3.1题目描述 (17) 3.2 输入要求 (17) 3.3输出要求 (17) 3.4样例输入 (17) 3.5样例输出 (17) 3.6测试样例输入 (18) 3.7测试样例输出 (18) 3.8算法实现的文字描述 (18) 3.9算法程序流程 (19) 3.10算法的程序实现代码 (20) 算法分析与设计课程总结 (23) 参考文献 (24) II 题目1 电梯调度 1.1 题目描述 一栋高达31层的写字楼只有一部电梯，其中电梯每走一层需花费4秒，并且在每一层楼停靠的时间为10秒，乘客上下一楼需要20秒，在此求解最后一位乘客到达目的楼层的最短时间以及具体的停靠计划。例如：此刻电梯停靠需求为4 5 10（有三位乘客，他们分别想去4楼、5楼和10楼），如果在每一层楼都停靠则三位乘客到达办公室所需要的时间为3*4=12秒、4*4+10=26秒、4*9+2*10=56秒，则最后一位乘客到达办公室的时间为56秒，相应的停靠计划为4 5 10均停靠。对于此测试用例电梯停靠计划方案：4 10，这样到第4楼的乘客所需时间为3*4=12秒，到第5楼的乘客所需时间为3*4+20=32秒，到第10楼的乘客所需时间为9*4+10=46秒，即最后到达目的楼层的顾客所需时间为46秒。 输入要求： 输入的第1行为整数n f1 f2 … fn，其中n表示有n层楼需要停靠，n=0表示没有更多的测试用例，程序终止运行。f1 f2 … fn表示需要停靠的楼层（n<=30，2<=f1 课程设计（大作业）报告 课程名称：算法设计与分析 设计题目：医院病床安排 院系：信息技术学院 班级：10 级计科1班 设计者： 学号： 指导教师： 设计时间： 信息技术学院 昆明学院课程设计（大作业）任务书 姓名：院（系）：信息技术学院 专业：计算机网络工程方向学号： 任务起止日期：2013-7-8至2013-7-11 课程设计题目：医院病床安排 课程设计要求： 在处理每一个题目的时候，要从分析题目的需求入手，按设计抽象数据类型、构思算法、通过类的设计实现抽象数据类型、编制上机程序代码并调试的步骤完成题目，最终写出完整的分析报告。见到题目，案头工作准备不足，忙于上机敲程序不是优秀程序员的工作风格。注意设计与实现过程的经验积累，编码应尽量利用前阶段的成熟数据结构包，加大代码的重用率。 工作计划及安排： 7月8日：（第一天）分好组并确定要完成的课程设计题目，上网查资料； 7月9日：（第二天）根据第一天上网搜的资料开始着手做该课程设计题目； 7月10日：（第三天）基本完成该课程设计所要求的内容； 7月11日：（第四天）完善内容和调整格式准备答辩； 指导教师签字 年月日 课程设计（大作业）成绩 学号：姓名：指导教师： 课程设计题目：医院病床安排 总结： 在本次的课程设计中,我遇到很多意想不到的问题,并没有开始我想的那样简单,我开始的想法是先到先服务,但是最后想到问题的要求是要使等待的时间最短,所以这个想法是不正确的,通过老师的提示和上网查阅资料,最后得出结论就是用贪心算法来解决该问题才是最合理的,使每一个病人按住院时间短的先入住,那就节省了后面等待入住病人的时间,相反之,如果使住院时间长的病人先入住,那么后面等待入住的病人等待的时间就越长,这样就会使总体的等待时间就越长,而平均等待时间=总等待时间/病人总数,我们这里讨论的是病人总数一定,那么就只有总等待时间越小,平均等待时间就越短,故该问题的解决方法就是用贪心算法策略——住院时间短的病人先住院。通过该次实训，也表现出了我们对课本理论知识的欠缺，团队合作精神也有待提高，今后需丰富自己的理论知识和提高团队合作的精神。也要加强自己的动手能力，为步入社会打下良好的实践动手能力。 指导教师评语： 成绩： 填表时间：2013年7月11日指导教师签名： 实验一找最大和最小元素与归并分类算法实现（用分治法）一、实验目的 1．掌握能用分治法求解的问题应满足的条件； 2．加深对分治法算法设计方法的理解与应用； 3．锻炼学生对程序跟踪调试能力； 4．通过本次实验的练习培养学生应用所学知识解决实际问题的能力。 二、实验内容 1、找最大和最小元素 输入n 个数，找出最大和最小数的问题。 2、归并分类 将一个含有n个元素的集合，按非降的次序分类（排序）。 三、实验要求 （1）用分治法求解问题 （2）上机实现所设计的算法； 四、实验过程设计（算法设计过程） 1、找最大和最小元素 采用分治法，将数组不断划分，进行递归。递归结束的条件为划分到最后若为一个元素则max和min都是这个元素，若为两个取大值赋给max，小值给min。否则就继续进行划分，找到两个子问题的最大和最小值后，比较这两个最大值和最小值找到解。 2、归并分类 使用分治的策略来将一个待排序的数组分成两个子数组，然后递归地对子数组进行排序，最后将排序好的子数组合并成一个有序的数组。在合并过程中，比较两个子数组的首个元素，将较小的元素放入辅助数组，并指针向后移动，直到将所有元素都合并到辅助数组中。 五、源代码 1、找最大和最小元素 #include 算法设计与分析实验报告 教师： 学号： 姓名： 实验一：串匹配问题 实验目的：(1) 深刻理解并掌握蛮力法的设计思想; (2) 提高应用蛮力法设计算法的技能; (3) 理解这样一个观点: 用蛮力法设计的算法, 一般来说, 经过适度的努力后, 都可以对算法的第一个版本进行一定程度的改良, 改进其时间性能。 三、实验要求：( 1) 实现BF 算法; (2 ) 实现BF 算法的改进算法: KMP 算法和BM 算法; (3 ) 对上述3 个算法进行时间复杂性分析, 并设计实验程序验证 分析结果。 #include "stdio.h" #include "conio.h" #include 算法设计课程设计报告 一、课程简介 算法设计课程是计算机科学与技术、软件工程等专业中的一门基础课程。本课程旨在帮助学生掌握算法基础及其应用，培养学生在算法设计和分析上的能力，以及解决复杂问题的能力。 二、课程目标 1.了解常见算法的设计和实现方式，如分治、贪心、动态规划等。 2.掌握常见数据结构的特点及其应用，例如堆、树、图等。 3.学习算法分析方法，包括时间复杂度、空间复杂度等，并能在实际问题中应用。 4.培养学生的编程能力，包括实现算法、调试程序、编写算法程序文档等。 5.提高学生的解决问题能力，能够独立解决复杂问题。 三、教学方式 1.理论讲解：讲授算法设计的基础知识，包括算法和数据结构的基本概念、算法设计方法和分析方法等。 2.实践操作：通过编写算法程序实现课程所学知识，并在实践中理解相关理论。 3.课程作业：布置算法分析作业、程序设计作业等，帮助学生巩固课程所学知识。 4.项目编程：设计一个包含多个问题的综合性项目，帮助学生综合运用所学知识。 四、教学内容 1.算法和数据结构基本概念 2.分治算法 3.贪心算法 4.动态规划算法 5.图算法 6.字符串算法 7.时间复杂度分析 8.空间复杂度分析 9.递归算法 10.基本排序算法 11.基本搜索算法 12.树和二叉树 13.堆和优先队列 五、教学评估 1.期末考试：评估学生对于算法设计和分析的理解和掌握程度。 2.作业评估：评估学生实践操作能力以及编程能力。 3.项目评估：评估学生综合运用所学知识的能力。 4.平时成绩：评估学生的出勤情况、参与度和表现情况。 六、教学经验 1.建立良好的师生关系，积极引导学生探究、实践和思考，重视学生自主学习的兴趣和意愿，让学生在学习中体验到成长的乐趣。 2.在实践操作中着重培养学生编程技能，既重视代码实现的正确性，也注重代码的可读性和维护性。 3.注重在教学过程中培养学生的合作精神和团队意识，通过面向项目的设计教学，协同解决实际问题，增强了学生的感性认识和合作能力。 4.充分利用互联网资源，如OJ等在线判题系统作为课程的辅助教学资源，帮助学生掌握课程内容，增强自学能力。 算法分析与设计课程设计 一、项目背景 随着信息技术的飞速发展，算法设计与分析在信息领域日益重要。本课程旨在通过探究算法的基本概念和设计方法，培养学生的算法思维能力，提高学生的算法实践能力，达到掌握算法设计和分析的目标。 二、课程目标 1.大致了解算法基础、设计思想和分析方法； 2.掌握常见算法及其实现原理； 3.能够根据问题确定合适的算法解决方案； 4.能够对算法时间复杂度和空间复杂度进行分析； 5.综合应用掌握的知识，实现一项经典算法。 三、课程内容 3.1 算法基础 1.算法定义及特征 2.算法分析的基本方法 3.时间复杂度和空间复杂度 3.2 常见算法 1.排序算法：插入排序、选择排序、快速排序 2.查找算法：顺序查找、二分查找 3.图算法：广度优先搜索、深度优先搜索、最短路径算法 3.3 算法设计思想 1.贪心算法 2.分治算法 3.动态规划算法 3.4 课程实践 1.队列模拟实现 2.快速排序算法实现 四、考核方式 1.课堂测试 30% 2.课程设计项目 40% 3.期末考试 30% 五、课程设计项目 为了巩固学习成果，提高学生的算法实践能力，设计一项经典算法实现，包括算法的设计思路、实现过程、效率分析等。 5.1 选题范围 根据自己的兴趣和能力，从以下算法中任选一项： 1.矩阵连乘问题 2.背包问题 3.最大子段和问题 4.八皇后问题 5.2 项目内容 1.算法原理简介 2.程序设计思路 3.程序实现方法 4.效率分析 六、参考资料 1.《算法设计与分析基础》第3版，作者：邓俊辉 2.《算法艺术与信息学竞赛》第2版，作者：陈启峰 3.《算法》第4版，作者：Robert Sedgewick和Kevin Wayne 七、总结 算法设计与分析是信息领域的核心知识之一。本课程旨在通过理论探究和实践项目，帮助学生掌握算法基础、常见算法和算法设计思想，提升学生实际解决问题的能力。 在课程设计项目中，学生可以自由发挥，选择适合自己的经典算法进行实现，着重体现算法设计思路、实现过程和效率分析。希望学生通过本课程能够加深对算法设计和分析的理解，为以后的学习和工作打下坚实基础。 算法设计与分析报告 学生姓名 学号 专业班级 指导教师 完成时间 目录 一、课程内容 (3) 二、算法分析 (3) 1、分治法 (3) （1)分治法核心思想 (3) （2）MaxMin算法分析 (3) 2、动态规划 (4) （1）动态规划核心思想 (4) （2）矩阵连乘算法分析 (5) 3、贪心法 (5) (1）贪心法核心思想 (5) （2）背包问题算法分析 (6) （3）装载问题算法分析 (7) 4、回溯法 (7) （1）回溯法核心思想 (7) （2)N皇后问题非递归算法分析 (7) (3）N皇后问题递归算法分析 (8) 三、例子说明 (9) 1、MaxMin问题 (9) 2、矩阵连乘 (10) 3、背包问题 (10) 4、最优装载 (10) 5、N皇后问题(非递归） (11) 6、N皇后问题(递归) (11) 四、心得体会 (12) 五、算法对应的例子代码 (12) 1、求最大值最小值 (12) 2、矩阵连乘问题 (13) 3、背包问题 (15) 4、装载问题 (17) 5、N皇后问题(非递归） (19) 6、N皇后问题(递归） (20) 一、课程内容 1、分治法,求最大值最小值，maxmin算法； 2、动态规划，矩阵连乘，求最少连乘次数； 3、贪心法，1）背包问题，2）装载问题； 4、回溯法，N皇后问题的循环结构算法和递归结构算法。 二、算法分析 1、分治法 （1）分治法核心思想 当要求解一个输入规模为n,且n的取值相当大的问题时，直接求解往往是非常困难的。如果问题可以将n个输入分成k个不同子集合，得到k个不同的可独立求解的子问题，其中1 算法分析与设计课程设计报告 目录 一、问题描述 (1) 1、普通背包问题 (1) 2、0-1背包问题 (1) 3、棋盘覆盖问题 (1) 二、问题分析 (2) 1、普通背包问题 (2) 2、0-1背包问题 (2) 3、棋盘覆盖问题 (3) 三、算法设计 (3) 1、普通背包问题 (3) 2、0-1背包问题 (4) 3、棋盘覆盖问题 (4) 四、算法实现 (6) 1、普通背包问题 (6) 2、0-1背包问题 (8) 3、棋盘覆盖问题 (10) 五、测试分析 (11) 1、普通背包问题 (11) 2、0-1背包问题 (13) 3、棋盘覆盖问题 (15) 六、结论 (16) 七、源程序 (17) 1、普通背包问题 (17) 2、0-1背包问题 (20) 3、棋盘覆盖问题 (24) 八、参考文献 (26) 一、问题描述 1、普通背包问题 有一个背包容量为C，输入N个物品，每个物品有重量S[i]，以及物品放入背包中所得的收益P[i]。求选择放入的物品，不超过背包的容量，且得到的收益最好。物品可以拆分，利用贪心算法解决。 2、0-1背包问题 在0/1背包问题中，需对容量为c的背包进行装载。从n个物品中选取装入背包的物品，每件物品i的重量为wi, 价值为pi。对于可行的背包装载，背包中的物品的总重量不能超过背包的容量，最佳装载是指所装入的物品价值最高， 即取得最大值。约束条件 <=c和。在这个表达式中，需求出xi的值。xi=1表示物品i装入背包中，xi=0表示物品i不装入背包。 3、棋盘覆盖问题 在一个2k×2k 个方格组成的棋盘中，恰有一个方格与其它方格不同，称该方格为一特殊方格，且称该棋盘为一特殊棋盘。在棋盘覆盖问题中，要用图示的4种不同形态的L型骨牌覆盖给定的特殊棋盘上除特殊方格以外的所有方格，且任何2个L型骨牌不得重叠覆盖。 ∑ = n i i i x w 1 []()n i xi≤ ≤ ∈1 1,0 ∑ = n i i i x p 1 - 1 - 目录 1、课程设计的目的 (2) 2、课程设计的技术要求 (2) 3、题目分析 (2) 4、算法分析与设计 (3) 4.1游戏运行活动图 (3) 4.2具体算法与程序流程分析 (3) 5、方法定义及调用关系 (4) 5.1方法定义: (4) 5.2方法调用关系: (4) 6、游戏细节设计 (4) 6.1攻击招式统计: (4) 6.2受到攻击后响应动作统计： (4) 7、界面设计 (5) 8、部分程序分析 (6) 8.1 游戏初始化方法 (6) 8.2 启动游戏线程方法 (6) 8.3 获取两位挑战者属性的方法 (7) 8.4 游戏结果返回方法 (7) 8.5 游戏循环方法说明方法 (8) 8.6 攻击方法说明方法 (9) 8.7 防守方法 (11) 8.8 休眠动作方法 (14) 8.9 动作表现方法 (14) 8.10游戏的循环逻辑方法 (15) 9、运行结果显示与分析 (16) 9.1运行结果 (16) 9.2运行结果分析 (18) 10、实验总结 (18) 11、参考文献 (18) 附录 (19) MainGame.java (19) InputFun.java (20) GameWorld.java (21) Role.java (28) Test.java (32) 姓名挑战游戏 1、课程设计的目的 学习算法的最终目的是解决实际的应用问题，特别是非数值计算类型的应用问题。课程设计要求同学独立完成一个较为完整的应用需求分析，在完成设计和编程大型作业的过程中，深化对算法课程中基本概念、理论和方法的理解；训练综合运用所学知识处理实际问题的能力，强化面向对象的程序设计理念；使同学的程序设计与调试水平有一个明显的提高。经过查找参考资料、技术手册和撰写文档的实践，进一步培养软件工程师的综合素质。 2、课程设计的技术要求 同学在处理每一个题目的时候，要从分析题目的需求入手，按设计抽象数据类型、构思算法、通过类的设计实现抽象数据类型、编制上机程序代码并调试的步骤完成题目，最终写出完整的分析报告。见到题目，案头工作准备不足，忙于上机敲程序不是优秀程序员的工作风格。注意设计与实现过程的经验积累，编码应尽量利用前阶段的成熟数据结构包，加大代码的重用率。 课程设计所安排的题目，在难度和深度方面都大于课内的上机训练。程序作业以Java完成，配有图形界面。作业一般要达到3000行以上的代码量。最后提交作业包括：课程设计报告；完整程序，应该具有可显示界面；PPT及算法说明。 3、题目分析 姓名挑战游戏说明：输入两个中文姓名，通过一种算法，计算出姓名的血值和攻击力，使两个名字进行对战，进行多轮回合后，决定双方输赢。 在运行界面中输入两个挑战者的姓名，软件就会计算出两个挑战者初始状态的血值和攻击力之类的属性值。然后两个挑战者一边挑战，系统会自动显示目前两个挑战者的一系列属性。两个人一直挑战，直到其中一者的hp的值为0，则 算法设计与分析课程设计报告 压缩软件课程设计书 一、问题描述： 建立一个文本文件，统计该文件中各字符频率，对各字符进行Huffman编码，将该文件至翻译成Huffman编码文件，再将Huffman编码文件翻译成原文件。 二、算法分析及思路： 对于该问题，我们做如下分析： （1）首先得构造出哈弗曼树，我们用函数HuffmanTree(int w[],int s[],int n)设计； （2）在构建哈弗曼树的基础上，进一步实现哈弗曼编码问题，我们用函数Huffmancode(char wen[])设计； （3）实现哈弗曼编码后再进一步实现哈弗曼译码问题，我们用函数Huffmandecode()设计； （4）其中编码问题中，得进一步统计出各个字符在文件中的频率，并进行一些必要的标记，我们用函数runhuffman(char wen[])设计； （5）在译码过程中，还有必要的一步是比较原文件与译码后的文件是否相同，我们用函数compare(char wen[])设计； （6）其中的文件输入我们用到类”fstream.h”中的输入输出流，并在运行的文件夹中建立一个文件名为逍遥游的文本文件，且在逍遥游文件中输入需要编码的数据。 三、主要解决的设计问题： 1.写一个对txt文件压缩和解压的程序，使用动态编码。 2.使用Huffman编码压缩和解压时，Huffman树的存储可以直接存储树结构，也可以存储所有字符的频度或权值，然后读取时建立Huffman树； 3.使用Huffman编码压缩和解压时，注意定义压缩码的结束标记，可以使用一个特殊的字符作为结束标记，也可以在压缩码之前存储其比特长度；如果使用一个特殊字符作为结束标记，则其频度为1，需要在建立Huffman树时把它看作一个独立的字符进行建树。 4.使用Huffman编码压缩和解压时，在一个缓冲区里面收集压缩码比特流，每当收集的比特数满8时，可以把这8比特通过位操作合并成一个字节写入文件 湖南理工学院课程论文 论文题目 0-1背包问题的设计与实现 课程名称数据结构与算法设计 姓名学号 专业班级年级 2014级 学院计算机学院日期 2015年6月25日 课程论文评价标准 目录 1.问题描述 (3) 2.算法设计分析 (3) 3.程序编码与调试分析 (5) 4.测试结果 (7) 5.自学知识 (7) 6.课程设计心得体会 (8) 7.参考文献 (8) 1.问题描述 给定n种物品和一个背包，物品i的重量是w i，其价值为v i，背包容量为C。在选择装入背包的物品时，对每种物品i只有两种选择：装入背包或不装入背包，即不能将物品i装入背包多次，也不能只装入物品i的一部分。问：如何选择装入背包的物品，使得装入背包中物品的总价值最大？ 2.算法设计与分析 算法分析 在0-1背包问题中，物体被装入一个背包，或者不被装入背包，设x i表示物品i装入背包的情况，则当x i=0时，表示物品i没有被装入背包，x i=1时，表示物品i被装入背包。假设有五个物品，其重量分别是{2，2，6，5，4}，价值分别是{6，3，5，4，6}，背包的容量为10。根据动态规划函数，用一个(n+1)×(C+1)的二维表V，V[i][j]表示把前i个物品装入容量为j的背包中获得的最大价值。 按下述方法来划分阶段：第一阶段，只装入前1个物品，确定在各种情况下的背包能够得到的最大价值；第二阶段，只装入前2个物品，确定在各种情况下的背包能够得到的最大价值；依此类推，直到第n个阶段。最后，V(n,C)便是在容量为C的背包中装入n个物品时取得的最大价值。 为了确定装入背包的具体物品，从V(n,C)的值向前推，如果V(n,C)>V(n-1, C)，表明第n个物品被装入背包，前n-1个物品被装入容量为C-w 的背包中； n 否则，第n个物品没有被装入背包，前n-1个物品被装入容量为C的背包中。依此类推，直到确定第1个物品是否被装入背包中为止。 华中科技大学文华学院《算法分析与设计》课程设计报告 专业：计算机科学与技术 班级：2班 姓名：肖红红 学号：0701******** 指导老师：秦明 设计时间：5周-12周 目录 实验1 用分治法进行归并分类 1.1归并分类思想........................................... (3) 1.2归并分类流程图 (3) 1.3归并分类源程序 (4) 1.4归并分类结果截图 (5) 实验2 用分治法进行快速分类 2.1快速分类思想及代码 (6) 2.2快速分类流程图 (7) 2.3快速分类源程序 (8) 2.4快速分类结果截图 (8) 实验3 贪心算法求背包问题 3.1 背包问题思想................................... (9) 3.2 背包问题流程图 (9) 3.3背包问题源程序 (10) 3.3 背包问题结果截图 (11) 实验4 贪心算法求单源点最短路径 4.1单源点最短路径思想 (12) 4.2单源点最短路径流程图 (12) 4.3单源点最短路径源程序 (13) 4.4单源点最短路径结果截图 (14) 心得体会 (15) 实验一：《归并排序》 1.1归并排序设计思想： 归并排序采用的是分治策略，主要分为3个过程。 第一, 分解: 把待排序的 n 个元素的序列分解成两个子序列, 每个子序列包括 n/2 个元素。 第二, 治理: 对每个子序列分别调用归并排序MergeSort, 进行递归操作。 第三, 合并: 将已分类的两个序列合并成一个含有n个元素的分好累的序列,并生成最后的排序结果。 1.2归并排序流程图如下： 题目 1 电梯调度 (1) 1.1 题目描述 (1) 1.2 算法文字描述 (1) 1.3 算法程序流程 (4) 1.4 算法的程序实现代码 (8) 题目 2 切割木材 (10) 2.1 题目描述 (10) 2.2 算法文字描述 (10) 2.3 算法程序流程 (11) 2.4 算法的程序实现代码 (15) 题目 3 设计题 (17) 3.1 题目描述 (17) 3.2 输入要求 (17) 3.3 输出要求 (17) 3.4 样例输入 (17) 3.5 样例输出 (17) 3.6 测试样例输入 (17) 3.7 测试样例输出 (18) 3.8 算法实现的文字描述 (18) 3.9 算法程序流程 (19) 3.10 算法的程序实现代码 (20) 算法分析与设计课程总结 (23) 参考文献 (24) 一栋高达 31 层的写字楼惟独一部电梯，其中电梯每走一层需花费 4 秒，并且在每一层楼停靠的时间为 10 秒，乘客上下一楼需要 20 秒，在此求解最后一位乘客到达目的楼层的最短期以及具体的停靠计划。例如：此刻电梯停靠需求为 4 5 10 (有三位乘客，他们分别想去 4 楼、 5 楼和 10 楼)，如果在每一层楼都停 靠则三位乘客到达办公室所需要的时间为 3*4=12 秒、4*4+10=26 秒、4*9+2*10=56 秒，则最后一位乘客到达办公室的时间为 56 秒，相应的停靠计划为 4 5 10 均停靠。对于此测试用例电梯停靠计划方案： 4 10，这样到第 4 楼的乘客所需时间为3*4=12 秒，到第 5 楼的乘客所需时间为 3*4+20=32 秒，到第 10 楼的乘客所需时间为 9*4+10=46 秒，即最后到达目的楼层的顾客所需时间为 46 秒。 输入的第 1 行为整数n f1 f2 … fn，其中 n 表示有 n 层楼需要停靠， n=0 表示没有更多的测试用例，程序终止运行。f1 f2 … f n 表示需要停靠的楼层 (n<=30，2<=f1 算法分析与设计以大学生程序设计竞赛为例课程设计 1、项目背景 随着信息技术的高速发展，计算机编程已成为当代人们日常生活和工作必不可 少的一部分。而程序设计竞赛则是考验计算机编程能力的一种形式，它可以帮助学生加强对计算机程序设计的认识和理解，提高编程能力和团队协作能力，培养创新思维和解决问题的能力。因此，在大学计算机科学教育中，将程序设计竞赛纳入课程体系中是非常必要的。 2、项目目的 目前，许多高校都会组织学生参加各类程序设计竞赛，比如ACM、ICPC、NOI 等，这些比赛涉及到高级算法和数据结构、高效程序设计和优化等方面的知识点。本课程设计旨在通过深入研究程序设计竞赛的相关知识和技巧，来帮助学生进一步提高自己的编程能力和竞赛水平，为日后从事计算机相关行业工作打下坚实的基础。 3、项目内容 本课程设计以大学生程序设计竞赛为例，主要包括以下内容： 3.1、算法分析和设计基础 本部分主要介绍程序设计竞赛中涉及到的常见算法和数据结构，以及它们的基 本原理和应用场景。比如：常见的排序算法、图论算法、动态规划等。 3.2、高效程序设计和优化 本部分主要介绍如何在竞赛中设计高效的程序，提高程序的执行效率和减小程 序的内存占用等问题。比如：如何合理地使用数据结构、算法和面向对象编程等技术来优化程序性能。 3.3、实战演练和团队协作 本部分主要是通过课程设计的实战演练，来锻炼学生的团队协作和解决问题的能力。在课程的实践中，学生将会分成小组，选择一些国内外知名的程序设计竞赛题目进行独立的解题和优化，最终提交自己的程序代码。 4、学习方法 本课程设计将采用以下学习方法： 4.1、理论授课 本课程设计将结合案例分析和代码实践，通过讲解和演示，来帮助学生深入理解和掌握程序设计竞赛中常见的算法和数据结构，并学习如何在竞赛中设计高效的程序。 4.2、实践演练 本课程设计中的实践演练环节非常重要，通过小组合作的方式，让学生在竞赛题目中实践所学的知识，同时也锻炼了学生的团队协作和解决问题的能力。 4.3、课后作业 为了加强学生的巩固和应用，本课程设计将会布置一些课后作业，包括代码实现、文献阅读和思考题等。 5、评价方式 本课程设计的评价方式主要包括： 5.1、上课表现和参与度 在课程中，学生应认真听讲、积极参与讨论和课堂互动等，以此来体现自己的参与度和学习态度。 算法设计与分析第2版课程设计 一、设计背景 《算法设计与分析》是计算机科学与技术专业的一门重要课程，也是计算机程序设计中最为基础的知识之一。通过本课程的学习，可以使学生掌握算法的设计原理、常用算法的基本思想和算法分析的方法。本课程是培养计算机科学与技术专业学生的基本能力的重要环节。 二、设计目标 本次课程设计旨在通过学习算法设计与分析的基本理论，培养学生的算法设计能力和解决问题的能力，同时提高学生的编程能力、数据结构和算法分析能力，为其以后的学习和工作打下坚实的基础。 三、设计内容 1. 理论讲解 本次课程设计的主要内容包括以下几个方面： •基本算法思想：包括贪心算法、动态规划、分治算法、回溯算法等。 •基本数据结构：包括数组、链表、栈、队列、堆、树等。 •算法复杂度分析：包括时间复杂度、空间复杂度等。 2. 实际编程 本次课程设计有两个实验任务，以帮助学生巩固所学知识。 •实验一：使用贪心算法解决问题 •实验二：使用动态规划算法解决问题 3. 指导练习 为了帮助学生更好地掌握所学知识，课堂上还将进行相关练习，包括但不限于以下几个方面： •课后习题的讲解和解答； •真实案例的讲解和分析； •算法实现的练习。 四、评价标准 为了评价学生在本次课程设计中的表现，我们将采用以下几个方面作为评价标准： •知识储备：学生是否掌握了所学知识的核心内容； •实践操作：学生是否能够独立完成实验任务； •思考分析：学生是否能够运用所学知识进行问题分析和思考； •团队协作：学生是否能够与他人配合完成实验任务。 五、总结 通过本次课程设计的学习，相信学生们能够更好地掌握算法设计与分析的基本理论和应用技巧，从而为其以后的学习和工作打下坚实的基础。 《算法设计与分析》 １什么是算法？算法的特征有哪些？ 根据我自己的理解，算法是解决问题的方法步骤。比如在解决高数问题的时候，可以分步骤进行解答，在编程的过程算法可以得到最好的体现。 算法是一系列解决问题的清晰指令，因为我最近在考研复习，对于会的题目还有进行多次的巩固，但是一步步的写很浪费时间，所以我只是写出关键指令，比如化简通分，洛必达法则，上下同阶。这样可以提高效率。算法的指令也是同样的。能够对一定规*的输入，在有限时间内获得所要求的输出。一个算法的优劣可以用空间复杂度与时间复杂度来衡量。 ２若给定*一算法，一般如何对其分析与评价？ 一个算法的复杂性的高低体现在运行该算法所需要的计算机资源的多少上面，所需的资源越多，我们就说该算法的复杂性越高；反之，所需的资源越低，则该算法的复杂性越低。计算机的资源，最重要的是时间和空间（存储器）资源。算法的复杂性有时间复杂性和空间复杂性之分。1.时间复杂性：例1：设一程序段如下（为讨论方便，每行前加一行号） (1) for i:=1 to n do (2) for j:=1 to n do (3) *:=*+1 ......试问在程序运行中各步执行的次数各为多少？解答：行号次数(频度) (1) n+1 (2) n*(n+1) (3) n*n可见，这段程序总的执行次数是：f(n)=2n2+2n+1。在这里，n可以表示问题的规模，当n趋向无穷大时，如果f(n)的值很小，则算法优。作为初学者，我们可以用f(n)的数量级O来粗略地判断算法的时间复杂性，如上例中的时间复杂性可粗略地表示为T(n)=O(n2)。 2.空间复杂性:例2:将一一维数组的数据(n个)逆序存放到原数组中,下面是实现该问题的两种算法:算法1:for i:=1 to n do b[i]:=a[n-i+1]; for i:=1 to n do 算法设计与分析课程报告 第一章算法问题求解基础 1、算法的概念：算法是指解决问题的一种方法或过程，是由若干条指令组成的有穷序列。 2、算法的特性 ①有穷性：一个算法必须保证执行有限步之后结束； ②确切性：算法的每一步骤必须有确切的定义； ③输入：一个算法有0个或多个输入，以刻画运算对象的初始情况，所谓0个输入是指算法本身定除了初始条件； ④输出：一个算法有一个或多个输出，以反映对输入数据加工后的结果。没有输出的算法是毫无意义的； ⑤可行性：算法原则上能够精确地运行，而且人们用笔和纸做有限次运算后即可完成 3、算法与程序的关系： 区别：程序可以不一定满足可终止性。但算法必须在有限时间内结束； 程序可以没有输出,而算法则必须有输出； 算法是面向问题求解的过程描述，程序则是算法的实现。 联系：程序是算法用某种程序设计语言的具体实现； 程序可以不满足算法的有限性性质。 4、算法描述方式：自然语言，流程图，伪代码，高级语言。 第二章算法分析基础 1、算法复杂性分析： 算法复杂性的高低体现运行该算法所需计算机资源（时间，空间）的多少。 算法复杂性度量： 期望反映算法本身性能，与环境无关。 理论上不能用算法在机器上真正的运行开销作为标准（硬件性能、代码质量影响）。一般是针对问题选择基本运算和基本存储单位，用算法针对基本运算与基本存储单位的开销作为标准。算法复杂性C依赖于问题规模N、算法输入I和算法本身A。即C=F(N, I, A)。 第五章分治法 1、递归算法：直接或间接地调用自身的算法。 用函数自身给出定义的函数称为递归函数。 注：边界条件与递归方程是递归函数的二个要素。 实例：①阶乘函数； ②Fibonacci数列； ③Ackerman函数； ④排列问题； ⑤整数划分问题； 算法分析与设计实验报告 姓名：殷健 学号：134553225 专业：软件工程 目录 BF算法 (3) 回溯算法的改进 (4) KMP算法 (5) 汉诺塔问题 (6) Linux中调试快速排序 (7) 最大字段和问题 (8) 三路归并 (9) 二叉查找树 (11) 堆排序 (13) BF算法 一、描述 BF算法是一种蛮力算法，是普通的模式匹配算法。他的思想就是将目标串S的第一个字符与模式串T的第一个字符进行匹配，若相等，则继续比较S的第二个字符和 T的第二个字符；若不相等，则比较S的第二个字符和T的第一个字符，依次比较下去，直到得出最后的匹配结果。 二、分析 两个字符数组S跟T，首先S[1]和T[1]比较，若相等，则再比较S[2]和T[2]，一直到T[M]为止；若S[1]和T[1]不等，则S向右移动一个字符的位置，进行比较S[2]与T[1]。如果存在k，1≤k≤N，且S[k+1…k+M]=T[1…M]，则匹配成功；否则失败。 伪代码步骤： 初始化主串比较的开始位置index=0； 在主串和子串中设置比较的起始下标i=0,j=0； 重复以下操作，直到主串或子串的所有字符比较完毕。 若主串和子串中一组字符相等，则继续比较下一组字符； 否则，下一趟匹配的开始位置index++，下标i=index,j=0。 若子串中所有字符比较完毕，则返回匹配的开始位置index，否则返回0。三、代码 #include算法设计与分析实验报告
算法分析与设计课程设计报告 ppt课件
算法设计与分析课程设计
算法设计与分析实验报告
算法设计与分析实验报告
算法设计课程设计报告
算法分析与设计课程设计
算法设计与分析实验报告
算法分析与设计课程设计报告
算法分析与设计课程设计报告
算法设计与分析课程设计报告
算法设计与分析课程设计报告
算法分析之课程设计实验报告
算法分析与设计-课程设计报告
算法分析与设计以大学生程序设计竞赛为例课程设计
算法设计与分析第2版课程设计
算法设计课程设计报告
算法设计与分析课程报告
算法分析与设计报告
相关主题
文本预览