XmlHttpRequest学习笔记 (2) 基本操作

XmlHttpRequest里面常用的函数和属性无非就这几个:

其中method的值多数为Get或者Post(不区分大小写)用于从服务器获取数据和向服务器发送数据,还有Head, Put, Delete之类的,基本不会用到;url是实际要访问的url地址,比如http://leonax.net;async的值为true或者false,表示是否要以异步模式(即非阻塞模式)进行通信;user和password为访问url所需的用户名和密码,一般都是省略掉的。

open函数只是初始化一下Xmlhttp对象,它并不会向url所对应的服务器发送数据。比较奇怪的是,W3C的规范中async的缺省值为true,也就是说,以下代码会以异步模式运行:

Msxml3和IE的XmlHttpRequest遵循了这一规范,而Msxml6中的缺省值为false。既然缺省值都为true,为什么不把参数名改成sync呢?在Javascript(以及各种脚本语言)中,缺省参数一般为null,而null和false等价,所以把缺省值定为true实在是太令人费解了。

真正把数据发出去的是这个函数。text可以是任何值,它会被当作数据包的正文发给服务器。

在open之前调用send会报错。

以异步模式open之后,send函数会立刻返回;相反,在同步模式的时候,它会等到接收完服务器所有的回应才返回。

responseText

这是一个属性,在收到服务器的回复之后,可以通过它来查看回复的正文部分。如:

将显示出一个很简易的Html :P。在未完全收到回复之前,responseText返回一个空字符串。

XmlHttpRequest学习笔记 (1) 创建

XmlHttpRequest是一个用于在网页中读取服务器数据的组件。最初是由微软开发用来访问Outlook Web Access 2000的。在目前流行的IE版本中都支持(从IE5到IE9),只不过问题是这个东东目前还没有成为标准(W3C正在讨论,只有一个draft可作参考),于是就有了万恶的浏览器兼容性的问题。常见的生成XmlHttpRequest对象的Javascript是这么写的:

在IE7之前,IE中的XmlHttpRequest组件都是由Msxml提供的。尽管Msxml目前有很多版本(从3.0到6.0都是被支持的),但只有3.0是从Win2000到Vista都带的,6.0只在XP SP3和Vista以之后的操作系统中有,而且3.0有个好处是创建的时候只要写"Msxml.Xmlhttp"即可,不用像6.0一样加上后缀的版本号。当然6.0在安全和性能方面都要比3.0好,大有取而代之的趋势。

Joseph问题的数学解法……

好久没做题了……一下子想不起来,只好google了。留个备份,以免以后再忘记=.=

约瑟夫问题的数学方法
[ 2006-5-5 14:26:00 | By: lower ]

看到这个想起了去年的省赛上,我们就是被一个约瑟夫问题的变种搞的几乎发狂了,一直是WA,出了赛场才发现并不是真正的约瑟夫问题。

对于约瑟夫问题,今天看到了一篇好帖子,是用数学方法处理的,感觉还不错的

无论是用链表实现还是用数组实现都有一个共同点:要模拟整个游戏过程,不仅程序写起来比较烦,而且时间复杂度高达O(nm),当n,m非常大(例如上百万,上千万)的时候,几乎是没有办法在短时间内出结果的。

为了讨论方便,先把问题稍微改变一下,并不影响原意:

问题描述:n个人(编号0~(n-1)),从0开始报数,报到(m-1)的退出,剩下的人继续从0开始报数。求胜利者的编号。

我们知道第一个人(编号一定是m%n-1) 出列之后,剩下的n-1个人组成了一个新的约瑟夫环(以编号为k=m%n的人开始):
k  k+1  k+2  ... n-2, n-1, 0, 1, 2, ... k-2
并且从k开始报0。

现在我们把他们的编号做一下转换:
k     --> 0
k+1   --> 1
k+2   --> 2
...
...
k-2   --> n-2
k-1   --> n-1

变换后就完完全全成为了(n-1)个人报数的子问题,假如我们知道这个子问题的解:例如x是最终的胜利者,那么根据上面这个表把这个x变回去不刚好就是n个人情况的解吗?!!变回去的公式很简单,相信大家都可以推出来:x'=(x+k)%n

如何知道(n-1)个人报数的问题的解?对,只要知道(n-2)个人的解就行了。(n-2)个人的解呢?当然是先求(n-3)的情况 ---- 这显然就是一个倒推问题!好了,思路出来了,下面写递推公式:

令f[i]表示i个人玩游戏报m退出最后胜利者的编号,最后的结果自然是f[n]

递推公式
f[1]=0;
f[i]=(f[i-1]+m)%i;  (i>1)

有了这个公式,我们要做的就是从1-n顺序算出f[i]的数值,最后结果是f[n]。因为实际生活中编号总是从1开始,我们输出f[n]+1

由于是逐级递推,不需要保存每个f[i],程序也是异常简单:

这个算法的时间复杂度为O(n),相对于模拟算法已经有了很大的提高。算n,m等于一百万,一千万的情况不是问题了。
====================================================================
另外要说明的是,这个方法只能在o(n)的方法内求出第任意某个出去的人的位置。如果要求出整个出去序列,用这个方法还是o(n^2)的。。求所以出去序列,用线段数可以做到o(nlog(n))..ms没有比这个快的了。。

Javascript 学习心得

这几天做 Ajax,顺便研究了一下 Javascript,发现以前对 Javascript 是完全不了解=.=

总结如下(以下简称 Js):

1、Js 中没有 Class,只有 Function,一个 Function 可以看成一个类的构造函数,new Function 即 new Class。每个 Function 有一个对象prototype,new Function 的时候,自动把这个 Function 的 prototype 复制到新的对象中。

2、Function 中可以使用 this 关键字,指代的是包含这个 Function 的类,不过 this 是动态绑定的,比如

运行结果是 y。这种模式在 Lua 中见过,如果要让运行结果是 x,要对 x.a 做一个 Binder,显示指定 this 为 x,并调用 a.x.apply(obj, ...)。

3、Js 中没有继承,要实现继承的功能,有 N 种比较猥琐的方法。一种是在新的对象中放一个 base 指针,指向它的父类。还有一种是复制 prototype。不过看上去都很恶心。以前看过 Lua 中有一种继承的方法是做一个索引表,调用函数的时候查找它父类的函数,不过 Js 不支持运算符重载=.=

4、Js 中唯一的网络组件是 XMLHttpRequest,在 IE 7 和 Firefox 中可用,IE 6 要用 new ActiveXObject("Msxml2.XMLHTTP")。XMLHttpRequest 可以产生一个异步通讯的线程,是 Ajax 的主要工具之一。线程的管理依赖于浏览器,具体的说明可以看 Ray 的一篇文章

5、Js 中数值 0 等价于 false,也就是 if (0) {} 等价于 if (false) {},在写 Array.Contains 的时候总算明白了为什么 Lua 中 0 不等价于 false,因为 Array.Contains 可以返回 null 表示没有找到,而调用的时候可以写 If (obj.Contains(val)) {},而不用写 if (obj.Contains(val) != null){},但是 Js 中就只有写后一种了 =.=

6、Js 中有 delete 关键字,但不是用来进行垃圾回收的,只能用来在类中删除一个元素。垃圾回收是自动的。

7、Js 中有很多保留字(因为 ECMA 规范的缘故),比如 class,IE 7 会认为 var class = 0 是错误而停止执行。

8、Firefox 中的 String 重载了 [] 运算符,等价于 charAt,但这不是标准。

9、Js 和 Java 同宗,N 多相似的地方,比如 Date 中月份从 0 开始,0 表示一月;String 是不可变类;函数的命名和 Java 几乎完全相同。

10、Firefox 下不允许修改 Object.prototype,而 IE 下可以。

先写到这,以后再补……