论坛 › 数据结构与算法 › 算法每日一题(五）

仰望天上的光 发表于 2011-7-8 12:24:44

算法每日一题(五）

asd82937121 发表于 2011-7-8 13:14:35

光光为什吗你出题总这么不靠谱

仰望天上的光 发表于 2011-7-8 14:24:00

为什么不靠谱？

asd82937121 发表于 2011-7-8 15:26:21

仰望天上的光 发表于 2011-7-8 14:24 static/image/common/back.gif
为什么不靠谱？

这问题明显高不成低不就啊论坛里的新人压根看不懂， 百度上又能直接搜到
这都属于现成的已经被前人开发好的东西， 若是让我们自己想一套新的，你觉得可能嘛？
就算你出这回溯法的问题，也要把初始的问题改了呀，或者再改简单一点， 直接照搬， 不是我吐槽，真的不太靠谱

《永不言败》 发表于 2011-7-8 16:51:23

这个还真是看不懂

仰望天上的光 发表于 2011-7-8 17:01:02

asd82937121 发表于 2011-7-8 15:26 static/image/common/back.gif
这问题明显高不成低不就啊论坛里的新人压根看不懂， 百度上又能直接搜到
这都属于现成的已经被前人开 ...

其实...在这里出现的编程题，哪个是在baidu上搜不到的？

仰望天上的光 发表于 2011-7-8 17:04:13

#include<stdio.h>
#include<math.h>
#define N 8
/*
因为每行只能放1个皇后，用数组board表示每行的皇后放在哪列
示例：如borad[]={0,1,2,3,4,5,6,7};则说明皇后放在
0行0列，1行1列，2行2列，3行3列，4行4列，5行5列，6行6列，7行7列
*/
int board;

//第m行的皇后是否与前面的皇后冲突
int conflicts( int m ){
        int i=0;
        for(;i<m;++i){
                if(board==board||abs(m-i)==abs(board-board))
                        return 1;
        }
        return 0;
}


void print(){
        static int num;
        int i,j;
        printf("solution#%d:\n",++num);
        for(i=0;i<N;++i){
                for(j=0;j<N;++j){
                        putchar((board==j)?' Q':' X');
                }
        putchar('\n');
        }
}

//从第m行开始放置皇后
void place( int m ){
        int n;
        //测试m行的每一列
        for(n=0;n<N;++n){
                board=n;
                //若m行n列放皇后和前面行的皇后不冲突
                if(!conflicts( m )){
                        //若没放完8行继续放下一行
                        if(m<N-1)
                                place(m+1);
                        else
                        //打印结果
                                print();
                }
        }
}

int main(){
        place(0);
}

LNH_Sniper 发表于 2011-7-8 18:33:33

这道题就是基本算法思想中的回溯法，用到了树，通常是按照深度优先搜索的方法，从根结点出发深度探索解空间树。当探索到某一结点时，要先判断该结点是否包含问题的解，如果包含，就从该节点出发继续探索下去；如果该节点不包含问题的解，那就说明以该结点为根节点的子树一定不包含问题的最终解，因此要跳过对以该结点为根的子树的系统搜索，逐层的向其祖先结点回溯。

LNH_Sniper 发表于 2011-7-8 18:40:12

仰望天上的光 发表于 2011-7-8 14:24 static/image/common/back.gif
为什么不靠谱？

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

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

与君共勉，共同将数据结构版块，办好。

chao_prince 发表于 2011-7-8 19:40:15

/*
**        Solve the Eight Queens Problem.
*/


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

#define TRUE   1
#define FALSE      0

int      board;

void
print_board()
{
        int       row;
        int       column;
        staticint         n_solutions;
       
        n_solutions += 1;
        printf( "Solution #%d:\n", n_solutions );
       
        for( row = 0; row < 8; row += 1 ){
                for( column = 0; column < 8; column += 1 ){
                        if( board[ row ][ column ] )
                                printf( " Q" );
                        else
                                printf( " +" );
                }
                putchar( '\n' );;
        }
        putchar( '\n' );
}

int
conflicts( int row, int column )
{
        int       i;
       
        for( i = 1; i < 8; i += 1 ){

                if( row - i >= 0 && board[ row - i ][ column ] )
                        return TRUE;
                if( column - i >= 0 && board[ row ][ column - i ] )
                        return TRUE;
                if( column + i < 8 && board[ row ][ column + i ] )
                        return TRUE;
               
                if( row - i >= 0 && column - i >= 0
                        && board[ row - i ][ column - i ] )
                        return TRUE;
                if( row - i >= 0 && column + i < 8
                        && board )
                        return TRUE;
        }
       
        return FALSE;
}

void
place_queen( int row )
{
        int       column;
       
        for( column = 0; column < 8; column += 1 ){
                board[ row ][ column ] = TRUE;
               
                if( row == 0 || !conflicts( row, column ) )
               
                if( row < 7 )
                        place_queen( row + 1 );
                else
                        print_board();
               
                board[ row ][ column ] = FALSE;
        }
       
}

int
main()
{
        place_queen( 0 );
        return EXIT_SUCCESS;
}

x8888k 发表于 2011-7-8 20:33:35

LNH_Sniper 发表于 2011-7-8 22:01:27

x8888k 发表于 2011-7-8 20:33 static/image/common/back.gif
皇后问题书上就有

记住 书上的永远是书上的，不是你自己的。每个问题，只有自己思考了，独立做出来，才是自己掌握了。

查看完整版本: 算法每日一题(五）