回溯法__算法实验报告.doc

实 验 报 告（2014/2015学年 第二学期）课程名称算法分析与设计实验名称回溯法实验时间2015年5月28日指导单位计算机学院软件工程系指导教师张怡婷学生姓名王珣班级学号B13040212学院(系)计算机学院、软件学院专 业计算机科学与技术实 验 报 告实验名称回溯法指导教师张怡婷实验类型验证实验学时2实验时间2015-5-28一、 实验目的和任务 学习编程实现深度优先搜索状态空间树求解实际问题的方法，着重体会求解第一个可行解和求解所有可行解之间的差别。加深理解回溯法通过搜索状态空间树、同时用约束函数剪去不含答案状态子树的算法思想，会用蒙特卡罗方法估计算法实际生成的状态空间树的结点数。 二、 实验环境(实验设备) VC+6.0 三、实验原理及内容（包括操作过程、结果分析等）1、求24点问题给定四个1-9之间的自然数，其中每个数字只能使用一次，用算术运算符，构造出一个表达式，将这4个正整数连接起来（可以使用括号），使最终的得数为24。要求根据问题的特征设计具体算法并编程实现，输入数据为4个自然数。输出若有多个满足要求的表达式，则只输出其中一组；若搜索失败，则输出“Fail!”。【示例】采用一个表达式中用括号确定运算先后次序的方式，如：输入1，5，5，5四个自然数，输出(5-(1/5)*5)。输入3，3，8，8四个自然数，输出(8/(3-(8/3)。【测试数据】(1) 1,5,5,5(2) 3,3,8,8(3) 3,8,8,8(4) 1,2,3,4(5) 2,4,5,6(6) 4,2,2,5(7) 1,2,2,6(8) 4,2,8,8(9) 0,3,8,8代码:#include#include#includeusing namespace std;const double PRECISION = 1E-6; /精度常量const int COUNT_OF_NUMBER = 4; /算24点的自然数个数const int NUMBER_TO_BE_CAL = 24;class RationalNumber /定义有理数类（分子、分母） protected: int numerator,denominator; /numerator：分子，denominator：分母 bool inf; protected: int gcd(int a,int b) /求a和b的最大公约数 int n=1,t; if(a=b) return a; if(anumerator=numerator; this-denominator=denominator; Simplify(); virtual RationalNumber() void Simplify() if(denominator=0) inf=true; else if(numerator=0) denominator=1; inf=false; else int k=gcd(abs(numerator),abs(denominator); numerator/=k; denominator/=k; inf=false; RationalNumber operator+(const RationalNumber& b) const RationalNumber result; result.denominator=this-denominator*b.denominator; result.numerator=this-numerator*b.denominator+this-denominator*b.numerator; result.Simplify(); return result; RationalNumber operator-(const RationalNumber& b) const RationalNumber result; result.denominator=this-denominator*b.denominator; result.numerator=this-numerator*b.denominator-this-denominator*b.numerator; result.Simplify(); return result; RationalNumber operator*(const RationalNumber& b) const RationalNumber result; result.denominator=this-denominator*b.denominator; result.numerator=this-numerator*b.numerator; result.Simplify(); return result; RationalNumber operator/(const RationalNumber& b) const RationalNumber result; result.denominator=this-denominator*b.numerator; result.numerator=this-numerator*b.denominator; result.Simplify(); return result; RationalNumber& operator=(const RationalNumber& b) denominator=b.denominator; numerator=b.numerator; return (*this); RationalNumber& operator=(int b) denominator=1; numerator=b; return (*this); bool operator=(const RationalNumber& b) const double x,y; x=denominator*1.0/b.denominator; y=numerator*1.0/b.numerator; if(x=y) return true; else return false; bool operator=(int b) const int x,y; x=numerator/denominator; y=numerator%denominator; if(x=b&y=0) return true; else return false; bool operator!=(const RationalNumber& b) const double x,y; x=denominator/b.denominator; y=numerator/b.numerator; if(x!=y) return true; else return false; bool operator!=(int b) const int x,y; x=numerator/denominator; y=numerator%denominator; if(x!=b|y!=0) return true; else return false; int Numerator() const return numerator; int Denominator() const return denominator; ;RationalNumber numberCOUNT_OF_NUMBER; /用数组number保存操作数string expressionCOUNT_OF_NUMBER; /用数组expression保存算式bool Search(int n) /递归函数 if (n=1) if (number0=NUMBER_TO_BE_CAL) /成功搜索得到24 /若number是double型 /也可用if (fabs(number0-NUMBER_TO_BE_CAL)PRECISION) coutexpression0endl; /输出表达式 return true; else return false; for (int i=0;in;i+) for (int j=i+1;jn;j+) RationalNumber a, b; string expa, expb; a=numberi; /用a保存numberi b=numberj; /用b保存numberj numberj=numbern-1; /将numbern-1向前填入到原来numberj的位置 expa=expressioni; /用expa保存expressioni expb=expressionj; /用expb保存expressionj expressionj=expressionn-1; /将expressionn-1向前填入到原来expressionj的位置 /因为下一层递归调用search(n-1)将仅对下标为0n-2的数进行操作了 /加法 expressioni=(+expa+expb+); /将a和b计算的算式填入到原来expressioni的位置 numberi=a+b; /将a和b计算的结果填入到原来numberi的位置 if (Search(n-1) return true; /一旦得到一个可行解，即层层向上返回，从而确保只输出一个可行解 /减法有两种情况a-b和b-a expressioni=(+expa+-+expb+); numberi=a-b; if (Search(n-1) return true; expressioni=(+expb+-+expa+); numberi=b-a; if (Search(n-1) return true; /乘法 expressioni=(+expa+*+expb+); numberi=a*b; if (Search(n-1) return true; /除法也有两种情况a/b和b/a if (b!=0) expressioni=(+expa+/+expb+); numberi=a/b; if (Search(n-1) return true; if (a!=0) expressioni=(+expb+/+expa+); numberi=b/a; if (Search(n-1) return true; /本轮调用完毕后，用a,b,expa,expb将数组number和expression恢复原状 numberi=a; numberj=b; expressioni=expa; expressionj=expb; return false;int main() cout请输入COUNT_OF_NUMBER个数endl; for (int i=0;ix; numberi=x; itoa(x,buffer,10); /itoa():将一个10进制的integer数转换为string类型 /即：把输入的int型操作数x，转变成可以放在buffer中的string类型 expressioni=buffer; /用expressioni指针指向buffer数组空间的起始位置 if(Search(COUNT_OF_NUMBER); else coutFail!endl; return 0;2、n皇后问题要求用回溯法求解8-皇后问题，使放置在8*8棋盘上的8个皇后彼此不受攻击，即：任何两个皇后都不在同一行、同一列或同一斜线上。请输出8皇后问题的所有可行解。代码:#include #include using namespace std;bool Place(int k,int i,int *x) /判定两个皇后是否在同一列或在同一斜线上 for (int j=0;jk;j+) if (xj=i)|(abs(xj-i)=abs(j-k) return false; return true;void NQueens(int k,int n,int *x) /递归函数（求解n皇后问题） for (int i=0;in;i+) if(Place(k,i,x) xk=i; if (k=n-1) for (i=0;in;i+) coutxi ; coutendl; else NQueens(k+1,n,x); void NQueens(int n,int *x) NQueens(0,n,x);int main() int x8; for (int i=0;i=LCSLength(i,j-1) cij=LCSLength(i-1,j); sij=2; else cij=LCSLength(i,j-1); sij=3; return cij; / void LCS:CLCS(int i, int j) const / /if(i=0|j=0) return; / if(ai=bj) / / CLCS(i-1,fj-1); / cout=cij-1) CLCS(i-1,j); / else CLCS(i,j-1); / / 思考题3#include #include using namespace std; #define maxlength 11 class LCS public: LCS(int nx,int ny,char *x,char *y) m=nx; n=ny; a=new charm+1; b=new charn+1; memset(a,0,m+2); memset(b,0,n+2); for(int i=0;inx;i+) ai+1=xi; for(int i=0;in) l=m; s=n; else char *t; t=x; x=y; y=t; s=m; l=n; c1=new ints+1; c2=new ints+1; for(int i=0;is;i+) c1i=c2i=0; int LCSLength(); private: 10 int m,n; int *c1,*c2; int l,s; char *a,*b; ; int LCS:LCSLength() int *temp; for(int i=0;is;i+) c1i=0; for(int i=1;i=l;i+) for(int j=1;j=c2j-1) c2j=c1j; else c2j=c2j-1; for(int z=0;zs;z+) c1z=c2z; return c2s; int main() int nx,ny; char *x; char *y; x=new charmaxlength; y=new charmaxlength; coutInput string x:x; nx=strlen(x); coutInput string y:y; ny=strlen(y); LCS lcs(nx,ny,x,y); coutlcs.LCSLength()endl; delete x; delete y; return 0; 回溯法应用实例：采用回溯法框架来计算字典序排列：123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778#include using namespace std; char str = abc; const int size = 3; void constructCandidate(char *input, int inputSize, int index, char *states, char *candidates, int *ncandidates) if (input = NULL | inputSize = 0 | index 0 | candidates = NULL | ncandidates = NULL) return; bool buff256; for (int i = 0; i 256; i+) buffi = false; int count = 0; for (int i = 0; i index; i+) buffstatesi = true; for (int i = 0; i inputSize; i+) if (buffinputi = false) candidatescount+ = inputi; *ncandidates = count; return; bool isSolution(int index, int inputSize) if (index = inputSize) return true; elsereturn false; void processSolution(char *input, int inputSize) if (input = NULL | inputSize = 0) return; for (int i = 0; i inputSize; i+) cout inputi; cout endl; void backTack(char *input, int inputSize, int index, char *states, int stateSize) if (input = NULL | inputSize = 0 | index 0 | states = NULL | stateSize = 0) return; char candidates100; int ncandidates; if (isSolution(index, inputSize) = true) processSol