成绩评定表课程设计任务书摘要随着科技的日新月异，计算机的应用在科技领域变得不可代替，所以研究计算机的算法设计在计算机应用方面有重要意义。
本文主要研究算法中的分治法以及回溯法。
本文第一问，是使用分治法解决集合划分问题，即n个元素的集合可以划分为多少个不同的由m 个非空子集组成的集合。
设S(n,m)代表最后所求的集合个数，运用自顶向下的方法，将第一个集合中的元素的个数从最高依次往下分配，在分配过程中运用递归分治法来计算集合的个数，可以得到递归方程S(n,m)=m*S(n-1,m)+S(n-1,m-1)。
然后根据分治法的思想结合此问题写出本题的算法，最后通过C++语言编程实现。
本文第二问，是使用回溯法解决最小重量机器问题，即在总价格不超过c 的范围内设计出是机器重量最小的方案，该问题为NP难解问题，它的解空间可以用子集树表示。
在搜索空间树时，只要其做儿子节点是一个可行节点，搜索就进入其左子树。
当右子树中可能包含最优解是才进入右子树搜索。
否则将右子树剪去。
设w是当前剩余机器部件重量的总和；wp是当前机器重量；bestw是当前最小重量；cost是当前的消费；c是总价格。
当wp+w<=bestw或者cost>c时，可剪去右子树。
最后根据回溯算法思想以及本题实际情况，设计出合适的算法，并用C++语言编程实现。
关键字：回溯法；分治法；C++语言；目录1 分治法解决集合划分问题 (1)1.1问题重述 (1)1.2问题分析 (1)1.3 算法分析与设计 (2)1.4算法的实现与结果 (3)2 回溯法解决最小重量机器问题 (6)2.1 问题重述 (6)2.2问题分析 (6)2.3算法分析与设计 (7)2.4算法实现与结果 (8)心得体会 (12)参考文献 (13)1 分治法解决集合划分问题1.1问题重述集合划分问题问题描述：n个元素的集合{1,2,.,n }可以划分为若干个非空子集。
例如，当n=4 时，集合{1,2,3,4}可以划分为15个不同的非空子集。
其中，集合{{1，2，3，4}} 由1个子集组成；集合{{1，2}，{3，4}}，{{1，3}，{2，4}}，{{1，4}，{2，3}}，{{1，2，3}，{4}}，{{1，2，4}，{3}}，{{1，3，4}，{2}}，{{2，3，4}，{1}}由2个子集组成；集合{{1，2}，{3}，{4}}，{{1，3}，{2}，{4}}，{{1，4}，{2}，{3}}，{{2，3}，{1}，{4}}，{{2，4}，{1}，{3}}，{{3，4}，{1}，{2}}由3个子集组成；集合{{1}，{2}，{3}，{4}}由4个子集组成。
编程任务：给定正整数n 和m，计算出n个元素的集合{1,2,., n }可以划分为多少个不同的由m 个非空子集组成的集合。
数据输入：由文件input.txt提供输入数据。
文件的第1行是元素个数n和非空子集数m。
结果输出:程序运行结束时，将计算出的不同的由m个非空子集组成的集合数输出到文件output.txt中。
1.2问题分析假设将n个元素分解到m个集合中，首先考虑将(n – (m - 1))个元素分到第一个集合中，将余下的(n - 1)个元素分别分配到余下的(m - 1)个集合中，然后再考虑将(n – (m - 2))个元素分配到第一个集合中，将余下的(n - 2)个元素分别分配到余下的(m - 1)集合中，依此类推，直到后面的有一个集合中的元素个数比第一个集合中的元素个数多为止。
对于每种分配方法的集合个数的求法，可以先用排列组合的方法计算出元素选取的情况，再通过递归计算出选取该元素后所组成的集合的个数。
即运用自顶向下的方法，将第一个集合中的元素的个数从最高依次往下分配，在分配过程中运用递归分治法来计算集合的个数。
1.3 算法分析与设计算法分析：本题求解主要用到了分治法，分治法的基本思想是将一个规模为n的问题分解为k个规模较小的子问题，这些子问题互相独立且与原问题相同。
递归地解这些子问题，然后将各个子问题的解合并得到原问题的解。
它的一般算法设计模式如下：divide-and-conquer(p){if(|P|<=n0)adhoc(P);divide Pinto smaller subinstances P1,P2,…,Pk;for(i=1;i<=k;i++)yi=divide-and-conquer(Pi);return merge(y1,y2,…,yk);}其中，|P|表示问题P的规模，n0为一阈值，表示当问题P的规模不超过n0是，问题已容易解出，不必再继续分解。
adhoc（P）是改分执法中的基本子算法，用于直接解小规模的问题P。
当P的规模不超过n0是，直接用算法adhoc（P）求解。
算法merge（y1，y2，…,yk）是该分治法中的子算法，用于将P的子问题P1,P2,…,Pk的解y1，y2，…,yk合并为P的解。
从分治法的一般设计模式可以看出，用它设计出的程序一般是递归算法。
我们运用自顶向下的方法，将第一个集合中的元素的个数从最高依次往下分配，即首先考虑将(n – (m - 1))个元素分到第一个集合中，将余下的(n - 1)个元素分别分配到余下的(m - 1)个集合中，然后再考虑将(n – (m - 2))个元素分配到第一个集合中，将余下的(n - 2)个元素分别分配到余下的(m - 1)集合中，依此类推，直到后面的有一个集合中的元素个数比第一个集合中的元素个数多为止。
由此可以得到下面的递归方程：S(n,n+1)=0S(n,0)=0S(0,0)=1S(n,m)=m*S(n-1,m)+S(n-1,m-1)算法设计：void StirlingNumbers2(int m,int n){int min;S[0][0]=1;for(int i=1;i<=m;i++)S[i][0]=0;for(i=0;i<=m;i++)S[i][i-1]=0;for(i=1;i<=m;i++){for(int j=1;j<=min;j++)S[i][j]=j*S[i-1][j]+S[i-1][j-1];}}int computcB(int m){StirlingNumbers2(m,m);for(int i=0;i<=m;i++)B[i]=0;for(i=1;i<=m;i++){for(int j=0;i<=i;j++)B[i-1]+=S[i][j]}}1.4算法的实现与结果用C++语言来实现上述算法，代码如下：#include <iostream>using namespace std ;int zuhe(int m, int n, int r){int p = m, q = n, t = 1, s = 1 ;for(int i = 0; i < p; i++){t *= n ;n-- ;s *= m ;m-- ;}if(q == p * 2 && r == 1) return (t / s) / 2 ;return t / s ;}//运用递归计算集合的个数int jihe(int m, int n) //m为元素的个数, n为集合的个数{int count = 0 ;if(m == n || m == 0) return 1;if(n == 1) return 1 ;for(int i = (m - n + 1); i >= (m - i + (n - 2))/(n - 1); i--){count += zuhe(i, m, n - 1) * jihe(m - i, n - 1) ;}return count ;}int main(){int m, n ;cout<<"请输入元素的个数和集合的个数: ";cin>>m>>n ;cout<<jihe(m, n)<<endl ;return 0 ;}运行结果：图1 集合划分的输入界面图2集合划分的结果界面结果分析：通过上述运行结果可以看到，4个元素的集合可以划分为6个不同的由3个非空子集组成的集合。
本题运用自顶向下的方法，将第一个集合中的元素的个数从最高依次往下分配，在分配过程中运用递归分治法来计算集合的个数。
在这个过程中，关键部分还是循环条件的控制。
2 回溯法解决最小重量机器问题2.1 问题重述最小重量机器问题问题描述：最小重量机器设计问题：设某一机器由N个部件组成，每一个部件都可以从M个不同的供应商处购得。
设wij是从供应商j处购得部件i的重量，cij是相应的价格。
试设计一个算法,给出总价格不超过c的最小重量机器设计。
算法设计：对于给定的机器部件重量和及其部件价格，计算总价格不超过c的最小重量机器设计。
2.2问题分析最小重量机器问题同0-1背包问题一样，都是子集的选取问题，一般情况下最小重量机器问题是NP难解的。
它的解空间可以用子集树表示。
在搜索空间树时，只要其做儿子节点是一个可行节点，搜索就进入其左子树。
当右子树中可能包含最优解是才进入右子树搜索。
否则将右子树剪去。
设w是当前剩余机器部件重量的总和；wp是当前机器重量；bestw是当前最小重量；cost是当前的消费；c是总价格。
当wp+w<=bestw或者cost>c时，可剪去右子树。
2.3算法分析与设计算法分析：本题的解决方法主要是回溯法，回溯法有通用的解题法之称。
用它可以系统的搜索一个问题的所有解或任意解，回溯法是一个既带有系统性有带有跳跃性的搜索算法。
他从开始结点出发，以深度优先的方式搜索整个解空间。
这个开始借点成为活结点，同时也成为当前的扩展结点。
在当前的扩展节点处，搜索向纵深方向移至一个新结点。
这个新节点就成为新的活结点，并成为当前的扩展结点。
如果在当前的扩展节点处不能再向纵深方向移动，则当前扩展结点就成为四节点。
此时，应往回移动（回溯法）至最近的一个活结点处，并使这个活结点成为当前的扩展结点。
回溯法以这种工作方式递归地在解空间中搜索，直至找到所要求的解或解空间中已无活结点时为止。
算法设计：template<class Typew,class Typep>bool Machine<Typew,Typep>：：backtrack（int i）{if (i>n){bestw=cw;for (int j=1;j<=n;j++)bestx[j]=x[j];return true;}bool found=faulse;if(bestw<=cc)found=true;for(int j=1;j<=m;j++){x[i]=j;cw+=w[i][j];cp+=c[i][j];}return found;}2.4算法实现与结果根据上面的算法设计，使用C++语言编程，代码如下：#include<iostream>using namespace std;#define N 50class MinWmechine{int n; //部件个数int m; //供应商个数int COST; //题目中的Cint cw; //当前的重量int cc; //当前花费int bestw; //当前最小重量int bestx[N];int savex[N];int w[N][N];int c[N][N];public:MinWmechine();void machine_plan(int i);void prinout();};MinWmechine::MinWmechine(){cw=0; //当前的重量cc=0; //当前花费bestw=-1; //当前最小重量bestx[N];savex[N];cout<<"请输入部件个数：";cin>>n;cout<<"请输入供应商个数：";cin>>m;cout<<"请输入总价格不超过：";cin>>COST;for(int j=0;j<m;j++){for(int i=0;i<n;i++){cout<<"请输入第"<<j+1<<" 个供应商的第"<<i+1<<" 个部件的重量：";cin>>w[i][j];cout<<"请输入第"<<j+1<<" 个供应商的第"<<i+1<<" 个部件的价格：";cin>>c[i][j];if(w[i][j]<0 || c[i][j]<0){cout<<"重量或价钱不能为负数！\n";i=i-1;}}}}void MinWmechine::machine_plan(int i){if(i>=n){if(cw <bestw || bestw==-1){bestw=cw;for(int j=0;j<n; j++) //把当前搜过的路径记下来savex[j]=bestx[j];}return;}for(int j=0; j<m; j++) //依次递归尝试每个供应商{if(cc+c[i][j]<COST){cc+=c[i][j];cw+=w[i][j];bestx[i]=j;machine_plan(i+1);bestx[i]=-1;cc-=c[i][j];cw-=w[i][j];}}}void MinWmechine::prinout(){int i,j,ccc=0;for(j=0;j<m;j++){for(i=0;i<n;i++){cout<<"第"<<j+1<<" 供应商的第"<<i+1<<" 部件重量："<<w[i][j]<<"价格："<<c[i][j]<<"\n";}}for(j=0; j<n; j++){bestx[j]=-1;}machine_plan(0);cout<<"\n最小重量机器的重量是: "<<bestw<<endl;for(int k=0; k<n; k++){cout<<" 第"<<k+1<<" 部件来自供应商"<<savex[k]+1<<"\n";ccc+=c[k][savex[k]];}cout<<"\n该机器的总价钱是: "<<ccc<<endl;cout<<endl;}int main(void){MinWmechine Y;Y.prinout();return 0;}图3 最小重量机器的输入界面图4最小重量机器的运行界面通过上面的运行结果可以看到在上面情况中从第一供应商选择第一个部件，从第二供应商选择第二个部件，此时机器最小重量为5，对应花费为8。
