鱼C论坛

 找回密码
 立即注册
查看: 5399|回复: 11

[争议讨论] 算法每日一题(五)

[复制链接]
发表于 2011-7-8 12:24:44 | 显示全部楼层 |阅读模式

马上注册,结交更多好友,享用更多功能^_^

您需要 登录 才可以下载或查看,没有账号?立即注册

x
a.jpg
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
发表于 2011-7-8 13:14:35 | 显示全部楼层
光光  为什吗你出题总这么不靠谱
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
 楼主| 发表于 2011-7-8 14:24:00 | 显示全部楼层
为什么不靠谱?
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
发表于 2011-7-8 15:26:21 | 显示全部楼层

这问题明显高不成低不就啊  论坛里的新人压根看不懂, 百度上又能直接搜到
这都属于现成的已经被前人开发好的东西, 若是让我们自己想一套新的,你觉得可能嘛?
就算你出这回溯法的问题,也要把初始的问题改了呀,或者再改简单一点, 直接照搬, 不是我吐槽,真的不太靠谱
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
发表于 2011-7-8 16:51:23 | 显示全部楼层
这个还真是看不懂
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
 楼主| 发表于 2011-7-8 17:01:02 | 显示全部楼层
asd82937121 发表于 2011-7-8 15:26
这问题明显高不成低不就啊  论坛里的新人压根看不懂, 百度上又能直接搜到
这都属于现成的已经被前人开 ...

其实...在这里出现的编程题,哪个是在baidu上搜不到的?
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
 楼主| 发表于 2011-7-8 17:04:13 | 显示全部楼层
  1. #include<stdio.h>
  2. #include<math.h>
  3. #define N 8
  4. /*
  5. 因为每行只能放1个皇后,用数组board表示每行的皇后放在哪列
  6. 示例:如borad[]={0,1,2,3,4,5,6,7};则说明皇后放在
  7. 0行0列,1行1列,2行2列,3行3列,4行4列,5行5列,6行6列,7行7列
  8. */
  9. int board[N];

  10. //第m行的皇后是否与前面的皇后冲突
  11. int conflicts( int m ){
  12.         int i=0;
  13.         for(;i<m;++i){
  14.                 if(board[i]==board[m]||abs(m-i)==abs(board[m]-board[i]))
  15.                         return 1;
  16.         }
  17.         return 0;
  18. }


  19. void print(){
  20.         static int num;
  21.         int i,j;
  22.         printf("solution#%d:\n",++num);
  23.         for(i=0;i<N;++i){
  24.                 for(j=0;j<N;++j){
  25.                         putchar((board[i]==j)?' Q':' X');
  26.                 }
  27.         putchar('\n');
  28.         }
  29. }

  30. //从第m行开始放置皇后
  31. void place( int m ){
  32.         int n;
  33.         //测试m行的每一列
  34.         for(n=0;n<N;++n){
  35.                 board[m]=n;
  36.                 //若m行n列放皇后和前面行的皇后不冲突
  37.                 if(!conflicts( m )){
  38.                         //若没放完8行继续放下一行
  39.                         if(m<N-1)
  40.                                 place(m+1);
  41.                         else
  42.                         //打印结果
  43.                                 print();
  44.                 }
  45.         }
  46. }

  47. int main(){
  48.         place(0);
  49. }
复制代码
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
发表于 2011-7-8 18:33:33 | 显示全部楼层
这道题就是基本算法思想中的回溯法,用到了树,通常是按照深度优先搜索的方法,从根结点出发深度探索解空间树。当探索到某一结点时,要先判断该结点是否包含问题的解,如果包含,就从该节点出发继续探索下去;如果该节点不包含问题的解,那就说明以该结点为根节点的子树一定不包含问题的最终解,因此要跳过对以该结点为根的子树的系统搜索,逐层的向其祖先结点回溯。
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
发表于 2011-7-8 18:40:12 | 显示全部楼层
仰望天上的光 发表于 2011-7-8 14:24
为什么不靠谱?

不得不承认,对于没有数据结构基础的人来说,此题是不可解的。所以,我认为,最理想的是,由浅入深的让大家每天做一道,同时给出问题的解题思路和方法。
而对于算法方面的问题通常可以分为:编程基本功(特殊字符个数、图案、位运算、基本语法规则等)
                                                            数学问题(完全数、阶乘、排列等)
                                                            数据结构问题(链表、栈、队列、树、图)
以及相应的基本算法思想:如 回溯法、
                                               穷举、
                                               递归与分治、
                                               贪心法
等等,而诸如ACM\ICPC,蓝点杯,百度之星等以算法为主的比赛来说,实际问题,往往需要问题的抽象,选择相应的数据结构与相应算法进行求解。

所以我认为,讲解+练习+实例分析  这种模式才能有所提高。

与君共勉,共同将数据结构版块,办好。
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
发表于 2011-7-8 19:40:15 | 显示全部楼层
  1. /*
  2. **        Solve the Eight Queens Problem.
  3. */


  4. #include <stdio.h>
  5. #include <stdlib.h>

  6. #define TRUE   1
  7. #define FALSE      0

  8. int      board[8][8];

  9. void
  10. print_board()
  11. {
  12.         int       row;
  13.         int       column;
  14.         static  int         n_solutions;
  15.        
  16.         n_solutions += 1;
  17.         printf( "Solution #%d:\n", n_solutions );
  18.        
  19.         for( row = 0; row < 8; row += 1 ){
  20.                 for( column = 0; column < 8; column += 1 ){
  21.                         if( board[ row ][ column ] )
  22.                                 printf( " Q" );
  23.                         else
  24.                                 printf( " +" );
  25.                 }
  26.                 putchar( '\n' );;
  27.         }
  28.         putchar( '\n' );
  29. }

  30. int
  31. conflicts( int row, int column )
  32. {
  33.         int       i;
  34.        
  35.         for( i = 1; i < 8; i += 1 ){

  36.                 if( row - i >= 0 && board[ row - i ][ column ] )
  37.                         return TRUE;
  38.                 if( column - i >= 0 && board[ row ][ column - i ] )
  39.                         return TRUE;
  40.                 if( column + i < 8 && board[ row ][ column + i ] )
  41.                         return TRUE;
  42.                
  43.                 if( row - i >= 0 && column - i >= 0
  44.                         && board[ row - i ][ column - i ] )
  45.                         return TRUE;
  46.                 if( row - i >= 0 && column + i < 8
  47.                         && board[row - i ][column + i] )
  48.                         return TRUE;
  49.         }
  50.        
  51.         return FALSE;
  52. }

  53. void
  54. place_queen( int row )
  55. {
  56.         int       column;
  57.        
  58.         for( column = 0; column < 8; column += 1 ){
  59.                 board[ row ][ column ] = TRUE;
  60.                
  61.                 if( row == 0 || !conflicts( row, column ) )
  62.                  
  63.                 if( row < 7 )
  64.                         place_queen( row + 1 );
  65.                 else
  66.                         print_board();
  67.                
  68.                 board[ row ][ column ] = FALSE;
  69.         }
  70.        
  71. }

  72. int
  73. main()
  74. {
  75.         place_queen( 0 );
  76.         return EXIT_SUCCESS;
  77. }
复制代码
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
头像被屏蔽
发表于 2011-7-8 20:33:35 | 显示全部楼层
提示: 作者被禁止或删除 内容自动屏蔽
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
发表于 2011-7-8 22:01:27 | 显示全部楼层
x8888k 发表于 2011-7-8 20:33
皇后问题书上就有

记住 书上的永远是书上的,不是你自己的。每个问题,只有自己思考了,独立做出来,才是自己掌握了。
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
您需要登录后才可以回帖 登录 | 立即注册

本版积分规则

小黑屋|手机版|Archiver|鱼C工作室 ( 粤ICP备18085999号-1 | 粤公网安备 44051102000585号)

GMT+8, 2024-3-29 18:49

Powered by Discuz! X3.4

© 2001-2023 Discuz! Team.

快速回复 返回顶部 返回列表