《算法设计与分析-回溯法》上机实验报告

253、     while (!q.empty()){

254、         n1 = q.front();

255、         q.pop();

256、         sum++;

257、         for (int i = 0; i < 4; i++){

258、             int xtmp = n1.x + direction[i].dx;

259、             int ytmp = n1.y + direction[i].dy;

260、             //符合要求且颜色相同

261、             if (judge(xtmp, ytmp) && color[xtmp][ytmp] == color[x][y]){

262、                 node n2;

263、                 n2.x = xtmp;

264、                 n2.y = ytmp;

265、                 q.push(n2);

266、                 visited[xtmp][ytmp] = true;

267、             }

268、         }

269、     }

270、     return sum;

271、 }

272、

273、 int main()

274、 {

275、     initDirection();

276、     while(cin>>m>>n){

277、         //访问初始化

278、         memset(visited, false, sizeof(visited));

279、         for(int i=0; i

280、             cin >> color[i];

281、         int maxSum = 0;

282、         for(int i=0; i

283、             for(int j=0; j

284、                 maxSum = max(maxSum,bfs(i,j));

285、             }

286、         }

287、         cout<

288、     }

289、     return 0;

290、 }

1、 素数环--1789

2、 八皇后--1058

3、 迷宫问题--1165

4、 魔方问题--1061

1、素数环问题，一直显示超时，后来经过老师提醒，判断如果奇数则跳过后AC了。

2、八皇后问题，输出顺序老是不对，后来发现原来题目中输出时将i和j顺序互换了。

3、迷宫问题发现了昨天的错误，是判断超过边界的判断式有问题，不过这次我仍然用的加边框的方式过的。

回溯法问题。

1、 素数环--1789

1） 基本思想

对于第一个点，固定为1，剩下的点我们从2开始不断试探，如果不满足条件（和前一个点相加不为素数或者重复）则回溯。

PS:最后一个点和第一个点相加

2、 八皇后--1058

1） 基本思想

首先对于每一行，先从第一列开始放置，如果不行(竖线和对角有其他皇后)换下一个个位置，可以的话换下一行。如果有一行的皇后无法摆放就回溯。要是所有都试过了仍然有皇后没有摆放位置，则无解。

3、 迷宫问题--1165

1） 基本思想

首先从起点出发，搜索8个方向，如果通且未访问过则继续，并标记已访问，如果不通已访问则试探下一个点，如果都不行则回溯。这里在外层全套上0，即加入不可通的边框。

4、 魔方问题--1061

1） 基本思想

其实非常类似迷宫问题，上下左右四个方向进行搜寻，如果访问过就标记下，没有了或者全部访问过了则返回，对于输入的每一个颜色重复上述操作，如果有更大的便更新最大色块来找到最大的那个色块。

1、 素数环--1789

2、 #include 

3、 #include 

4、 using namespace std;

5、

6、 int a[21] = {0};   //数

7、 int n;

8、

9、 //判断是否是素数

10、 bool isPrime(int tmp){

11、     for(int i=2; i<=sqrt(tmp); ++i)

12、         if(tmp % i == 0)

13、             return 0;

14、     return 1;

15、 }

16、

17、 //判断素数是否重复

18、 bool judge(int k){

19、     bool flag = 0;

20、     //重复则返回0

21、     for(int i=0; i

22、         if(a[i]==a[k])

23、             return 0;

24、     flag = isPrime(a[k]+a[k-1]);

25、     //最后一个数和第一个数

26、     if(flag==1 && k==n-1)

27、         flag = isPrime(a[k]+a[0]);

28、     return flag;

29、 }

30、

31、 void primeCircle(int n){

32、     //初始化数组

33、     for(int i=0; i

34、         a[i] = 0;

35、     }

36、     int k=1;    //下标

37、     a[0] = 1;   //初始化为第一个数

38、     while(k>=1){

39、         a[k] += 1;  //取下一个数

40、         //判断重复就取别的数

41、         while(a[k]<=n){

42、             if(judge(k))

43、                 break;

44、             else

45、                 a[k] += 1;

46、         }

47、         //输出

48、         if(a[k]<=n && k==n-1){

49、             for(int i=0; i

50、                 cout<

51、             cout<

52、         }

53、         //处理下个顶点

54、         if(a[k]<=n && k

55、             k += 1;

56、         else

57、             a[k--] = 0; //回溯

58、     }

59、 }

60、

61、 int main()

62、 {

63、     int count = 0;

64、     while(cin>>n){

65、         count++;

66、         cout<<"Case "<

67、         if(n==1)

68、             cout<<1<

69、         if(n%2==1)

70、             continue;

71、         primeCircle(n);

72、     }

73、     return 0;

74、 }

75、 八皇后--1058

76、 #include 

77、 #include 

78、 using namespace std;

79、

80、 int x[100]={0}; //第i个皇后摆放在第i行第i个位置

81、 int count = 0;  //记录有几个解

82、

83、 //看皇后k放在x[k]会不会冲突

84、 bool judge(int k){

85、     for(int i=0; i

86、         if(x[i]==x[k] || abs(i-k)==abs(x[i]-x[k]))

87、             return 1;

88、     return 0;

89、 }

90、

91、 void Queen(int n){

92、     for(int i=0; i

93、         x[i] = -1;

94、     int k=0;

95、     while(k>=0){

96、         x[k]++; //在下一列放皇后k

97、         //冲突处理

98、         while(x[k]

99、             x[k]++; //试探下一个位置

100、         //输出一个解

101、         if(x[k]

102、             count++;

103、             cout<<"No. "<

104、             for(int i=0; i

105、                 for(int j=0; j

106、                     cout<<(i==x[j])<<" ";

107、                 cout<

108、             }

109、         }

110、         //有皇后未摆放

111、         else if(x[k]

112、             k++;    //准备摆放

113、         else

114、             x[k--] = -1;    //回溯，重放皇后k

115、     }

116、 }

117、

118、 int main()

119、 {

120、 //    int n;

121、 //    cin>>n;

122、     Queen(8);

123、     //cout<<"共"<

124、     return 0;

125、 }

126、 迷宫问题--1165

127、 #include 

128、 using namespace std;

129、

130、 int xIn, yIn, xOut, yOut;   //出入口坐标

131、 int xLength, yLength; //迷宫的行数和列数

132、 int maze[1000][1000];       //迷宫数组

133、 bool visited[1000][1000] = {0};       //访问标记数组

134、

135、 struct direction{

136、     int dx, dy;

137、     void setDirection(int dx,int dy){

138、         this->dx = dx;

139、         this->dy = dy;

140、     }

141、 }direction[4];

142、

143、 void initDirection(){

144、     direction[0].setDirection(0,1);     //东

145、     direction[1].setDirection(1,0);     //南

146、     direction[2].setDirection(0,-1);    //西

147、     direction[3].setDirection(-1,0);    //北

148、 }

149、

150、 //解决迷宫问题的递归算法

151、 bool seekPath(int x, int y){

152、     //从迷宫某一位置[i][j]开始，寻找出口[xOut][yOut]的一条路径,如果找到，则函数返回true

153、     int xtmp, ytmp; //记录位置信息

154、     if(x==xOut && y==yOut)

155、         return true;

156、     //循环遍历(x,y)的8个方向

157、     for(int i=0; i<4; i++) {

158、         xtmp = x+direction[i].dx;

159、         ytmp = y+direction[i].dy;

160、

161、 //        if(xtmp<0 || xtmp>=xLength || ytmp<0 || ytmp>=yLength)

162、 //            continue;

163、

164、         //找下一位置寻找通向出口的路径

165、         if(maze[xtmp][ytmp]==1 && visited[xtmp][ytmp]==0){ //如果通且未被访问过

166、             visited[xtmp][ytmp] = 1; //标记为已访问过

167、             if(seekPath(xtmp, ytmp)){ //递归试探

168、 //                printf("(%d,%d)\n",xtmp-1,ytmp-1);//逆向输出路径坐标

169、                 return true;

170、             }

171、         }

172、         //回溯，换一个方向再试探通向出口的路径

173、     }

174、     return false; //找不到通向出口的路径

175、 }

176、

177、 int main(){

178、     initDirection();    //初始化方向

179、     while(cin>>xLength>>yLength){

180、         for(int i=0; i<=yLength+1; ++i){

181、             maze[0][i] = 0;

182、             maze[xLength+1][i] = 0;

183、         }

184、         for(int i=0; i<=xLength+1; ++i){

185、             maze[i][0] = 0;

186、             maze[i][yLength+1] = 0;

187、         }

188、         for(int i = 1; i <= xLength; i++)

189、             for(int j = 1; j <= yLength; j++) {

190、                 cin >> maze[i][j];

191、                 visited[i][j] = 0;

192、             }

193、         xIn = 1;

194、         yIn = 1;

195、         xOut = xLength;

196、         yOut = yLength;

197、         visited[xIn][yIn] = 1;  //从入口开始

198、         if(seekPath(xIn, yIn))

199、             cout<<"Bingo";

200、         else

201、             cout<<"No way";

202、         cout<

203、     }

204、     return 0;

205、 }

206、 魔方问题--1061

207、 #include 

208、 #include 

209、 #include 

210、 #include 

211、 using namespace std;

212、

213、 char color[100][100];

214、 bool visited[100][100];

215、 int m, n;   //魔方的行、列

216、

217、 struct direction{

218、     int dx, dy;

219、     void setDirection(int dx,int dy){

220、         this->dx = dx;

221、         this->dy = dy;

222、     }

223、 }direction[4];

224、

225、 void initDirection(){

226、     direction[0].setDirection(0,1);     //东

227、     direction[1].setDirection(1,0);     //南

228、     direction[2].setDirection(0,-1);    //西

229、     direction[3].setDirection(-1,0);    //北

230、 }

231、

232、 struct node{

233、     int x, y;

234、 };

235、

236、 bool judge(int x, int y){

237、     if(x>=0 && x=0 && y

238、         return 1;

239、     return 0;

240、 }

241、

242、 int bfs(int x, int y){

243、     if (visited[x][y] == 1){

244、         return 0;

245、     }

246、     queue q;

247、     node n1;

248、     n1.x = x;

249、     n1.y = y;

250、     q.push(n1);

251、     visited[x][y] = 1;

全套毕业设计论文现成成品资料请咨询