N王后问题,是一个科学谜题,指的是在把N个王后放到N*N的棋盘上,结果是任何王后之间都不会彼此威胁。换句话说,每个后继的王后既不能与前面的王后在同一行、同一列,也不能位于同一对角线上。N王后问题给出了Python代码。下面是JavaScript代码,但结果有些误差,不知何故。
- function conflict(state,posX) {
- var posY = state.length;
- for (var i=0;i<posY ;i++ )
- {
- var differ = Math.abs(state[i]-posX);
- if (differ == 0 || differ == (posY - i))
- {
- return true;
- }
- }
- return false;
- }
- function queens(num,state,solutions){
- for (var x=0;x<num ;x++ )
- {
- if (!conflict(state,x))
- {
- if (state.length == (num-1))
- {
- solutions.unshift(x);
- return true;
- }
- var result = queens(num,state.concat(x),solutions);
- if (result)
- {
- if (state.length==0)
- {
- solutions.unshift(x);
- continue;
- }
- solutions.unshift(x);
- return true;
- }
- }
- }
- }
用法如下:
- var result = [];
- queens(4,[],result);
- console.log(result);// [3, 1, 0, 2, 2, 0, 3, 1, 1, 3, 0, 2, 0, 3, 1, 2]
短路逻辑与条件运算符
2008年12月30日 编程技术
逻辑运算符包括逻辑与、逻辑或、逻辑非,英文分别对应:(logical)and、or、not。由于逻辑运算返回的是布尔值true(真)或false(假),因此逻辑运算符也叫布尔运算符。(英文operator在程序设计的语境下有两种译为:运算符、操作符。)
Python中的逻辑运算符有一个非常有意思的特性——“短路”,即不做无用功、选择最短路线。具体来说,逻辑运算中的短路表现在逻辑运算符只对有必要求值的表达式求值。例如,表达式x and y(x和y都有可能是表达式),只在x和y同时为真的情况下才会返回True。显然,如果x为假,那么就没有再对y求值的必要了——即使y为真,整个表达式仍然会返回False。因此,and运算符的行为就是:如果x为假,返回x;否则,返回y。
and运算符的这种行为就叫“短路逻辑”(或者懒惰求值)。可见,逻辑运算符的右运算数(如这里的y)有可能不会被求值——原因就是“短路”。
同样,or运算符也有短路行为。例如,对于表达式x or y,如果x是真,则返回x;否则,返回y。
设计短路逻辑有目的何在呢?主要是为了减少不必要的计算。但是,在短路逻辑的基础上,还可以实现一些巧妙的结构。例如:
name = raw_input(‘Enter name:’) or ‘<unknow>’
这个赋值语句就利用逻辑运算符or实现了在用户输入为空的情况下为name设置默认值的操作。另外,利用短路逻辑还可以实现另一种运算符,即条件运算符,或者叫三元运算符:
b if a else c # 如果a为真,则返回b;否则,返回c
短路逻辑与条件运算符同样也存在于JavaScript中。即,x && y的行为是:如果x可以转换false,则返回x;否则,计算并返回y的值。x || y的行为是:如果x可以转换为true,则返回x;否则,计算并返回y的值。显示,如果&&、||运算符分别在x可转换为false、true的情况下,会执行短路操作——忽略右运算数y。
而利用or运算符的短路行为,JavaScript也实现了为变量赋默认值:
//如果name可以转换为false,则不能短路,必须对右运算符求值,从而实现赋默认值
var name = name || ‘unprovided’;
以及另一种表现形式的条件表达式——?::
x > 0 ? x * y : -x * y
JavaScript中的Function(函数)对象
2008年12月26日 编程技术
JavaScript中的Function对象是函数,函数的用途分为3类:
- 作为普通逻辑代码容器;
- 作为对象方法;
- 作为构造函数。
1.作为普通逻辑代码容器
function multiply(x, y){
return x*y;
}
函数multiply封装了两位数的乘法运算公式:
var product = multiply(128,128); // product = 16384
创建函数实例的方式有3种。第一种是声明式,即像声明变量一样,将通过function(){}标识符创建的匿名函数直接赋值给变量,以该变量作为调用时的函数名称:
var multiply = function(x, y){
return x*y;
}
第二种是定义式,即以function关键字后跟函数名称及(){}来直接定义命名函数,前面第一个multiply函数就是通过定义式创建的。
第三种是构造函数式,即通过new运算符调用构造函数Function来创建函数。这种方式极不常用,因此就不作介绍了。 查看全文 »
浅复制与深复制中的传值与传址
2008年12月24日 编程技术
这个标题念起来有点拗口,但却是理解数据结构的关键。标题中的4个术语,对应的英文分别是:shallow copy(注意,不是shadow copy)、deep copy、pass by value、pass by reference(或pass by address)。传址和传引用是一回事。
一门编程语言的核心是数据结构,粗略来讲,可以把数据结构分成不可变类型(immutable)和可变类型(mutable)。为什么这么分呢?这涉及到内存分配问题。对于不可变类型,只要分配有限的内存空间即可,而对于可变类型,理论上则要分配没有大小限制的空间。因此,这么分是出于合理利用系统资源的考虑。实际上,栈内存和堆内存分别用于保存不可变类型值和可变类型值。
什么是不可变类型?就是该值一旦赋予某个变量,就只属于某个变量,不能同属于其他变量。如:
var stringValue = “I’m immutable data structure, mean you can’t modify me!”;
var anotherStringValue = stringValue;
stringValue = “I have changed”;
此时,anotherStringValue中保存的值会不会也变成“I have changed”?不会。因为
var anotherStringValue = stringValue;
照stringValue中保存的字符串的原样,复制一个字符串(相应地,在内存中分配一块新空间),并将该字符串赋给anotherStringValue。换句话说,这两个变量虽然保存的值相同,但它们的值并不在一块内存中。因此,修改任何一个变量,都不会影响另一个变量。即
stringValue = “I have changed”;
只会影响stringValue的值。但是,确切来讲,stringValue = “I have changed”;并不是修改stringValue,而是创建了一个新字符串(相应地,在内存中分配一块新空间),然后让stringValue引用该字符串——更像是替换变量的值;原来的字符串呢?因为没有变量引用它,也就成为垃圾了(当然,垃圾所占用的内存会被回收)。 查看全文 »
本博客专注于Web前后端技术和技术翻译。目前正在翻译《JavaScript高级程序设计(第2版)》。新浪微博(t.sina.com.cn/lisf),Twitter(@cncuckoo,仅仅用于跟踪国外牛人;我翻不了墙,无法接受各位朋友的follow,抱歉!)