2 个回答
-
| 2017-10-19 06:23:56 广告
哪里有那么麻烦呀?八皇后明明只需要 5行代码就搞定了,递归版,统计所有解的数量:f = lambda A, x, y: y < 0 or (not (A[y] in (A[x], A[x] + (x - y), A[x] - (x - y)))) g = lambda A, x, y: (not x) or (f(A, x, y) and ((y < 0) or g(A, x, y - 1))) h = lambda A, x: sum([ g(A, x, x - 1) and 1 or 0 for A[x] in range(len(A)) ]) q = lambda A, x: h(A, x) if (x is 7) else sum([ q(A, x + 1) for A[x] in range(8) if g(A, x, x - 1) ]) print q([ 0 for i in xrange(8) ], 0)
本问答由匿名用户提供
-
| 2017-10-19 05:52:19 广告
谢邀。
前面所有回答都跑题了,我来终结此问题。
先说结论:
1. 能动态地生成for
2. 不能改成等价的递归 (我理解的等价是"速度严格变快或持平")
下面展开说:
1. 能动态地生成for
题主所贴代码可称为“枚举剪枝算法”(后面会再提到),思路是:按行号顺序摆放皇后(Queen,下简称Q),为第j行的Q选择列数时,根据前j-1行中摆放Q的位置进行筛选,筛选原则是:第x行(前j-1行中的某一行)已放列不选,第x行已放列向前数第j-x列不选,第x行已放列向后数第j-x列不选(之所以这个原则有效,是因为这些列是前j-1行的Q在第j行的可攻击位置,画一下图就明白了)
思路理解之后,求Q代码和打印求Q代码的代码都可以写出来了。
打印求Q代码的代码(代码A):代码A会打印出代码B (即求Q代码,即题主所贴queen11的等效代码):n=11print'def queen%d():'%nprint' s=set(xrange(1,%d))'%(n+1)print' for x1 in s:'foriinxrange(2,n+1):buf=' '*(i)buf+='for x%din s - {'%ilist=[]forjinxrange(1,i):list.append(j)forjinlist:buf+='x%d+%d,'%(i-abs(j),0)forjinxrange(1,i):list.append(-j)forjinlist:buf+='x%d+%d,'%(i-abs(j),j)buf=buf[:-1]buf+='}:'printbufbuf=' '*(n+1)+'yield 'forjinxrange(1,n+1):buf+='x%d,'%jbuf=buf[:-1]printbufprint'for i in queen%d():'%nprint' print i'
2. 不能改成等价的递归defqueen11():s=set(xrange(1,12))forx1ins:forx2ins-{x1+0,x1+1,x1+-1}:forx3ins-{x2+0,x1+0,x2+1,x1+2,x2+-1,x1+-2}:forx4ins-{x3+0,x2+0,x1+0,x3+1,x2+2,x1+3,x3+-1,x2+-2,x1+-3}:forx5ins-{x4+0,x3+0,x2+0,x1+0,x4+1,x3+2,x2+3,x1+4,x4+-1,x3+-2,x2+-3,x1+-4}:forx6ins-{x5+0,x4+0,x3+0,x2+0,x1+0,x5+1,x4+2,x3+3,x2+4,x1+5,x5+-1,x4+-2,x3+-3,x2+-4,x1+-5}:forx7ins-{x6+0,x5+0,x4+0,x3+0,x2+0,x1+0,x6+1,x5+2,x4+3,x3+4,x2+5,x1+6,x6+-1,x5+-2,x4+-3,x3+-4,x2+-5,x1+-6}:forx8ins-{x7+0,x6+0,x5+0,x4+0,x3+0,x2+0,x1+0,x7+1,x6+2,x5+3,x4+4,x3+5,x2+6,x1+7,x7+-1,x6+-2,x5+-3,x4+-4,x3+-5,x2+-6,x1+-7}:forx9ins-{x8+0,x7+0,x6+0,x5+0,x4+0,x3+0,x2+0,x1+0,x8+1,x7+2,x6+3,x5+4,x4+5,x3+6,x2+7,x1+8,x8+-1,x7+-2,x6+-3,x5+-4,x4+-5,x3+-6,x2+-7,x1+-8}:forx10ins-{x9+0,x8+0,x7+0,x6+0,x5+0,x4+0,x3+0,x2+0,x1+0,x9+1,x8+2,x7+3,x6+4,x5+5,x4+6,x3+7,x2+8,x1+9,x9+-1,x8+-2,x7+-3,x6+-4,x5+-5,x4+-6,x3+-7,x2+-8,x1+-9}:forx11ins-{x10+0,x9+0,x8+0,x7+0,x6+0,x5+0,x4+0,x3+0,x2+0,x1+0,x10+1,x9+2,x8+3,x7+4,x6+5,x5+6,x4+7,x3+8,x2+9,x1+10,x10+-1,x9+-2,x8+-3,x7+-4,x6+-5,x5+-6,x4+-7,x3+-8,x2+-9,x1+-10}:yieldx1,x2,x3,x4,x5,x6,x7,x8,x9,x10,x11foriinqueen11():printi
考虑到问题中的代码功能是输出N皇后的所有的解
此问题的递归解法,再牛也绕不过剪枝
而剪枝,再牛也比不过“枚举剪枝算法”中的剪枝(只需调用系统的集合减操作)
用“枚举剪枝算法”中的剪枝的话,可以写成如下样子(以4皇后的递归写法为例,感兴趣的同学可尝试把打印该代码的代码写出来),
但需要 额外递归开销+数组变量访问,远不如原算法中的 无额外开销+整型变量访问 高效。-n=0defqueen4(x,r):globalns=set(xrange(1,n+1))ifx==1:forx1ins:r[1]=x1queen4(x+1,r)elifx==2:forx2ins-{r[1]+0,r[1]+1,r[1]-1}:r[2]=x2queen4(x+1,r)elifx==3:forx3ins-{r[2]+0,r[1]+0,r[2]+1,r[1]+2,r[2]-1,r[1]-2}:r[3]=x3queen4(x+1,r)elifx==4:forx4ins-{r[3]+0,r[2]+0,r[1]+0,r[3]+1,r[2]+2,r[1]+3,r[3]-1,r[2]-2,r[1]-3}:r[4]=x4printrn=4r=[0foriinxrange(0,n+1)]queen4(1,r)
不信结论2的同学可以看下能否跑过我写的版代码:
版本1 (2.842秒):版本2 (3.075秒):defcheck(x,y,n,a):foriinxrange(x):ifa[i][y]:returnFalsei=x-1j=y-1whilei>=0andj>=0:ifa[i][j]:returnFalsei-=1j-=1i=x-1j=y+1whilei>=0andj<n:ifa[i][j]:returnFalsei-=1j+=1returnTruedefput(x,n,a,r,c):ifx==n:c[0]+=1# print rreturnforiinxrange(n):ifcheck(x,i,n,a):a[x][i]=Truer[x]=iput(x+1,n,a,r,c)a[x][i]=Falsedefqueen(n):a=[[Falseforjinxrange(n)]foriinxrange(n)]r=[0foriinxrange(n)]c=[0]put(0,n,a,r,c)printc[0]queen(11)
这两版的代码都验证过无法超过“枚举剪枝算法”了:cnt=0defcheck(x,r,rx):foriinxrange(x):ifrx==r[i]orabs(rx-r[i])==x-i:returnFalsereturnTruedefput(x,n,r,c):ifx==n:# print rc[0]+=1returnforiinxrange(n):r[x]=iifcheck(x,r,i):put(x+1,n,r,c)defqueen(n):r=[0foriinxrange(n)]c=[0]put(0,n,r,c)printc[0]queen(11)
枚举剪枝算法 (0.394秒):defqueen11(c):s=set(xrange(1,12))forx1ins:forx2ins-{x1+0,x1+1,x1+-1}:forx3ins-{x2+0,x1+0,x2+1,x1+2,x2+-1,x1+-2}:forx4ins-{x3+0,x2+0,x1+0,x3+1,x2+2,x1+3,x3+-1,x2+-2,x1+-3}:forx5ins-{x4+0,x3+0,x2+0,x1+0,x4+1,x3+2,x2+3,x1+4,x4+-1,x3+-2,x2+-3,x1+-4}:forx6ins-{x5+0,x4+0,x3+0,x2+0,x1+0,x5+1,x4+2,x3+3,x2+4,x1+5,x5+-1,x4+-2,x3+-3,x2+-4,x1+-5}:forx7ins-{x6+0,x5+0,x4+0,x3+0,x2+0,x1+0,x6+1,x5+2,x4+3,x3+4,x2+5,x1+6,x6+-1,x5+-2,x4+-3,x3+-4,x2+-5,x1+-6}:forx8ins-{x7+0,x6+0,x5+0,x4+0,x3+0,x2+0,x1+0,x7+1,x6+2,x5+3,x4+4,x3+5,x2+6,x1+7,x7+-1,x6+-2,x5+-3,x4+-4,x3+-5,x2+-6,x1+-7}:forx9ins-{x8+0,x7+0,x6+0,x5+0,x4+0,x3+0,x2+0,x1+0,x8+1,x7+2,x6+3,x5+4,x4+5,x3+6,x2+7,x1+8,x8+-1,x7+-2,x6+-3,x5+-4,x4+-5,x3+-6,x2+-7,x1+-8}:forx10ins-{x9+0,x8+0,x7+0,x6+0,x5+0,x4+0,x3+0,x2+0,x1+0,x9+1,x8+2,x7+3,x6+4,x5+5,x4+6,x3+7,x2+8,x1+9,x9+-1,x8+-2,x7+-3,x6+-4,x5+-5,x4+-6,x3+-7,x2+-8,x1+-9}:forx11ins-{x10+0,x9+0,x8+0,x7+0,x6+0,x5+0,x4+0,x3+0,x2+0,x1+0,x10+1,x9+2,x8+3,x7+4,x6+5,x5+6,x4+7,x3+8,x2+9,x1+10,x10+-1,x9+-2,x8+-3,x7+-4,x6+-5,x5+-6,x4+-7,x3+-8,x2+-9,x1+-10}:# yield x1,x2,x3,x4,x5,x6,x7,x8,x9,x10,x11c[0]+=1c=[0]queen11(c)printc[0]
本问答由匿名用户提供
更多
- 通付POS客服服务电话是多少?
- 1
- 3
- 通联收银宝pos机网络连接失败怎么办?
- 32
- 3
- 星驿付pos机400客户服务电话是什么?
- 56
- 3
- 通联收银宝pos机400客服热线是多少?
- 9
- 3
- 光速宝POS客服服务电话是多少
- 18
- 3
- 星支付POS客服服务电话是多少
- 95
- 3
- 1分钟怎么游戏数值jj租号新玩法:捕鱼绝妙策略
- 90
- 3
- 通联收银宝pos机400客服热线是多少?
- 35
- 3
- 保亭本地宠物托运猫狗托运流程查询
- 16
- 3
- 立刷POS客服服务电话是多少?
- 29
- 3