下载文档原格式
《算法设计与分析》实验报告实验一递归与分治策略应用基础学号：**************姓名：*************班级：*************日期：2014-2015学年第1学期第九周一、实验目的1、理解递归的概念和分治法的基本思想2、了解适用递归与分治策略的问题类型，并能设计相应的分治策略算法3、掌握递归与分治算法时间空间复杂度分析，以及问题复杂性分析方法二、实验内容任务：以下题目要求应用递归与分治策略设计解决方案，本次实验成绩按百分制计，完成各小题的得分如下，每小题要求算法描述准确且程序运行正确。
1、求n个元素的全排。
（30分）2、解决一个2k*2k的特殊棋牌上的L型骨牌覆盖问题。
（30分）3、设有n=2k个运动员要进行网球循环赛。
设计一个满足要求的比赛日程表。
（40分）提交结果：算法设计分析思路、源代码及其分析说明和测试运行报告。
三、设计分析四、算法描述及程序五、测试与分析六、实验总结与体会#include "iostream"using namespace std;#define N 100void Perm(int* list, int k, int m){if (k == m){for (int i=0; i<m; i++)cout << list[i] << " ";cout << endl;return;}else{for (int i=m; i<k; i++){swap(list[m], list[i]);Perm(list, k, m+1);swap(list[m], list[i]);}}}void swap(int a,int b){int temp;temp=a;a=b;b=temp;}int main(){int i,n;int a[N];cout<<"请输入排列数据总个数：";cin>>n;cout<<"请输入数据：";for(i=0;i<n;i++){cin>>a[i];}cout<<"该数据的全排列："<<endl;Perm(a,n,0);return 0;}《算法设计与分析》实验报告实验二递归与分治策略应用提高学号：**************姓名：*************班级：*************日期：2014-2015学年第1学期一、实验目的1、深入理解递归的概念和分治法的基本思想2、正确使用递归与分治策略设计相应的问题的算法3、掌握递归与分治算法时间空间复杂度分析，以及问题复杂性分析方法二、实验内容任务：从以下题目中任选一题完成，要求应用递归与分治策略设计解决方案。
快速傅里叶变换的基本思路和原理一、引言快速傅里叶变换（FFT）是一种高效的算法，用于计算离散傅里叶变换（DFT）及其逆变换。
它通过将DFT计算中的复杂度从O(N^2)降低到O(N log N)，极大地提高了计算效率，成为信号处理、图像处理、通信等领域中的重要工具。
本文将介绍快速傅里叶变换的基本思路和原理，主要包括分治策略、递归实施、周期性和对称性、蝶形运算、高效算法等方面。
二、分治策略快速傅里叶变换的基本思路是将原问题分解为若干个子问题，通过对子问题的求解，逐步递归地得到原问题的解。
这种分治策略的思想来源于算法设计中的“分而治之”原则，即将一个复杂的问题分解为若干个较小的、简单的问题来处理。
在FFT中，分治策略将DFT的计算过程分为多个步骤，逐步简化问题规模，最终实现高效的计算。
三、递归实施递归是实现分治策略的一种常用方法。
在快速傅里叶变换中，递归地实施分治策略，将问题规模不断缩小，直到达到基本情况（通常是N=1或2），然后逐步推导到原问题。
递归实施使得FFT算法的代码简洁明了，易于实现和理解。
同时，递归也使得算法能够利用计算机的存储器层次结构，将计算过程中的中间结果存储起来，避免重复计算，进一步提高计算效率。
四、周期性和对称性在快速傅里叶变换中，利用了离散傅里叶变换的周期性和对称性。
周期性是指DFT的结果具有周期性，即对于输入序列x[n]，其DFT的结果X[k]具有N的周期性。
对称性是指DFT的结果具有对称性，即对于输入序列x[n]，其DFT的结果X[k]具有对称性。
这些性质在FFT算法中得到了广泛应用，它们有助于简化计算过程，提高计算效率。
例如，在蝶形运算中，利用周期性和对称性可以避免某些不必要的计算，从而减少运算量。
五、蝶形运算蝶形运算是快速傅里叶变换中的基本运算单元。
它利用离散傅里叶变换的周期性和对称性，将多个复数相加和相乘组合在一起，形成一个类似蝴蝶形状的运算流程。
蝶形运算的复杂度为O(log N)，是实现快速傅里叶变换的关键步骤之一。
《算法设计与分析》习题第一章引论习题1-1 写一个通用方法用于判定给定数组是否已排好序。
解答：Algorithm compare(a,n)BeginJ=1;While (j<n and a[j]<=a[j+1]) do j=j+1;If j=n then return trueElseWhile (j<n and a[j]>=a[j+1]) do j=j+1;If j=n then return true else return false end ifEnd ifend习题1-2 写一个算法交换两个变量的值不使用第三个变量。
解答：x=x+y; y=x-y; x=x-y;习题1-3 已知m,n为自然数，其上限为k（由键盘输入，1<=k<=109）,找出满足条件(n2-mn-m2)2=1 且使n2+m2达到最大的m、n。
解答：m:=k; flag:=0;repeatn:=m;repeatl:=n*n-m*n-m*n;if (l*l=1) then flag:=1 else n:=n-1;until (flag=1) or (n=0)if n=0 then m:=m-1until (flag=1) or (m=0);第二章基础知识习题2-1 求下列函数的渐进表达式：3n 2+10n ; n 2/10+2n ; 21+1/n ; log n 3; 10 log3n 。
解答： 3n 2+10n=O （n 2）， n 2/10+2n =O （2n ）， 21+1/n=O （1）， log n 3=O （log n ），10 log3n =O （n ）。
习题2-2 说明O (1)和 O (2)的区别。
习题2-3 照渐进阶从低到高的顺序排列以下表达式：!n ，3/22,2,20,3,log ,4n n n n n 。
解答：照渐进阶从低到高的顺序为：!n 、 3n、 24n 、23n 、20n 、log n 、2习题2-4（1） 假设某算法在输入规模为n 时的计算时间为n n T 23)(⨯=。
计算机算法设计五⼤常⽤算法的分析及实例摘要算法（Algorithm）是指解题⽅案的准确⽽完整的描述，是⼀系列解决问题的清晰指令，算法代表着⽤系统的⽅法描述解决问题的策略机制。
也就是说，能够对⼀定规范的输⼊，在有限时间内获得所要求的输出。
如果⼀个算法有缺陷，或不适合于某个问题，执⾏这个算法将不会解决这个问题。
不同的算法可能⽤不同的时间、空间或效率来完成同样的任务。
其中最常见的五中基本算法是递归与分治法、动态规划、贪⼼算法、回溯法、分⽀限界法。
本⽂通过这种算法的分析以及实例的讲解，让读者对算法有更深刻的认识，同时对这五种算法有更清楚认识关键词：算法，递归与分治法、动态规划、贪⼼算法、回溯法、分⽀限界法AbstractAlgorithm is the description to the problem solving scheme ,a set of clear instructions to solve the problem and represents the describe the strategy to solve the problem using the method of system mechanism . That is to say, given some confirm import，the Algorithm will find result In a limited time。
If an algorithm is defective or is not suitable for a certain job, it is invalid to execute it. Different algorithms have different need of time or space, and it's efficiency are different.There are most common algorithms: the recursive and divide and conquer、dynamic programming method、greedy algorithm、backtracking、branch and bound method.According to analyze the five algorithms and explain examples, make readers know more about algorithm , and understand the five algorithms more deeply.Keywords: Algorithm, the recursive and divide and conquer, dynamic programming method, greedy algorithm、backtracking, branch and bound method⽬录1. 前⾔ (4)1.1 论⽂背景 (4)2. 算法详解 (5)2.1 算法与程序 (5)2.2 表达算法的抽象机制 (5)2.3 算法复杂性分析 (5)3．五中常⽤算法的详解及实例 (6)3.1 递归与分治策略 (6)3.1.1 递归与分治策略基本思想 (6)3.1.2 实例——棋盘覆盖 (7)3.2 动态规划 (8)3.2.1 动态规划基本思想 (8)3.2.2 动态规划算法的基本步骤 (9)3.2.3 实例——矩阵连乘 (9)3.3 贪⼼算法 (11)3.3.1 贪⼼算法基本思想 (11)3.3.2 贪⼼算法和动态规划的区别 (12)3.3.3 ⽤贪⼼算法解背包问题的基本步骤： (12)3.4 回溯发 (13)3.4.1 回溯法基本思想 (13)3.3.2 回溯发解题基本步骤 (13)3.3.3 实例——0-1背包问题 (14)3.5 分⽀限界法 (15)3.5.1 分⽀限界法思想 (15)3.5.2 实例——装载问题 (16)总结 (18)参考⽂献 (18)1. 前⾔1.1 论⽂背景算法（Algorithm）是指解题⽅案的准确⽽完整的描述，是⼀系列解决问题的清晰指令，算法代表着⽤系统的⽅法描述解决问题的策略机制。
c语言中的算法基本概念C语言中的算法基本概念在计算机科学中，算法是指解决特定问题或执行特定任务的一组有限指令序列。
而C语言作为一种高级编程语言，常用于编写和实现各种算法。
本文将一步一步回答关于C语言中算法基本概念的问题。
一、什么是算法？算法是指解决特定问题或执行特定任务的一组有限指令序列。
它是为了解决问题而采取的一种策略或方法。
算法可以用来计算、排序、搜索、加密等各种操作。
在计算机科学中，算法的设计和分析是一个重要的研究领域。
二、C语言中如何表示算法？在C语言中，算法通常以函数的形式表示。
函数是一段可重复使用的代码，它接受输入参数并产生输出结果。
通过将算法封装在函数中，可以在程序中多次调用该函数来解决问题。
C语言中的函数通常包含函数声明和函数定义两个部分。
函数声明告诉编译器函数的名称、参数类型和返回值类型，而函数定义则是函数的具体实现。
三、C语言中的算法常见操作1. 输入输出操作：C语言提供了丰富的输入输出函数来与用户进行交互。
例如，使用scanf函数从键盘读取输入数据，使用printf函数将结果输出到屏幕上。
2. 条件判断和循环结构：在算法中经常需要根据条件进行判断和循环执行相应的操作。
C语言提供了if-else、switch-case等条件判断语句，和for、while、do-while等循环语句，用于控制程序的流程。
3. 数组和指针操作：数组是一种存储相同类型数据的集合，而指针是指向内存地址的变量。
在算法中，我们可以利用数组和指针来处理大量数据和进行数据的访问和修改。
C语言提供了强大的数组和指针操作功能。
4. 递归：递归是一种在算法中常用的技术，它指的是由函数自身调用自身。
递归在解决一些复杂问题时非常有用，例如在树的遍历和排序算法中常见。
四、算法的性能分析算法的性能分析是衡量算法优劣的一种方法。
主要考虑两个方面：时间复杂度和空间复杂度。
1. 时间复杂度：时间复杂度是算法执行时间随输入规模增长的增长量度。
第2章递归与分治策略实验2 分治算法的递归程序实现与时间复杂度测试1. 实验目的编程实现合并排序和快速排序算法，理解分治算法设计的基本思想、递归程序实现的基本方法，加深对分治算法设计与分析思想的理解。
通过程序的执行时间测试结果，与理论上的时间复杂度结论进行对比、分析和验证。
2. 原理解析分治算法的基本思想分治算法的基本思想是将一个规模为n的问题分解为k个规模较小的子问题，这些子问题相互独立且与原问题性质相同。
求出子问题的解，就可得到原问题的解。
分治算法设计的一般步骤包括：(1) 分解，将要解决的问题划分成若干规模较小的同类问题；(2) 求解，当子问题划分得足够小时，用较简单的方法解决；(3) 合并，按原问题的要求，将子问题的解逐层合并构成原问题的解。
分治法的基本设计范式如下：DivideAndConquer(data,n,solution)if(n≤SizeLimit) thenDirectSolution(data,n,solution)elseDivideInput(data,n,smallerSets,smallerSizes,numberSmaller) for i=1 to numberSmaller doDivideAndConquer(smallerSets[i],smallerSizes[i],smallerSolution[i])end forCombineSolutions(smallerSolution,numberSmaller,solution) end if测试算法不同问题的分治算法在分解与合并步骤可能有所不同，例如合并排序和快速排序这两个有代表性的分治算法中，合并排序算法没有分解、只有合并，快速排序算法没有合并、只有分解；这两个算法的计算时间分别取决于合并与分解步骤。
这两个算法分别如下：1、MergeSort(list, first, last)if first<last thenmiddle=(first+last)/2MergeSort(list, first, middle)MergeSort(list, middle+1, last)MergeLists(list, first, middle, middle+1, last) end ifMergeLists(list, start1, end1, start2, end2)while (start1≤end1) and (start2≤end2) doif list[start1] < list[start2] thenresult[indexC]=list[start1]start1=start1+1elseresult[indexC]=list[start2]start2=start2+1end ifindexC=indexC+1end whileif start1≤end1 thenfor i=start1 to end1 doresult[indexC]=list[i]indexC=indexC+1end forelsefor i=start2 to end2 doresult[indexC]=list[i]indexC=indexC+1end forindexC=1for i=finalStart to finalEnd dolist[i]=result[indexC]indexC=indexC+1end for2、QuickSort(list, first, last)if first<last thenpivot=PivotList(list, first, last)QuickSort(list, first, pivot-1)QuickSort(list, pivot+1, last)end ifPivotList (list, first, last)PivotValue= list[first]PivotPoint=firstfor index=first+1 to last doif list[index]<PivotValue thenPivotPoint=PivotPoint+1Swap(list[PivotPoint],list[index])end ifend forSwap(list[first],list[PivotPoint]return PivotPoint以上两个算法具有O(n log n)的时间复杂度。
3. 实验内容(1)编程实现以上两个用于排序的分治算法，使用生成的随机数作为测试数据。
对每个算法，记录随着测试数据增加算法基本操作执行次数，分析并以图形方式展现增长率；对于两个理论上均为最优的排序算法，对比随着测试数据增加算法增长率变化趋势；测试、验证、对比算法的时间复杂度。
4. 实验步骤和要求(1) “比较”是以上两个排序算法的基本操作，在算法中设置比较操作执行的全局计数器，编程实现算法（输出最终的计数值）。
快速排序import java.util.Scanner; package com.ntz.text;public class Text{public static voidmain(String[] args){quicksort qs = newquicksort();int i,N;Scanner scanner = newScanner(System.in);N =scanner.nextInt();int []A = new int[N];for(i=0;i<N;i++){A[i] =(int)(Math.random()*100);}qs.data= A; //将该数组赋值给快速排序的数组qs.sort(0,qs.data.length-1); //调用排序方法qs.display(); //显示排序后的记录}}class quicksort{int m=0;public int data[];private int partition(int sortArray[],int low,inthigh){ int key =sortArray[low];//关键字通常设置为序列的第一项while(low<high){while(low<high &&sortArray[high]>=key)//判断记录右侧是否有小于关键字的记录high--; //如果没有，则移动右侧的指针sortArray[low] =sortArray[high];//如果有则交换while(low<high &&sortArray[low]<=key)//判断记录左侧是否有大于关键字的记录low++; //如果没有，则移动左侧的指针sortArray[high] =sortArray[low];//如果有则交换}sortArray[low] = key; //排序的终止条件是左侧指针和右侧指针重合，即low=highreturn low;}public void sort(int low,inthigh){if(low<high){int result= partition(data ,low,high); sort(low,result-1);sort(result+1,high); } m ++; } public void display(){ for (int i=0;i<data .length ;i++) //利用循环，输出排列后的序列{ System.out .print(data [i]);System.out .print(" ");} System.out .println();System.out .println("次数为："+m ); } } 归并排序package com.ntz.text;import java.util.Arrays;import java.util.Scanner;public class Text {private static int m =0;public static voidmerge(int [] a, int low, intmid, int high) {int [] temp = new int [high - low + 1];int i = low;// 左指针 int j = mid + 1;// 右指针 int k = 0;// 把较小的数先移到新数组中 while (i <= mid && j <= high) {if (a[i] < a[j]) {temp[k++] = a[i++]; } else { temp[k++] =a[j++];}} while (i <= mid){ temp[k++] =a[i++]; }while (j <= high) {temp[k++] =a[j++]; } for (int k2 = 0;k2 < temp.length ; k2++) { a[k2 + low] =temp[k2];}}public static voidmergeSort(int [] a, int low,int high) {int mid = (low + high)/ 2;if (low < high) {// 左边 mergeSort (a, low, mid); // 右边mergeSort(a, mid + 1, high);// 左右归并merge(a, low, mid, high);}m++;}public static voidmain(String[] args) {int N;Scanner scanner = new Scanner(System.in);N =scanner.nextInt();int []a = new int[N];for(int i=0;i<N;i++){a[i] =(int)(Math.random()*100);}mergeSort(a, 0,a.length - 1);System.out.println("排序结果：" +Arrays.toString(a));System.out.println("次数为"+m);}}设置记录每次递归调用时描述问题规模的变量，程序结束时输出其值。
通过测试保证程序正确无误。
注意递归程序的实现、调试和测试。
