算法设计与分析论文

2022-10-30 19:57:24 第一文档网 [ 字体：小中大 ] [ 阅读： ] [

【#第一文档网# 导语】以下是®第一文档网的小编为您整理的《算法设计与分析论文》，欢迎阅读！
算法,分析,论文,设计
083411 14 陈彬

算法设计与分析论文

算法理论研究的是算法的设计技术和分析技术，两者是相互依存的，设计出的算法需要

检验和评价，对算法的分析反过来又将改进算法的设计。

算法设计与分析中包含非常经典的算法设计技术，例如递归与分治、动态规划、贪心、回溯、分支限界、图算法，也包括了一些高级的算法设计主题，例如网络流和匹配、启发式搜索、线性规划、数论以及计算几何。下面我将介绍一下递归与分治策略。

具体实验如下：

一、实验目的：熟练掌握递归与分治的思想并应用其解决实际问题。二、递归与分治策略思想

基本思想将要求解的较大规模的问题分割成k个更小规模的子问题。

对这k个子问题分别求解。如果子问题的规模仍然不够小，则再划分为k个子问题，如此递归的进行下去，直到问题规模足够小，很容易求出其解为止。

实验题目：找出从自然数1,2,…….，n其中任取r个数的所有组合。算法思想：当组合的第一个数字选定时，其后的数字是从余下的m-1个数中取k-1数的组合。这就将求m个数中取k个数的组合问题转化成求m-1个数中取k-1个数的组合问题。设数引入工作数组a[]存放求出的组合，约定函数将确定的k个数字组合的第一个数字放在a[k]中，当一回组合求出后，才将啊a[]中的一个组合输出。第一个数可以是m、m-1、……、k，函数将确定组合的第一个数字放入数组后，有两种可能的选择，因还未确定组合的其余元素，继续递归去确定；或已确定了组合的元素，输出这个组合。

问题描述：找出从自然数1、2、……、n中任取r个数的所有组合。例如n=5，n=3的所有组合为：

（1）5、4、3 （2）5、4、2 （3）5、4、1

（4）5、3、2 （5）5、3、1 （6）5、2、1 （7）4、3、2 （8）4、3、1 （9）4、2、1 （10）3、2、1

分析所列的10个组合，可以采用这样的递归思想来考虑求组合函数的算法。设函数为void find(int m,int k)为找出从自然数1、2、……、m中任取k个数的所有组合。当组合的第一个数字选定时，其后的数字是从余下的m-1个数中的组合问题。设函数引入工作数组a[]存放求出的组合的数字，约定函数将确定的k个数字组合的第一个数字放在a[k]中，当一个组合求出后，才将a[]中的一个组合输出。第一个数可以是m、m-1、……、k，函数将确定组合的第一个数字放入数组后，有两种肯的选择，因还未去顶组合的其余元素，继续递归去确定；或因已确定了组合的全部元素，输出这个组合。细节见一下程序中的函数。

【程序】

#include #include using namespace std; #define MAXN 1000 int a[MAXN]; void f(int m,int k) {

int i,j;

for(i=m;i>=k;i--) {

a[k]=i;

if(k>1)f(i-1,k-1); else {

for(j=1;a[j]>0;j++) printf(“%4d”,a[j]); printf(“\n”); } } }

int main() {

int m,k,i;

while(cin>>m>>k) {

for(i=0;i a[i]=0; a[0]=m-1; f(m,k); }

return0;

}

程序运行结果：

5 4 2 3 4 5 1 3 4 5 1 2 4 5 1 2 3 5 1 2 3 4

以上则是我解决该问题的具体方法和编程过程。