文档介绍：实验报告
(2014/2015学年第二学期)
课程名称
算法分析与设计
实验名称
回溯法
实验时间
2015
年
5
月
28
日
指导单位
计算机学院软件工程系
指导教师
张怡婷
学生姓名
王珣
班级学号
B13040212
学院(系)
计算机学院、软件学院
专业
计算机科学与技术
实验报告
实验名称
回溯法
指导教师
张怡婷
实验类型
验证
实验学时
2
实验时间
2015-5-28
实验目的和任务
学****编程实现深度优先搜索状态空间树求解实际问题的方法,着重体会求解第一个可行解和求解所有可行解之间的差别。加深理解回溯法通过搜索状态空间树、同时用约束函数剪去不含答案状态子树的算法思想,会用蒙特卡罗方法估计算法实际生成的状态空间树的结点数。
实验环境(实验设备)
VC++
三、实验原理及内容(包括操作过程、结果分析等)
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<iostream>
#include<cmath>
#include<>
using 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(a<b){
t=a;
a=b;
b=t;
}
for(;n!=0;){
n=a%b;
a=b;
b=n;
}
return a;
}
public:
RationalNumber(){
inf=false;
}
RationalNumber(int n){
numerator=n;
denominator=1;
inf=false;
}
RationalNumber(int numerator,int denominator){
this->numerator=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;
=this->denominator*;
=this->numerator*b.