用全局变量记录调用深度,直观展现递归过程

一个小小的 JavaScript 框架,用全局变量记录调用的深度,用 console.log() 直观展现递归过程,以利调试或演示。

Abstract: 一个小小的 JavaScript 框架,用全局变量记录调用的深度,用 console.log() 直观展现递归调用的过程,以利调试或演示。


最近写了一个 JavaScript 的扫雷游戏。当玩家点开一个空白格子,一大片空白格子都会打开。为了实现这一特性,我采用了递归算法。

因为本人水平有限,难以一次写对,又因为本人水平有限,只会用 console.log() 进行调试。。所以写了点代码,用 console.log() 直观地展现出递调用的过程。感觉这个小小的框架完全可以复用,于是就发在这里了。。

//全局变量
var depth=0;
function openBox(x,y){
	//递归终止条件
	//if(...) return;
	
	depth++;
	var str='';
	for (var i = 0; i < depth; i++)str += ' ';
	console.log(str + '<' + x + ',' + y);
	
	//主要代码
	//...
	//openBox(a,b)...
	//...
	
	console.log(str + '/' + x + ',' + y);
	depth--;
}

我们将在控制台得到以下直观优美的图形:

(完)

投针法生成正态分布随机数

用投针法,将“均匀分布随机数”转化为“正态分布随机数”,附 C 语言源代码。

恩,主流程序设计语言都提供生成(伪)随机数的函数,比如 C 的 rand():

The rand() function returns a pseudo-random integer in the range 0 to RAND_MAX inclusive (i.e., the mathematical range [0, RAND_MAX]).

江湖传言,该函数给出的随机数服从均匀分布。果真如此吗……?恩,试一下不就知道了嘛。来十万个。

好极了。不过区间 [0, RAND_MAX] 并不实用。我们用以下函数把它拓展为任意的 [min, max]:

double randUniform(double min, double max){
	return (rand()/(RAND_MAX + 1.0)*((max)-(min))+(min));
}

下面我们将利用这个函数生成服从正态分布的随机数。我们打算用投针法。

原理是,先画出所要正态分布的概率密度曲线,然后拿一个矩形框起来,然后在这个矩形内随机取点(投针)。舍弃那些落在曲线上方的点。剩下的点的 x 坐标是我们要的。

从原理可以看出,本方法可以拓展到任意已知概率密度函数的分布。缺陷是,只能在有限区间内生成随机数,且并不能保证在有限步骤内结束

效果是极好的。比如我们生成 100000 个,保存到文件中,用 Mathematica 画出来,与标准正态曲线放在一起比较:

以下是 C 语言的源代码。

#include 
#include 
#include 
#include 

#define PI 4.0*atan(1.0)
#define E exp(1.0)

//uniform distribution in range [min, max]
double randUniform(double min, double max){
	return (rand()/(RAND_MAX + 1.0)*((max)-(min))+(min));
}
//probability density function of normal distribution
double pdfNormal(double x, double mu, double sigma){
	return 1/(pow(E,pow(-mu+x,2)/(2.0*pow(sigma,2)))*sqrt(2*PI)*sigma);
}
//normal distribution (mu, sigma), in range [-k*sigma, k*sigma]
double randNormal(double mu, double sigma, double k){
	double x, y, ymax=pdfNormal(mu,mu,sigma), xmax=k*sigma;
	while(233){
		x = randUniform(-xmax, xmax);
		y = randUniform(0,ymax);
		if(y
	

PHP:UTF-8 BOM 会导致 HTTP 头的发送

如题,PHP Warning 奇遇记: Cannot modify header information – headers already sent

用 Notepad++ 写 PHP 代码不小心踩中一颗地雷。即使代码看起来是这样


运行起来仍然会产生

Warning: Cannot modify header information - headers already sent by (output started at E:\test.php:1) in E:\test.php on line 2

而不管是用 curl 命令还是浏览器,看到HTTP消息正文都是空的。(PHP/5.3.10, PHP/5.3.29, nginx/1.4.4, Apache/2.2.21, libcurl/7.40.0)


真是怪了。第 1 行真的输出了什么奇怪的东西?在 Notepad++ 显示不可见字符,一无所获。一拍脑袋,用 UltraEdit 十六进制视图观察了一下。前三个字节映入眼帘,

0xEF 0xBB 0xBF

和传说中的“锟斤拷”简直神似……豁然开朗!于是回到 Notepad++,将编码格式由 “UTF-8” 改为 “UTF-8 无 BOM” ,问题排除。

(完)

身份证号补全工具 Ver 2.0

本程序可补全污损的、不完整的身份证号,最多允许有 2 位空缺。

本项目时代久远……最新版本的可执行文件编译时间在2011年6月。

曾在百度空间发表。看起来可能有点用,于是就搬运过来了。

是客户端exe软件。名称:身份证号补全工具 Ver2.0  completeID_2.exe

程序功能概述:给出身份证号中的任意17位,即可确定未知的一位。给出16位可进行推算,列出可能的情况。已知数字须按顺序给出,并标明未知数字位置。

下载地址completeID_2.exe

原理概述:身份证号的最后一位是“验证码”,是由前17位根据公式算出来的,故可以利用公式,根据给出的前17位,算出最后一位验证码。在已知验证码和前面17位中的16位的情况下,也可逆用公式,反推未知数字。
有两个未知数字时,实际上构成二元不定方程,可以求出几种可能的情况。

执行标准:本程序算法执行 GB 11643-1999 和 ISO 7064: 1983, MOD 11-2 标准。

版权说明:本程序使用的有关公式和算法,从《中华人民共和国著作权法》第五条之规定,均属于公有领域,作者不主张版权。您可以自由地分发、传播本程序。

特别声明:1.公民身份号码中校验码的算法不属于有关国家秘密的内容;2.使用者不得利用本程序从事违法违规不正当活动,请不要利用本程序虚构身份证号码,由此造成的后果作者不承担责任。

用词说明:本文和本程序中使用的“身份证号”、“二代身份证号”均为俗称,应为公民身份号码

联系作者:博客首页http://blog.nullspace.cn;电子邮件地址lizy14@yeah.net

关于程序:VB6编制,单模块Sub Main搞定,未设计UI。

开源。completeID_2.bas

SAE屏蔽迅雷离线服务器

昨天本博客迎来了一个访问量高峰,我不得不两度上调配额。想来可能是因为被学术状态帝转了一篇文章;也因为做了点广告;检查日志还发现了谷歌爬虫光顾的踪迹,这无疑都是令人欣喜的。亲眼看了谷歌爬虫的 User-Agent:

Mozilla/5.0 (compatible; Googlebot/2.1; +http://www.google.com/bot.html)

这货刚一来,首先就请求我的 /robots.txt 。果然高风亮节。话说我还得到了谷歌爬虫的一些 IP :66.249.79.* 。用 MyIP.cn 查询得:美国 加利福尼亚州圣克拉拉县山景市谷歌公司。

顺便说一下,MyIP.cn 拥有我所见过的最 NB 没有之一的 IP 归属地数据库。拿紫荆宿舍网口的 IP 查居然可以精确到门牌号,让我十分震惊。当然上学期宿舍网口换成 DHCP 动态 IP 后就不准了,但是还是很 NB 有木有。

但是很快我就在日志中发现了不对劲的事情。有一个 URL 似乎被同一个 IP 反复请求。SAE 的日志中心还是可以,过滤了一下,发现果然不对劲。

221.204.204.140。这货非常勤劳,也非常守时嘛!从 17/Feb/2015 00:23:47 +0800 开始,像被上了发条一样,每 55 秒请求一次,永不停歇。

赶快查一下这是什么鬼东西。MyIP.cn 告诉我,这个 IP 属于“山西省太原市 迅雷离线服务器”。站长工具给出的则是“山西省太原市 迅雷网络联通节点”。

我想,很有可能是有一位可爱的读者,用迅雷下载我的了 GradeSDK.zip;也许他选择了离线下载;反正,迅雷的系统有 Bug。。。就开始无休止地向我请求这个文件。

调试好了再上线不好嘛!!迅雷你酱紫很桑我们这些小站长的心你造吗??

怎么办呢,把它屏蔽掉吧。因为这个文件被我偷懒放在代码空间里了,所以我想只能求助于 SAE 平台了。既然 “SAE 提供的是云计算服务,不同于一般的空间提供商”,那么,我想屏蔽一个 IP 的功能应该是有的吧?

找到 管理应用界面 > 安全与运维 > 应用防火墙 ,简直是救命稻草。文档里写着“应用防火墙针对访问行为提供如下三种控制机制:黑白名单机制;频率/流量限制机制;访问速度限制机制”,看起来十分强大嘛!好极了。不料,点开后就得到提示“您还未通过实名认证,无法配置应用防火墙”。而实名认证需要 3 个工作日。呜呼,3 个工作日后我的云豆要被迅雷这样消耗多少去了!

好在天无绝人之路,我又找到了 管理应用界面 > 开发与调优 > AppConfig > 基于主机的访问控制,“您可以限制或允许某个IP访问您的应用,或您应用的某个目录”,这货看起来只提供 IP 黑白名单,但是对付你个调皮的迅雷服务器是够了!果断加黑名单,

 - hostaccess: deny "221.204.204.140"

至此世界重归平静。(完)

 

Update: 加黑名单之后,该 IP 的所有请求都得到了 403 ……但是这货不懂知难而退啊……在日志中心可以看到,这货仍然锲而不舍。截止此刻仍在每 65 分钟请求一次。恩,频率倒是下降了不少。(2015-2-17 20:55:41)

送你一只托里拆利小号

介绍一个具有怪异性质的几何图形——托里拆利小号。

首先考虑函数 y = 1/x 的图象。我们取它在第一象限,且 x > 1 的部分。

下面我们将它绕 x 轴旋转一圈。可以想象,将会得到这样的图形:

旋转得到的图形——托里拆利小号

注意这只“小号”其实是无限长的,图中画出的只是一部分。下面我们来求一下它的体积。根据旋转体体积公式和关于广义积分的熟知的结论(你应该可以在任意一本微积分或数学分析教材中找到),

\(V = \int_1^{\infty} \pi y^2 \mathrm{d}x = \pi \int_1^{\infty} \frac{1}{x^2} \mathrm{d}x = \pi\)

恩,体积是有限的。下面我们来求一下它的表面积:

\(A = \int_1^{\infty} 2 \pi y \sqrt{ 1 + ( \frac{\mathrm{d}y}{\mathrm{d}x} )^2 } \mathrm{d}x = 2 \pi \int_1^{\infty} \frac{ \sqrt{ 1 + \frac{1}{x^4} } }{x} \mathrm{d}x > 2 \pi \int_1^{\infty} \frac{1}{x} \mathrm{d}x = {\infty}\)

这是因为最后那个无穷限积分的分母的次数不同……导致敛散性不同。1/x 恰恰是分界点。那么现在,事情变得有意思了:这只小号具有有限的体积,却具有无限的表面积。如果你还没有看出这一性质的古怪之处,我们换一种直观的语言来叙述:你可以用有限的油漆把它内部充满,但是却无法用油漆把它的内表面刷上一遍。

这个古怪的图形是由意大利数学家埃万杰利斯塔·托里拆利 (Evangelista Torricelli) (对,就是用水银柱测量大气压的那个托里拆利)发明的,世称“托里拆利小号”。当时还没有微积分,他是用祖暅原理证明上述结论的。

参考资料:维基百科“托里拆利小号”条目

(完)

如何科学地将木桶原理批判一番

一只木桶盛水的多少,并不取决于桶壁上最高的那块木块,而是取决于桶壁上高度与正弦曲线偏差最大的那块木块。

给偏科党送上鸡汤一碗。本文将科学地、定量地将木桶原理批判一番。首先,我们将证明以下两个几何体具有相同的体积,也具有相同的侧面积。

……圆柱的一半,横着切或者斜着切

 
 
 
 
 
 
 
 
 
 
 
 
 
 
……这还用证吗?(完)

循环赛最短赛程问题

设计一个单循坏赛程表,每位选手每天最多比赛 1 场,还要使比赛在尽可能短的时间内结束。这也许是程序设计课程的经典题目了。不同的是,本文希望探讨人数不是 2 的整数次幂的情形。

要求是,设计一个单循坏赛程表,每位选手每天最多比赛 1 场,还要使比赛在尽可能短的时间内结束。

一种易于写成递归算法的想法是这样。

【方案一】

  • 假如我们已经安排好了 n 个人的单循环赛程表,用时 d 天。
  • 那么,对于 2n 人,我们可以这样安排:
    • 将这 2n 人分成两组,每组 n 人。为便于叙述,记为 甲组 和 乙组。
    • 在前 d 天,让每组的 n 个人分别进行单循环(这将是递归调用);
    • 之后花 n 天,完成所有“一个选手来自甲组,一个选手来自乙组”的比赛。
      • 比如说,这 n 天中第 1 天,甲组1号 vs 乙组1号,甲组2号 vs 乙组2号,直到甲组n号 vs 乙组n号;
      • 第 2 天,把每个乙组选手的编号加1,安排甲组1号 vs 乙组2号,甲组2号 vs 乙组3号,直到甲组(n-1)号 vs 乙组n号,甲组n号 vs 乙组1号;
      • 这样下去第 n 天,安排 甲组1号 vs 乙组n号,甲组2号 vs 乙组1号,直到甲组(n-1)号 vs 乙组(n-2)号,甲组n号 vs 乙组(n-1)号。

可以验证,以上的方案安排比赛,可以做到不重不漏。当 n = 2 时显然有 d = 1,继而可以用数学归纳法证明,

当比赛人数 n 是 2 的幂次(比如 4, 8, 256, 2048, 65536)时,以上方法可以让比赛用时 (n-1) 天结束。

下面来证明该方案是用时最短的方案——根据单循环“每两个选手都比赛一次”的要求,n 人的单循环要比赛 n(n-1)/2 场,而根据“每位选手每天最多比赛 1 场”的要求, (n-1) 天最多只能进行 n(n-1)/2 场比赛。所以赛程不可能比 (n-1) 天更短了。

分治递归,该方案容易编程实现。附 C 语言的代码。

以上方案有个明显的缺陷——只能处理比赛人数 n 是 2 的幂次的情况。如果比赛人数是 33,如果还想用这个方案的话,我们将只能“虚拟”出第 34 到 64 号选手来,然后按 64 个选手来安排。赛程将是 63 天。当然其中有大量的比赛是实际不存在的。有虚拟选手参加的比赛直接从赛程表上抹掉就可以了,不必担心真选手或者裁判员被虚拟选手“放鸽子”自不必担心。我心疼的是,轮空太多了,赛程中的时间将被白白浪费掉。

下面我们希望解决的问题是,对于比赛人数是 33 人这种情况,我们是否可以设计出更短的赛程?

对于人数是奇数的情况,我们首先可以给出日程长度的下限:n,因为要比赛 n(n-1)/2 场,而每天最多只能进行 (n-1)/2 场比赛。对于人数是偶数的情况,同样方法给出的下限是 (n-1)。

下面是资料给出的,人数是偶数时,(n-1) 天搞定的排法:

【方案二】

来源:http://www.docin.com/p-430759465.html

容易验证该方案满足要求。而对于人数是奇数的情况,我们可以虚拟出 1 个选手,应用以上方案,就可以得到一个 n 天的赛程了。

至此我们构造性地证明了以下定理:

若选手数是偶数,单循环赛轮数的最小值是 (n-1) ;若是奇数,最小值是 n 。

(完)

像薛定谔一样查分……附查分脚本简易SDK

鼠标一点,成绩单一览无余,这太残酷了。如何优雅地文明地查到分数?本文实现了一个SDK,可在此基础上写出查分用的UserScript;作为该SDK的示例,给出“薛定谔的查分”脚本。

查分是一件令人痛苦的事情。鼠标一点,全部成绩毫无遮拦地就会展现在你眼前。这太残酷了。为了减轻这种痛苦,前辈们做过很多工作,开过很多脑洞。比如 这里这里,还有这里(均为人人网日志,可能需要登录)。

不管是“刮刮乐”,还是“玻璃心”,其思想都是每次只提供成绩信息的一部分,来使查分者得到更多的心理缓冲。这方面可以考虑的玩法还有很多,比如今天我要介绍的,——像薛定谔一样查分。

如果你安装了这个脚本(下载地址和安装方法见后),当你查成绩的时候,你的分数都会被隐藏起来,变成了“观测”按钮:

当你点击这个按钮,程序会要求你提供一个区间宽度:

然后你就会得到一个区间。宽度是你指定的值。而你的真实分数可能是这个区间内的任何一个数(含端点)。

就像薛定谔关于猫的那个经典的思想实验一样,由于量子随机性(误)和观测条件(误)的共同限制(误),“你无法确切地知道自己的分数”……

你可以随意指定区间宽度,可以观测任意多次。推荐的玩法是,先从很大试起,慢慢缩小区间宽度,直到减小到 0,你就得知了自己的确切成绩。

支持校内,支持校外sslvpn,支持中文成绩单,也支持英文的,支持老门户,支持排名查询页面,一网打尽。

如果你不去修改代码的话……是只适用于清华滴

脚本下载地址:http://200404.sinaapp.com/scripts/SchrodingerGrade.user.js

安装教程:(回头再详细写。。。。你可能需要先安装个插件,比如 Firefox 上的 GreaseMonkey 或者 Chrome 上的 TamperMonkey,然后把这个脚本挂载上去)


//以下内容写给开发者

下面我将要贴 JavaScript 源代码。事实上,它可以被作为一个 SDK 使用。这样是为了避免重复劳动,方便大家发挥创意,共同携手,使查分的过程更加美好~~~~

基于该 SDK 开发查分脚本非常简单,你只需要自己写一个 ReplaceHTML 函数,再修改一下前几行的 meta 信息,就可以拿出去分发了。ReplaceHTML 函数接受的参数是表示成绩的字符串,返回用来替换显示的 HTML。详见注释。后面有更多的示例。

// ==UserScript==
// @name          Schrodinger's Grade
// @author        Zhaoyang - http://200404.sinaapp.com/
// @namespace     200404_Schrodinger_Grade
// @description   薛定谔的查分
// @version       0.1
// @include       *://*.tsinghua.edu.cn*bks_yxkccj*
// @include       *://*.tsinghua.edu.cn*yjs_yxkccj*
// @include       *://*.tsinghua.edu.cn*bks_cjdcx*
// @include       *://*.tsinghua.edu.cn*yjs_cjdcx*
// @include       *://*.tsinghua.edu.cn*cj.cjCj*
// ==/UserScript==


/********************************

ReplaceHTML

gradeStr: string,  such as '80', '***', '合格'
gradeID : integer, a unique ID for each grade, starting from 0

return: a string contaning HTML, to be displayed in place of grade

**********************************/

function ReplaceHTML(gradeStr, gradeID){
	if(gradeStr=='***'||gradeStr=='') return '暂无成绩';
	var x=parseInt(gradeStr);
	var divID="GradeBox"+gradeID;
	var onclickscript;
	if(isNaN(x)){
		onclickscript="javascript:if(confirm('成绩不是数字。是否直接显示?')) \
		document.getElementById('"+divID+"').innerHTML='" + gradeStr + "'"
	}
	else{
		onclickscript="javascript:var range=prompt('请输入区间宽度'); \
		range = parseInt(range); \
		if(range>100)range=100; \
		rand=Math.floor(Math.random() * ( range + 1)); \
		x=" + x +"; \
		a= x-rand; \
		b= x+range-rand; \
		if(b>100){b=100;a=100-range;} \
		if(a<0){a=0;b=range;} \
		document.getElementById('"+divID+"').innerHTML=a+' - '+b;";
	}
	var html="
"; return html; } //查分脚本简易 SDK //您只需要自己实现 ReplaceHTML 函数即可 //By Zhaoyang, 2015.2, http://200404.sinaapp.com/ function main(){ var i,j; var tableGrade; { var tables = document.getElementsByTagName("table"); for (i=0; i

这个 SDK 给出了一系列以通配符表示的需要处理的地址(@include),负责了从页面上寻找成绩的工作——如前所示,它支持校内网直接访问的和 sslvpn 的,支持包括老门户、排名查询在内的所有地方的成绩栏,支持中文也支持英文。

最后再编几个,基于这个 SDK 的简单例子吧。

//这个例子什么都不做
function ReplaceHTML(gradeStr, gradeID){
	return gradeStr;
}
//这个例子显示随机数
function ReplaceHTML(gradeStr, gradeID){
	return Math.floor(Math.random()*(101));
}
//这个例子显示一个按钮,点击后弹出成绩
function ReplaceHTML(gradeStr, gradeID){
	var onclickscript="javascript:alert('" + gradeStr + "');"
	var html="";
	return html;
}
//这个例子改变字号,分越高,字越大。。
function ReplaceHTML(gradeStr, gradeID){
	var size=parseInt(gradeStr)/5;
	if(isNaN(size))size=12;
	var html="

" + gradeStr + "

"; return html; }

为了便于本地调试,我还给各位制作了一个简单的 HTML 页面,请将它下载到本地使用。——使用时在控制台定义你的 ReplaceHTML() 函数,然后调用 main() 即可。

所以说完整的 SDK 含有两个文件,一个 .user.js 和 一个 .html。下载链接:http://200404.sinaapp.com/scripts/GradeSDK.zip

(完)