算法分析与设计实验报告 CQUPT(4)

}

}//end out for

int path = 100; int count = 0;

int paths[MAXVEXS];

for (int d = 1; d < G->number_vertex; d++){ count = 0; }

printf(\到V%d的最短距离是:%d \\n\printf(\经过的最短路径是：\\n\path = d; do{ paths[count++] = path; path = shortPath[path];

} while (path != 0); paths[count] = path;

printf(\while (count >=0){ printf(\ printf(\ count--; }

printf(\

dijkstra算法程序结果：

Floyd算法结果：

心得体会：

通过本次实验，了解了动态规划的基本设计策略。掌握了dijkstra贪心法求解最短路径问题的方法。通过改写dijkstra算法，使之成为Floyd算法求解最短路径问题的方法。通过对比这两个算法的实现过程，更好地了解这两个算法的本质区别。同时也加深了对排序算法的理解与实现。

实验报告四N-皇后问题求解

实验目的：

1）以Q-皇后问题为例，掌握回溯法的基本设计策略。 2）掌握回溯法解决Q-皇后问题的算法并实现； 3）分析实验结果。

实验内容与步骤

1.用回溯法求解N-Queen，参考教材算法思想，并实现算法。 要求：用键盘输入N；输出此时解的个数，并统计运算时间。 2.给出N=4,5,6时，N-Queen解的个数。

3.尝试增大N，观察运行情况；并理解该算法的时间复杂度。

实验主要步骤：

#include #include int X[10];

bool PLACE (int k) { int i=1; while(i

void main() { int k=1,n; int count=0; printf(\请输入一个正整数：\\n\ scanf(\ while (k>0) //对所有行执行以下语句 { X[k] = X[k]+1; //移到下一列 while(X[k]<=n && !PLACE(k) )

}

}

{

X[k] = X[k]+1; //移到下一列，再判断 }

if (X[k] <= n) //找到一个位置 {

if (k==n) //一个完整的解 { //print

printf(\可行方案:\\n\ for (int t=1;t<=n;t++) printf(\ printf(\ count +=1 ; } else {k=k+1; X[k]=0;} //转向下一行 } else k=k-1; //回溯

printf(\可行方案个数： %d \\n\

实验结果：

N=4时，解的情况为：

N=5时，解的情况为：

N=6时，解的情况为：

心得体会：

通过本次实验，我加深了对回溯法的了解，掌握了利用回溯法解决N-皇后问题的算法。N-皇后问题中，只要抓住了求解问题的本质所在，其中遇到的困惑就会迎刃而解的，编程过程也会轻松一些。对算法的深入分析是很有用的。

百度搜索“77cn”或“免费范文网”即可找到本站免费阅读全部范文。收藏本站方便下次阅读，免费范文网，提供经典小说综合文库算法分析与设计实验报告 CQUPT(4)在线全文阅读。