月度归档:2013年11月

53张牌中找出缺少的牌的花色和点数–raid3,4,5,6的容错原理

一副扑克牌,抽出一张,要求找出抽出的牌的点数和花色。

算法的主要思想就是用异或运算来确定丢的牌的花色。四种花色分别如下表示:红桃用1(二进制0001)表示,黑桃用2(二进制0010)表示,黑桃用4(0100)表示,方块用8(1000)表示,这样当同一点数的四个花色都齐全的话,则四种花色异或的结果再与15(1111)异或之后,结果为0。如果确实一种花色,则三张存在的牌的花色值异或后与15异或所得的结果为抽出的花色的值。比如说:抽出的花色为红桃,则0010^0100^1000^1111=0001,正好等于红桃的值。具体实现见下面的代码。

#include
#include

#define NUMS 2 //NUMS = 2 用于演示,如果是一副牌的话NUMS应定义为53
using namespace std;

typedef struct Card{
  int num; //num用0-13分别表示A,2,3,4……,10,J,Q,K,王
  int flower; //flower表示花色 1表示红桃,3表示大王,2表示黑桃,12表示小王,3表示梅花,4表示方块
}Card;

void find(Card cards[])
{
int i;
map numclass_Map;
for(i=0;i<NUMS;i++)numclass_Map[i] = 15;

for(i = 0;i<NUMS*4-1;i++)
{
  numclass_Map[cards[i].num]^=cards[i].flower;
  if(numclass_Map[cards[i].num] == 0) numclass_Map.erase(cards[i].num);
}
map::iterator it;
it = numclass_Map.begin();
printf(“点数:%d 花色:%d\n”,it->first+1,it->second);
}

void main()
{
//just for test
Card cards[NUMS*4-1];

cards[0].num = 0;
cards[0].flower = 1;

cards[1].num = 0;
cards[1].flower = 2;

cards[2].num = 0;
cards[2].flower = 4;

cards[3].num = 0;
cards[3].flower = 8;

cards[4].num = 1;
cards[4].flower = 1;

cards[5].num = 1;
cards[5].flower = 2;

cards[6].num = 1;
cards[6].flower = 4;

//cards[7].num = 1;
//cards[7].flower = 8;

find( cards);
}

输出:

点数:2 花色:8

如果是抽出两种牌,这个算法也是可以分别找出抽出的牌的点数和花色的。这种容错的方法也就是raid3,4,5,6的容错方法,也就是奇偶校验方法。

抽样问题

需求:从正整数1-100中随机抽取20个数。

以下算法均来自与《编程珠玑》

1.精妙的算法,运用概率的知识。

或许你不理解rand()%(n-i)<m这一句,我开始也不理解,请教了高人之后才理解的,所以就写了这篇博客,以免忘了。

从n中选m个数,每个数被选中概率为m/n。

第一个数被选中的概率是m/n。

第二数被选中概率的计算如下:如果第一数被选中了,(m-1)/(n-1); 如果第一个数没有被选中,m/(n-1)。所以总体概率为m/n * (m-1)/(n-1) +(n-m)/n * m/(n-1) = m/n

以此类推。。。每个数被选中的概率都是m/n。

假设一个随机数生成器R,生成的数属于[0,Z-1],且生成每个数的概率相等。

对任意一个小于Z的数Q,那么R()<Q的概率即Q/Z。所以rand()%(n-i) < m 即表示m/n-i的概率,也就是当前数字被选中的概率。

严格来说,rand()%(n-i)并不是一个等概率生成器,因为rand()显然不是对每个i都是n-i的整数倍。

(以上解释出自肖微)

2.往一个初始为空的集合中插入随机整数,直到填入足够的整数。需要额外的m*size(int)的空间,最大的问题是需要查询重复元素。

3.弄乱n个元素,时间复杂度是O(m),但需要做交换操作。

用telnet和php的curl库测试http

一.telnet测试http

telnet简介

    Telnet协议是TCP/IP协议族的其中之一,是Internet远端登录服务的标准协议和主要方式,常用于网页服务器的远端控制,可供使用者在本地主机执行远端主机上的工作。

使用者首先在电脑执行Telnet程序,连线至目的地服务器,然后输入帐号和密码以验证身份。使用者可以在本地主机输入命令,然后让已连接的远端主机执行,就像直接在对方的控制台上输入一样。

传统Telnet会话所传输的资料并未加密,帐号和密码等敏感资料容易会被窃听,因此很多服务器都会封锁Telnet服务,改用更安全的SSH

(以上介绍摘自维基百科http://zh.wikipedia.org/wiki/Telnet

windows7系统中telnet

windows7默认是关闭telnet服务的,windows7启用telnet过程见 http://soft.yesky.com/204/31059704.shtml

 

用telnet的远程登录命令示例 telnet 127.0.0.1或者telnet localhost,如果连接成功,输入用户名、密码便可以远程控制目标主机了。

下面是重点,用telnet测试http

比如说,我要用get和post方法获得http服务器222.31.76.182上的页面。

http报文如图所示:

http请求报文

http请求头的格式参见http://zh.wikipedia.org/wiki/%E8%B6%85%E6%96%87%E6%9C%AC%E4%BC%A0%E8%BE%93%E5%8D%8F%E8%AE%AE和http://royaki.iteye.com/blog/685317

(以下测试均在ubuntu系统上进行)

    GET方法:

1.使用telnet连接到HTTP服务器222.31.76.182,并指定80端口

telnet 222.31.76.182 80

2.连接http服务器后,发送http请求信息:

GET /test.html HTTP/1.1

Connection:close

Host:222.31.76.182

输入上面的内容后,连续敲击两个回车,就可以看到返回的结果了。

 

    POST 方法:

telnet 222.31.76.182

POST /telnettest.php HTTP/1.1

Host: 222.31.76.182

Content-Type: application/x-www-form-urlencoded

Content-Length: 10

//注意此处要空一行,作为http请求头与请求内容直接的分隔

test=hello

按两次enter键,将会出现类似于以下的结果,最后一行是返回的数据

二.php的curl测试http

这里仅举例说明php的curl函数库的用法,详细用法参考php官方文档http://my.oschina.net/leadsir/blog/137755

首先要保证php的设置里开启了curl库。windows下只需修改php.ini文件,将extention=php_curl.dll前的注释符删掉就行,linux下需要重新编译PHP,在configure时加上“–with-curl”参数。

获取一个页面

此处获得的结果跟上面的telnet用get获取的内容是一样的。

    POST数据

此处获得的结果跟上面telnet用post方法获取的内容是一样的。

三.linux的curl

当然如果你用的是linux系统,用curl也是一种非常好的http测试工具。可参考http://www.linuxidc.com/Linux/2008-01/10891.htm

Javascript null和undefined

Javascript的数据类型包括数字、字符串、布尔值、null、undefined和对象。其中null和undefined是两种特殊的原始类型,很容易混淆。今天就来剖析一下null和undefined这两种数据特殊类型的区别。

null

null是Javascript的关键字,它通常用来描述空值

可以看出null是一个特殊的对象,含义是“非对象”。可以认为null是它自有类型的唯一一个成员,它可以表示数字、字符串、对象是“无值”的。因为null没有其他属性和方法了,比如说执行null.length,会报错:TypeError: Cannot read property ‘length’ of null。

null 参与数值运算时其值会自动转换为 0 ,因此,下列表达式计算后会得到正确的数值:

undefined

undefined不是Javascript的关键字。undefined用未定义的值表示更深层次的“空值”。它是变量的一种取值,表面变量没有初始化。如果要查询对象属性或数组元素的值时返回undefined,说明这个属性或元素不存在。如果函数没有返回值,则返回undefined。引用没有提供实参的函数,函数形参的值也只会是undefined。在ECMAScript5中,undefined是只读的。typeof undefined,会返回“undefined”,表明“undefined”是这个类型的唯一成员。

尽管null和undefined是不同的,但它们都表示“值的空缺”,两者往往可以互换。

关于Javascript我还遇到一个有意思的现象:

第一句比较怪异。原因是这样的,“==”是松散比较,也就是说如果比较的双方类型不一致,Javascript会先把它们转成同一类型,再做严格比较。如果双方中有一个为数字类型或布尔类型,则javascript会将它们转成数字类型或布尔类型,如果双方中有string类型而没有数值类型或布尔类型,则会把不是string类型强制转换为string类型。这段代码的第一句,比较双方是””和0,””会被强制转成Number型0,所以“” == 0,返回true。

参考:

《JavaScript权威指南》44-45页

区分JS中的undefined,null,””,0和false

http://www.cnblogs.com/birdshome/archive/2005/03/04/111991.html

解剖JavaScript中的null和undefined

http://blog.csdn.net/leadzen/article/details/3899392

stackoverflow

http://stackoverflow.com/questions/12422064/why-javascript-treats-0-equal-to-empty-string

获取DOM父元素和子元素

利用javascript可以遍历DOM树,这篇文章介绍用获取一个DOM元素的所有父节点和获取一个DOM元素的所以子孙节点。

1.获取所有父节点。用递归的方法,用parentNode属性。

<!DOCTYPE html>
<html lang=”en” >
<head>

<title>getParents</title>

</head>
<body >
<div >
<div id=”test”> </div>
<div></div>
</div>

<script type=”text/javascript”>
var getParents=function(id){
var dom=id.parentNode;
while(dom.tagName!=null){
document.write(dom.tagName);
dom=dom.parentNode;
}
return dom;
}
getParents(test);
</script>
</body>
</html>

运行结果(chrome、firefox、IE9):DIVBODYHTML

2.遍历所以子孙节点。

<!DOCTYPE HTML>
<html>
<head>
<meta charset = “utf-8″/>
<title>getChildren</title>
</head>
<body>
<div>&nbsp;&nbsp;I am in second floor
<div>&nbsp;&nbsp;I am in second floor</div>
</div>
<div>1
<div>&nbsp;&nbsp;I am in second floor
<div>&nbsp;&nbsp;&nbsp;&nbsp;I am in third floor</div>
</div>
</div>
<div>1</div>
<div>1</div>
<div>1</div>
<div id=”test”>
<div>&nbsp;&nbsp;I am in second floor</div>
<div>&nbsp;&nbsp;I am in second floor</div>
</div>
<script type=”text/javascript”>
var node;
node = document.getElementsByTagName(‘body’);

//深度遍历
function getChildren(node,f){ //f表示第几层,根元素为第0层
if(node.nodeType!=3){
console.log(“nodename: “+node.nodeName);
console.log(“nodetype: ” + node.nodeType);
console.log(“the “+f+”th floor”);
var childlist = node.childNodes;
console.log(childlist);
var length;
length = childlist.length;
if(childlist.length>0){
var f = f+1;
for(var i=0;i<childlist.length;i++){
getChildren(childlist[i],f);
}
}
}else if(node.nodeValue.length > 1){ //因为每个nodeValue都带一个换行符”%0A”
console.log(“value: “+node.nodeValue);
}
}

getChildren(node[0],0);
//层次遍历DOM树
function getChildrenByLev(arr,f,Matri){ //f表示第几层,根元素为第0层,arr表示遍历起始层的节点,Matri为层次遍历输出的结果,结果以一个二维数组表示,第一个索引表示层次
if(arr.length<1)return Matri;
f = f+1;
Matri[f] = Matri[f] || new Array();
for(var i = 0; i < arr.length ; i++){
children = arr[i].childNodes;
for(j in children){
if(children[j].nodeType == 1){
Matri[f].push(children[j]);
}
}
}
getChildrenByLev(Matri[f],f,Matri);
}

var levelMatri = new Array();
levelMatri[0] = new Array();
levelMatri[0][0] = node[0];
getChildrenByLev(node,0,levelMatri);
console.log(levelMatri);
</script>
</body>
</html>

深度遍历的结果如图(注意:截图不全):

traverse1

层次遍历的结果如图:

traverse2