实验四回溯算法

算法设计与分析实验报告实验名称_____回溯算法_____学院________数学与计算机学院____ 班级_______信科00000___________ 学号_______6666666666__________ 姓名_____000000________________ 2016年月日{if(((a+b)==24)||((a-b)==24)||((a*b)==24)||(b!=0&&a%b==0&&a/b==24)){//如果经过上面的计算得到解while(!route.empty()){node now=route.front();printf("%d%c%d=%d\n",now.a,now.oper,now.b,now.sum);//依次输出前面的计算过程route.pop();}if((a+b)==24){if(b>a) swap(a,b);printf("%d+%d=%d\n",a,b,a+b);}if((a-b)==24) printf("%d-%d=%d\n",a,b,a-b);if((a*b)==24) {if(b>a) swap(a,b);printf("%d*%d=%d\n",a,b,a*b);}if(a%b==0&&b!=0&&(a/b)==24) printf("%d/%d=%d\n",a,b,a/b);//a/b比较特殊，要求结果必须是整数flag=true;//表示找到解，一旦找到任何一个解就退出}return ;}queue <node> temp=route;node x;x.a=a,x.b=b,x.sum=a+b,x.oper='+';if(b>a) swap(x.a,x.b);temp.push(x);dfs(cur+1,a+b,num[cur+1],temp);//(((a*b)*c)*d) 模型temp=route;x.a=a,x.b=b,x.sum=a*b,x.oper='*';if(b>a) swap(x.a,x.b);temp.push(x);dfs(cur+1,a*b,num[cur+1],temp);temp=route;x.a=a,x.b=b,x.sum=a-b,x.oper='-';temp.push(x);dfs(cur+1,a-b,num[cur+1],temp);if(b!=0&&a%b==0){//a/b需要验证合法性temp=route;x.a=a,x.b=b,x.sum=a/b,x.oper='/';temp.push(x);dfs(cur+1,a/b,num[cur+1],temp);}temp=route;x.a=b,x.b=num[cur+1],x.sum=b+num[cur+1],x.oper='+';if(x.b>x.a) swap(x.a,x.b);temp.push(x);dfs(cur+1,a,b+num[cur+1],temp);//a*((b*c)*d) 模型temp=route;x.a=b,x.b=num[cur+1],x.sum=b*num[cur+1],x.oper='*';if(x.b>x.a) swap(x.a,x.b);temp.push(x);dfs(cur+1,a,b*num[cur+1],temp);temp=route;x.a=b,x.b=num[cur+1],x.sum=b-num[cur+1],x.oper='-';temp.push(x);dfs(cur+1,a,b-num[cur+1],temp);if(num[cur+1]!=0&&b%num[cur+1]==0) {temp=route;x.a=b,x.b=num[cur+1],x.sum=b/num[cur+1],x.oper='/';temp.push(x);dfs(cur+1,a,b/num[cur+1],temp);}}int main(){//freopen("point24.in","r",stdin);//输入输出重定向//freopen("point24.out","w",stdout);queue <node> t;scanf("%d %d %d %d",&num[0],&num[1],&num[2],&num[3]);while(!flag){dfs(1,num[0],num[1],t);printf("%d %d %d %d\n",num[0],num[1],num[2],num[3]);if(!next_permutation(num,num+4)) break;}if(!flag) printf("No answer!\n");system("pause");return 0;}。

对应的邻接矩阵
01 234 001 1 01 1 1 01 01 21 1 01 0 3001 01 41 1 01 0
class MGraph { public:
MGraph(int v,int s); void mColoring(int m,int *x); //一维数组x，存放1~n个顶点的颜色 ~MGraph(); private: void NextValue(int k,int m,int *x); void mColoring (int k,int m,int *x); int **a; //二维数组a，存储图的邻接矩阵 int n,e; //n表示图的顶点数，e表示边数 };
无向图G
【实验内容与要求】
图的着色问题：设G=(V,E)是一连通无向图，有3 种颜色，用这些颜色为G的各顶点着色，每个顶点着 一种颜色，且相邻顶点颜色不同。试用回溯法设计一 个算法，找出所有可能满足上述条件的着色法。
无向图G
无向图G
对应这个无向图的状态空间树应该是怎样的？
是一个完全3叉树，共6层
实验四 回溯法 — 图的着色问题
图的着色问题是由地图的着色问题引申而来的： 用m种颜色为地图着色，使得地图上的每一个 区域着一种颜色，且相邻区域颜色不同。
问题处理：如果把每一个区域收缩为一个顶点， 把相邻两个区域用一条边相连接，就可以把一
个区域图抽象为一个平面图。
地图（map）中地区的相邻关系，在图（graph ）中用边表示。
//若(i, j)是图的边，且相邻结点k和j颜色相同 //发生冲突，选下一种颜色
if (j==k) return; //成功选择一种颜色返回 }while (1); //循环尝试颜色 }
运行结果：

算法设计与分析实验报告1.骑士游历问题（采用回溯法）：在国际象棋的棋盘（8行×8列）上放置一个马，按照“马走日字”的规则，马要遍历棋盘，即到达棋盘上的每一格，并且每格只到达一次。

若给定起始位置（x0,y0）,编程探索出一条路径，沿着这条路径马能遍历棋盘上的所有单元格。

2. 行列变换问题（采用分支限界法）：给定两个m n方格阵列组成的图形A和图形B，每个方格的颜色为黑色或白色，如下图所示。

行列变换问题的每一步变换可以交换任意2行或2列方格的颜色，或者将某行或某列颠倒。

上述每次变换算作一步。

试设计一个算法，计算最少需要多少步，才能将图形A变换为图形B。

图形A图形B}}实例：2. 行列变换问题的程序：package ;import graph{static int sour, dest;//sour是图形的初始整数，dest是图形的目的整数static int ans[]=new int[1<<16];//静态变量（即全局变量），用于存放图形变换的路径int m=4,n=4,x;int row[]=new int[4];int col[]=new int[4];void setx(int x){=x;}int getx(){return ;}x/=2;}}}public static void output(int N){if(N=={outb(N);return;}output[N]);//[N]存放着从初始值到目的值的遍历路径outb(N);}}实例：实验成绩：指导教师：年月日精心搜集整理，。

三、实验结果 通过实验编程，运行程序输入数据后，得到如下结果：
提高题一：用回溯法求解跳马问题
一、实验要求 1、 掌握回溯法的基本原理。 2、 使用回溯法编程，求解跳马问题 二、实验内容 1、 问题描述： 在 N*N 棋盘上有 N2 个格子， 马在初始位置 （X0， Y0） ， 按照象棋中马走 “日” 的规则，使马走遍全部格子且每个格子仅经过一次。编程输出马的走法。 2、 给出算法描述。 编程实现，给出 N=5， （X0，Y0）=（1，1）时的运行结果。 二、实验结果 通过实验编程，运行程序输入数据后，得到如下结果：
四、实验总结与体会
教师评 价
优
良
中
及格
不及格
教师签名
日期
中国矿业大学计算机学院实验报告
课程名称 算法设计与分析 实验名称 2.实验内容 5.流程图 实验四 回溯算法 3：1.实验目的 4.运行结果
基本题一：符号三角形问题
一、实验目的 1、掌握符号三角形问题的算法； 2、初步掌握回溯算法； 二、实验内容 下面都是“-” 。 下图是由 14 个“+”和 14 个“-”组成的符号三角形。2 个同号下面都是 “+” ，2 个异号下面都是“-” 。 + + - + - + + + - - - - + - + + + - + + - + - + 在一般情况下，符号三角形的第一行有 n 个符号。符号三角形问题要求对于给定的 n，计 算有多少个不同的符号三角形，使其所含的“+”和“-”的个数相同。
三、实验结果 通过实验编程，运行程序输入数据后，得到如下结果：
基本题二：0—1 背包问题