N王后问题（续）

2009年01月22日 编程技术

N王后问题，是一个科学谜题，指的是在把N个王后放到N*N的棋盘上，结果是任何王后之间都不会彼此威胁。换句话说，每个后继的王后既不能与前面的王后在同一行、同一列，也不能位于同一对角线上。N王后问题给出了Python代码。下面是JavaScript代码，但结果有些误差，不知何故。

  1. function conflict(state,posX)    {
  2.     var posY = state.length;
  3.     for (var i=0;i<posY ;i++ )
  4.     {
  5.         var differ = Math.abs(state[i]-posX);
  6.         if (differ == 0 || differ == (posY - i))
  7.         {
  8.             return true;
  9.         }
  10.     }
  11.     return false;
  12. }
  13.  
  14. function queens(num,state,solutions){
  15.     for (var x=0;x<num ;x++ )
  16.     {
  17.         if (!conflict(state,x))
  18.         {
  19.             if (state.length == (num-1))
  20.             {
  21.                 solutions.unshift(x);
  22.                 return true;
  23.             }
  24.             var result = queens(num,state.concat(x),solutions);
  25.             if (result)
  26.             {
  27.                 if (state.length==0)
  28.                 {
  29.                     solutions.unshift(x);
  30.                     continue;
  31.                 }
  32.                 solutions.unshift(x);
  33.                 return true;
  34.             }
  35.        
  36.         }
  37.  
  38.     }
  39. }

用法如下：

  1. var result = [];
  2. queens(4,[],result);
  3. console.log(result);// [3, 1, 0, 2, 2, 0, 3, 1, 1, 3, 0, 2, 0, 3, 1, 2]
有 1 条评论

短路逻辑与条件运算符

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. 作为普通逻辑代码容器；
  2. 作为对象方法；
  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来创建函数。这种方式极不常用，因此就不作介绍了。 查看全文 »

有 11 条评论

浅复制与深复制中的传值与传址

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引用该字符串——更像是替换变量的值；原来的字符串呢？因为没有变量引用它，也就成为垃圾了（当然，垃圾所占用的内存会被回收）。 查看全文 »

有 7 条评论