8皇后问题的c＋＋与python实现对比
c＋＋经典书多，但貌似不太新，而python则新书很多，能体现一些新思路新概念。看python的书，写python代码，再用c＋＋实现一遍，这样互补的学习方式貌似也蛮适合自己的。在《Beginning Python From Novice to Professional》一书的八皇后问题上，python果然精妙而优雅。
在对待
[*]foreachpossibilityatlevel1:
[*]foreachpossibilityatlevel2:
[*]foreachpossibilityatleveln:
[*]...
[*]isitviable
形式的循环下，它有yield， generator递归。短短20来行代码就搞定了八皇后，如下：
[*]defconflict(state,nextX):
[*]nextY=len(state)
[*]ifnextY==0:print0
[*]foriinrange(nextY):
[*]ifabs(nextX-state)in(0,nextY-i):
[*]returnTrue
[*]returnFalse
[*]
[*]defqueen(num,state=()):
[*]printstate
[*]forposinrange(num):
[*]ifnotconflict(state,pos):
[*]iflen(state)==num-1:
[*]yield(pos,)
[*]else:
[*]forresultinqueen(num,state+(pos,)):
[*]yield(pos,)+result
[*]
[*]defprettyprint(solution):
[*]defline(pos,length=len(solution)):
[*]return'.'*pos+'X'+'.'*(length-pos-1)
[*]forposinsolution:
[*]printline(pos)
[*]
[*]if__name__=='__main__':
[*]importrandom
[*]prettyprint(random.choice(list(queen(4))))
其中
[*]forresultinqueen(num,state+(pos,)):
[*]yield(pos,)+result
2句由为精妙，自己苦思很久，没有能完全理解yield的精髓。。。。。
在用c＋＋实现的时候，一直想模仿实现这句话的功能，却被这句话困扰了2个多小时，看书看久了不休息果然效率奇差。
今天早上醒来，才恍然大悟，其实不就是个栈么。
[*]/*
[*]*=====================================================================================
[*]*
[*]*Filename:eightqueen.cpp
[*]*
[*]*Description:8皇后问题，c＋＋实现
[*]*
[*]*Version:1.0
[*]*Created:2008年12月30日19时46分52秒
[*]*Revision:none
[*]*Compiler:gcc
[*]*
[*]*Author:LiWeiJian(mn),lwj1396@163.com
[*]*Company:hunanuniversity
[*]*
[*]*=====================================================================================
[*]*/
[*]
[*]#include<vector>
[*]#include<iostream>
[*]#include<cmath>
[*]usingnamespacestd;
[*]
[*]boolconflict(constvector<int>&state,intnextX)
[*]{
[*]intnextY=state.size();
[*]for(inti=0;i<nextY;i++)
[*]{
[*]if(abs(nextX-state)==0||abs(nextX-state)==(nextY-i))
[*]returntrue;
[*]}
[*]returnfalse;
[*]}
[*]
[*]voidqueen(intnum,vector<int>&state)
[*]{
[*]for(inti=0;i<num;i++)
[*]{
[*]state.clear();
[*]state.push_back(i);
[*]intpos=0;
[*]while(state.size()!=num)
[*]{
[*]if(conflict(state,pos))//冲突了
[*]{
[*]if(pos==num-1)//已经是最后一个位置
[*]{
[*]state.pop_back();
[*]break;
[*]}
[*]pos++;//尝试下一个pos
[*]continue;
[*]}
[*]else//没有冲突
[*]{
[*]state.push_back(pos);
[*]pos=0;
[*]}
[*]}
[*]if(state.size()==num)
[*]return;
[*]}
[*]}
[*]
[*]voidprint(intnum,constvector<int>result)
[*]{
[*]for(inti=0;i<result.size();i++)
[*]{
[*]for(intj=0;j<result;j++)
[*]cout<<".";
[*]cout<<"X";
[*]for(intj=0;j<num-result-1;j++)
[*]cout<<".";
[*]cout<<endl;
[*]}
[*]}
[*]
[*]intmain()
[*]{
[*]vector<int>state;
[*]queen(16,state);
[*]print(16,state);
[*]}
[*]
在实现之后，对比了一下，效率的差距果然满大，python跑14皇后，等了几分钟没搞定，而c＋＋跑16皇后，都是刷的一下出来了，不过可能c＋＋没有用递归也是一个原因。
最后再总结2句：
1 一本书，无论薄厚，都不能欺负它，不要想1，2天就看完
2 c＋＋虽然经典，但书籍过老了，要拿一门有活力的语言为它开路，其实boost的c＋＋已经很python了。
页:
[1]