Crane
Table_bottom

Search
Loading
Table_bottom

分类
Table_bottom

随机文章
Table_bottom

标签云
Table_bottom

最新评论
Table_bottom

链接
Table_bottom

功能
Table_bottom

VHDL编程之可逆计数器

数字逻辑学了一个学期,始终都是一堆的门元件和触发器接来接去,实在是搞得人有点晕乎,到了最后大规模集成电路的时候,终于不用(好像也不可能)那些方法了,话说coding the world不是没有道理的,这大规模的电路设计最后还是得软件来搞,可惜还没到CPLD/FPGA的地步,我们就搞了一个用VHDL做的4位(其实用VHDL 的话这个位数只是个数字而已)可逆计数器,觉得蛮有意思,代码丢在这里,万一以后想到查呢?

题目是这样的:

设计一个能清0,置数和进位输出的增1/减1的4位二进制计数器。

输入信号clr为清0端,低电平有效,信号ld为置数端,也是低电平有效,将A,B,C,D的输入值送到计数器中,并立即在Qa,Qb,Qc,Qd中输出。输入信号m为模式选择端,m=1时为加1计数,m=0时为减1计数。当cp端输入一个上升沿信号时进行一次计数,有进位/借位时qcc输出一个负脉冲。

代码如下

library ieee;
use ieee.std_logic_1164.all;
use ieee.std_logic_unsigned.all;
use ieee.std_logic_arith.all;
entity counte is
        port(cp,clr,ld,m:in std_logic;
             abcd:in std_logic_vector(3 downto 0);
               qcc:out std_logic;
                qcount:out std_logic_vector(3 downto 0));
end;
architecture count of counte is
begin
        process(cp,clr,ld)
                begin
                        if(clr='0')then
                                qcount<="0000";
                                if(m='0')then
                                        qcc<='0';
                                end if;
                        elsif(ld='0')then
                                if(abcd="0000" and m='0')then
                                        qcount<=abcd;
                                        qcc<='0';
                                elsif(abcd="1111" and m='1')then
                                        qcount<=abcd;
                                        qcc<='0';
                                else
                                        qcount<=abcd;
                                        qcc<='1';
                                end if;
                        elsif(cp'event and cp='1')then
                        if(qcount="1110" and m='1')then
                                qcount<="1111"
                                qcc<='0';
                        elsif(m='1')then
                                qcount<=qcount+1;
                                qcc<='1';
                        end if;
                        if(qcount="0001" and m='0')then
                                qcount<="0000";
                                qcc<='0';
                        elsif(m='0')then
                                qcount<=qcount-1;
                                qcc<='1';
                        end if;
                       
                        end if;
                end process;
end  count;

 

 

 

其中字母基本上和上面要求对应,就是上边的qcount对应Qa,Qb,Qc,Qd。

感觉这样的begin和end的配对,而且整个程序看起来和PASCAL还是有点像的。

比较程序的效率

今天老师给了个这样的题:

  1. 编写程序,测试两条循环语句的执行时间。分析为何执行时间不同。
  2.  
  3. int A[ROWS][COLS];
  4. for(row=0; row<ROWS;row++)
  5.     for(col=0;col<COLS;col++)
  6.        A[row][col]=0;
  7. for(col=0;col<COLS;col++)
  8.     for(row=0; row<ROWS; row++)
  9.        A[row][col]=0;

于是就需要在程序中计算某一段执行的时间,找了一下,发现C/C++中的计时函数是clock(),而与其相关的数据类型是clock_t。查得clock函数定义如下:

clock_t clock( void );

这个函数返回从“开启这个程序进程”到“程序中调用clock()函数”时之间的CPU时钟计时单元(clock tick)数。其中clock_t是用来保存时间的数据类型,在time.h文件中,我们可以找到对 它的定义:

#ifndef _CLOCK_T_DEFINED
typedef long clock_t;
#define _CLOCK_T_DEFINED
#endif

很明显,clock_t是一个长整形数。在time.h文件中,还定义了一个常量CLOCKS_PER_SEC,它用来表示一秒钟会有多少个时钟计时单元,其定义如下:

#define CLOCKS_PER_SEC ((clock_t)1000)

 

所以我们需要使用clock()算出程序执行期间的tick总数,再除以这个CLOCKS_PER_SEC,所以程序可以这样写:

 

  1. #include<stdio.h>
  2. #include<time.h>
  3. #include<stdlib.h>
  4. #define ROWS 10000
  5. #define COLS 10000
  6. int a[ROWS][COLS];
  7. main()
  8. {
  9.         clock_t start,finish;
  10.         double elapsed1,elapsed2;
  11.         int row,col;
  12.         start=clock();
  13.         for(row=0;row<ROWS;row++)
  14.         for(col=0;col<COLS;col++)
  15.         a[row][col]=0;
  16.         finish=clock();
  17.         elapsed1=(double)(finish-start)/CLOCKS_PER_SEC;
  18.         start=clock();
  19.         for(col=0;col<COLS;col++)
  20.         for(row=0;row<ROWS;row++)
  21.         a[row][col]=0;
  22.         finish=clock();
  23.         elapsed2=(double)(finish-start)/CLOCKS_PER_SEC;
  24.         printf("the first loop cost %f seconds.\n",elapsed1);
  25.         printf("the second loop cost %f seconds.\n",elapsed2);
  26.         system("pause");
  27.         return 0;
  28. }

输出:

the first loop cost 1.381000 seconds.
the second loop cost 6.880000 seconds.

这样哪个循环运行更快,一下子就看出来。

C/C++中的日期和时间

以前看过一个笑话,有人问一geek:Can you tell me the time now?被这样回答:Of course,it's 1229883309 seconds since 1970/1/1。

笑话归笑话,但是程序员往往能从中看出点有趣的东西出来,比如说这样的时间怎么得到,怎么用程序得到?如何将这样的时间还原成看得懂的时间?这样的计时方法有没有什么优点或者不足的地方?

其实这样的时间有个名字叫日历时间(Calendar time),要得到这样的时间很容易,C标准库就有函数可以做到,在time.h中定义了一个这样的函数:

time_t time(time_t * timer);

其中的time_t是这样定义的:

#ifndef _TIME_T_DEFINED
typedef long time_t;         /* 时间值 */
#define _TIME_T_DEFINED      /* 避免重复定义 time_t */
#endif

于是通过这样的函数调用 time(NULL) 就可以得到我们需要的东西,从上面的定义中可以看到,这个值是保存在一个长整型数中的,但是我们都知道长整数是有限制的,当这个数达到这个限制的时候会发生什么事呢?这可以算是Unix/Linux系统的千年虫问题了,现在一般都是32位系统,我们知道这个最大的数是2147483647,那么这会在什么时候发生呢,其实不用太担心,在2038年才会出现,准确的说是2038年1月19日03时14分07秒,不过在这么长的时间内,硬件的发展肯定可以补上这个漏洞,所以我们大可不必担心。

下来又有一个问题,如果我们得到了一个日历时间,怎么知道真实的时间呢?

同样的在time.h中有相应的函数:

char * ctime(const time_t *timer);

这个函数可以把日历时间格式化输出,像这样的样子

Tue Jan 19 11:14:07 2038

这就是上面说到的那个时间,有8小时的时差,是因为中国和UTC时间差了8个小时的原因。

其实在C标准中还有一个表示日期和时间的数据结构:

#ifndef _TM_DEFINED
struct tm {
        int tm_sec;     /* 秒 – 取值区间为[0,59] */
        int tm_min;     /* 分 - 取值区间为[0,59] */
        int tm_hour;    /* 时 - 取值区间为[0,23] */
        int tm_mday;    /* 一个月中的日期 - 取值区间为[1,31] */
        int tm_mon;     /* 月份(从一月开始,0代表一月) - 取值区间为[0,11] */
        int tm_year;    /* 年份,其值等于实际年份减去1900 */
        int tm_wday;    /* 星期 – 取值区间为[0,6],其中0代表星期天,1代表星期一,以此类推 */
        int tm_yday;    /* 从每年的1月1日开始的天数 – 取值区间为[0,365],其中0代表1月1日,1代表1月2日,以此类推 */
        int tm_isdst;   /* 夏令时标识符,实行夏令时的时候,tm_isdst为正。不实行夏令时的进候,tm_isdst为0;不了解情况时,tm_isdst()为负。*/
        };
#define _TM_DEFINED
#endif

time.h还提供了两种不同的函数将日历时间(一个用time_t表示的整数)转换为我们平时看到的把年月日时分秒分开显示的时间格式tm:

struct tm * gmtime(const time_t *timer);                                          
struct tm * localtime(const time_t * timer);

还有个函数像上面说到的ctime一样,格式输出tm结构中的日期和时间。

char * asctime(const struct tm * timeptr);

看名字就知道了,asctime嘛!

来看个程序,实战:

 

  1. #include "time.h"
  2. #include "stdio.h"
  3. int main(void)
  4. {
  5.   time_t lt;
  6.   struct tm st,*pt;
  7.   lt=time(NULL);
  8.   printf("The Calendar time now is %ld\n",lt)
  9.   lt =2147483647;
  10.   printf("The bug time(local) is %s\n",ctime(&lt));
  11.   pt=gmtime(&lt);
  12.   printf("The bug time(UTC) is %s",asctime(pt));
  13.   pt=localtime(&lt);
  14.   printf("The bug time(local) is %s\n",time(pt));
  15.   system("pause");
  16.   return 0;
  17. }

会输出:

The Calendar time now is 1239709783
The bug time(local) is Tue Jan 19 11:14:07 2038

The bug time(UTC) is Tue Jan 19 03:14:07 2038
The bug time(local) is Tue Jan 19 11:14:07 2038

不过,如果我们不喜欢像Tue Jan 19 11:14:07 2038的形式,想按我们自己的想法输出,该怎么办呢,time.h还有个函数strftime,观名知义,格式化时间,原型如下:

size_t strftime(
   char *strDest,
   size_t maxsize,
   const char *format,
   const struct tm *timeptr
);

我们可以根据format指向字符串中格式命令把timeptr中保存的时间信息放在strDest指向的字符串中,最多向strDest中存放maxsize个字符。该函数返回向strDest指向的字符串中放置的字符数。

函数strftime()的操作有些类似于sprintf():识别以百分号(%)开始的格式命令集合,格式化输出结果放在一个字符串中。格式化命令说明 串strDest中各种日期和时间信息的确切表示方法。格式串中的其他字符原样放进串中。格式命令列在下面,它们是区分大小写的。

%a 星期几的简写
%A 星期几的全称
%b 月分的简写
%B 月份的全称
%c 标准的日期的时间串
%C 年份的后两位数字
%d 十进制表示的每月的第几天
%D 月/天/年
%e 在两字符域中,十进制表示的每月的第几天
%F 年-月-日
%g 年份的后两位数字,使用基于周的年
%G 年分,使用基于周的年
%h 简写的月份名
%H 24小时制的小时
%I 12小时制的小时
%j 十进制表示的每年的第几天
%m 十进制表示的月份
%M 十时制表示的分钟数
%n 新行符
%p 本地的AM或PM的等价显示
%r 12小时的时间
%R 显示小时和分钟:hh:mm
%S 十进制的秒数
%t 水平制表符
%T 显示时分秒:hh:mm:ss
%u 每周的第几天,星期一为第一天 (值从0到6,星期一为0)
%U 第年的第几周,把星期日做为第一天(值从0到53)
%V 每年的第几周,使用基于周的年
%w 十进制表示的星期几(值从0到6,星期天为0)
%W 每年的第几周,把星期一做为第一天(值从0到53)
%x 标准的日期串
%X 标准的时间串
%y 不带世纪的十进制年份(值从0到99)
%Y 带世纪部分的十进制年份
%z,%Z 时区名称,如果不能得到时区名称则返回空字符。
%% 百分号

还是来个例子:

 

  1. #include <stdio.h>
  2. #include <time.h>
  3.  
  4. main( void )
  5. {
  6.   struct tm *newtime;
  7.   char tmpbuf[128];
  8.   time_t lt1;
  9.   time( &lt1 );
  10.   newtime=localtime(&lt1);
  11.   strftime( tmpbuf, 128, "Today is %A, day %d of %B in the year %Y.\n", newtime);
  12.   printf(tmpbuf);
  13.   system("pause");
  14. }
  15.  

程序输出:

Today is Tuesday, day 14 of April in the year 2009.

呵呵,按我们自己的意愿了。

 

 

程序员的十层楼

本文转自周伟民老师的博客。

原文在这里

自西方文艺复兴以来,中国在自然科学方面落后西方很多,软件领域也不例外。当然现在中国的许多程序员们对此可能有许多不同的意见,有些人认为中国的程序员水平远落后于西方,有些则认为中国的程序员个人能力并不比西方的程序员差,只是整个软件产业落后而已。

那么,到底中国的程序员水平比西方程序员水平差,还是中国有许多优秀的程序员达到或超过了西方程序员同等水平呢?要解决这个问题,必须先知道程序员有多少种技术层级,每个层级需要什么样的技术水平,然后再比较中国和西方在各个技术层级的人数,就可以知道到底有没有差距,差距有多大。

当然,对于如何划分程序员的技术层级,不同公司或不同人会有不同的划分标准,下面的划分仅代表个人的观点,如有不当之处,还请砸板砖予以纠正。


第1层  菜鸟

第1层楼属于地板层,迈进这层楼的门槛是很低的。基本上懂计算机的基本操作,了解计算机专业的一些基础知识,掌握一门基本的编程语言如C/C++,或者Java,或者JavaScript,...,均可入门迈进这层。

在这层上,中国有着绝对的优势,除了从计算机专业毕业的众多人数外,还有大量的通信、自动化、数学等相关专业的人士进入这一行,此外还有众多的其他专业转行的人士,人数绝对比西方多出甚多。并且还有一个优势就是我们这层人员的平均智商比西方肯定高。

没有多少人愿意一辈子做菜鸟,因为做"菜鸟"的滋味实在是不咋的,整天被老大们吆喝着去装装机器,搭建一下测试环境,或者对照着别人写好的测试用例做一些黑盒测试,好一点的可以被安排去写一点测试代码。当然如果运气"好"的话,碰到了国内的一些作坊式的公司,也有机会去写一些正式的代码。

所以,菜鸟们总是在努力学习,希望爬更高的一层楼去。
第2层 大虾

从第1层爬到第2层相对容易一些,以C/C++程序员为例,只要熟练掌握C/C++编程语言,掌握C标准库和常用的各种数据结构算法,掌握STL的基本实现和使用方法,掌握多线程编程基础知识,掌握一种开发环境,再对各种操作系统的API都去使用一下,搞网络编程的当然对socket编程要好好掌握一下,然后再学习一些面向对象的设计知识和设计模式等,学习一些测试、软件工程和质量控制的基本知识,大部分人经过2~3年的努力,都可以爬到第2层,晋升为"大虾"。

中国的"大虾"数量和"菜鸟"数量估计不会少多少,所以这层上仍然远领先于西方。

大虾们通常还是有些自知之明,知道自己只能实现一些简单的功能,做不了大的东西,有时候还会遇到一些疑难问题给卡住,所以他们对那些大牛级的人物通常是非常崇拜的,国外的如Robert C. Martin、Linus Torvalds,国内的如求伯君、王志东等通常是他们崇拜的对象。其中的有些人希望有一天也能达到这些大牛级人物的水平,所以他们继续往楼上爬去。
第3层 牛人

由于"大虾"们经常被一些疑难问题给卡住,所以有了"大虾"们只好继续学习,他们需要将原来所学的知识进一步熟练掌握,比如以熟练掌握C++编程语言为例,除了学一些基础性的C++书籍如《C++ Primer》,《Effective C++》,《Think in C++》,《Exception C++》等之外,更重要的是需要了解C++编译器的原理和实现机制,了解操作系统中的内部机制如内存管理、进程和线程的管理机制,了解处理器的基础知识和代码优化的方法,此外还需要更深入地学习更多的数据结构与算法,掌握更深入的测试和调试知识以及质量管理和控制方法,对各种设计方法有更好的理解等。

学习上面说的这些知识不是一挥而就的,不看个三五十本书并掌握它是做不到的。以数据结构算法来说,至少要看个5~10本这方面的著作;以软件设计来说,光懂结构化设计、面向对象设计和一些设计模式是不够的,还要了解软件架构设计、交互设计、面向方面的设计、面向使用的设计、面向数据结构算法的设计、情感化设计等,否则是很难进到这个楼层的。

当然除了上面说的知识外,大虾们还需要去学习各种经验和技巧。当然这点难不倒他们,现在出版的书籍众多,网络上的技术文章更是不胜数,然后再去各种专业论坛里泡一泡,把这些书籍和文章中的各种经验、技能、技巧掌握下来,再去学习一些知名的开源项目如Apache或Linux操作系统的源代码实现等。此时对付一般的疑难问题通常都不在话下,菜鸟和大虾们会觉得你很"牛",你也就爬到了第3层,晋升为"牛人"了。

看了上面所讲的要求,可能有些大虾要晕过去了,成为牛人要学这么多东西啊!要求是不是太高了?其实要求一点也不高,这么点东西都掌握不了的话,怎么能让别人觉得你"牛"呢?

需要提一下的是,进入多核时代后,从第2层爬到第3层增加了一道多核编程的门槛。当然要迈过这道门槛并不难,已经有很多前辈高人迈进了这道门槛,只要循着他们的足迹前进就可以了。想迈进这道门槛者不妨去学习一下TBB开源项目的源代码(链接:http://www.threadingbuildingblocks.org/),然后上Intel的博客(http://softwareblogs-zho.intel.com/)和多核论坛(http://forum.csdn.net/Intel/IntelMulti-core/)去看看相关文章,再买上几本相关的书籍学习一下。

在国内,一旦成为"牛人",通常可以到许多知名的公司里去,运气好者可以挂上一个架构师的头衔,甚至挂上一个"首席架构师"或者"首席xx学家"的头衔也不足为奇。有不少爬到这层的人就以为到了楼顶了,可以眼睛往天上看了,开始目空一切起来,以为自己什么都可以做了,什么都懂了,经常在网络上乱砸板砖是这个群体的最好写照。由此也看出,国内的牛人数量仍然众多,远多于西方的牛人数量,在这层上仍然是领先的。

也有不少谦虚的"牛人",知道自己现在还不到半桶水阶段。他们深知爬楼的游戏就像猴子上树一样,往下看是笑脸,往上看是屁股。为了多看笑脸,少看屁股,他们并没有在此停步不前,而是继续寻找到更上一层的楼梯,以便继续往上爬。
第4层 大牛

从第3层爬到第4层可不像上面说过的那几层一样容易,要成为大牛的话,你必须要能做牛人们做不了的事情,解决牛人们解决不了问题。比如牛人们通常都不懂写操作系统,不会写编译器,不懂得TCP/IP协议的底层实现,如果你有能力将其中的任何一个实现得象模象样的话,那么你就从牛人升级为"大牛"了。

当然,由于各个专业领域的差别,这里举操作系统、编译器、TCP/IP协议只是作为例子,并不代表成为"大牛"一定需要掌握这些知识,以时下热门的多核编程来说,如果你能比牛人们更深入地掌握其中的各种思想原理,能更加自如的运用,并有能力去实现一个象开源项目TBB库一样的东西,也可以成为"大牛",又或者你能写出一个类似Apache一样的服务器,或者写出一个数据库,都可以成为"大牛"。

要成为"大牛"并不是一件简单的事情,需要付出比牛人们多得多的努力,一般来说,至少要看过200~400本左右的专业书籍并好好掌握它,除此之外,还得经常关注网络和期刊杂志上的各种最新信息。

当"牛人"晋升为"大牛",让"牛人们"发现有比他们更牛的人时,对"牛人"们的心灵的震撼是可想而知的。由于牛人们的数量庞大,并且牛人对大虾和菜鸟阶层有言传身教的影响,所以大牛们通常能获得非常高的社会知名度,几乎可以用"引无数菜鸟、大虾、牛人竞折腰"来形容,看看前面提过的Linus Torvalds等大牛,应该知道此言不虚。

虽然成为"大牛"的条件看起来似乎很高似的,但是这层楼并不是很难爬的一层,只要通过一定的努力,素质不是很差,还是有许多"牛人"可以爬到这一层的。由此可知,"大牛"这个楼层的人数其实并不像想像的那么少,例如比尔·盖茨之类的人好像也是属于这一层的。

由于"大牛"这层的人数不少,所以也很难统计除到底是中国的"大牛"数量多还是西方的大牛数量多?我估计应该是个旗鼓相当的数量,或者中国的"大牛"们会更多一些。

看到这里,可能会有很多人会以为我在这里说瞎话,Linus Torvalds写出了著名的Linux操作系统,我国并没有人写出过类似的东西啊,我国的"大牛"怎么能和西方的比呢? 不知大家注意到没有,Linus Torvalds只是写出了一个"象模象样"的操作系统雏形,Linux后来真正发展成闻名全球的开源操作系统期间,完全是因为许多支持开源的商业公司如 IBM等,派出了许多比Linus Torvalds更高楼层的幕后英雄在里面把它开发出来的。

可能有些菜鸟认为Linus Torvalds是程序员中的上帝,不妨说个小故事:

Linus,Richard Stallman和Don Knuth(高德纳)一同参加一个会议。

Linus 说:"上帝说我创造了世界上最优秀的操作系统。"

Richard Stallman自然不甘示弱地说:"上帝说我创造了世界上最好用的编译器。"

Don Knuth一脸疑惑的说:"等等,等等,我什么时候说过这些话?"

由此可以看出,Linus Torvalds的技术水平并不像想像中那么高,只是"牛人"和"大虾"觉得"大牛"比他们更牛吧了。在我国,有一些当时还处于"大虾"层的人物,也能写出介绍如何写操作系统的书,并且书写得非常出色,而且写出了一个有那么一点点象模象样的操作系统来。我想中国的"大牛"们是不会比西方差的,之所以没有人写出类似的商业产品来,完全是社会环境的原因,并不是技术能力达不到的原因。

"大牛"们之所以成为大牛,主要的原因是因为把"牛人"给盖了下去,并不是他们自己觉得如何牛。也许有很多菜鸟、大虾甚至牛人觉得"大牛"这层已经到顶了,但大多数"大牛"估计应该是有自知之明的,他们知道自己现在还没有爬到半山腰,也就勉强能算个半桶水的水平,其中有些爬到这层没有累趴下,仍然能量充沛,并且又有志者,还是会继续往更上一层楼爬的。

看到这里,也许有些菜鸟、大虾、牛人想不明白了,还有比"大牛"们更高的楼层,那会是什么样的楼层?下面就来看看第5层楼的奥妙。
第5层 专家

当大牛们真正动手做一个操作系统或者类似的其他软件时,他们就会发现自己的基本功仍然有很多的不足。以内存管理为例,如果直接抄袭Linux或者其他开源操作系统的内存管理算法,会被人看不起的,如果自动动手实现一个内存管理算法,他会发现现在有关内存管理方法的算法数量众多,自己并没有全部学过和实践过,不知道到底该用那种内存管理算法。

看到这里,可能有些人已经明白第5层楼的奥妙了,那就是需要做基础研究,当然在计算机里,最重要的就是"计算"二字,程序员要做基础研究,主要的内容就是研究非数值"计算"。

非数值计算可是一个非常庞大的领域,不仅时下热门的"多核计算"与"云计算"属于非数值计算范畴,就是软件需求、设计、测试、调试、评估、质量控制、软件工程等本质上也属于非数值计算的范畴,甚至芯片硬件设计也同样牵涉到非数值计算。如果你还没有真正领悟"计算"二字的含义,那么你就没有机会进到这层楼来。

可能有人仍然没有明白为什么比尔·盖茨被划在了大牛层,没有进到这层来。虽然比尔·盖茨大学未毕业,学历不够,但是家有藏书2万余册,进入软件这个行业比绝大部分人都早,撇开他的商业才能不谈,即使只看他的技术水平,也可以算得上是学富五车,顶上几个普通的计算机软件博士之和是没有问题的,比起 Linus Torvalds之类的"大牛"们应该技高一筹才对,怎么还进不了这层楼呢?

非常遗憾的是,从Windows操作系统的实现来看,其对计算的理解是很肤浅的,如果把Google对计算方面的理解比做大学生,比尔·盖茨只能算做一个初中生,所以比尔·盖茨永远只能做个大牛人,成不了"专家"。

看到这里,也许国内的大牛们要高兴起来了,原来比尔·盖茨也只和我等在同一个层次,只要再升一层就可以超越比尔·盖茨了。不过爬到这层可没有从"牛人"升为"大牛"那么简单,人家比尔·盖茨都家有2万多册书,让你看个500~1000本以上的专业书籍并掌握好它应该要求不高吧。当然,这并不是主要的条件,更重要的是,需要到专业的学术站点去学习了,到ACM,IEEE,Elsevier,SpringerLink,SIAM等地方去下载论文应该成为你的定期功课,使用Google搜索引擎中的学术搜索更是应该成为你的日常必修课。此外,你还得经常关注是否有与你研究相关的开源项目冒出来,例如当听到有TBB这样针对多核的开源项目时,你应该第一时间到Google里输入"TBB"搜索一下,将其源代码下载下来好好研究一番,这样也许你的一只脚已经快迈进了这层楼的门槛。

当你象我上面说的那样去做了以后,随着时间的推移,总会有某天,你发现,在很多小的领域里,你已经学不到什么新东西了,所有最新出来的研究成果你几乎都知道。此时你会发现你比在做"牛人"和"大牛"时的水平不知高出了多少,但是你一点也"牛"不起来,因为你学的知识和思想都是别人提出来的,你自己并没有多少自己的知识和思想分享给别人,所以你还得继续往楼上爬才行。

我不知道国内的"专家"到底有多少,不过有一点可以肯定的是,如果把那些专门蒙大家的"砖家"也算上的话,我们的砖家比西方的要多得多。
第6层 学者

当"专家"们想继续往上一层楼爬时,他们几乎一眼就可以看到楼梯的入口,不过令他们吃惊的是,楼梯入口处竖了一道高高的门槛,上面写着"创新"二字。不幸的是,大多数人在爬到第5层楼时已经体能消耗过度,无力翻过这道门槛。

有少数体能充足者,可以轻易翻越这道门槛,但是并不意味着体力消耗过度者就无法翻越,因为你只是暂时还没有掌握恢复体能的方法而已,当掌握了恢复体能的方法,将体能恢复后,你就可以轻易地翻越这道门槛了。

怎么才能将体能恢复呢?我们的老祖宗"孔子"早就教导过我们"温故而知新",在英文里,研究的单词是"research",其前缀"re" 和"search"分别是什么意思不用我解释吧。或许有些人觉得"温故而知新"和"research"有些抽象,不好理解,我再给打个简单的比方,比如你在爬一座高山,爬了半天,中途体力不支,怎么恢复体力呢?自然是休息一下,重新进食一些食物,体力很快就可以得到恢复。

由此可知,对体能消耗过度者,休息+重新进食通常是恢复体能的最佳选择。可惜的是,国内的老板们并不懂得这点,他们的公司里不仅连正常国家规定的休息时间都不给足,有些公司甚至有员工"过劳死"出现。所以国内能翻越"创新"这道门槛的人是"少之又少",和西方比起来估计是数量级的差别。

再说说重新进食的问题,这个重新进食是有讲究的,需要进食一些基础性易消化的简单食物,不能进食山珍海味级的复杂食物,否则很难快速吸收。以查找为例,并不是去天天盯着那些复杂的查找结构和算法进行研究,你需要做的是将二分查找、哈希查找、普通二叉树查找等基础性的知识好好地复习几遍。

以哈希查找为例,首先你需要去将各种冲突解决方法如链式结构、二次哈希等编写一遍,再试试不同种类的哈希函数,然后还需要试试在硬盘中如何实现哈希查找,并考虑数据从硬盘读到内存后,如何组织硬盘中的数据才能快速地在内存中构建出哈希表来,...,这样你可能需要将一个哈希表写上十几个不同的版本,并比较各个版本的性能、功能方面的区别和适用范围。

总之,对任何一种简单的东西,你需要考虑各种各样的需求,以需求来驱动研究。最后你将各种最基础性的查找结构和算法都了然于胸后,或许某天你再看其他更复杂的查找算法,或者你在散步时,脑袋里灵光一现,突然间就发现了更好的方法,也就从专家晋升为"学者"了。

学者所做的事情,通常都是在前人的基础上,进行一些小的优化和改进,例如别人发明了链式基数排序的方法,你第1个发现使用一定的方法,可以用数组替代链表进行基数排序,性能还能得到进一步提高。

由于学者需要的只是一些小的优化改进,因此中国还是有一定数量的学者。不过和国外的数量比起来,估计少了一个数量级而已。

也许有人会觉得现在中国许多公司申请专利的数量达到甚至超过西方发达国家了,我们的学者数量应该不会比他们少多少。因此,有必要把专利和这里说的创新的区别解释一下。

所谓专利者,只要是以前没有的,新的东西,都可以申请专利;甚至是以前有的东西,你把他用到了一个新的领域的产品里去,也可以申请专利。比如你在房子里造一个水泥柱子,只要以前没有人就这件事申请专利,那么你就可以申请专利,并且下次你把水泥柱子挪一个位置,又可以申请一个新的专利;或者你在一个柜子上打上几个孔,下次又把孔的位置改一改,...,均可申请专利。

这层楼里所说的创新,是指学术层面的创新,是基础研究方面的创新,和专利的概念是完全不同的,难度也是完全不同的。你即使申请了一万个象那种打孔一类的专利,加起来也够不到这层楼里的一个创新。

当你爬到第6层楼时,你也许会有一种突破极限的快感,因为你终于把那道高高的写着"创新"二字的门槛给翻过去了,实现了"0"的突破。这时,你也许有一种"独上高楼,欲望尽天涯路"的感觉,但是很快你会发现看到的都是比较近的路,远处的路根本看不清楚。如果你还有足够的体力的话,你会想爬到更高一层的楼层去。

第7层 大师

从第6层楼爬到第7层楼,并没有多少捷径可走,主要看你有没有足够的能量。你如果能象Hoare一样设计出一个快速排序的算法;或者象Eugene W. Myers一样设计出了一个用编辑图的最短路径模型来解决diff问题的算法;或者象M.J.D. Powell一样提出了一个能够处理非线性规划问题的SQP方法;或者你发现基于比较的排序算法,它的复杂度下界为O(NLogN);或者你发现用栈可以将递归的算法变成非递归的;或者你设计出一个红黑树或者AVL树之类的查找结构;或者你设计出一个象C++或Java一样的语言;或者你发明了 UML;...,你就爬到了第7层,晋升为"大师"了。

上面举的这些例子中,其中有些人站的楼层比这层高,这里只是为了形象说明而举例他们的某个成就。从上面列出的一些大师的贡献可以看出,成为大师必须要有较大的贡献。首先解决问题必须是比较重要的,其次你要比前辈们在某方面有一个较大的提高,或者你解决的是一个全新的以前没有解决过的问题;最重要的是,主要的思路和方法必须是你自己提供的,不再是在别人的思路基础上进行的优化和改进。

看了上面这些要求,如果能量不够的话,你也许会觉得有些困难,所以不是每个人都能成为"大师"的。中国软件业里能称得上是"大师"的人,用屈指可数来形容,估计是绰绰有余。值得一提得是,国外的"大师"就象我们的"大牛"一样满天飞的多。

我把我猜测本国有可能进到这层楼的大师列一下,以起个抛砖引玉的作用。汉王的"手写识别"技术由于是完全保密的,不知道它里面用了什么思想,原创思想占的比重有多少,因此不知道该把它划到这层楼还是更高一层楼去。原山东大学王小云教授破解DES和MD5算法时,用到的方法不知道是不是完全原创的,如果是的话也可进到这层楼来。

陈景润虽然没有彻底解决哥德巴赫猜想,但他在解决问题时所用的方法是创新的,因此也可以进到这层楼来。当然,如果能彻底解决哥德巴赫猜想,那么可以算到更高的楼层去。

求伯君和王志东等大牛们,他们在做WPS和表格处理之类的软件时,不知是否有较大的原创算法在里面,如果有的话就算我错把他们划到了大牛层。由于所学有限,不知道国内还有那些人能够得上"大师"的级别,或许有少量做研究的教授、院士们,可以达到这个级别,有知道的不妨回个帖子晾一晾。

鉴于"大师"这个称号的光环效应,相信有不少人梦想着成为"大师"。或许你看了前面举的一些大师的例子,你会觉得要成为大师非常困难。不妨说一下,现在有一条通往"大师"之路的捷径打开了,那就是多核计算领域,有大量的处女地等待大家去挖掘。

以前在单核时代开发的各种算法,现在都需要改写成并行的。数据结构与算法、图像处理、数值计算、操作系统、编译器、测试调试等各个领域,都存在大量的机会,可以让你进到这层楼来,甚至有可能让你进到更高一层楼去。
第8层 科学家

科学家向来都是一个神圣的称号,因此我把他放在了“大师”之上。要成为科学家,你的贡献必须超越大师,不妨随便举一些例子。

如果你象Dijkstra一样设计了ALGOL语言,提出了程序设计的三种基本结构:顺序、选择、循环,那么你可以爬到第8层楼来。顺便说一下,即使抛开这个成果,Dijkstra凭他的PV操作和信号量概念的提出,同样可以进到这层楼。

如果你象Don Knuth一样,是数据结构与算法这门学科的重要奠基者,你也可以进到这层楼来。当然,数据结构和算法这门学科不是某个人开创的,是许多大师和科学家集体开创的。

如果你象巴科斯一样发明了Fortran语言,并提出了巴科斯范式,对高级程序语言的发展起了重要作用,你也可以进到这层楼来。

或者你象Ken Thompson、Dennis Ritchie一样发明了Unix操作系统和功能强大、高效、灵活、表达力强的C语言,对操作系统理论和高级编程语言均作出重大贡献,那么你也可以进到这层楼来。

或者你有Frederick P. Brooks一样机会,可以去领导开发IBM的大型计算机System/360和OS/360操作系统,并在失败后反思总结,写出《人月神话》,对软件工程作出里程碑式的贡献,你也可以进到这层来。

或者你提出了面向对象设计的基本思想,或者你设计了互联网的TCP/IP协议,或者你象Steven A.Cook一样奠定NP完全性的理论基础,或者你象Frances Allen一样专注于并行计算来实现编译技术,在编译优化理论和技术取得基础性的成就,…,均可进入这层。

当然,如果你发明了C++语言或者Java语言,你进不到这层来,因为你用到的主要思想都是这层楼中的科学家提出的,你自己并没有没有多少原创思想在里面。

看了上面列出的科学家的成就,你会发现,要成为“科学家”,通常要开创一门分支学科,或者是这个分支学科的奠基者,或者在某个分支学科里作出里程碑式的重大贡献。如果做不到这些的话,那么你能象Andrew C. Yao(姚期智)一样在对计算理论的多个方向如伪随机数生成,密码学与通信复杂度等各个方向上作出重要贡献,成为集大成者,也可以进入这层楼。

成为“科学家”后,如果你有幸象Dijkstra一样,出现在一个非常重视科学的国度。当你去世时,你家乡满城的人都会自动地去为你送葬。不过如果不幸生错地方的话,能不挨“板砖”估计就算万幸了。

从上面随便举的一些例子中,你可能能猜到,西方科学家的数量是非常多的,于是你会想中国应该也有少量的科学家吧?我可以很负责任地告诉你一个不幸的结果,中国本土产生的科学家的数量为0。目前在国内,软件领域的唯一的科学家就是上面提过的姚期智,还是国外请回来的,并不是本土产生的。

可能你不同意我说的本土科学家数量为0的结论,因为你经常看到有许多公司里都有所谓“首席XX科学家”的头衔。我想说的是,这些所谓的“首席XX科学家”都是远远够不到这层楼的级别的,有些人的水平估计也就是一个“牛人”或“大牛”的级别,好一点的最多也就一个“学者”的级别。尤其是那些被称作“首席经X学家”的,基本上可以把称号改为“首席坑大家”。

虽然我国没有人能爬到这层楼上来,但是西方国家仍然有许多人爬到了比这层更高的楼上。如果要问我们比西方落后多少?那么可以简单地回答为:“落后了三层楼”。下面就来看看我们做梦都没有到过的更高一层楼的秘密。

第9层 大科学家

进入这层楼的门槛通常需要一些运气,比如某天有个苹果砸到你头上时,你碰巧发现了万有引力,那么你可以进到这层楼来。当然,万有引力几百年前就被人发现了,如果你现在到处嚷嚷着说你发现了万有引力,恐怕马上会有人打110,然后警察会把你送到不正常人类的聚集地去。因此,这里举万有引力的例子,只是说你要有类似的成就才能进到这层楼来。

牛顿发现万有引力定律开创了经典物理运动力学这门学科,如果你也能开创一门大的学科,那么你就从科学家晋升为“大科学家”。比如爱因斯坦创建了相对论,从一个小职员变成了大科学家。当然大科学家可远不止这两人,数学界里比物理学界更是多得多,如欧几里得创建了平面几何,笛卡尔开创解析几何,还有欧拉、高斯、莱布尼茨等数不清的人物,跟计算相关的大科学家则有图灵等人。

从上面列出的一些大科学家可以发现,他们的成就不仅是开创了一个大的学科,更重要的是他们的成就上升到了“公理”的层面。发现公理通常是需要一点运气的,如果你的运气不够好的话,另外还有一个笨办法也可以进到这层楼来,那就是成为集大成者。例如冯·诺伊曼,对数学的所有分支都非常了解,许多领域都有较大的贡献,即使撇开他对计算机的开创贡献,成为大科学家照样绰绰有余。

当然,程序员们最关心的是自己有没有机会变成大科学家。既然计算机这门大学科的开创性成果早就被冯·诺伊曼、图灵等人摘走了,那么程序员们是不是没有机会变成大科学家了呢?我们的古人说得好:“江山代有才人出,各领风骚数百年”,现在在计算机这门学科下面诞生了许多非常重要的大的分支,所以你还是有足够的机会进到这层楼的。

如果你能够彻底解决自然语言理解(机器翻译)这门学科中的核心问题, 或者你在人工智能或者机器视觉(图像识别)方面有突破性的发现,那么你同样可以轻易地晋升为“大科学家”。这样当某天你老了去世时,或许那天国人已经觉醒,你也能享受到如Dijkstra一样的待遇,有满城甚至全国的人去为你送葬。

现在还剩下另外一个大家感兴趣的问题没有讨论,那就是这层中已经出现了牛顿、爱因斯坦、高斯等我们平常人都认为是顶级的科学家,是不是这层已经是楼顶了呢?相信还记得本文标题的人应该知道现在仅仅是第9层,还有第10层没有到达呢。可能不少人现在要感到困惑了,难道还有人站在比牛顿、爱因斯坦、高斯等人更高的楼层上?

这个世界上确实存在可以用一只手的手指数得清的那么几个人,他们爬到了第10层楼上。因此,第10层楼不是虚构的,而是确实存在的。如果对此有疑惑或者认为我在胡诌一番的话,那么不妨继续往下看下去,窥一下第10层楼的秘密。
第10层 大哲

看了这层楼的名字“大哲”,可能不少人已经猜到了这层楼的秘密,那就是你的成果必须要上升到哲学的高度,你才有机会能进到这层来。

当然,上升到哲学高度只是一个必要条件,牛顿的万有引力似乎也上升到了哲学的高度,因为不知道引力到底是怎么来的,但是牛顿没有被划到这一层,因为进到这层还有另外的条件,那就是你的成果必须引起了哲学上的深度思考,并能让人们的世界观向前跨进一大步。窃以为牛顿、爱因斯坦等人的成就还达不到让人们世界观向前跨进一大步的程度。

所以,这层楼中的人的成就对我们普通人认识世界非常重要,你可以不学相对论,但是你不可以不对这层楼的人所作出的成就不了解,否则你的世界观就是极其不完整的,会犯许多认识上的错误。不幸的是,中国的科普知识普及还不够到位,知道这层楼成就的人好像并不多,程序员中恐怕更少。下面就来看看这些用一只手的手指数得清的大哲们,到底有什么成就,能比万有引力定律和相对论还重要。

1、希尔伯特 (1862~1943)

第1位进到此楼层是一位名叫“希尔伯特”的大数学家,如果你学过《泛函分析》,那么你在学习希尔伯特空间时可能已经对这位大数学家有所了解;如果你不是学数学出身的,又对数学史不感兴趣的话,恐怕你从来没有听说过这个名字。不过如果我问一下,知不知道二次世界大战前世界数学中心在那里,你肯定会有兴趣想知道。

不妨说一下,二战前整个世界的数学中心就在德国的哥廷根,而我们这位大数学家希尔伯特便是它的统帅和灵魂人物。即使在二战期间,希特勒和丘吉尔也有协定,德国不轰炸牛津和剑桥,作为回报,英国不轰炸海德堡和哥廷根。

整个二十世纪上半期的超一流数学家,几乎都出自其门下。这里不妨举几个我们熟悉的人物,例如冯·诺伊曼就曾受到他和他的学生施密特和外尔的思想影响,还到哥廷根大学任过希尔伯特的助手,钱学森的老师冯·卡门是在哥廷根取得博士学位的。顺便提一下,这位大数学家发现当时物理学上出了很多大的成果如相对论和量子力学,但是这些物理学家的数学功力明显不足,因此有一段时间带领他的学生们研究过物理学,并独立发现了广义相对论,只是不好意思和物理学家争功劳,将广义相对论的功劳全部让给了爱因斯坦。

广义相对论相对于这位大数学家在数学上的贡献,其实是算不了什么的,只是由此可看出这位大数学家品格的高尚之处。如果再去看看牛顿之流的人物的品行,整天和莱布尼茨、虎克等人争功劳,利用自己的优势地位打压他人,甚至闹得上法庭,和这位希尔伯特先生比起来,简直就是个小丑。

说到这里,你可能对这位大数学家“希尔伯特”有了一些初步映象,感觉到了他的重要性,不过他在数学上的主要成就可不是几句话说得清楚的。首先,他是一位集大成者,精通当时数学所有分支领域,在数学的各个领域都有较大的贡献,当然这些成就只能让他成为一个大科学家,不能带他进入这层楼。事实上这位“希尔伯特”解决的任何一个数学问题都够不到这层楼的高度,那么他怎么混到这层楼来了呢?

话得从1900年说起,当时还很年轻的希尔伯特在当时的世界数学大会上做了一个报告,高屋建瓯地提出了著名的23个未解决的数学问题,然后整个二十世纪上半期,全世界的数学家们都在这23个问题的指导下展开研究,直到现在仍然有许多数学家受这23个问题的指导在进行研究。例如我们熟知的哥德巴赫猜想,就属于其中第8个问题素数分布的一个子问题。

如果用“高瞻远瞩”来形容这位大数学家的话,那么这个世界上恐怕没有第二个人再配得上“高瞻远瞩”这四个字,不论是欧拉、高斯、牛顿、爱因斯坦还是被誉为最有才华的数学家伽罗华,概不例外。

虽然那23个问题是归纳总结出来的,并不全是原创,但是其中有不少问题是可以上升到哲学的高度,引起深度思考的。可能大多数人都会觉得希尔伯特是进不到这层楼的,我们知道提出问题的人和解决问题的人是一样伟大的,何况他提出的问题是如此之多,基于这点,个人觉得应该让希尔伯特跨进这层楼的门槛里。

看完这位希尔伯特的成就,你可能会觉得对你的世界观并没有产生任何影响。确实如此,他提出的问题不是用来影响你的,而是用来影响其他大科学家和大哲的,下面再来说说另一位对他提出的23个问题中的第2个问题有杰出贡献的大哲,你就会感觉到大哲们的成果的威力了。

2、哥德尔 (1906~1978)

这位大哲的名字叫“哥德尔 (G?del) ”,你可能从来也没有听说过这个名字,即使你读了一个数学系的博士学位,如果你的研究方向不和这位大哲对口的话,你也不一定了解这位大哲的成就,更不知道他的成果对我们这个世界有何意义。

简单地说,这位大哲20多岁时就证明了两个定理,一个叫做“哥德尔完全性定理”,另一个更重要的叫做“哥德尔不完全性定理”。你也许会觉得奇怪,第9层楼的成就就已经上升到了公理的高度,这种证明定理的事情不是学者和大师们做的事情吗?怎么能比第9层楼的成就还高呢?下面就来简单说一下这两个定理的含义,你就会明白这属于系统级的定理,绝不是普通的定理和公理所能比拟的。

“哥德尔完全性定理”证明了逻辑学的几条公理是完备的,即任何一个由这些公理所产生出的问题,在这个公理系统内可以判定它是真的还是假的,这个结论表明了我们人类所拥有的逻辑思维能力是完备的。这条定理并不能将其带入这层楼来,带其进入这层楼的是另一条定理。

“哥德尔不完全性定理”是在1930年证明的,它证明了现有数学的几条公理(ZF公理系统)是不完备的,即由这些公理产生出的问题,无法由这几条公理判断它是真的还是假的。例如希尔伯特23个问题中的第1个问题,也就是著名的康托尔连续统假设,哥德尔在1938年证明了现有公理系统中不能证明它是“假”的,科恩(Cohen,或许也可以称得上是“半”个大哲)在1963年证明了现有公理系统不能证明它是“真”的。最有趣的是,即使你将某个不可判定的问题,作为一条新的公理加入进去,所组成的新的公理系统仍然是不完备的,即你无法构造一个有限条公理的系统,让这个公理系统是完备的。

也许你仍然无法理解上面这段话的含义,不妨先说一下它对我们现实世界的影响。你可能知道1936年出现的图灵机是现代计算机的理论模型,如果没有哥德尔不完全性定理的思想,图灵机什么时候能出来是很难说的,所以这位哥德尔可以算作计算机理论的奠基者的奠基者。计算机对我们这个世界产生的影响比原子弹大了多少,我想不用我说大家也都清楚。当然,对现实世界的影响只能把哥德尔同图灵等人一样划到大科学家那一层去,能进入这层乃是另有原因。

可能你看过《未来战士》、《黑客帝国》、《I,Robot》之类的科幻电影,于是你产生制造一个和人一样或者比人更高一级的智能机器人的想法,这就引入了一个达到哲学高度的问题,“人到底能不能制造出具有和人一样的思维能力的机器来?”。

我只能告诉你,“你的愿望是良好的,但现实是残酷的”。如果你仔细思考一下不完全性定理的含义,并结合现代计算机所具有的能力分析一下,你会发现这个问题的答案暂时是否定的。如果你想造出和人一样思维能力的机器,那么你需要去好好学习这位大哲及其后续研究者的成果,并在他们的基础上有新的突破才行。

为了说明这位大哲所研究领域的重要性,这里顺便再讨论一个我们日常争议不休的问题,那就是孔夫子的“人之初、性本善”以及西方认为“人之初、性本恶”的观点孰优孰劣的问题。可能有许多人发现西方社会现在领先我们,于是就认为“性本恶”是对的,“性本善”是错的,中国应该抛弃以前的旧思想,改用西方的思想。当然也有一些老学究们,认为中国的人文思想是领先于西方的,自然而然地认为“性本善”是对的,“性本恶”是错的。

如果你学过大哲用过的公理化的分析方法,你就知道一套系统的多条公理间只要不会推导出矛盾的地方,即可以自圆其说,那么它可以看作是对的。这样你可以很轻易地给这个问题下一个结论,即“性本善”和“性本恶”是对等的,不存在孰优孰劣的问题,更不存在谁对谁错的问题。只要你不同时将“性本善”和“性本恶”放入一个系统内,那么是不会有问题的,甚至你也可以认为“人之初、既无善、亦无恶”,或者认为“人之初、部分善、部分恶”,都是可以自圆其说的,所以我们的老祖宗提出的思想并没有问题,之所以落后乃是其他原因造成的。这个问题其实在高斯所处的时代就有了结论,那时有人提出了非欧几何,即平行线公理问题,有人认为过一点可以作多条平行线,还有人认为平行线在无穷远点是相交的,和欧氏几何关于过一点只能作一条平行线的公理都是矛盾的,但是他们各自的系统内推导出的结论都是正确的。

上面说的只是对哥德尔不完全性定理的一些粗浅解析,实际上如果深入思考一下它的含义的话,你会发现它对物理学等许多学科有重大影响,包含的道理实在是深刻,远非一般的思想所能比拟,有兴趣者不妨“google”或“百度”一下“哥德尔”。或许只有我们的老祖宗“老子”提出的哲学思想,深度可以有得一比。

哥德尔不完全性定理也给那些认为科学是严谨的人当头一棒,原来连数学这样的纯理论学科都是不严谨的,其他学科就更不用说了。

至此,已经说完数学上的大哲,下面不妨再看看物理学上的大哲,物理学上好像只出过一位叫“海森堡”的大哲(注:由于本人对物理学不甚了解,不知道“霍金”够不够得上大哲的称号)。

P.S:看完之后,感觉自己只不过是走出了小小的一步,总算看到了这个世界有多大,这幢楼有多高,从今天开始,爬楼!
 

黑色星期五

在西方人看来,星期五本就是个不好的日子,大概是因为人们认为是这天是耶稣被 害的日子吧!因此这天在西方人看来是不吉利的,甚至有些人不起床,不出去,怕遇到霉运。同样的,13也是个不吉利的数字,因为传说背叛耶稣的传道者犹大是最后的晚餐中的第13个客人,所以西方人竭力避免13号的出现,像有没有球员愿意穿13号球衣,80%的楼层没有13层,机场漏过13号门等等。而如果星期五和13号是一天的时候,更被认为是特大倒霉日,人们称为黑色星期五,这两个代表坏运气的个体的结合被人们认为是超级不幸的一天。

呵呵,不过突然发现今年的2-14情人节之前的星期五正好是13号,不知道这个黑色星期五会不会影响西方人的情人节心情呢,还能不能Happy Valentine's Day 呢!

不过其实黑色星期五出现的时候是不少的,否则那个著名的黑色星期五病毒不是少有发作的机会了吗,你说一个病毒怎么会安安静静地待在里而不发作呢?

怎么验证呢,其实说难也不难,可以利用Zeller公式计算一下13号落在星期五的次数,像USACO上就有一个题是干这无聊的事的(那个Friday the thirteenth),像这样的C代码便可以办到,从friday.in中读入一个整数,这里是400(因为每400年是历法的一个循环),然后计算从1900开始的400年内所有的13号落在每天的次数,把结果写在friday.out中。

 

#include<stdio.h>
main()

{

        int days[2][13]={{0,31,28,31,30,31,30,31,31,30,31,30,31},
                                        {0,31,29,31,30,31,30,31,31,30,31,30,31}};
        int monthcode[13]={0};
        int week[7]={0};
        int i,j,n,year,isleap;
        freopen("friday.in","r",stdin);
        freopen("friday.out","w",stdout);
        scanf("%d",&n);
        for(i=0;i<n;i++){
                year=1900+i;
                isleap=year%400==0?1:(year%100==0?0:(year%4==0?1:0));
                for(j=1;j<=12;j++){
                        monthcode[j]=(days[isleap][j-1]+monthcode[j-1])%7;
                }
                monthcode[0]=(monthcode[12]+days[isleap][12])%7;
                for(j=1;j<=12;j++){
                        week[(monthcode[j]+13)%7]++;
                }
        }
        for(j=6,i=1;i<=7;i++){
                printf("%d%c",week[j],(i!=7?32:'\n'));
                j++;
                j%=7;
        }
        return 0;
}
 

现在打开friday可以发现(下面的结果略有排版,数字表示的是这400年来13号落在这一天的次数):

  • Sunday     687
  • Monday     685
  • Tuesday    685
  • Wednesday  687
  • Thursday   684
  • Friday     688
  • Saturday   684

仔细看一下,其实13号落在星期五的次数是最多的。