保健品有没有副作用:一步一步写算法（之八皇后）

来源：百度文库 编辑：偶看新闻 时间：2024/04/30 00:04:20

【 声明：版权所有，欢迎转载，请勿用于商业用途。 联系信箱：feixiaoxing @163.com】


八皇后是一道很具典型性的题目。它的基本要求是这样的：在一个8*8的矩阵上面放置8个物体，一个矩阵点只允许放置一个物体，任意两个点不能在一行上，也不能在一列上，不能在一条左斜线上，当然也不能在一条右斜线上。

初看到这道题目，大家的第一印象是遍历，但是经过实践之后发现遍历其实不好写，而且复杂度很低。不仅需要遍历8*8*8*8*8*8*8*8*8 = 2^24次数据，还要判断各种条件，实际的计算复杂度还要比较这个高。其实我们仔细看一看，这中间很多的计算其实很多是不需要的，因为如果我们在某一行没有可以插入的数据的话，那么这后面的行其实就不用考虑了。也就是说，我们只有在保证前面 插入的物体都合法有效的情况下，才能进行下一次的物体插入。无谓的遍历只会是无用功。

那么，我们应该怎么做呢？其实步骤不太难：

（1）在第n行寻找可以插入的位置，中间涉及到位置合法性的判断

（2）如果没有可以插入的位置，返回

（3）如果有可以插入的位置， 插入数据。此时再判断是否已经是最后一行，如果是，打印输出返回；反之继续对下一行数据进行试探处理。

有了上面的步骤，我们就可以书写代码了。老规矩，朋友们可以自己先尝试一下。

a）定义全局堆栈和打印函数

view plaincopy to clipboardprint?

  1. static int gEightQueen[8] = {0};
  2. static int gCount = 0;
  4. void print()
  5. {
  6. int outer;
  7. int inner;
  9. for(outer = 0; outer <8; outer ++){
  10. for(inner = 0; inner < gEightQueen[outer]; inner ++)
  11. printf("* ");
  13. printf("# ");
  15. for(inner = gEightQueen[outer] + 1; inner < 8; inner ++)
  16. printf("* ");
  18. printf("\n");
  19. }
  21. printf("=====================================\n");
  22. }
b）添加位置合法性的函数判断

view plaincopy to clipboardprint?

  1. int check_pos_valid(int loop, int value)
  2. {
  3. int index;
  4. int data;
  6. for(index = 0; index < loop; index ++){
  7. data = gEightQueen[index];
  9. if(value == data)
  10. return 0;
  12. if((index + data) == (loop + value))
  13. return 0;
  15. if((index - data) == (loop - value))
  16. return 0;
  17. }
  19. return 1;
  20. }
c） 八皇后遍历

view plaincopy to clipboardprint?

  1. void eight_queen(int index)
  2. {
  3. int loop;
  5. for(loop = 0; loop < 8; loop++){
  6. if(check_pos_valid(index, loop)){
  7. gEightQueen[index] = loop;
  9. if(7 == index){
  10. gCount ++, print();
  11. gEightQueen[index] = 0;
  12. return;
  13. }
  15. eight_queen(index + 1);
  16. gEightQueen[index] = 0;
  17. }
  18. }
  19. }

总结：

（1）迭代递归是编程的难点，需要自己好好实践，看别人写一百遍，不如自己写一遍

（2）递归的时候务必注意函数return的出口

（3）递归函数中语句的顺序不要随意更换

（4）递归函数中注意数据的保存和恢复

（5）递归函数也要验证，可以用程序验证法，也可以用其他函数的结果来验证

八皇后问题的算法是什么? 八皇后问题的遗传算法解法，c语言编写 求~~~pascal八皇后 非递归详细算法和程序 怎样利用翻转和旋转简化八皇后问题的算法？ 八皇后怎么编程 八皇后问题 八皇后问题 求解八皇后问题 八皇后问题流程图 谁有八皇后非递归算法? 高斯的八皇后数学题用qbasic能解决么？该怎么写程序？ 高斯的八皇后数学题用qbasic能解决么？该怎么写程序？ 八皇后问题的解决方法 关于八皇后的思考 救助八皇后JAVA程序代码 八皇后的C++代码 改一个八皇后程序 请问高手怎么用PROLOG解决八皇后问题（回溯法） 求八皇后问题C++程序设计 八皇后的C++程序解法 八皇后的问题怎么解啊？ 八皇后问题 c程序原代码 有谁知道八皇后问题的源代码吗？ 使用pascal编写解决八皇后问题的程序