数据结构与算法课程报告。
回溯算法。学号。
姓名魏炜焙
班级。教师。
华侨大学电子工程系。
设计目的 掌握并熟练运用《数据结构与算法分析》中所学到的知识解决问题。
基本要求。找一个现实的例子，根据第十章内容，选择一个算法进行解决，并进行分析。
设计内容。本实验运用的是回溯算法，解决跳马问题。跳马问题也称为骑士周游问题，是算法设计中的经典问题。
国际象棋棋盘上某个位置的一只马，只走63步，正好走过除起点外的其他63个位置各一次。
问题分析。此题实际上是一个hamilton回路问题，和迷宫问题很相似，可以用回溯算法来解决。考虑到马在每一个位置，最多有8种跳法，如下图所示：
以当前马所在格子为中心，用回溯算法一一尝试八种跳法，该算法最坏的时间复杂度为o(8n*n)。这是一个相当大的数字，不能接受，但实际情况好得多。并且在37步的时候，开始发生回溯，可通过改backtrace中的第一个if中的参数发现。
据统计，总的回溯次数达300多百万次。用一般计算机运行20分钟也没运行出结果。我们可以考虑，当n=8时，为2^192，即使对于2^100=1.
3*10^30，对于一台每秒1万亿（10^12）次操作的计算机，也需要4*10^10才能完成，超过了45亿年——地球的估计年龄。但是，该算法可以适当改进，考虑到即向前看两步，当每准备跳一步时，设准备跳到(x，y)点，计算(x，y)这一点可能往几个方向跳（即向前看两步），将这个数目设为(x，y)点的权值，将所有可能的(x，y)按权值排序，从最小的开始，循环遍历所有可能的(x，y)，回溯求出结果。算法可以求出所有可能的马跳棋盘路径，算出一个可行的结果很快，但在要算出所有可能结果时，仍然很慢，因为最坏时间复杂度本质上并没有改变，仍为o(8^(n * n))，但实际情况很好，在瞬间即可得到一个解，当然，要求得所有解，也需要很长的时间。
程序。#include <>
#include <>
/棋盘行数。
const int n = 8;
int step[n * n] =保存每一步做出的选择。
int chess[n][n] =棋盘。
int jump[8][2] =
int p = 0;//对解的个数计数。
/判断是否合法。
int canjump(int x, int y)
if (x >=0 &&x < n &&y >=0 &&y < n &&chess[x][y] =0)
return 1;
return 0;
/求权值。int weightstep(int x, int y)
int count = 0;
for (int i = 0; i < 8; +i)
return count;
/权值排序。
void inssort(int a,int b,int n)
if (n <=0) return;
for (int i = 0; i < n; +i)
/输出结果。
void outputchess()
int i;
for (i = 1; i <=n * n - 1; +i)
printf("");
for(i=0;i
/回溯算法。
void backtrace(int t, int x, int y)
if (t >=n * n)
elseinssort(count, possiblesteps, k);/排序。
for (i = 0; i < k; +i)
int main()
int x = 0;
int y = 0;
chess[x][y] =1;
backtrace(1, x, y);
printf("all results number = d ",p);
运行结果。
数据结构与算法
本章知识要点 算法的基本概念 数据结构的定义 线性表的定义和存储 树 二叉树的定义和存储 查找与排序算法。算法 algorithm 是一组有穷的规则，规定了解决某一特定类型问题的一系列运算，是对解题方 与完整的描述。算法是解题的步骤，可以把算法定义成解一确定类问题的任意一种特殊的方法。在计算机科学中...
算法与数据结构
学院专业姓名学号。实验1 线性表的操作 12学时 问题描述 假设一个班级内有n个学生，定义一个学生类和一个班级类。学生类中包括学号 姓名 性别 年龄 专业等属性 班级类包括一个学生对象链表。定义如下 class student class myclass student stu head 链表表头指...
算法与数据结构
1 简述算法的概念及其五个重要特性。2 下图是用邻接表存储的图，请画出此图，写出其邻接矩阵以及从c点开始分别按广度优先搜索和深度优先搜索遍历该图的结果。给定一棵用二叉链表表示的二叉树，其根指针为root，编写求此二叉树叶结点个数的算法，要求先写出二叉链表的类型定义。2.编写简单选择排序的算法。1 用...