程序执行的时间与估计的渐近时间出现了很大的出入，程序的结构如下：

float maxsubarr3(int l,int u){
    ......//省略
    return max(lmax+rmax,max(maxsubarr3(l,m),maxsubarr3(m+1,u)));
}

问题在max定义上，我用宏定义了max，如下：

#define max(a,b) ((a)>(b)?(a):(b))

忽视了宏替换的一个缺陷：作为参数的表达式重复计算了两次。而且本身参数是递归定义函数，时间的开销就会增长巨大，导致了在数量级到达5的时候，程序就无法运行了。

明确了问题所在，那就可以更正了。解决的方法：

1.将宏定义改为函数定义。

float max(float a,float b){
    return a>b?a:b;
}

2.更正宏定义的方式。

 #define max(a,b) \
   ({ __typeof__ (a) _a = (a); \
       __typeof__ (b) _b = (b); \
     _a > _b ? _a : _b; })

 使用函数定义后，bug就没了。

参考：

http://stackoverflow.com/questions/3437404/min-and-max-in-c

----------------以下仅提供了解体的思路，代码未完善，上机时有些题可以直接算出来的------------------------------

1.求两个正整数的最大公约数.

def gcd(a,b):
    while b:
        a,b=b,a%b
    return a

2.令S=s1s2s3...s2n是一个符合规范的括号字符串。可以采用两种方式对S编码：
（1）一个整数序列P=p1p2...pn，其中pi是字符串S中第i个右括号前左括号的个数（记为P序列）；
（2）一个整数序列W=w1w2...wn，其中wi是字符串S中第i个右括号往左数遇到和它相匹配的左括号时经过的左括号个数（记为W序列).
要求：对于一个符合规范的括号字符串，将其P序列转化为W序列.

def translate( a ):
    #stack
    s=[]
    b=[]
    for i in range(len(a)):
        if i==0:
            for j in range(a[i]):
                s.append('(')
                b.append(1)
            s.append(')')
            b.append(1)
        else:
            for j in range(a[i]-a[i-1]):
                s.append('(')
                b.append(1)
            s.append(')')
            b.append(1)
    c=[]
    for m,v in enumerate(s):
        count=0
        if v==')':
            for n in range(m-1,-1,-1):
                if s[n]=='(':
                    count+=1
                if s[n]=='(' and b[n]==1:
                    b[n]=0
                    break;
            c.append(count)

    for e in c:
        print e ,
    print '\n-----------'

3.有n个半圆形金属条c1,c2,c3...cn,半圆直径分别为l1,l2,l3...ln.(如图)问可否将这些金属环首尾相接形成一个大环.
要求:输入3组直径数据(组内数据之间已用逗号隔开,每组数据间已用分号隔开),判断这3组金属条各自是否可以首尾相接.针对每组数据，如果可以，输出Y，否则输出N.

def isconnect(a):
    m=max(a)
    s=0
    first=True
    for e in a:
        if e!=m:
            s+=e
        if e==m and first:
            first=False
        elif e==m and not first:
            s+=e
    if m>s:
        return False
    else:
        return True

4.设有一个由0和1组成的字符串b1b2……bn（bi为0或1）.由该字符串可以生成一个旋转矩阵B如下:
b1     b2 …  bN−1  bN （第一行为原字符串，以下n-1行均由其前一行的串循环左移一位构成）
b2     b3 …  bN      b1  
…
bN−1 bN …  bN−3  bN−2
bN     b1 …  bN−2  bN−1
矩阵B的每一行可视为一个二进制数.对这n个二进制数由小到大排序形成矩阵C.
比如有一个二进制串00110，生成的旋转矩阵为
00110
01100
11000
10001
00011
对其排序得
00011（第一行的00011<第二行的00110<第三行的01100<......）
00110
01100
10001
11000
现在设有一个二进制串r经以上变换及排序后生成矩阵C1.
要求:输入一个二进制串，如果将其视为C1的最后一列,推测并输出C1的第一行数据.
例:输入10010       程序需要输出00011

def bwt(s):
    assert '\0' not in s, "s CAN NOT contains ('\0')"
    s+='\0'
    table=sorted(s[i:]+s[:i] for i in range(len(s)))
    r=[row[-1] for row in table]
    return ''.join(r)

def ibwt(r):
    table=['']*len(r)
    for i in range(len(r)):
        table=sorted(r[i]+table[i] for i in range(len(r)))
    s=[row for row in table if row.endswith('\0')][0]
    return s.rstrip('\0')

　我收到了很多年轻开发人员写给我的邮件，希望可以提升自己的编程能力。我肯定不是第一个讨论这个话题的人，所以我不确定还可以说出什么新意。然而，我认为，这里还是有几个重要点，非常值得列出：

• 要跟其他开发者一起工作。我们正处在科技史上的黄金时期，这是第一次，身处何地，雇主是谁变得不那么重要。只要你的网络带 宽足够，你就可以与身处地球任何位置的另一位开发者搭档共同编写代码。越来越多我认识的资深开发者都在贡献自己的时间分享这样的知识。我朋友Evan Light有“开放办公时间”[2]，而且还在开发一个网站帮助 Rubyists[1] 搭档。我也这样做了好一阵了。想要研究FLOSS[3]代码？发邮件给我，我们会把事情安排好。

• 阅读经典书籍。如《代码大全》、《程序员修炼之道》、《程序设计实践》、《设计模式》等。

• 要读 WikiWiki （有时又叫做 WardsWiki）。这一点非常重要。有时我觉得，在我的学习遇到瓶颈时，我就是通过浏览WikiWiki 而得以学到所有我真正需要的东西的。

• 要阅读他人编写的代码。为GitHub 喝彩！如果你想以编撰得更好的作品为开始而你又对 Ruby、有所了解，那么就试一试解决Ruby Quiz上的问题。（关于这个话题，Alan Skorkin 写过一篇很全面的文章：《阅读优秀代码是提高开发人员修为的一种捷径》。）

• Ruby，一种为简单快捷对象导向编程（面向对象程序设计）而创的脚本语言，由日本人松本行弘开发，遵守GPL协议和Ruby License。Ruby的作者认为Ruby > Smalltalk Perl，表示Ruby是一个语法像Smalltalk一样完全面向对象、脚本执行、又有Perl强大的文字处理功能的程序语言。其它特色包括： 运算符重载 自动垃圾回收、在Windows上，载入DLL 巨大的标准库。

• 加入本地用户组。如果没有这样的群，那就创建一个，然后开始交流。我不在意你是一个多么差劲的菜鸟。要想使你全面了解一个问题，再没有比这更好的方法了。

• 开一个博客。不要担心自己会成为异类。一些最有用的博客其实主要记录了一个程序员的经验和错误以及他们是如何克服困难。反思是学习的最重要的一部分，而写作则会帮助你反思。并且，在你思考之前，你又会从其他程序员那得到反馈。

• 我相信你已经听说过这一点了：为一个开源项目提交补丁。

• 用掷硬币的方式来作决定。正面朝上就选择 Vim，背面朝上就选Emacs。开始学习容易上手的编辑器。这两种中的任何一种都会在你剩余的编程生涯中一直与你同在。强大、灵活的工具能使优秀程序员更加优秀。（编注：看来国外很多程序员都在用Vim或Emacs，Akash Manohar 在《写给即将入行的程序员的一封信》这篇文章中，也是推荐这些工具。）

• 学习多种编程语言。但首先你得学好一编种程语言。你需要一种可以使你得到灵感并且快速掌握的在一天内迅速地 写出第一个版本的编程语言，从而不用花费大量的时间去学习你会很容易忘记的语言细节。然而，一旦你已经掌握了这门语言，你就要去学习新的语言，来挑战所有 你从之前所学习的语言中学到的假设。要选择风格完全不同的编程语言。我所看过的一本书《七周掌握七门语言》 中就对编程思维模型进行了全面、广泛的概括。（相关阅读：《学习不同编程语言的重要性》）

• 为你所使用的编程语言和平台建立邮件列表。人们有时会忘记在博客、Hacker News和推特以外还有很多讨论是非常有益的。跟其它场合比起来邮件列表通常是文明而有用的工具。

• StackOverflow 是你的良师益友。

• 不要花费太多的时间去为某物找寻“最好”的工具。我过去常常会花费好几天或几个星期，去试着为我即将开始的项目寻找最好的框架，以致我的工作进度停滞不前。不要掉进这个陷阱里。当你已经是个相对有经验的开发人员时，选择那些有很多人在用的语言和框架。在你遇到困难时，知道如何继续下去比选择完美的工具要重要。

• 寻找练习的机会。

• 当然，还有一点就是：练习、练习、练习。上班时写代码。在家写代码。练习 code katas 。编程与其它技能一样：说到底，它的本质还是练习。

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

　编注：Rubyist 是指那些对Ruby的关心程度超过常人的人。
　编注：“开放办公室时间”是美国大学的传统，作法是学校每周开放办公室数小时，学生不需事先预约就能和老师面谈。
　编注：Free/Libre/Open Source Software 免费/自由/开源软件。

译文出处：伯乐在线 - 职场博客 - 程序员
译文链接：http://www.jobbole.com/entry.php/1419
原文：Avdi Grimm　　翻译：敏捷翻译 - 张秀君

如果你的机器是windows7和arch双启动的系统，可能windows与arch时间上出现不同步的问题。这是由于windows与linux对待硬件时钟不一致，即每次操作系统启动时读取硬件时钟，计算系统时间的方法不一致。这里介绍两个概念，

      *硬件时钟是bois中的时间；

      *系统时间是操作系统kernel中的时间。

下面介绍操作系统计算出自身系统时间的两种方式：

      *把系统硬件时间当作本地时间(local time)，即操作系统中显示的时间跟BIOS中显示的时间是一样的

      *把硬件时间当作 UTC，操作系统中显示的时间是硬件时间经过换算得来的

注：协调世界时，又称世界标准时间或世界协调时间，简称UTC，在中国大陆的本地时间比UTC快8小时，就会写作UTC+8。

有了以上基础，就可以设置windows7和arch3了，两个系统必须使用相同的方式，要么是UTC，要么是localtime。

1.windows 和arch 均采用UTC。

   arch设置：在/etc/rc.conf里面设置：

HARDWARECLOCK="UTC"
TIMEZONE="Shanghai/Asia"

 windows设置：新建chTimetoUTC.reg,输入以下内容，运行。

Windows Registry Editor Version 5.00
[HKEY_LOCAL_MACHINE\SYSTEM\CurrentControlSet\Control\TimeZoneInformation]
     "RealTimeIsUniversal"=dword:00000001

然后，在bios里面设置正确的硬件时钟就okay了。

2.windows和arch均采用localtime设置。

   arch设置：在/etc/rc.conf里面设置：

HARDWARECLOCK="UTC"
TIMEZONE="Shanghai/Asia"

  windows设置：windows默认采用，不用设置。

注：*RealTimeIsUniversal = 0 Windows使用本地时间。   *RealTimeIsUniversal = 1 Windows使用UTC时间。

选择使用那种设置，取决于我们自己，在arch wiki里面建议使用UTC，对localtime的描述为：

Warning: 使用 localtime 将导致很多已知的不可修复的BUG.尽管,没有计划放弃对localtime的支持。

我自己的观点是：在系统安装时选择localtime会省去很多的麻烦。

参考：

【1】http://forum.ubuntu.org.cn/viewtopic.php?t=256151

【2】http://space.itpub.net/23137730/viewspace-661609

【3】https://wiki.archlinux.org/index.php/Beginners%27_Guide/Preface

ABS:arch build system , a port-like system.
ABS-----------|ABS tree           :ABS的目录结构
                     |PKGBUILDS    ：bash脚本，包含了软件代码的URL
                     |makepkg          ：根据PKGBUILDS，产生二进制的安装包pkg.tar.gz
                     |pacman            :   包管理
                     |AUR                 ：用户软件仓库
1.ABS的安装
   #pacman -S abs
2.ABS的配置
   #vim /etc/abs.conf
3.建ABS tree
   #abs
4.建build目录
 $mkdir -p $HMOE/abs
5.ABS方式编译软件, 举例，安装gksu为例

复制port 到Build目录

$ sudo cp -r /var/abs/extra/gksu ~/abs

写PKGBUILD文件

$ vim PKGBUILD

产生可安装的二进制文件

$ makepkg -s

root安装产生的二进制文件

# pacman -U gksu-2.0.2-3-i686.pkg.tar.xz

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

pacman : arch的包管理软件。
配置位置：/etc/pacman.conf
使用：
1.安装
   # pacman -S package_name1 package_name2 …
2.卸载
  # pacman -R package_name
3.升级软件包
  # pacman -Syu
4.查询
从库查询软件：     $ pacman -Ss string1 string2 …
从本地查询软件：  pacman -Qs string1 string2 …
5.安装本地包
   # pacman -U /path/to/package/package_name-version.pkg.tar.xz
详细的使用说明：man pacman

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

yaourt：是pacman的一个外壳，而且支持AUR。

yaourt的使用与pacman的用法基本相同。

        archlinux的详细安装过程，在这里就不赘述了，在https://wiki.archlinux.org/index.php/Beginners%27_Guide有详细的描述，在这里记录一下自己安装过程出现的问题。

1.我使用的U 盘安装，使用了×nix的方式：
# dd if=archlinux-2010.05-{core|netinstall}-{i686|x86_64|dual}.iso of=/dev/sdx
要注意：是sdx，而不是sdx1.［wiki中特别提到］。当时看着手机，漏了一些文字。

2.安装过程中的分区。
根据不同的用户机器情况，分区也不不同。wiki中提到了四种方式，特别注意：
Warning: 磁盘分区会毁掉原分区内的数据。强烈建议先备份重要的数据
我使用了第三种方式，由于原来的分区是安装fedora的，我还以为只是简单的把分区挂到对应的目录。没想到都给我格式化了，所以分区要注意，避免自己的数据遗失。

3.安装grub。

由于以前安装的fedora没有卸载，在fedora上覆盖安装arch，发现grub没有正确的安装。建议先保存文件，格式化一下分区，这样应该不容易出问题。如果因为因为没有正确的安装grub，导致grub无法引导系统启动，可参考https://wiki.archlinux.org/index.php/Grub，应该可以修复。

在安装arch的过程中出现了上面的问题，其中（2）影响最大，导致我在暑假的时候做的很多东西都没了；（3）顺道学了一下grub的知识。只要仔细的阅读文档，安装arch并不是很困难，不要想我这种小白犯了这么多错。

4.安装显卡。
机子是N卡，我安装了nvidia的私有驱动。https://wiki.archlinux.org/index.php/Nvidia。过程并不困难，可以直接用pacman安装。

5.gnome3安装。
在这里，犯了一个很fool的错误：以为只安装gnome-exra就好了。唉！没有安装gnome软件包，导致gnome启动不了，郁闷了很久。

6.日期和时间设置。

选择UTC还是localtime呢？推荐UTC，还是要仔细的设置一下,我设置成了UTC，但是在双系统下时间并不同步呀。

7.安装networkmanager，yaourt
参考英文wiki
 

      一、构建git仓库。

有两种取得 Git 项目仓库的方法。第一种是在现存的目录下,通过导入所有文件来创建新的 Git 仓库。第二种是从已有的 Git 仓库克隆出一个新的镜像仓库来。下面尝试第一种方法：

在项目目录下：

git init

     二、构建更新到仓库。

1.查看状态：

git status

刚新建的仓库是没有任何文件被跟踪的：

# On branch master
#
# Initial commit
#
# Untracked files:
#   (use "git add <file>..." to include in what will be committed)
#
#	__init__.py
#	__init__.pyc
#	apache/
#	bookmark_base/
#	manage.py
#	media/
#	settings.py
#	settings.pyc
#	template/
#	urls.py
#	urls.pyc
nothing added to commit but untracked files present (use "git add" to track)

2.跟踪新文件

git add  XXX

3.提交

git commit -m ""

       三、远程仓库。

git remote add origin git@github.com:username/Hello-World.git
git push origin master

文章来源：《pro git》作者：Scott Chacon
 

         版本控制软件(VCS)是软件设计师常会利用版本控制来追踪、维护源码、文件以及设定档等等的改动，并且提供控制这些改动控制权的程序。一般有3种：

1.本地。

2.集中式。

3.分布式。

           Git属于第三种，有以下的要点：

1. 直接快照,而非比较差异
Git 和其他版本控制系统的主要差别在于,Git 只关心文件数据的整体是否发生变化,而大多数其他系统则只关心文件内容的具体差异。Git记录的是每个版本文件的快照。

2.近乎所有操作都可本地执行
在 Git 中的绝大多数操作都只需要访问本地文件和资源,不用连网。但如果用 CVCS 的话,差不多所有操作都需要连接网络。因为 Git 在本地磁盘上就保存着所有有关当前项目的历史更新,所以处理起来速度飞快。

3.时刻保持数据完整性
在保存到 Git 之前,所有数据都要进行内容的校验和(checksum)计算,并将此结果作为数据的唯一标识和索引。换句话说,不可能在你修改了文件或目录之后,Git 一无所知。

4.多数操作仅添加数据
常用的 Git 操作大多仅仅是把数据添加到数据库。因为任何一种不可逆的操作,比如删除数据,要回退或重现都会非常困难。

5.三种状态
好,现在请注意,接下来要讲的概念非常重要。对于任何一个文件,在 Git 内都只有三种状态:已提交(committed),已修改(modified)和已暂存(staged)。已提交表示该文件已经被安全地保存在本地数据库中了;已修改表示修改了某个文件,但还没有提交保存;已暂存表示把已修改的文件放在下次提交时要保存的清单中。


安装

sudo apt-get install git-core git-gui git-doc

配置

1.用户信息
第一个要配置的是你个人的用户名称和电子邮件地址。这两条配置很重要,每次 Git 提交时都会引用这两条信息,说明是谁提交了更新,所以会随更新内容一起被永久纳入历史记录:

git config --global user.name "xx"
git config --global user.email xx@example.com

2.其他。

3.如果使用github还可能需要设置：

git config --global github.user username
git config --global github.token 0123456789yourf0123456789token

帮助

想了解 Git 的各式工具该怎么用,可以阅读它们的使用帮助,方法有三:

git help <verb>
git <verb> --help
man git-<verb>

文章来源：内容大多数来自《pro Git》。