算法每日一题(五）

仰望天上的光

asd82937121

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

仰望天上的光

为什么不靠谱？

asd82937121

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

                               
登录/注册后可看大图

为什么不靠谱？

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

《永不言败》

这个还真是看不懂

仰望天上的光

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

                               
登录/注册后可看大图

这问题明显高不成低不就啊  论坛里的新人压根看不懂， 百度上又能直接搜到
这都属于现成的已经被前人开 ...

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

仰望天上的光

#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[N];

//第m行的皇后是否与前面的皇后冲突
int conflicts( int m ){
        int i=0;
        for(;i<m;++i){
                if(board[i]==board[m]||abs(m-i)==abs(board[m]-board[i]))
                        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[i]==j)?' Q':' X');
                }
        putchar('\n');
        }
}

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

int main(){
        place(0);
}

LNH_Sniper

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

LNH_Sniper

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

                               
登录/注册后可看大图

为什么不靠谱？

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

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

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

chao_prince

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


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

#define TRUE   1
#define FALSE      0 

int      board[8][8]; 

void 
print_board() 
{ 
        int       row; 
        int       column; 
        static  int         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[row - i ][column + i] ) 
                        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; 
}

LNH_Sniper

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

                               
登录/注册后可看大图

皇后问题书上就有

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