Category: 木有技术

Categories
不学无术 木有技术

浅谈PCA 人脸识别

版权声明：转载时请以超链接形式标明文章原始出处和作者信息及本声明
http://leen2010.blogbus.com/logs/124631640.html

前几天讨论班我讲了基于PCA的人脸识别，当时我自己其实也只是知道这个算法流程，然后基于该算法利用c++实现了，效果还不错。后来跟师兄一起讨论的时候，才发现这个PCA还是有相当深刻的意义。
PCA的算法：矩阵C=AAT，A的每一列是一张人脸注（将一张人脸图片用一个列向量表示，即对于128*128的图片，将视为16384维的列向量），A的列数就是图片的张数。算法就是求矩阵C的特征向量，每个向量称之为特征脸[1]。为了简单，只取其中部分的特征向量，这些特征向量对应于某些特征值，通常是前M个大的特征值。这样便得到了M个特征向量。接下来就是将每张图片在这M个特征向量上做投影，得到一个M维的权重向量w=（w1,…wM），一个人可能有多张图片，于是将对应于这个人的权重向量做一个平均作为这个人的权重向量。然后对于每个新来的人脸，先求得一个权重向量，然后与人脸库中每个人的权重向量做比较，如果小于某个阈值，则认为他是人脸库中的这个人；否则视为unknown。当然，文章中还给出了另外一个判断一张图像是否是人脸的方法，这里不再讨论。对于计算的时候我们实际上求的是ATA，至于二者的关系，可以参考文章[1]，因为与后面讨论的关系不大，这里不细说了。
有个上述简介，我们就大概知道了PCA到底是怎么做的了。刨根问底一下，C到底是什么，C的特征向量又到底是什么，对应于特征值大的特征向量有有什么意义。
1.C到底是什么？我们先看一下C的（i,j）元素是什么。很简单，就是A的第i行与AT的第j列的乘积。那么A的第i行又是什么呢？就是每张图片的第i个像素构成的一个向量。则C的（i,j）元素就是每张图片的第i个像素构成的向量与每张图片的第j个像素构成的向量的乘积。回忆一下概率论中的协方差cov(x,y)=E((x-x–)(y- y–)),这里x– 是x的平均。如果我们把图片的第i个像素视为一个随机变量Xi，那么人脸库中的每张人脸的第i个像素的取值即为这个随机变量的所有取值。根据注，A的第i行的每个值都已经减去了Xi的均值，因此C的（i,j）元素就是随机变量Xi与Xj的协方差。到此，我们已经知道C是什么了。
2.C的特征向量是什么。我们知道对C求特征向量是找到一个可逆矩阵Q，使得Q-1CQ是一个对角阵D，D的元素即为特征值，Q中的每一列即为特征向量，与特征值所在的列一一对应。注意，因为C是实对称阵，故必然可以对角化。由于C是对称的，C的特征向量是正交的，因此Q便是一个正交阵，故Q-1即为QT。先从简单的角度来看，假设C已经是一个对角阵了，并且对角元素依次递减。即随机变量Xi与Xj(i!=j)时是不相关的，而Xi的方差则随着i的增大而减小。也就是前几个像素是方差比较大的像素，即在第一个像素上，每张图片的值变化最大，第二个像素次之，依此类推。举个例子，假设第一个像素表示人脸的额头上的某个点（也许你会问，第一个像素不是图片的最左上角的那个像素吗？为什么会是额头上的某个点，后面会说明为什么可以这么假设），而在这个点上，有些人有痣，有些人没有，那么这一点的方差就会比相邻的额头上的其他点大，因为其他点上，每个人的额头都差不多，因此其像素值也差不多，方差就小了。现在来考虑QTAATQ=D,这里依然假设D中的元素依次递减。对于QTA，QT的每一行是一个特征向量，QT的第i行与A的每一列相乘得到QTA的每一行，从矩阵的角度也可以看作是用QT对A做一个变换。记住这里的QTA可以看做前面讨论的A，那么变换的结果就是使得QTA前面的行对应的是方差大的像素，而且这个变换会把方差最大的放到了第一行（因为D的降序排列），这里也就解释了为什么前面那个例子可以认为第一个像素是额头上的某个点，因为做了变换。我们选择了QT的前M行作为特征向量，因为他们对应了前M个大的特征值。这里可以举一个直观但是不一定恰当的例子，人的头发部分对应的那些像素，经过QT变换后回到某个像素上，那么这个像素会是QTA中的哪个位置呢，我认为应该是QTA的列中靠下面的像素，因为在头发这个像素的地方每个人基本都是头发（这句话很别扭，我是想说，对于比较正规的人脸库，即每张人脸不会有太大的变化，某个人头发的对应的那几个像素对于其他人来说也都是头发，因此变换后这个像素对于每个人都差不多，方差小，固然会在比较靠后的位置了）。QTA的每一列的前M个元素对应的就是每张人脸的权重向量w。因此每张人脸的权重向量的同一个分量可以看作是新的像素，这些新的像素对应着方差依次减小的像素。对于一张新来的人脸，让他在特征向量上作投影得到权重向量，在这些方差大的像素处，如果跟某个人的比较接近，则认为是这个人，这个也是合理的。至此，也许没能讲清楚特征向量是什么，但我想对应于特征值大的特征向量有什么意义这一点也交代的差不多了。
3.2中交代了说了，这里想不到有什么需要补充的了。
理解了这几个问题之后，PCA简洁明了（这本来就是的）而又有深刻意义了。我突然发现原来看似简单的理论其实水深的很，o(︶︿︶)o ！我看文章实在是不够认真，如果没有师兄提问，估计我也不会去想这个问题。再次感谢WF师兄。
 
[1]Eigenfaces for Recognition. Matthew Turk,Alex Pentland 1991
注：A的每一列是一张人脸，这里的人脸是每张人脸减去了所有人脸的平均后的人脸

Categories
木有技术

如何在 VPS 上搭建 PPTP/L2TP VPN 简易教程

首先是L2TP的，来自http://www.kukaka.org/home/content/640

如之前所说，PPTP 类的 VPN 可以在 iPhone 手机上使用，但是不能在 Mac OS X 电脑系统上使用，于是，我需要使用 L2TP/IPSec (L2TP over IPSec，即在 IPSec 上搭建 L2TP) 类的 VPN。
这篇文章将介绍如何在 VPS （Xen）上搭建 L2TP/IPSec 类的 VPN，而你只需要一个 VPS 和一台可以上网的电脑。和 PPTP 的一样，L2TP/IPSec 的操作步骤也是基于 Mac 电脑的终端应用程序，对 Linux 系统来讲，步骤几乎是一模一样的，而对 Windows 用户来讲，则需要先安装一个叫 Putty 的软件。
顺便提一下，Xen VPS 的 Ubuntu 系统最好使用 11.04 版本的，因为其他较低的版本（例如 10.04）很可能不行。
 

I、连接 VPS

打开终端应用程序并输入以下命令：
ssh [email protected]
记得将 “xxx.xxx.xxx.xxx” 替换成 VPS 的 IP 地址，例如 “178.18.17.30”，然后回车就可以了。
P.S.:
如果在连接的过程中遇到问题，可以参考之前的 PPTP 教程。

II、安装 OpenSwan

虽然你可以通过输入 “aptitude install openswan” 命令直接安装 OpenSwan，但根据我分别在两个不同的 VPS 上测试的结果，这种方法已经无效，所以，最好还是直接从 OpenSwan 官方网站下载再安装，具体方法如下：

1、输入以下命令：

aptitude install build-essential
回车，输入 “y”，再回车。

2、输入以下命令：

aptitude install libgmp3-dev gawk flex bison
回车，输入 “y”，再回车。

3、输入以下命令：

wget http://www.openswan.org/download/openswan-2.6.35.tar.gz
回车。

4、输入以下命令：

tar xzvf openswan-2.6.35.tar.gz
回车。

5、输入以下命令：

cd openswan-2.6.35
回车。

6、输入以下命令：

make programs
回车。

7、输入以下命令：

make install
回车。到此，OpenSwan 就安装成功了。
备注：
a、2.6.35 是目前最新的版本，将来你可以访问 OpenSwan 官方网站看看有没有更新的版本，如有，不妨尝试一下。
b、文章中的所有命令都可以直接复制粘贴到终端应用程序。

III、编辑 IPSec

OpenSwan 是用来建 IPSec 的，而 IPSec 是用来建 L2TP 的。

1、输入以下命令：

vi /etc/ipsec.conf
回车，输入 “dG” 删除所有内容，按 “i” 键，然后复制并粘贴以下内容：
version 2.0
config setup
    nat_traversal=yes
    virtual_private=%v4:10.0.0.0/8,%v4:192.168.0.0/16,%v4:172.16.0.0/12,%v4:25.0.0.0/8,%v6:fd00::/8,%v6:fe80::/10
    oe=off
    protostack=netkey
conn %default
    forceencaps=yes
conn L2TP-PSK-NAT
    rightsubnet=vhost:%priv
    also=L2TP-PSK-noNAT
conn L2TP-PSK-noNAT
    authby=secret
    pfs=no
    auto=add
    keyingtries=3
    rekey=no
    ikelifetime=8h
    keylife=1h
    type=transport
    left=YOUR.VPS.IP.ADDRESS
    leftprotoport=17/1701
    right=%any
    rightprotoport=17/%any
记得将 YOUR.VPS.IP.ADDRESS 替换成自己 VPS 的 IP 地址，例如 178.18.17.30。替换方法如下：
按下”ESC” 键退出插入模式，将光标移到 “Y” 字母上，接着按下 “i” 键，输入 IP 地址，再按一下 “ESC” 键，并将光标移到 “YOUR.VPS.IP.ADDRESS” 上，然后按下 “x” 键把它们全部删除。或者你可以先把内容粘贴到记事本之类的编辑器上并修改好之后再复制粘贴到终端应用程序。
完了之后，输入 “:wq” 并回车保存所做的修改。
备注：
在 Vi 编辑模式下，你需要按 “i” 才能插入内容，完了之后，要按 “ESC” 退出插入模式和保存。

2、输入以下命令：

vi /etc/ipsec.secrets
回车，按 “i” 键并输入以下内容：
YOUR.VPS.IP.ADDRESS %any: PSK “YourSharedSecret”
例如：
178.18.17.30 %any: PSK “123456abcdef”
（小技巧：你需要按 Tab 键创建不同数值之间的空格。）
按 “ESC” 键，输入 “:wq”，再回车保存。

3、一行一行地输入以下命令：

for each in /proc/sys/net/ipv4/conf/*
do
echo 0 > $each/accept_redirects
echo 0 > $each/send_redirects
done
每一行都要回车。

4、输入以下命令：

service ipsec restart
回车。
备注：
输入 “ipsec verify”，回车，如果一切正确，你将会看到如下图所示的结果：
如果不是，则需要重新检查之前的操作步骤，特别是 “ipsec.conf” 的内容。

IV、安装 L2TP

基于 IPSec 的 L2TP 就是 VPN 了。

1、输入以下命令：

cd ..
回车以便进入 VPS 根目录。

2、输入以下命令：

aptitude install xl2tpd
回车，输入 “y”，再回车。

3、输入以下命令：

vi /etc/xl2tpd/xl2tpd.conf
回车，输入 “dG” 删除所有的内容，按下 “i” 键，然后粘贴以下内容：
[global]
; listen-addr = 192.168.1.98
[lns default]
ip range = 10.1.1.2-10.1.1.255
local ip = 10.1.1.1
require chap = yes
refuse pap = yes
require authentication = yes
name = LinuxVPNserver
ppp debug = yes
pppoptfile = /etc/ppp/options.xl2tpd
length bit = yes
按下 “ESC” 键，输入 “:wq”，并回车保存。

V、创建 xl2tpd

这里假设你的 VPS 已经支持 PPP，如果没有，先输入 “aptitude install ppp” 命令安装 PPP。

1、输入以下命令：

vi /etc/ppp/options.xl2tpd
回车，按下 “i” 键，然后粘贴以下内容：
require-mschap-v2
ms-dns 8.8.8.8
ms-dns 8.8.4.4
asyncmap 0
auth
crtscts
lock
hide-password
modem
debug
name l2tpd
proxyarp
lcp-echo-interval 30
lcp-echo-failure 4
按下 “ESC” 键，输入 “:wq”，并回车保存。
备注：
你可以将 8.8.8.8 和 8.8.4.4 替换成 208.67.222.222 和 208.67.220.220。

2、输入以下命令：

vi /etc/ppp/chap-secrets
回车，按下 “i” 键，并输入如下内容：
username l2tpd password *
例如：
freenuts l2tpd 123456 *
记得用 “tab” 键输入空格，用 “:wq” 保存文件。

3、输入以下命令：

service xl2tpd restart
回车。

VI、IP 转发

这个步骤将使你的 VPN 连接整个互联网。

1、输入以下命令：

vi /etc/sysctl.conf
回车，找到 “#net.ipv4.ip_forward=1” 这一行，接着按 “x” 键删除 “#” 号，然后输入 “:wq” 保存。

2、使转发生效：

sysctl -p
回车，如果一切正常，你将会只看到以下结果：
net.ipv4.ip_forward = 1

3、输入以下命令：

iptables -t nat -A POSTROUTING -s 10.1.1.0/24 -o eth0 -j MASQUERADE
回车之后，你就可以连接自己的 L2TP/IPSec VPN 翻墙了，但是如果你重启 VPS 的话，就需要重新执行一次 iptables 命令，并重启 ipsec，为了避免这些，你只需要输入以下命令：
vi /etc/rc.local
并在 “exit 0” 这一行之前粘贴以下内容就可以了：
for each in /proc/sys/net/ipv4/conf/*
do
echo 0 > $each/accept_redirects
echo 0 > $each/send_redirects
done
iptables -t nat -A POSTROUTING -s 10.1.1.0/24 -o eth0 -j MASQUERADE
/etc/init.d/ipsec restart
完了之后，你就可以尽情地享用自己搭建的 L2TP/IPSec VPN 了。
额外收获：
以下是根据上面的教程在 2host 的 Xen VPS 上搭建的 L2TP/IPSec VPN：
Server Address: 178.18.17.30
Account Name: freenuts
Password: 123456
Shared Secret: 123456abcdef
这个 VPN 帐号会免费大概半个月，你可以参考这篇文章 在电脑或者手机上试用。
=====================================================

然后是PPTP的（这种方便一些）

在 Ubuntu 上搭建 VPN 服务器的方法非常多，比较著名的有 PPTP, L2TP/IPSec 和 OpenVPN。这里介绍一下pptp的安装配置方法。
服务器环境是单网卡 eth0。
在 Ubuntu 中建立 pptp server 需要的软件包为 pptpd，用 apt-get 即可安装：
sudo apt-get pptpd
安装好后，首先编辑 /etc/pptpd.conf
sudo vi /etc/pptpd.conf
去掉文件最末端的 localip 和 remoteip 两个参数的注释，并进行相应修改。这里，localip 是 VPN 连通后服务器的 ip 地址，而 remoteip 则是客户端的可分配 ip 地址。
localip 10.100.0.1
remoteip 10.100.0.2-10
编辑好这个文件后，我们需要编辑 /etc/ppp/pptpd-options 文件，我们只需要改变其中的 ms-dns 选项，为 VPN 客户端指派 DNS 服务器地址：
ms-dns 202.113.16.10
ms-dns 208.67.222.222
修改 /etc/ppp/chap-secrets 文件，这里面存放着 VPN 的用户名和密码，根据你的实际情况填写即可。如文件中注释所示，第一列是用户名，第二列是服务器名（默认写 pptpd 即可，如果在 pptpd-options 文件中更改过的话，注意这里保持一致），第三列是密码，第四列是 IP 限制（不做限制写 * 即可）。
全部搞定后，我们需要重启 pptpd 服务使新配置生效：
sudo /etc/init.d/pptpd restart
找一台 Windows 电脑，新建个 VPN 链接，地址填服务器的 IP（或域名），用户名密码填刚才设置好的，域那项空着（如果你在 pptpd-options 中设置了，这里就保持一致），点连接就可以了。正常情况下您应该能够建立与服务器的 VPN 链接了。
建立连接之后，您会发现除了可以访问服务器的资源，其余内外和互联网的内容均无法访问。如果需要访问这些内容的话，我们还需要进一步设置：
首先，开启 ipv4 forward。方法是，修改 /etc/sysctl.conf，找到类似下面的行并取消它们的注释：
net.ipv4.ip_forward=1
然后使新配置生效：
sudo sysctl -p
有些时候，经过这样设置，客户端机器就可以上网了（我在虚拟机上这样操作后就可以了）。但我在实验室的服务器上这样操作后仍然无法访问网络，这样我们就需要建立一个 NAT。这里我们使用强大的 iptables 来建立 NAT。首先，先安装 iptables：
sudo apt-get intall iptables
装好后，我们向 nat 表中加入一条规则：
sudo iptables -t nat -A POSTROUTING -s 10.100.0.0/24 -o eth0 -j MASQUERADE
这样操作后，客户端机器应该就可以上网了。
但是，只是这样，iptables 的规则会在下次重启时被清除，所以我们还需要把它保存下来，方法是使用 iptables-save 命令：
sudo iptables-save > /etc/iptables-rules
然后修改 /etc/network/interfaces 文件，找到 eth0 那一节，在对 eth0 的设置最末尾加上下面这句：
pre-up iptables-restore < /etc/iptables-rules
这样当网卡 eth0 被加载的时候就会自动载入我们预先用 iptables-save 保存下的配置。
到此，一个 VPN Server/Gateway 基本就算架设完毕。当然，也许你按照我的方法做了，还是无法成功，那么下面总结一些我碰到的问题和解决方案：
无法建立 VPN 连接
安装好 pptpd 并设置后，客户端还是无法建立到服务器的连接。造成的原因可能有以下几种：
1. 服务器端的防火墙设置：PPTP 服务需要使用 1723(tcp) 端口和 gre 协议，因此请确保您的防火墙设置允许这两者通行。
2. 如果服务器在路由器后面，请确保路由器上做好相应的设置和端口转发。
3. 如果服务器在路由器后面，那么请确保你的服务器支持 VPN Passthrough。
4. 如果客户端在路由器后面，那么客户端所使用的路由器也必须支持 VPN Passthrough。其实市面上稍微好点的路由器都是支持 VPN Passthrough 的，当然也不排除那些最最最便宜的便宜货确实不支持。当然，如果你的路由器可以刷 DD-Wrt 的话就刷上吧，DD-Wrt 是支持的。
能建立链接，但“几乎”无法访问互联网
这里我使用“几乎”这个词，是因为并不是完全不能访问互联网。症状为，打开 Google 搜索没问题，但其它网站均无法打开；SSH 可用，但 scp 不行；ftp 能握手，但传不了文件。我就遇到了这种情况，仔细 Google 后发现原来是 MTU 的问题，用 ping 探测了一下果然是包过大了。知道问题就好办了，我们可以通过 iptables 来修正这一问题。具体原理就不讲了，需要的自己 Google。这里只说解决方案，在 filter 表中添加下面的规则：
sudo iptables -A FORWARD -s 10.100.0.0/24 -p tcp -m tcp –tcp-flags SYN,RST SYN
-j TCPMSS –set-mss 1200
上面规则中的 1200 可以根据你的实际情况修改，为了保证最好的网络性能，这个值应该不断修改，直至能保证网络正常使用情况下的最大值。
好了，至此，一台单网卡 pptp-server 就算完成了。
这篇来自http://www.study365.org/linux/30.html
=====================================================
附加教程：

Ubuntu搭建VPN服务器pptpd安装配置http://www.study365.org/linux/30.html

centos 5搭建vpn服务器请访问http://www.study365.org/linux/60.html

Categories
不学无术 木有技术

【Android Camera】之 Preview

本文转载自：

http://blog.csdn.net/yiyaaixuexi/article/details/6455741

================================================================
实在不好复制过来，去原文看吧。

Categories
木有技术

ThinkPad RnR 系统恢复盘 IMD IMZ 文件解压密码表

本文转载自：
http://forum.51nb.com/thread-1343052-1-1.html
=================================
ThinkPad RnR 系统恢复盘 IMD IMZ 文件解压密码表

ENCYPTED DECRYPTED PASSWORD
BMGR be0d
HURRICANES xwbdbgmlbu
HUURICANES xwvdbgmlbu
STANLEYCUP u1kmkblhvi
TVTPASS 2b0ilsu
CKD158A iqyrabm
CKD164T iqyrhk2
CKD170T iqyrzm2
CKD171A iqyrzpm
CKD173T iqyrzd2
CKD174T1 iqyrzk2q
CKD179T iqyrzs2
CKD185T1 iqyrc`2q
CKD192T iqyrtj2
CKD196T iqyrtg2
CKD197T iqyrty2
CKD199T iqyrts2
CKD204A iqylnkm
CKD205T iqyln`2
BKD010F bqyoqmu
BKD023F bqyokdu
BKD0025F bqyonjbt
BKD037A bqyoeym
BKD047F bqyolyu
CM2ZCFR iejfhsd
以上是已被别人解开的密码，
以下是别人通过以上密码绘制的对应图表：

Thinkpad RnR 系统恢复盘 密码表
Thinkpad RnR 系统恢复盘 密码表

以下是我通过上面的对应图表列出的X60 7CD XP恢复盘文件的密码，成功解压无误。
2GLGU31_  ickb1bdc
3GZUM0A0  fljbcbdk
CKD158A   iqyrabm
CKD1642   iqyrhkl
CKD1702   iqyrzml
CKD171A   iqyrzpm
CKD1732   iqyrzdl
CKD17421  iqyrzklq
CKD1792   iqyrzsl
CKD1852   iqyrc`l
CKD1922   iqyrtjl
CKD1962   iqyrtgl
CKD1972   iqyrtyl
CKD1992   iqyrtsl
CKD204A   iqylnkm
XM2AACS   rejmlgu
XM2UACS   rejxlgu
TVTPASS   2b0ilsu
图表来自“http://forum.notebookreview.com/ … vice-partition.html”
向那些神人致敬！

Categories
不学无术 木有技术

1042. Shuffling Machine (20)

Shuffling is a procedure used to randomize a deck of playing cards. Because standard shuffling techniques are seen as weak, and in order to avoid “inside jobs” where employees collaborate with gamblers by performing inadequate shuffles, many casinos employ automatic shuffling machines. Your task is to simulate a shuffling machine.
The machine shuffles a deck of 54 cards according to a given random order and repeats for a given number of times. It is assumed that the initial status of a card deck is in the following order:
S1, S2, …, S13, H1, H2, …, H13, C1, C2, …, C13, D1, D2, …, D13, J1, J2
where “S” stands for “Spade”, “H” for “Heart”, “C” for “Club”, “D” for “Diamond”, and “J” for “Joker”. A given order is a permutation of distinct integers in [1, 54]. If the number at the i-th position is j, it means to move the card from position i to position j. For example, suppose we only have 5 cards: S3, H5, C1, D13 and J2. Given a shuffling order {4, 2, 5, 3, 1}, the result will be: J2, H5, D13, S3, C1. If we are to repeat the shuffling again, the result will be: C1, H5, S3, J2, D13.
Input Specification:
Each input file contains one test case. For each case, the first line contains a positive integer K (<= 20) which is the number of repeat times. Then the next line contains the given order. All the numbers in a line are separated by a space.
Output Specification:
For each test case, print the shuffling results in one line. All the cards are separated by a space, and there must be no extra space at the end of the line.
Sample Input:

2
36 52 37 38 3 39 40 53 54 41 11 12 13 42 43 44 2 4 23 24 25 26 27 6 7 8 48 49 50 51 9 10 14 15 16 5 17 18 19 1 20 21 22 28 29 30 31 32 33 34 35 45 46 47

Sample Output:

S7 C11 C10 C12 S1 H7 H8 H9 D8 D9 S11 S12 S13 D10 D11 D12 S3 S4 S6 S10 H1 H2 C13 D2 D3 D4 H6 H3 D13 J1 J2 C1 C2 C3 C4 D1 S5 H5 H11 H12 C6 C7 C8 C9 S2 S8 S9 H10 D5 D6 D7 H4 H13 C5

===================================
本题目主要难度：英语阅读。
就是数组里面元素换来换去没啥好说的，就是发现自己数组指针这块了解的不是很清晰，以后得注意。
===================================

#include 
#include 
using namespace std;
const int SUFF_SIZE = 54;
int *cards = new int[SUFF_SIZE]; //扑克牌数组
int *results = new int[SUFF_SIZE];
int* suffle(int * src, int* rule)
{
	for(int i=0; i= 10)
	{
		result += "1";
		postfix = postfix%10;
	}
	result += (char)(postfix + 0x30);
	return result;
}
int rules[SUFF_SIZE]; //suffle规则
int main()
{
	int K;
	cin >> K;
	for(int i=0; i> rules[i];
	}
	while(K--)
	{
		suffle(cards, rules);
		for(int i=0; i
Categories
不学无术 木有技术

第二章 啊哈！算法

原文见：

http://blog.csdn.net/silenough/article/details/7040028

 
A. 给定一个最多包含40亿个随机排列的32位整数的顺序文件，找出一个不在文件中的32位整数(在文件中至少缺少一个这样的数—为什么？)。在具有足够内存的情况下，如何解决该问题？如果有几个外部的“临时”文件可用，但是仅有几百字节的内村，又该如何解决该问题？
因为2^32 大于40亿，所以文件中至少缺失一个整数。我们从表示每个整数的32位的视角来考虑二分搜索，算法的第一趟（最多）读取40亿个输入整数，并把起始位为0的整数写入一个顺序文件，把起始位为1的整数写入另一个顺序文件。这两个文件中，有一个文件最多包含20亿个整数，接下来将该文件用作当前输入并重复探测过程，但这次探测的是第二个位。如果原始的输入文件包含n个元素，那么第一趟将读取n个整数，第二趟最多读取n/2个整数，第三趟最多读取n/4个整数，依次类推，所以总的运行时间正比于n。
如果内存足够，采用位图技术，通过排序文件并扫描，也能够找到缺失的整数，但是这样做会导致运行时间正比于nlog(n).
1. 考虑查找给定输入单词的所有变位词的问题。仅给定单词和字典的情况下，如何解决该问题？如果有一些时间和空间可以在响应任何查询之前预先处理字典，又会如何？
首先计算给定单词的标识，若果不允许预处理，那么久只能顺序读取整个文件，计算每个单词的标识，并于给定单词的标识进行比较。
 

  1. //压缩一个单词，形成其标识,设定单词中相同字母不会超过99个
  2. void compress(char * pWord, int len, char * pFlag)
  3. {
  4.     sort(pWord, pWord+len); //对单词进行排序
  5.     int i = 0;
  6.     int nCount;            //计数重复字母的个数
  7.     char chCount[3];       //存放整数到字符的转换值，整数最大为99
  8.     while (*pWord != ‘’)
  9.     {
  10.         char chTemp = *pWord;
  11.         char *pTemp = pWord + 1;
  12.         nCount = 1;
  14.         while (true)
  15.         {
  16.             if (chTemp == *pTemp++)
  17.             {
  18.                 ++nCount;
  19.             }
  20.             else
  21.             {
  22.                 *(pFlag + i++) = *pWord;
  23.             //  ++i;
  24.                 memset(chCount, ‘’, 3);
  25.                 _itoa(nCount, chCount, 10);
  26.                 if (nCount >= 10)
  27.                 {
  28.                     *(pFlag + i++) = *(chCount + 0);
  29.                 //  i++;
  30.                     *(pFlag + i++) = *(chCount + 1);
  31.                 //  ++i;
  32.                 }
  33.                 else
  34.                 {
  35.                     *(pFlag + i++) = *(chCount + 0);
  36.                 //  ++i;
  37.                 }
  38.                 pWord = pWord + nCount;
  39.                 break;
  40.             }
  41.         }
  42.     }
  43. }

如果允许进行预处理，我们可以在一个预先计算好的结构中执行二分查找，该结构中包含按标识排序的(标识，单词)对。
2. 给定包含4300 000 000 个32位整数的顺序文件，如何找出一个出现至少两次的整数？
 方法一：
二分搜索通过递归搜索包含半数以上整数的子区间来查找至少出现两次的单词。因为4300000000  > 2^32，所以必定存在重复的整数，搜索范围从[0, 2^32）开始，中间值mid为2^31，若区间[0, 2^31)内的整数个数大于2^31个，则调整搜索区间为[0, 2^31)，反之则调整搜索区间为[2^31， 2^32)，然后再对整个文件再遍历一遍，直到得到最后的结果。这样一共会有log2(n)次的搜索，每次遍历n个整数（每次都是完全遍历），总体的复杂度为o(nlog2(n))。
 

  1. #include <iostream>
  2. using namespace std;
  4. int pow2(int n)   //求2的n次幂
  5. {
  6.     int i;
  7.     int r = 1;
  8.     for (i = 0; i < n; i++)
  9.     {
  10.         r *=2;
  11.     }
  12.     return r;
  13. }
  16. int _tmain(int argc, _TCHAR* argv[])
  17. {
  18.     int arr[] = {4,2,5,1,6,3,8,0,7,6,11,12,14,9,15,10,13};
  19.     int len = sizeof(arr) / sizeof(int);
  21.     int nCount = 0;
  22.     int bit = 4;
  23.     int low = 0;
  24.     int high = pow2(bit);
  25.     int mid = (low +high) / 2;
  26.     int i;
  28.     while (low <= high )
  29.     {
  30.         mid = (low + high) / 2;  //取中间值
  31.         nCount = 0;
  33.         for (i = 0; i < len; i++)    //计数[low, mid）范围内整数的个数
  34.         {
  35.             if (arr[i] < mid && arr[i] >= low)
  36.             {
  37.                 ++nCount;
  38.             }
  39.         }  //end for
  41.         if (nCount == 0)     //若nCount为0，则mid即为重复的整数
  42.         {
  43.             cout << mid<<endl;
  44.             break;
  45.         }
  46.         else
  47.         {
  48.             if (nCount > (mid – low))  //若大于mid与low的差值,
  49.             {                          //表明重复的整数落在区间[low, mid）
  50.                 high = mid;        //缩小区间
  51.             }
  52.             else
  53.             {
  54.                 low = mid;
  55.             }  //end if
  56.         } //end if （） else（）
  57.     }  //end while
  58. }

 
   方法二：
 

  1. #include <iostream>
  2. #include <algorithm>
  3. using namespace std;
  5. int _tmain(int argc, _TCHAR* argv[])
  6. {
  7.     int arr[] = {4,2,5,1,7,3,8,0,7,6,11,12,14,9,15,10,13};
  8.     int len = sizeof(arr) / sizeof(int);
  10.     sort(arr, arr + len);   //先进行排序
  11.     int i;
  12.     int increase = arr[0];
  13.     for (i = 0; i < len; i++)
  14.     {
  15.         if (arr[i] > (i + increase))
  16.         {
  17.             increase += (arr[i] – i – increase);
  18.             continue;
  19.         }
  21.         if (arr[i] < (i + increase))
  22.         {
  23.             cout << arr[i] << endl;
  24.             break;
  25.         }
  26.     }
  27. }

3. 前面涉及了两个需要精巧代码来实现的向量旋转算法，将其分别作为独立的程序实现。在每个程序中，i和n的最大公约数如何实现？
采用辗转相除法求两个整数的最大公约数。
 

  1. int gcd(int a, int b)
  2. {
  3.     int temp;
  4.     if (a < b)  //使a始终为最大数
  5.     {
  6.         temp = a;
  7.         a = b;
  8.         b = temp;
  9.     }
  11.     while (b != 0)
  12.     {
  13.         temp = a % b;
  14.         a = b;
  15.         b = temp;
  16.     }
  17.     return a;
  18. }

 
 
方法一：海豚算法
 

  1. void Shifting(char * pArry, int rotdistance, int len)
  2. {
  3.     int i, j;
  4.     char temp;
  5.     int igcd = gcd(rotdistance, len);
  6.     for (i = 0; i < igcd; i++)
  7.     {
  8.         temp = pArry[i];
  9.         j = i;
  10.         for (; 😉
  11.         {
  12.             int k = j + rotdistance;
  13.             k %= len;
  14.             if ( k == i)
  15.             {
  16.                 break;
  17.             }
  18.             pArry[j] = pArry[k];
  19.             j = k;
  20.         }
  21.         pArry[j] = temp;
  22.     }
  23. }

方法二：块交换算法
 

  1. #include <iostream>
  2. using namespace std;
  4. //交换pArry[a…a+m-1]和pArry[b…b+m-1]
  5. void myswap(char *pArry, int a, int b, int m)
  6. {
  7.     char temp;
  8.     for (int i = 0; i < m; i++)
  9.     {
  10.         temp = pArry[a + i];
  11.         pArry[a + i] = pArry[b + i];
  12.         pArry[b + i] = temp;
  13.     }
  15. }
  17. void Shifting(char * pArry, int rotdistance, int len)
  18. {
  19.     if (rotdistance == 0 || rotdistance == len)
  20.     {
  21.         return;
  22.     }
  24.     int i, j, p;
  25.     i = p = rotdistance;
  26.     j = len – p;
  28.     while (i != j)
  29.     {
  30.         if (i > j)
  31.         {
  32.             myswap(pArry, p – i, p, j);
  33.             i -= j;
  34.         }
  35.         else
  36.         {
  37.             myswap(pArry, p – i, p + j – i, i);
  38.             j -= i;
  39.         }
  40.     }
  41.     myswap(pArry, p – i, p, i);
  42. }
  44. int _tmain(int argc, _TCHAR* argv[])
  45. {
  46.     char arry[] = “abcdefghijklmn”;
  47.     int len = strlen(arry);
  48.     Shifting(arry, 10, len);
  49.     return 0;
  50. }

方法三：求逆算法
根据矩阵的转置理论，对于矩阵AB，要得到BA，则分别求A和B的转置A’, B’，然后对(A’B’)转置，即(A’B’)’ = BA。同理，可以得到另一种一维向量向左旋转的算法。将要被旋转的向量x看做两部分ab，这里a代表x中的前rotdistance个元素。首先对a部分进行反转，再对b部分进行反转，最后对整个向量x进行反转即可。
对于字符串“abcdefgh”, rotdistance = 3, len = 8:
reverse(1, rotdistance);          //cbadefgh
reverse(rotdistance+1, len);  //cbahgfed
reverse(1, len);                       //defghabc
 

  1. #include <iostream>
  2. using namespace std;
  4. //对字符串中第i个字符到第j个字符进行反转，i、j>=1
  5. void MyReverse(char * pArry, int i, int j)
  6. {
  7.     int front = i;
  8.     int tail = j;
  9.     char temp;
  10.     while (front != tail && front < tail)
  11.     {
  12.         temp = pArry[front – 1];
  13.         pArry[front – 1] = pArry[tail – 1];
  14.         pArry[tail – 1] = temp;
  15.         ++front;
  16.         –tail;
  17.     }
  18. }
  20. //将字符串左旋转rotdistance个字符
  21. void Shifting(char * pArry, int rotdistance, int len)
  22. {
  23.     if (rotdistance == 0 || rotdistance == len)
  24.     {
  25.         return;
  26.     }
  27.     MyReverse(pArry, 1, rotdistance);
  28.     MyReverse(pArry, rotdistance + 1, len);
  29.     MyReverse(pArry, 1, len);
  30. }
  32. int _tmain(int argc, _TCHAR* argv[])
  33. {
  34.     char arry[] = “abcdefgh”;
  35.     int len = strlen(arry);
  36.     Shifting(arry, 5, len);
  37.     cout << arry << endl;
  38.     return 0;
  39. }

 
5. 向量旋转函数将向量ab变为ba。如何将向量abc变成cba？(这个交换非相邻内存块的问题进行了建模)
可以将bc看做一个整体，然后运用向量旋转算法，得到bca。然后对bc运用向量旋转算法，得到cb。最后变换后的向量为即cba.
 

  1. //交换pArry[a…a+m-1]和pArry[b…b+m-1]
  2. void myswap(char *pArry, int a, int b, int m)
  3. {
  4.     char temp;
  5.     for (int i = 0; i < m; i++)
  6.     {
  7.         temp = pArry[a + i];
  8.         pArry[a + i] = pArry[b + i];
  9.         pArry[b + i] = temp;
  10.     }
  12. }

 
 

  1. //对向量pArry中起始于ibegainPos位置的irotdistance-ibegainPos个元素
  2. //与起始于ibegainPos+irotdistance位置到位置iendPos之前的元素进行交换
  3. void SuccessiveSwap(char * pArry, int ibegainPos, int irotdistance, int iendPos)
  4. {
  5.     int i, j;
  6.     i = irotdistance – ibegainPos;
  7.     j = iendPos – irotdistance;
  9.     while (i != j)
  10.     {
  11.         if (i > j)
  12.         {
  13.             myswap(pArry, irotdistance – i, irotdistance, j);
  14.             i -= j;
  15.         }
  16.         else
  17.         {
  18.             myswap(pArry, irotdistance – i, irotdistance + j – i, i);
  19.             j -= i;
  20.         }
  21.     }
  22.     myswap(pArry, irotdistance – i, irotdistance, i);
  23. }

6. 如何实现一个以名字的按键编码为参数，并返回所有可能的匹配名字的函数
用按键编码标识每一个名字，并根据标识排序，然后顺序读取排序后的文件并输出具有不同名字的相同标识。为了检索出给定按钮编码的名字，可以使用一种包含编码标识和其他数据的结构。然后对该结构排序，使用二分搜索查询按键编码。
7. 转置一个存储在磁带上的4000×4000的矩阵(每条记录的格式相同，为数十个字节)。如何将运行的时间减少到半个小时？
给每条记录插入列号和行号，然后调用系统的磁带排序程序先按列排序再按行排序，最后使用另一个程序删除列号和行号。
8. 给定一个n元实数集合、一个实数t和一个整数k，如何快速确定是否存在一个k元子集，其元素之和不超过t？
对n元实数集合先进行排序，然后计算前k个元素的和既可以确定是否存在这样一个子集。若采用快速排序，时间复杂度为nlog10(n)。
9. 顺序搜素和二分搜索代表了搜索时间和预处理时间之间的折中。处理一个n元表格时，需要执行多少次二分搜索才能弥补对表进行排序所消耗的预处理时间？
对于顺序搜索，搜索k次的时间复杂度为O(kn);若采用二分搜索则需要先排序，则二分搜索的时间复杂度为O(nlog10(n)+log2(n))
变位词程序的实现
 

  1. //对从文件中读入的每个单词调用qsort库函数排序，输出到新的文件中
  2. void mysign(FILE * pFile1, FILE * pFile2)
  3. {
  4.     char word[20];
  5.     char sig[20];
  7.     pFile1 = fopen(“..file1.txt”, “r”);
  8.     if ( NULL == pFile1)
  9.     {
  10.         cout << “Open file1 error!” << endl;
  11.         return ;
  12.     }
  14.     pFile2 = fopen(“..file2.txt”, “w”);
  15.     if (NULL == pFile2)
  16.     {
  17.         cout << “Open file2 error!” << endl;
  18.         return ;
  19.     }
  20.     while (!feof(pFile1))
  21.     {
  22.         memset(word, ‘’, 20);
  23.         memset(sig, ‘’, 20);
  24.         fscanf(pFile1, “%s”, word);
  25.         strncpy(sig, word, strlen(word));
  26.         qsort(sig, strlen(sig), sizeof(char), charcomp);
  27.         fprintf(pFile2, “%s   %sn”, sig, word);
  28.     }
  29.     fclose(pFile1);
  30.     fclose(pFile2);
  31. }


 
 
使用sort程序将具有相同标识的单词归拢到一起，形成一个新的文件。最后调用squash()函数将具有相同变位词的单词在同一行输出。
 

  1. //将具有相同变位词的单词在同一行输出
  2. void squash()
  3. {
  4.     FILE * pFile3 = fopen(“..file3.txt”, “r”);
  5.     if ( NULL == pFile3)
  6.     {
  7.         cout << “Open file3 error!” << endl;
  8.         return ;
  9.     }
  11.     FILE * pFile4 = fopen(“..file4.txt”, “w”);
  12.     if (NULL == pFile4)
  13.     {
  14.         cout << “Open file4 error!” << endl;
  15.     }
  17.     char word[20];
  18.     char sig[20];
  19.     char oldsig[20];
  20.     int linenum = 0;
  21.     memset(oldsig, ‘’, 20);
  22.     while (!feof(pFile3))
  23.     {
  24.         memset(word, ‘’, 20);
  25.         memset(sig, ‘’, 20);
  26.         fscanf(pFile3, “%s %s”, sig, word);
  28.         if (strncmp(sig, oldsig, strlen(sig)) != 0 )
  29.         {
  30.             fprintf(pFile4, “n”);
  31.         }
  32.         strncpy(oldsig, sig, strlen(sig));
  33.         fprintf(pFile4, “%s “, word);
  34.     }
  35.     fclose(pFile3);
  36.     fclose(pFile4);
  37. }

Categories
不学无术 木有技术

1020. Tree Traversals (25)

Suppose that all the keys in a binary tree are distinct positive integers. Given the postorder and inorder traversal sequences, you are supposed to output the level order traversal sequence of the corresponding binary tree.
Input Specification:
Each input file contains one test case. For each case, the first line gives a positive integer N (<=30), the total number of nodes in the binary tree. The second line gives the postorder sequence and the third line gives the inorder sequence. All the numbers in a line are separated by a space.
Output Specification:
For each test case, print in one line the level order traversal sequence of the corresponding binary tree. All the numbers in a line must be separated by exactly one space, and there must be no extra space at the end of the line.
Sample Input:

7
2 3 1 5 7 6 4
1 2 3 4 5 6 7

Sample Output:

4 1 6 3 5 7 2

============================================================
传说中正确率比较高的一道题，有0.5哈哈
做起来却发现数据结构概念忘光光，后序遍历什么的一概忘掉了，百度百科了一下终于懂得了..
题目也没什么技巧，给定两种顺序，肯定能排出二叉树的
要求输出层次结构就更好办了…
因为题目简单所以多记下一点，怕自己万一碰到忘掉了。
============================================================
原理：
后序遍历的顺序是L-R-D，后面假定这个输入序列为A序列
中序遍历是L-D-R顺序，假定为B序列
序列遍历时其实是递归的感觉。
也就是说，后序遍历顺序的最后一个节点，肯定是D节点无误（一棵树不会没有根，除非是空树）
所以给定A、B序列，把A序列的最后一个节点放到B序列中，那么B序列就能被分割成左中右三个部分，
中间那个节点，中间节点的左子树、右子树。
于是也成为了个递归的过程，每次分割完成后，把左右字数再找他们对应的D节点（从序列A中看），就能到世界的尽头了。
============================================================
伪代码：

工作队列：W
输入序列：A, B
将B整个队列压入W
while(工作队列非空)
{
    取出工作队列的队首元素（也是一个队列）frontList
    弹出队首元素（c++里面取top()或者front()和pop()是两个过程）
    找出frontList中位于A列最后次序的元素m
    打印m
    将frontList中排在m元素左侧的那些元素组成新列表，压入W队列
    将frontList中排在m元素右侧的那些元素组成新列表，压入W队列
}

==============================================================
代码（高手勿喷，效率较低但是在PAT中耗时0ms,内存占用750k+-）：

#include 
#include 
using namespace std;
int N;
int* A; //后序遍历顺序
int* B; //中序遍历顺序
struct QueueElem
{
	//压到工作队列中的元素（其实也是个队列）
	int capacity;
	int curSize;
	int* elements;
	QueueElem(int _capacity)
	{
		capacity = _capacity;
		curSize = 0;
		elements = new int[capacity];
	}
	void addElem(int e)
	{
		if(curSize >= capacity )
		{
			cerr << "Fail to insert. Size exceeded!" << endl;
			return;
		}
		elements[curSize++] = e;
	}
};
queue W; //工作队列
int findLastOnePos(QueueElem e)
{
	//寻找QueueElem元素中处在A列次序最后的那个元素
	//返回值为该元素在【e列表】中的位置！
	//2层循环效率较低..
	int lastIndexA = -1;
	int lastIndexE = -1;
	for(int i=0; i lastIndexA)
			{
				lastIndexA = posA;
				lastIndexE = i;
				break;
			}
		}
	}
	return lastIndexE;
}
int main()
{
	cin >> N;
	A = new int[N];
	B = new int[N];
	QueueElem orig(N);
	for(int i=0; i>A[i];
	for(int i=0; i>B[i];
		orig.addElem(B[i]);
	}
	///////////
	W.push(orig);
	int count = N;
	while (count--)
	{
		QueueElem qe = W.front();
		W.pop();
		int posM = findLastOnePos(qe);
		cout << qe.elements[posM];
		if( count > 0)
			cout << " ";
		if(posM > 0)
		{
			//有左侧元素
			QueueElem L(posM);
			//左侧元素组成列压栈，务必保持原有顺序！
			for(int i=0; i 1)
		{
			//有右侧元素
			QueueElem R(qe.curSize - posM -1);
			//右侧元素组成列压栈，务必保持原有顺序！
			for(int i=posM +1; i
Categories
不学无术 木有技术

Python入门讲义

Python入门

By nincompoop

图文PDF下载：
Python讲义

参考教程：
http://www.cnblogs.com/known/archive/2010/07/31/1789249.html
 

官方介绍：Python是一种简单易学，功能强大的编程语言，它有高效率的高层数据结构，简单而有效地实现面向对象编程。Python简洁的语法和对动态输入的支持，再加上解释性语言的本质，使得它在大多数平台上的许多领域都是一个理想的脚本语言，特别适用于快速的应用程序开发。
创造者：Guido van Rossum（吉多·范罗苏姆【荷兰】）
它的特色：简单、易学、免费、开源、高层语言、可移植性、解释性、面向对象、可扩展性、可嵌入性、丰富的库。
官网：http://python.org/
Python支持命令式程序设计、面向对象程序设计、函数式编程、面向切面编程、泛型编程多种编程范式。与Scheme、Ruby、Perl、Tcl等动态语言一样，Python具备垃圾回收功能，能够自动管理存储器使用。它经常被当作脚本语言用于处理系统管理任务和网络程序编写，然而它也非常适合完成各种高级任务。Python虚拟机本身几乎可以在所有的作业系统中运行。

版本：3.x与2.x （Python 3.0于2008年12月3日发布，此版不完全兼容之前的Python源代码。不过，很多新特性后来也被移植到旧的Python 2.6/2.7版本。）
 

Hello World 程序

下面是一个在标准输设备上输出Hello World的简单程序，这种程序通常作为开始学习编程语言时的第一个程序：

  • 适用于Python 3.0以上版本以及Python 2.6、Python 2.7
  • 适用于Python 2.6以下版本以及Python 2.6、Python 2.7
print("Hello, world!")
print "Hello, world!"

将这行程序码保存为myhello.py。然后在Linux终端机下输入python myhello.py，或者在Windows命令编辑字符下输入myhello.py运行。Python也可以单步直译运行。运行Python解释器进入交互式命令行的环境，你可以在提示符号>>>旁输入print(“Hello, world!”)，按Enter键输出结果：

  • 适用于Python 3.0以上版本以及Python 2.6、Python 2.7
  • 适用于Python 2.6以下版本以及Python 2.6、Python 2.7
>>> print("Hello, world!")
Hello, world!
>>> print "Hello, world!"
Hello, world!
注意，低于3.0版本的Python，”Hello, world!”周围不需要括号。Python 3.x与Python 2.x的print语法是不一样的。

Python语法

Python的设计目标之一是让代码具备高度的可阅读性。它设计时尽量使用其它语言经常使用的标点符号和英文单字，让代码看起来整洁美观。它不像其他的静态语言如C、Pascal那样需要重复书写声明语句，也不像它们的语法那样经常有特殊情况和惊喜。

缩进（告别{}！）

Python开发者有意让违反了缩进规则的程序不能通过编译，以此来强制程序员养成良好的编程习惯。并且Python语言利用缩进表示语句块的开始和退出（Off-side规则），而非使用花括号或者某种关键字。增加缩进表示语句块的开始，而减少缩进则表示语句块的退出。缩进成为了语法的一部分。例如if语句：
 
根据PEP的规定，必须使用4个空格来表示每级缩进。使用Tab字符和其它数目的空格虽然都可以编译通过，但不符合编码规范。支持Tab字符和其它数目的空格仅仅是为兼容很旧的的Python程序和某些有问题的编辑程序。

语句和控制流

  • if语句，当条件成立时运行语句块。经常与else, elif(相当于else if) 配合使用。
  • for语句，遍列列表、字符串、字典、集合等迭代器，依次处理迭代器中的每个元素。
  • while语句，当条件为真时，循环运行语句块。
  • try语句。与except,finally配合使用处理在程序运行中出现的异常情况。
  • class语句。用于定义类型。
  • def语句。用于定义函数和类型的方法。
  • pass语句。表示此行为空，不运行任何操作。
  • assert语句。用于程序调适阶段时测试运行条件是否满足。
  • with语句。Python2.6以后定义的语法，在一个场景中运行语句块。比如，运行语句块前加密，然后在语句块运行退出后解密。
  • yield语句。在迭代器函数内使用，用于返回一个元素。自从Python 2.5版本以后。这个语句变成一个运算符。
  • raise语句。制造一个错误。
  • import语句。导入一个模块或包。
  • from import语句。从包导入模块或从模块导入某个对象。
  • import as语句。将导入的对象赋值给一个变量。
  • in语句。判断一个对象是否在一个字符串/列表/元组里。

表达式

Python的表达式写法与C/C++类似。只是在某些写法有所差别。

  • 主要的算术运算符与C/C++类似。+, -, *, /, //, **, ~, %分别表示加法或者取正、减法或者取负、乘法、除法、整除、乘方、取补、取模。>>, <<表示右移和左移。&, |, ^表示二进制的AND, OR, XOR运算。>, <, ==, !=, <=, >=用于比较两个表达式的值，分别表示大于、小于、等于、不等于、小于等于、大于等于。在这些运算符里面，~, |, ^, &, <<, >>必须应用于整数。
  • Python使用and, or, not表示逻辑运算。
  • is, is not用于比较两个变量是否是同一个对象。in, not in用于判断一个对象是否属于另外一个对象。
  • Python支持“列表推导式”（list comprehension），比如计算0-9的平方和:

 

  • Python使用lambda表示匿名函数。匿名函数体只能是表达式。比如：

  • Python使用y if cond else x表示条件表达式。意思是当cond为真时，表达式的值为y，否则表达式的值为x。相当于C++和Java里的cond?y:x。

  • Python区分列表(list)和元组(tuple)两种类型。list的写法是[1,2,3]，而tuple的写法是(1,2,3)。可以改变list中的元素，而不能改变tuple。在某些情况下，tuple的括号可以省略。tuple对于赋值语句有特殊的处理。因此，可以同时赋值给多个变量，比如：

  • Python使用‘(单引号)和“(双引号)来表示字符串。与Perl、Unix Shell语言或者Ruby、Groovy等语言不一样，两种符号作用相同。一般地，如果字符串中出现了双引号，就使用单引号来表示字符串;反之则使用双引号。如果都没有出现，就依个人喜好选择。出现在字符串中的(反斜杠)被解释为特殊字符，比如n表示换行符。表达式前加r指示Python不解释字符串中出现的。这种写法通常用于编写正则表达式或者Windows文件路径。
  • Python支持列表切割(list slices)，可以取得完整列表的一部分。支持切割操作的类型有str, bytes, list, tuple等。它的语法是…[left:right]或者…[left:right:stride]。假定nums变量的值是[1, 3, 5, 7, 8, 13, 20]，那么下面几个语句为真：
    • nums[2:5] == [5, 7, 8] 从下标为2的元素切割到下标为5的元素，但不包含下标为5的元素。
    • nums[1:] == [3, 5, 7, 8, 13, 20] 切割到最后一个元素。
    • nums[:-3] == [1, 3, 5, 7] 从最开始的元素一直切割到倒数第3个元素。
    • nums[:] == [1, 3, 5, 7, 8, 13, 20] 返回所有元素。改变新的列表不会影响到nums。
    • nums[1:5:2] == [3, 7] 从下标为1的元素切割到下标为5的元素但不包含下标为5的元素，且步长为2

函数

Python的函数支持递归、默认参数值、可变参数，但不支持函数重载。为了增强代码的可读性，可以在函数后书写“文档字符串”(Documentation Strings，或者简称docstrings)，用于解释函数的作用、参数的类型与意义、返回值类型与取值范围等。可以使用内置函数help()打印出函数的使用帮助。比如：

对象的方法

对象的方法是指绑定到对象的函数。调用对象方法的语法是instance.method(arguments)。它等价于调用Class.method(instance, arguments)。当定义对象方法时，必须显式地定义第一个参数，一般该参数名都使用self，用于访问对象的内部数据。这里的self相当于C++, Java里面的this变量，但是我们还可以使用任何其它合法的参数名，比如this 和 mine等，self与C++,Java里面的this不完全一样，它可以被看作是一个习惯性的用法，我们传入任何其它的合法名称都行，比如：

Python认识一些以“__”开始并以“__”结束的特殊方法名，它们用于实现运算符重载和实现多种特殊功能。

类型

Python采用动态类型系统。在编译的时候，Python不会检查对象是否拥有被调用的方法或者属性，而是直至运行时，才做出检查。所以操作对象时可能会抛出异常。不过，虽然Python采用动态类型系统，它同时也是强类型的。Python禁止没有明确定义的操作，比如数字加字符串。
与其它面向对象语言一样，Python允许程序员定义类型。构造一个对象只需要像函数一样调用类型即可，比如，对于前面定义的Fish类型，使用Fish()。类型本身也是特殊类型type的对象(type类型本身也是type对象)，这种特殊的设计允许对类型进行反射编程。
Python内置丰富的数据类型。与Java、C++相比，这些数据类型有效地减少代码的长度。下面这个列表简要地描述了Python内置数据类型(适用于Python 3.x)：

类型

描述

例子

str

 一个由字符组成的不可更改的有串行。在Python 3.x里，字符串由Unicode字符组成。 'Wikipedia'
"Wikipedia"
"""Spanning
multiple
lines"""
bytes 一个由字节组成的不可更改的有串行。 b'Some ASCII'
b"Some ASCII"
list 可以包含多种类型的可改变的有串行 [4.0, 'string', True]
tuple 可以包含多种类型的不可改变的有串行 (4.0, 'string', True)
set,frozenset 与数学中集合的概念类似。无序的、每个元素唯一。 {4.0, 'string', True}
frozenset([4.0, 'string', True])
dict 一个可改变的由键值对组成的无串行。 {'key1': 1.0, 3: False}
int 精度不限的整数 42
float 浮点数。精度与系统相关。 3.1415927
complex 复数 3+2.7j
bool 逻辑值。只有两个值：真、假 True
False
除了各种数据类型，Python语言还用类型来表示函数、模块、类型本身、对象的方法、编译后的Python代码、运行时信息等等。因此，Python具备很强的动态性。

开发环境

适用于Python的集成开发环境（IDE）软件，除了标准二进制发布包所附的IDLE之外，还有许多其他选择。其中有些软件设计有语法着色、语法检查、运行调试、自动补全、智能感知等便利功能。由于Python的跨平台出身，这些软件往往也具备各种操作系统的版本或一定的移植性。
而很多并非集成开发环境软件的文本编辑器，也对Python有不同程度的支持，并且加上专门为Python设计的编辑器插件也会有很高的可用性。
专门为Python设计的IDE软件：

  • Eric：基于PyQt的自由软件，功能强大。支持自动补全、智能感知、自动语法检查、工程管理、svn/cvs集成、自动单元测试等功能。调试功能与Visual Studio和Eclipse类似。目前同时有两个版本。Eric4支持Python2.x，Eric5支持Python3.x。使用前需要先安装相应的PyQt版本。
  • IDLE：Python“标准”IDE。一般随Python而安装，支持较少的编辑功能。调试功能也比较弱。
  • Komodo和Komodo Edit：后者是前者的免费精简版。也可以用于PHP，Ruby，Javascript，Perl，Web和云开发。
  • PyCharm：由JetBrains打造，该公司的Java IDE软件IntelliJ拥有海量的用户；PyCharm具备一般IDE的功能，比如， 调试、语法高亮、Project管理、代码跳转、智能提示、自动完成、单元测试、版本控制等等，同时另外，PyCharm还提供了一些很好的功能用于Django开发，同时支持Google App Engine，更酷的是，PyCharm支持IronPython。PyCharm是商业软件，目前已经到2.5版本。
  • PythonWin：包含在pywin32内的编辑器，仅适用于Windows。
  • SPE（Stani’s Python Editor）：功能较多的免费软件，依赖wxPython。
  • Ulipad：功能较全的免费软件，依赖wxPython。
  • WingIDE：可能是功能最全的IDE，但不是免费软件。
  • PyScripter：功能较全的开源IDE，使用Delphi开发。

通用IDE / 文本编辑器：

 

官网（英文）：http://www.djangoproject.com/

自学材料（中文）：http://djangobook.py3k.cn/2.0/

Django是一个开放源代码的Web应用框架，由Python写成。采用了MVC的软件设计模式，即模型M，视图V和控制器C。它最初是被开发来用于管理劳伦斯出版集团旗下的一些以新闻内容为主的网站的。并于2005年7月在BSD许可证下发布。这套框架是以比利时的吉普赛爵士吉他手Django Reinhardt来命名的。
Django的主要目标是使得开发复杂的、数据库驱动的网站变得简单。Django注重组件的重用性和“可插拔性”，敏捷开发和DRY法则（Don’t Repeat Yourself）。在Django中Python被普遍使用，甚至包括配置文件和数据模型。
Django 可以运行在启用了 mod python 的 Apache 2 上，或是任何WSGI兼容的Web服务器。 Django也有启动FastCGI服务的能力，因此能够应用于任何支持FastCGI的机器上。
下列数据库引擎被Django官方支持：

Microsoft SQL Server 的适配器正在开发中，处于试验阶段。（注：SQL Server的支持在1.0版本中已经被完全去除）
Django1.0已经可以利用Jython运行在任何J2EE服务器。

Categories
不学无术 木有技术 爪机爪机

[转]android 人脸识别

source:http://blog.sina.com.cn/s/blog_677fb16e010148be.html

import android.app.Activity;
import android.widget.TextView;
import android.os.Bundle;
import android.media.FaceDetector;    // 人脸识别接口
import android.widget.ImageView;
import android.graphics.BitmapFactory;
import android.graphics.Bitmap;
import android.graphics.PointF;
import android.graphics.Matrix;
import android.util.Log;
import android.graphics.Canvas;
import android.graphics.Paint;
public class MyDetectActivity extends Activity {
       private ImageView mImageView;    // 图片显示控件
       private Bitmap mBitmap;
       private float mScale = 1F;
       @Override
       public void onCreate(Bundle savedInstanceState) {
                super.onCreate(savedInstanceState);
                setContentView(R.layout.main);
                mImageView = (ImageView) this.findViewById(R.id.image);
                detect();      // 识别函数
       }
       private void handleFace(FaceDetector.Face f) {        // 在图片上对每张脸进行处理
                PointF midPoint = new PointF();
                int r = ((int) (f.eyesDistance() * mScale * 1.5));         // 取眼睛间距离
                f.getMidPoint(midPoint);       // 取脸的中点
                midPoint.x *= mScale;
                midPoint.y *= mScale;
                Canvas c = new Canvas(mBitmap);
                Paint p = new Paint();
                p.setAntiAlias(true);
                p.setAlpha(0x80);
                c.drawCircle(midPoint.x, midPoint.y, r, p)        // 用半透明标出人脸区域;
                mImageView.setImageBitmap(mBitmap);          // 显示图片
       }
       private void detect() {
                Matrix matrix = new Matrix();
                FaceDetector.Face[] mFaces = new FaceDetector.Face[3];         // 定义最多识别三张脸
                int mNumFaces = 0;
                mBitmap = BitmapFactory.decodeResource(getResources(), R.drawable.baby);     // 取原始图
                if (mBitmap == null) {
                         return;
                }
                if (mBitmap.getWidth() > 256) {
                         mScale = 256.0F / mBitmap.getWidth();
                }
                matrix.setScale(mScale, mScale);
                Bitmap faceBitmap = Bitmap.createBitmap(mBitmap, 0, 0, mBitmap
                                   .getWidth(), mBitmap.getHeight(), matrix, true);        // 生成缩放后的新图
                mScale = 1.0F / mScale;
                if (faceBitmap != null) {
                         FaceDetector detector = new FaceDetector(faceBitmap.getWidth(),
                                            faceBitmap.getHeight(), mFaces.length); // 创建识别器
                         mNumFaces = detector.findFaces(faceBitmap, mFaces);    // 识别
                         if (mNumFaces > 0) {
                                   for (int i = 0; i < mNumFaces; i++) {
                                            handleFace(mFaces[i]);        // 调用函数对人脸画面进行处理
                                   }
                         }
                }
       }
}