如何计算某一天是星期几?—— 蔡勒（Zeller）公式

来源:原文地址

---

历史上的某一天是星期几？未来的某一天是星期几？关于这个问题，有很多计算公式（两个通用计算公式和一些分段计算公式），其中最著名的是蔡勒（Zeller）公式。即w=y+[y/4]+[c/4]-2c+[26(m+1)/10]+d-1



公式中的符号含义如下，w：星期；c：世纪-1；y：年（两位数）；m：月（m大于等于3，小于等于14，即在蔡勒公式中，某年的1、2月要看作上一年的13、14月来计算，比如2003年1月1日要看作2002年的13月1日来计算）；d：日；[ ]代表取整，即只要整数部分。(C是世纪数减一，y是年份后两位，M是月份，d是日数。1月和2月要按上一年的13月和 14月来算，这时C和y均按上一年取值。)算出来的W除以7，余数是几就是星期几。如果余数是0，则为星期日。



以2049年10月1日（100周年国庆）为例，用蔡勒（Zeller）公式进行计算，过程如下：

蔡勒（Zeller）公式：w=y+[y/4]+[c/4]-2c+[26(m+1)/10]+d-1

=49+[49/4]+[20/4]-2×20+[26× (10+1)/10]+1-1

=49+[12.25]+5-40+[28.6]

=49+12+5-40+28

=54 (除以7余5)

即2049年10月1日（100周年国庆）是星期5。



你的生日（出生时、今年、明年）是星期几？不妨试一试。



不过，以上公式只适合于1582年10月15日之后的情形（当时的罗马教皇将恺撒大帝制订的儒略历修改成格里历，即今天使用的公历）。过程的推导:(对推理不感兴趣的可略过不看)

星期制度是一种有古老传统的制度。据说因为《圣经·创世纪》中规定上帝用了六天时间创世纪，第七天休息，所以人们也就以七天为一个周期来安排自己的工作和生活，而星期日是休息日。从实际的角度来讲，以七天为一个周期，长短也比较合适。所以尽管中国的传统工作周期是十天（比如王勃《滕王阁序》中说的“十旬休暇”，即是指官员的工作每十日为一个周期，第十日休假），但后来也采取了西方的星期制度。



在日常生活中，我们常常遇到要知道某一天是星期几的问题。有时候，我们还想知道历史上某一天是星期几。通常，解决这个方法的有效办法是看日历，但是我们总不会随时随身带着日历，更不可能随时随身带着几千年的万年历。假如是想在计算机编程中计算某一天是星期几，预先把一本万年历存进去就更不现实了。这时候是不是有办法通过什么公式，从年月日推出这一天是星期几呢？



答案是肯定的。其实我们也常常在这样做。我们先举一个简单的例子。比如，知道了2004年5月1日是星期六，那么2004年5月31日“世界无烟日”是星期几就不难推算出来。我们可以掰着指头从1日数到31日，同时数星期，最后可以数出5月31日是星期一。其实运用数学计算，可以不用掰指头。我们知道星期是七天一轮回的，所以5月1日是星期六，七天之后的5月8日也是星期六。在日期上，8-1=7，正是7的倍数。同样，5月15日、5月22日和5月29日也是星期六，它们的日期和5月1日的差值分别是14、21和28，也都是7的倍数。那么5月31日呢？31-1=30，虽然不是7的倍数，但是31除以7，余数为2，这就是说，5月31日的星期，是在5月1日的星期之后两天。星期六之后两天正是星期一。



这个简单的计算告诉我们计算星期的一个基本思路：首先，先要知道在想算的日子之前的一个确定的日子是星期几，拿这一天做为推算的标准，也就是相当于一个计算的“原点”。其次，知道想算的日子和这个确定的日子之间相差多少天，用7除这个日期的差值，余数就表示想算的日子的星期在确定的日子的星期之后多少天。如果余数是0，就表示这两天的星期相同。显然，如果把这个作为“原点”的日子选为星期日，那么余数正好就等于星期几，这样计算就更方便了。



但是直接计算两天之间的天数，还是不免繁琐。比如1982年7月29日和2004年5月1日之间相隔7947天，就不是一下子能算出来的。它包括三段时间：一，1982年7月29日以后这一年的剩余天数；二，1983-2003这二十一个整年的全部天数；三，从2004年

元旦到5月1日经过的天数。第二段比较好算，它等于21*365+5=7670天，之所以要加5，是因为这段时间内有5个闰年。第一段和第三段就比较麻烦了，比如第三段，需要把5月之前的四个月的天数累加起来，再加上日期值，即31+29+31+30+1=122天。同理，第一段需要把7月之后的五个月的天数累加起来，再加上7月剩下的天数，一共是155天。所以总共的相隔天数是122+7670+155=7947天。



仔细想想，如果把“原点”日子的日期选为12月31日，那么第一段时间也就是一个整年，这样一来，第一段时间和第二段时间就可以合并计算，整年的总数正好相当于两个日子的年份差值减一。如果进一步把“原点”日子选为公元前1年12月31日（或者天文学家所使用的公元0年12月31日），这个整年的总数就正好是想算的日子的年份减一。这样简化之后，就只须计算两段时间：一，这么多整年的总天数；二，想算的日子是这一年的第几天。巧的是，按照公历的年月设置，这样反推回去，公元前1年12月31日正好是

星期日，也就是说，这样算出来的总天数除以7的余数正好是星期几。那么现在的问题就只有一个：这么多整年里面有多少闰年。这就需要了解公历的置闰规则了。



我们知道，公历的平年是365天，闰年是366天。置闰的方法是能被4整除的年份在2月加一天，但能被100整除的不闰，能被400整除的又闰。因此，像1600、2000、2400年都是闰年，而1700、1800、1900、2100年都是平年。公元前1年，按公历也是闰年。



因此，对于从公元前1年（或公元0年）12月31日到某一日子的年份Y之间的所有整年中的闰年数，就等于



[(Y-1)/4] - [(Y-1)/100] + [(Y-1)/400]，



[...]表示只取整数部分。第一项表示需要加上被4整除的年份数，第二项表示需要去掉被100整除的年份数，第三项表示需要再加上被400整除的年份数。之所以Y要减一，这样，我们就得到了第一个计算某一天是星期几的公式：



W = (Y-1)*365 + [(Y-1)/4] - [(Y-1)/100] + [(Y-1)/400] + D．              (1)



其中D是这个日子在这一年中的累积天数。算出来的W就是公元前1年（或公元0年）12月31日到这一天之间的间隔日数。把W用7除，余数是几，这一天就是星期几。比如我们来算2004年5月1日：



W = (2004-1)*365 + [(2004-1)/4] - [(2004-1)/100] + [(2004-1)/400] +

   (31+29+31+30+1)

  = 731702，



731702 / 7 = 104528……6，余数为六，说明这一天是星期六。这和事实是符合的。



上面的公式(1)虽然很准确，但是计算出来的数字太大了，使用起来很不方便。仔细想想，其实这个间隔天数W的用数仅仅是为了得到它除以7之后的余数。这启发我们是不是可以简化这个W值，只要找一个和它余数相同的较小的数来代替，用数论上的术语

来说，就是找一个和它同余的较小的正整数，照样可以计算出准确的星期数。



显然，W这么大的原因是因为公式中的第一项(Y-1)*365太大了。其实，



(Y-1)*365 = (Y-1) * (364+1)

          = (Y-1) * (7*52+1)

          = 52 * (Y-1) * 7 + (Y-1)，



这个结果的第一项是一个7的倍数，除以7余数为0，因此(Y-1)*365除以7的余数其实就等于Y-1除以7的余数。这个关系可以表示为：



(Y-1)*365 ≡ Y-1 (mod 7)．



其中，≡是数论中表示同余的符号，mod 7的意思是指在用7作模数（也就是除数）的情况下≡号两边的数是同余的。因此，完全可以用(Y-1)代替(Y-1)*365，这样我们就得到了那个著名的、也是最常见到的计算星期几的公式：



W = (Y-1) + [(Y-1)/4] - [(Y-1)/100] + [(Y-1)/400] + D．                  (2)



这个公式虽然好用多了，但还不是最好用的公式，因为累积天数D的计算也比较麻烦。是不是可以用月份数和日期直接计算呢？答案也是肯定的。我们不妨来观察一下各个月的日数，列表如下：



月　　份：1月　2月　　3月　4月　5月　6月　7月　8月　9月　10月　11月　12月

--------------------------------------------------------------------------

天　　数： 31  28(29)  31   30   31   30   31   31   30   31    30    31



如果把这个天数都减去28（=4*7），不影响W除以7的余数值。这样我们就得到另一张表：



月　　份：1月　2月　3月　4月　5月　6月　7月　8月　9月　10月　11月　12月

------------------------------------------------------------------------

剩余天数： 3   0(1)  3    2    3    2    3    3    2    3     2     3

平年累积： 3   3     6    8   11   13   16   19   21   24    26    29

闰年累积： 3   4     7    9   12   14   17   20   22   25    27    30



仔细观察的话，我们会发现除去1月和2月，3月到7月这五个月的剩余天数值是3,2,3,2,3；8月到12月这五个月的天数值也是3,2,3,2,3，正好是一个重复。相应的累积天数中，后一月的累积天数和前一月的累积天数之差减去28就是这个重复。正是因为这种规律的存在，平年和闰年的累积天数可以用数学公式很方便地表达：



    ╭ d；　　　　　　　　　　　　　　　 　（当M＝1）

D = {  31 + d；　　　　　　　　　    　　  （当M＝2） 　　　　　　　　　 (3)

    ╰ [ 13 * (M+1) / 5 ] - 7 + (M-1) * 28 + d + i．　 （当M≥3）



其中[...]仍表示只取整数部分；M和d分别是想算的日子的月份和日数；平年i=0，闰年i=1。对于M≥3的表达式需要说明一下：[13*(M+1)/5]-7算出来的就是上面第二个表中的平年累积值，再加上(M-1)*28就是想算的日子的月份之前的所有月份的总天数。这是一个很巧妙的办法，利用取整运算来实现3,2,3,2,3的循环。比如，对2004年5月1日，有：



D = [ 13 * (5+1) / 5 ] - 7 + (5-1) * 28 + 1 + 1

  = 122，



这正是5月1日在2004年的累积天数。



假如，我们再变通一下，把1月和2月当成是上一年的“13月”和“14月”，不仅仍然符合这个公式，而且因为这样一来，闰日成了上一“年”（一共有14个月）的最后一天，成了d的一部分，于是平闰年的影响也去掉了，公式就简化成：



D = [ 13 * (M+1) / 5 ] - 7 + (M-1) * 28 + d．        （3≤M≤14）        (4)



上面计算星期几的公式，也就可以进一步简化成：



W = (Y-1) + [(Y-1)/4] - [(Y-1)/100] + [(Y-1)/400] + [ 13 * (M+1) / 5 ] - 7

   + (M-1) * 28 + d．



因为其中的-7和(M-1)*28两项都可以被7整除，所以去掉这两项，W除以7的余数不变，公式变成：



W = (Y-1) + [(Y-1)/4] - [(Y-1)/100] + [(Y-1)/400] + [ 13 * (M+1) / 5 ] + d．

(5)



当然，要注意1月和2月已经被当成了上一年的13月和14月，因此在计算1月和2月的日子的星期时，除了M要按13或14算，年份Y也要减一。比如，2004年1月1日是星期四，用这个公式来算，有：



W = (2003-1) + [(2003-1)/4] - [(2003-1)/100] + [(2003-1)/400] + [13*(13+1)/5]

   + 1

  = 2002 + 500 - 20 + 5 + 36 + 1

  = 2524；

2524 / 7 = 360……4．这和实际是一致的。



公式(5)已经是从年、月、日来算星期几的公式了，但它还不是最简练的，对于年份的处理还有改进的方法。我们先来用这个公式算出每个世纪第一年3月1日的星期，列表如下：



年份：  1(401,801,…,2001)                   101(501,901,…,2101)

--------------------------------------------------------------------

星期：　4                                      2

====================================================================

年份：201(601,1001,…,2201)                  301(701,1101,…,2301)

--------------------------------------------------------------------

星期：  0                                      5



可以看出，每隔四个世纪，这个星期就重复一次。假如我们把301(701,1101,…,2301)年3月1日的星期数看成是-2（按数论中对余数的定义，-2和5除以7的余数相同，所以可以做这样的变换），那么这个重复序列正好就是一个4,2,0,-2的等差数列。据此，我们可以得到下面的计算每个世纪第一年3月1日的星期的公式：



W = (4 - C mod 4) * 2 - 4．                                              (6)



式中，C是该世纪的世纪数减一，mod表示取模运算，即求余数。比如，对于2001年3月1日，C=20，则：



W = (4 - 20 mod 4) * 2 - 4

  = 8 - 4

  = 4．



把公式(6)代入公式(5)，经过变换，可得：



(Y-1) + [(Y-1)/4] - [(Y-1)/100] + [(Y-1)/400] ≡ (4 - C mod 4) * 2 - 1

(mod 7)．                                                               (7)



因此，公式(5)中的(Y-1) + [(Y-1)/4] - [(Y-1)/100] + [(Y-1)/400]这四项，在计算每个世纪第一年的日期的星期时，可以用(4 - C mod 4) * 2 - 1来代替。这个公式写出来就是：



W = (4 - C mod 4) * 2 - 1 + [13 * (M+1) / 5] + d．                       (8)



有了计算每个世纪第一年的日期星期的公式，计算这个世纪其他各年的日期星期的公式就很容易得到了。因为在一个世纪里，末尾为00的年份是最后一年，因此就用不着再考虑“一百年不闰，四百年又闰”的规则，只须考虑“四年一闰”的规则。仿照由公式(1)

简化为公式(2)的方法，我们很容易就可以从式(8)得到一个比公式(5)更简单的计算任意

一天是星期几的公式：



W = (4 - C mod 4) * 2 - 1 + (y-1) + [y/4] + [13 * (M+1) / 5] + d．       (9)



式中，y是年份的后两位数字。



如果再考虑到取模运算不是四则运算，我们还可以把(4 - C mod 4) * 2进一步改写成只含四则运算的表达式。因为世纪数减一C除以4的商数q和余数r之间有如下关系：



4q + r = C，



其中r即是 C mod 4，因此，有：



r = C - 4q

  = C - 4 * [C/4]．                                                     (10)



则



(4 - C mod 4) * 2 ＝ (4 - C + 4 * [C/4]) * 2

                  ＝ 8 - 2C + 8 * [C/4]

                  ≡ [C/4] - 2C + 1 (mod 7)．                           (11)



把式(11)代入(9)，得到：



W = [C/4] - 2C + y + [y/4] + [13 * (M+1) / 5] + d - 1．                 (12)



这个公式由世纪数减一、年份末两位、月份和日数即可算出W，再除以7，得到的余数是几就表示这一天是星期几，唯一需要变通的是要把1月和2月当成上一年的13月和14月，C和y都按上一年的年份取值。因此，人们普遍认为这是计算任意一天是星期几的最好的公式。这个公式最早是由德国数学家克里斯蒂安·蔡勒（Christian Zeller, 1822-1899）在1886年推导出的，因此通称为蔡勒公式（Zeller’s Formula）。为方便口算，式中的[13 * (M+1) / 5]也往往写成[26 * (M+1) / 10]。



现在仍然让我们来算2004年5月1日的星期，显然C=20，y=4，M=5，d=1，代入蔡勒公式，有：



W = [20/4] - 40 + 4 + 1 + [13 * (5+1) / 5] + 1 - 1

  = -15．



注意负数不能按习惯的余数的概念求余数，只能按数论中的余数的定义求余。为了方便计算，我们可以给它加上一个7的整数倍，使它变为一个正数，比如加上70，得到55。再除以7，余6，说明这一天是星期六。这和实际是一致的，也和公式(2)计算所得的结果一致。



最后需要说明的是，上面的公式都是基于公历（格里高利历）的置闰规则来考虑的。对于儒略历，蔡勒也推出了相应的公式是：



W = 5 - C + y + [y/4] + [13 * (M+1) / 5] + d - 1．                      (13)



这样，我们终于一劳永逸地解决了不查日历计算任何一天是星期几的问题。

x&(x-1)

来源： 原文链接

---

昨天在淘宝招聘会上遇到的这道笔试题：求下面函数的返回值 -- 统计1的个数

int func(int x)
{
    int countx = 0;
    while(x)
    {
        countx++;
        x = x&(x-1);
    }
    return countx;
}

假定x = 9999
10011100001111
答案: 8

思路: 将x转化为2进制，看含有的1的个数。
注: 每执行一次x = x&(x-1)，会将x用二进制表示时最右边的一个1 变为0，因为x-1将会将该位(x用二进制表示时最右边的一个1)变为0。

判断一个数(x)是否是2的n次方
-------------------------------------

#include <stdio.h>

int func(int x)
{
    if( (x&(x-1)) == 0 )
        return 1;
    else
        return 0;
}

int main()
{
    int x = 8;
    printf("%d\n", func(x));
}

注:
(1) 如果一个数是2的n次方，那么这个数用二进制表示时其最高位为1，其余位为0。
(2) ==优先级高于&

运行级别及Ubuntu启动进入文本模式

Update 20111028 以前转载的内容可能只适用于某个版本（至少Ubuntu 9.10就不适用了），又找到一些方法，经试用可行，记录在此。 来源：ubuntu 开机启动终端 字符模式 文本模式 注意　debian类系统的启动级别和往常的redhat等不同 rc0表示关机rc6表示重启 rc1表示单用户模式 rc2-rc4表示多用户模式 （ 0　关机 1　单用户模式 2　不带网络的多用户模式 3　带网络的多用户，也就是所谓的纯字符模式 4　保留，用户可以自给定义 5　图形界面的多用户模式 6　重起系统 ） 所以如果你想要启动到终端的话 你只需要关闭gdm的服务 我介绍一个简单的方法 代码: sudo apt-get install sysv-rc-conf sudo sysv-rc-conf 然后在里面找到一个叫做gdm的服务，别且在所有级别关闭它 然后q就ok了 找到的第二种方法 用nano编辑 /etc/X11/default-display-manager,把/usr/sbin/gdm注释掉,即在前面加个#号,改成#/usr/sbin/gdm,然后在加一行false这样保存既可. 完整的是这样： #/usr/sbin/gdm false 修改后重启，这样启动就是字符界面了。 找到的第三种方法 # 0 - halt (Do NOT set initdefault to this) 关机(不要设置为默认) # 1 - Single user mode 单用户模式 # 2 - Multiuser, without NFS (The same as 3, if you do not have networking) 多用户模式，但不支持NFS # 3 - Full multiuser mode 完全的多用户模式 # 4 - unused 没用到 # 5 - X11 图形界面 # 6 - reboot (Do NOT set initdefault to this) 重启(不要设置为默认) RedHat中要改变启动级别，只要修改/etc/inittab。Ubuntu有点不一样，网上的方法也很多，试过其中一种。 　　You need to open the /etc/default/grub file, locate the following line: 　　GRUB_CMDLINE_LINUX_DEFAULT="quiet splash" 　　and change it to: 　　GRUB_CMDLINE_LINUX_DEFAULT="quiet splash text" 　　update-grub 即编辑/etc/default/grub文件，将GRUB_CMDLINE_LINUX_DEFAULT="quiet splash"改为GRUB_CMDLINE_LINUX_DEFAULT="quiet splash text"，然后更新一下grub。 方法三还可以。如果想用这种方法永远启动到字符终端模式，则可以修改/boot/grub/grub.cfg，在相应的位置添加txt参照即可。但是grub.cfg是 自动生成的，所有的在里面的修改都可能被其它的操作覆盖掉，比如update-grub命令，如果不想被覆盖，则修改/etc/default/grub 把 GRUB_CMDLINE_LINUX_DEFAULT="quiet splash" GRUB_CMDLINE_LINUX="" 改成 GRUB_CMDLINE_LINUX_DEFAULT="text" GRUB_CMDLINE_LINUX="" 然后再运行一下update-grub命令，它会自动添加上text参数到内核参数中。 说明： 1，无论使用什么方式启动到字符终端模式，你都可以使用命令startx命令来启动Xwindow 2，在10.04 lucid 下测试成功 参数的含义（个人猜测，没有在网上找到相关内容） quiet 阻止内核输入到命令行 splash 显示启动画面，如ubuntu logo text 启动到字符终端模式 我的同时写上quiet 和text就起不来，停在checking battery status 下面不动了，也可以我为了测试等待的时间不够长，虽然不动了，可以按CTRL+ALT+DELETE重新启动。 文本与桌面模式切换： 文本模式登陆后，在普通用户权限下执行startx，进入到桌面模式。 一定要在普通用户权限下，root权限下startx，桌面模式都是默认设置，不加载个人设置！ 桌面到文本的切换： Ctrl+Alt+F1，切到文本界面，执行Ctrl+c，结束掉刚才启动的X server！

---

以下为旧文 来源：未知 Linux系统有7个运行级别(runlevel)  (注意下文，debian系衍生的linux 运行级不一样) 运行级别0：系统停机状态，系统默认运行级别不能设为0，否则不能正常启动 运行级别1：单用户工作状态，root权限，用于系统维护，禁止远程登陆 运行级别2：多用户状态(没有NFS) 运行级别3：完全的多用户状态(有NFS)，登陆后进入控制台命令行模式 运行级别4：系统未使用，保留 运行级别5：X11控制台，登陆后进入图形GUI模式 运行级别6：系统正常关闭并重启，默认运行级别不能设为6，否则不能正常启动 运行级别的原理： 1。在目录/etc/rc.d/init.d下有许多服务器脚本程序，一般称为服务(service) 2。在/etc/rc.d下有7个名为rcN.d的目录，对应系统的7个运行级别 3。rcN.d目录下都是一些符号链接文件，这些链接文件都指向init.d目录下的service脚本文件，命名规则为K+nn+服务名或S+nn+服务名，其中nn为两位数字。 4。系统会根据指定的运行级别进入对应的rcN.d目录，并按照文件名顺序检索目录下的链接文件      对于以K开头的文件，系统将终止对应的服务      对于以S开头的文件，系统将启动对应的服务 5。查看运行级别用：runlevel 6。进入其它运行级别用：init N 7。另外init0为关机，init 6为重启系统 ____________________________________________________________________________________________ 因为debian 系衍生出来的linux 一向是没有使用/etc/inittab 作为登入状态文档来使用的。但是虽然没有系统默认没有这个文件，但是你可以自己建一个inittab文件。 因为从/etc/event.d/中的rc-default文件中代码可以看出： script runlevel --reboot || true if grep -q -w -- "-s\|single\|S" /proc/cmdline; then telinit S elif [ -r /etc/inittab ]; then RL="$(sed -n -e "/^id:[0-9]*:initdefault:/{s/^id://;s/:.*//;p}" /etc/inittab || true)" if [ -n "$RL" ]; then telinit $RL else telinit 2 fi else telinit 2 fi end script 系统会首先搜寻inittab文件，如果不存在，那么将运行在2级别上。所以你可以自己建个inittab文件，或者把相应的telinit 2 改为 telinit X（你想要运行的级别） 转到kubuntu之前曾经学习了一下，了解到ubuntu在6.10开始用upstart替代init，主要脚本都在/etc/event.d下面，默认情况下/etc下没有inittab文件。 刚装上kubuntu时候专门到/etc/event.d下看了一下，特别注意到rc-default这个脚本，里面有一段内容: elif [ -r /etc/inittab ] then 说明默认情况下inittab虽然不存在，但是用户建立的inittab还是会被注意到的。然后又经别人的指点看了一下/usr/share/doc/upstart/下面的文档，其中README.Debian中有这么一段内容： 这就给我这样一个印象，即虽然ubuntu用upstart替代init，但还是和init保持兼容。 今天正好需要将系统直接启动到字符界面下，即不启动kdm。 edit the /etc/inittab file 那就试试自建一个inittab文件，并按照以前的习惯写入一行id:3:initdefault: ，保存后重新启动，结果发现毫无变化，依然启动到桌面，有点纳闷，难道inittab不起作用？在终端里输入runlevel检查当前状态，显示 N 3，说明inittab有效果，那是什么原因呢？ 将刚才建立的inittab移除，将系统恢复到之前的状态并重新启动，再用runlevel检查，显示 N 2，说明ubuntu系统的default runlevel可能是2，这和我以前的常识有些冲突，看来又需要学习了。 先去分别查看/etc/rc2.d至rc5.d下的内容，发现基本一致，都启动了kdm。这与其他的linux发行版不太一致，通常runlevel 3是Multi user mode，即直接登录到字符界面；而runlevel 5是Multi user mode with GUI，即登录到图形界面。 后来在Debian的FAQ里面搜索到这样的内容： 0(halt the system) 1(single-user mode) 2through5(various muli-user modes),and 6(reboot the system) 小区别就在这里了，看来debian以及衍生出来的发行版，如ubuntu的default runlevel确实是2，而且id 2至5都是一样的。 真相大白，再次建立inittab，写入id:3:initdefault: ，然后进入/etc/rc3.d，重命名S30gdm，重新启动系统，如愿以偿进入字符界面。 

在VC9.0中实现C++模板类头文件和实现文件分离的方法

来源：原文链接

---

如何实现C++模板类头文件和实现文件分离，这个问题和编译器有关。

引用<>里的观点：1）标准C++为编译模板代码定义了两种模型：“包含”模型和“分别编译”模型。2）所有编译器都支持“包含”模型

，某些编译器支持“分别编译”模型。

问题的提出：（帖子在：http://topic.csdn.net/u/20101215/15/f4f270f2-f0f9-4c5f-8765-1bfde2aeebbf.html）

第一种方法：按C++primer中的“包含”模型，在定义模板类的头文件中的末行用语句：#include "template_compile.cpp"

在类模板头文件template_compile.h中：


template  
class base
{
public:
    base() {};
    ~base() {};
    T add_base(T x,T y);
};
#include "template_compile.cpp"


在类模板的实现文件template_compile.cpp中：


template  
T base::add_base(T x,T y)  
{
    return x+y;
}


在使用模板的测试文件use_template.cpp中：

#include  
#include "template_compile.h"
using namespace std;
void main()
{
...
}


这种方法不能通过编译，"template_compile.cpp"文件不能"看见"“template_compile.h"文件。

然而：如果我把类模板的实现文件里代码放在类模板的头文件中，注释掉：#include "template_compile.cpp"，编译和运行不会有任何错误。理论上”把类模

板的实现文件里代码放在类模板的头文件中“和”在定义模板类的头文件中的末行用语句：#include "template_compile.cpp" “是一致的，但编译器就是通不

过。

实验证明：VC9.0不支持C++primer中所说的“包含”模型。

第二种方法：bruceteen提出的：使用define

在类模板头文件template_compile.h中：


template  
class base
{
public:
  base() {};
  ~base() {};
  T add_base(T x,T y);
};
#define xxx
#include "template_compile.cpp"


在类模板的实现文件template_compile.cpp中：


#ifdef xxx
template  
T base::add_base(T x,T y)  
{
  return x+y;
}
#endif


测试文件不变。

实验证明：在VC9.0中，这种方法可以实现类模板头文件和实现文件的分离

方法三：

在类模板头文件template_compile.h中：


template  
class base
{
public:
    base() {};
    ~base() {};
    T add_base(T x,T y);
};


在类模板的实现文件template_compile.cpp中：


#include "template_compile.h"
template  
T base::add_base(T x,T y)  
{
    return x+y;
}


在使用模板的测试文件use_template.cpp中：使用#include "template_compile.cpp"


#include  
#include "template_compile.cpp"
using namespace std;
void main()
{
...
}


实验证明：在VC9.0中，这种方法可以实现类模板头文件和实现文件的分离。

另外实验证明：VC9.0不支持“分别编译”模型。

“火柴棍式”程序员面试题

来源：原文链接

---

有时候，有些面试题是很是无厘头，这不，又有一个，还记得小时候玩的的"火柴棍游戏"吗，就是移动一根火柴棍改变一个图或字的游戏。程序面试居然也可以这么玩，看看下面这个火柴棍式的程序面试题吧。

下面是一个C程序，其想要输出20个减号，不过，粗心的程序员把代码写错了，你需要把下面的代码修改正确，不过，你只能增加或是修改其中的一个字符，请你给出三种答案。


int n = 20;
for(int i = 0; i < n; i--){
printf("-"); }


不要以为这题不是很难，我相信你并不那么容易能找到3种方法。我觉得，如果你能在10分钟内找出这三种方法，说明你真的很聪明，而且反应很快。当然，15分钟内也不赖。不过，你要是30分钟内找不到三种方法，当然，不说明你笨了，最多就是你的反应还不够快。嘿嘿。就当是玩玩吧。

下面是我的答案：

 
//第一种解法：在for循环中给n加一个负号 
for(int i = 0; i < -n; i--)  
//第二种解法：把 n 初始化成 -20 
int n = -20;  
//第三种解法：把for循环中的 i 初始化成40 
for(int i = 40; i < n; i--) 

不过，我要告诉你，以上这些答案都不对（我就知道你会偷看答案的），不过，顺着这些思路走很接近了。呵呵。

下面是正确答案——

//第一种解法：在for循环中给 i 加一个负号
for(int i = 0; -i < n; i--)

//第二种解法：在for循环中把 i-- 变成 n--
for(int i = 0; i < n; n--)

//第三种解法：把for循环中的 < 变成 +
for(int i = 0; i + n; i--)

其它相关的变种题如下：

• 通过修改、增加一个字符，让其输出21个减号
• 通过修改、增加一个字符，让其只输出1个减号
• 通过修改、增加一个字符，让其不输出减号

（全文完）

打印质数的各种算法

来源：原文链接

---

打印质数的算法应该是学习计算机编程的一个经典的问题，在这里想给大家展示一些方法，相信这些方法会对你的编程有一定的启发作用。请你注意几点，

• 实际应用和教学应用有很大的差别。
• 最后的那个使用编译时而不是运行时的方法大家可以重点看看。

教科书的示例

首先，先给一个教科书的示例。下面这个示例应该是教科书（至少是我上大学时的教科学）中算法复杂度最好的例子了。其想法很简单，先写一个判断是否是质数的函数isPrime()，然后从1到n分别调用isPrime()函数来检查。检查是否是质数的算法是核心，其简单的使用从2到n的开根的数作为除数。这样的算法复杂度几乎是O(n*log(n))，看上去不错，但其实很不经济。

#include <iostream> 
using namespace std;  
bool isPrime(int nr) {
     for (int d = 2; (d * d) <= (nr + 1); ++d){
         if (!(nr % d)){
             return false;
         }
      }
     return true;
 }  

int main (int argc, char * const argv[]) {
     for (int i = 0; i < 50; ++i){
         if (isPrime(i)){
             cout << i << endl;
         }
     }
 } 

较好的算法

我们知道，我们的算法如果写成线性算法，也就是O(n)，已经算是不错了，但是最好的是O(Log(n))的算法，这是一个级数级的算法，著名的二分取中（Binary Search）正是O(Log(n))的算法。通常来说，O(Log(n))的算法都是以排除法做为手段的。所以，找质数的算法完全可以采用排除法的方式。如下所示，这种算法的复杂度是O(n(log(logn)))。
示例：打印30以内的质数
一、初始化如下列表。

2  3  4  5  6  7  8  9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30

二、把第一个数（2）取出来，去掉所有可以被2整除的数。

2  3     5     7     9    11    13    15    17    19    21    23    25    27    29

三、取第二个数（3），去掉所有可以被 3整除的数。

2  3     5     7          11    13          17    19          23    25          29

四、取第三个数（5），因为4已经被去除了，再去掉所有可以被5整除的数。

2  3     5     7          11    13          17    19          23                29

接下来的数是7，但是7的平方是49，其大于了30，所以我们可以停止计算了。剩下的数就是所有的质数了。

实际应用的算法

实际应用中，我们通常不会使用上述的两种算法，因为那是理论学院派的算法。实际中的算法是，我把质数事先就计算好，放在一个文件中，然后在程序启动时（注意是在启动时读这个文件，而不是运行时每调用一次就读一次文件），读取这个文件，然后打印出来就可以了。如果需要查找的化，二分查找或是hash表查找将会获得巨大的性能提升。当然，这样的方法对于空间来说比前面两个都要消耗得大，但是你可以有O(log(n))或是O(1)的时间复杂度。
所以，我想在这里提醒大家——实际和理论的的方法很不一样的，千万不要读书读成书呆子。在游戏编程的世界里，大量的数据都不是运行计算的，而都是写在文件中的。比如，一个火焰效果，一个人物跑动的动作，都是事先写在文件中的。

使用编译时而不是运行时

下面这个例子（本例参考于这里）你需要注意了，这是一个高级用法，使用模式来在编译时计算质数，而不是运行时。这种技术使用了C++编译器对模板的特化时的处理来生成自己相要的结果。这种方法在技术上是相当Cool的，但并不一定实用，这里只是想像大家展示这种用法。这是C++的最骨灰级的用法了。
请看下面的两个模板类，第一个模板以递归的方式检查是否是质数，第二个方法是递归的退出条件（当N=1时），对于模板的重载，请参看相关的C++书籍。

template<int N, int D = N - 1> 
struct isPrime {
     enum {
         result = (N % D) && isPrime<N, D-1>::result
     };
 };

template<int N> 
struct isPrime<N, 1> {
     enum {
         result = true
     };
 }; 

于是，通过这个模板，我们可以使用下面的代码来检查是否是质数：

if (isPrime<3>::result)
     cout << "Guess what: 3 is a prime!";
 

下一步，我们需要打出一个区间内的质数，所以，我们需要继续设计我们的print模板。

template<int N, bool ISPRIME> 
struct printIfPrime {
     static inline void print() {} 
};  
template <int N> 
struct printIfPrime<N, true> {
     static inline void print() {
         std::cout << N << endl;     
     }
}; 

从上面的代码中，我们可以看到，我们的第一个实际是什么也没做，而第二个有输出，注意第二个的模板参数中有一个true，其意味着那个质数的判断。于是我们就可以给出下面的代码来尝试着打印出一段区间内的质数：（请不要编译！！因为那会让编译器进入无限循环中，原因是printPrimes会不停地调用自己永不停止）

template<int N, int MAX> 
struct printPrimes {
     static inline void print()     {
         printIfPrime<N, isPrime<N>::result>::print();
         printPrimes<N + 1, MAX>::print();
     }
 };
 

为了避免这个问题，你需要再加一个模板类，如下所示。这样当N变成MAX的时候，递归就结束了。

template<int N> 
struct printPrimes<N, N> {
     static inline void print() {
         printIfPrime<N, isPrime<N>::result>::print();     
     } 
}; 

最后，让我们来看看最终的调用：

int main (int argc, char * const argv[]) {
     printPrimes<2, 40>::print();
     return 0;
 } 

这个方法很NB，但是有两个问题：

• 比较耗编译时间。
• 不能在运行时输入MAX的值。

不过，相信这种玩法会启动你很多的编程思路。
（全文完)

C++中数组参数详解

在C++中，数组永远不会按值传递。它是传递第一个元素（准确地说是第0个）的指针。

例如，如下声明：

  void putValues(int[10]);

被编译器视为：

  void putValues(int*);

数组的长度与参数声明无关。因此，下列三个声明是等价的：

  void putValues(int*);

  void putValues(int[]);

  void putValues(int[10]);

因为数组被传递为指针，所以这对程序员有两个含义：

1、在被调函数内对参数数组的改变将被应用到数组实参上而不是本地拷贝上。当用作实参的数组必须保持不变时，程序员需要保留数组的拷贝。函数可以通过把参数类型声明为const来表明不希望改变数组元素：

  void putValues(const int[10]);

2、数组长度不是参数类型的一部分。函数不知道传递给它的数组的实际长度，编译器也不知道，当编译器对实参类型进行参数类型检查时，并不检查数组的长度。

例如：

void putValues(int[10]); //视为int*

int main()

{

    int i, j[2];

    putValues(&i); //ok:&i是int*; 潜在的运行错误

    putValues(j);  //ok:j被转换成第0个元素的指针

    // 实参类型为int*:潜在的运行错误

    return 0;

}

 

参数的类型检查只能保证putValues()的再次调用都提供了int*型的实参。类型检查不能检验实参是一个10元素的数组。

习惯上，C风格字符串是字符的数组，它用一个空字符编码作为结尾。但是所有其他类型，包括希望处理内含字符的字符数组，必须以某种方式在向函数传递实参时使其知道它的长度。一种常见的机制是提供一个含有数组实参的长度的额外参数。例如：

 void putValues(int[], int size);

int main()

{

    int i,j[2];

    putValues(&i, 1);

    putValues(j, 2);

    return 0;

}

另外一种机制是将参数声明为数组的引用。当参数是一个数组类型的引用时，数组长度成为参数和类型的一部分，编译器检查数组实参的长度与在函数参数类型中指定的长度是否匹配。

// 参数为10个int的数组

// parameter is a reference to an array of 10 ints

void putValues(int (&arr)[10]);

int main()

{

    int i, j[2];

    int a[10];

    putValues(i); // 错误：实参不是10个int的数组

    putValues(j); // 错误：实参不是10个int的数组

    putValues(a); // 正确

    return 0;

}

因为数组的长度现在是参数类型的一部分，所以putValues()的这个版本只接受10个int的数组。这限制了可以作为实参被传递给putValues()的数组的种类。但是，它也使函数的实现更加简单。