posts - 403, comments - 310, trackbacks - 0, articles - 7
  BlogJava :: 首页 :: 新随笔 :: 联系 :: 聚合  :: 管理

APUE上的例程,稍微改了下,在进程开始和结束的时候会分别显示当前的PID和退出状态。
不支持参数
1. fgets命令从标准输入读入命令,当键入文件结束字符(通常是Ctrl+D)时进程结束
2. 以\0替换输入命令的最后一个字符,即去掉换行符,使得execlp能够处理
3. fork函数创建一个新进程,对父进程返回新的子进程的非负PID,对子进程返回0
4. 在子进程中,调用execlp以执行从标准输入读入的命令。fork和exec的组合产生了一个新进程
5. 新的子进程开始执行后,父进程等待子进程的终止,这一要求由waitpid实现
6. 执行这个程序后还可以在这个简易shell中创建新的自身的进程

#include <sys/types.h>
#include 
<sys/wait.h>
#include 
"ourhdr.h"

int main(void)
{
    
char    buf[MAXLINE];
    pid_t   pid;
    
int     status;

    printf(
"%% ");
    
while (fgets(buf, MAXLINE, stdin) != NULL)
    {
        buf [strlen(buf) 
- 1= 0;

        
if ( (pid = fork()) < 0)
            err_sys(
"fork error");
        
else if (pid == 0)
        {
            execlp(buf, buf, (
char *0);
            err_ret(
"couldn't execute: %s", buf);
            exit(
127);
        }

        printf(
"*** %d ***\n", status);

        
/* parent */
        
if ( (pid = waitpid(pid, &status, 0)) < 0)
            err_sys(
"waitpid error");

        printf(
"*** %d ***\n", pid);
        printf(
"%% ");
    }
    exit(
0);
}

posted @ 2007-08-04 00:20 ZelluX 阅读(569) | 评论 (0)编辑 收藏

将两个文件放在同一目录中,修改gpa.sh中的账号密码,并用chmod设置为可执行,运行即可。
写得不怎么样,像URPParser里处理标签的时候直接输出了,很不规范,不过懒得改了
urpparser.py:
from sgmllib import SGMLParser

class URPParser(SGMLParser):
    
def reset(self):
        self.tdOpen 
= 0
        self.colCount 
= -1
        self.firstRow 
= 1
        self.pieces 
= []
        SGMLParser.reset(self)

    
def start_td(self, attrs):
        
"""
            When encountered with tag td, check whether there's
            an align property in the tag, which will distinguish
            score table from others.
        
"""
            
        
for (k, v) in attrs:
            
if (k == "align"):
                self.tdOpen 
= 1
                
break

    
def end_td(self):
        self.tdOpen 
= 0

    
def handle_data(self, text):
        
if (self.tdOpen > 0):
            
if (len(text.strip()) > 0):
                self.colCount 
+= 1
                
if (self.colCount > 6):
                    self.colCount 
= 0
                    self.firstRow 
= 0
                    
print
                
if (self.firstRow):
                    
return
                
if (self.colCount == 2):
                    
print "\t",
                
else:
                    
print text.strip(),"\t",

gpa.sh:
#!/usr/bin/python
import urllib, cookielib, urllib2

loginURL 
= "http://fdis.fudan.edu.cn:58080/amserver/UI/Login?" +\
           
"goto=http%3A%2F%2Fwww.urp.fudan.edu.cn%3A84%2Feps" +\
           
"tar%2Fapp%2Ffudan%2FframeSub.jsp%3FaffairNO%3D035067"
scoreURL 
= "http://www.urp.fudan.edu.cn:84/epstar/app/fudan/S" +\
           
"coreManger/ScoreViewer/Student/Course.jsp"
logoutURL 
= "http://www.urp.fudan.edu.cn/logout.jsp"

cookie 
= cookielib.CookieJar()
opener 
= urllib2.build_opener(urllib2.HTTPCookieProcessor(cookie))
urllib2.install_opener(opener)
str 
= urllib.urlencode({'Login.Token1''06301000000''Login.Token2'"yourpassword"})
sock1 
= urllib2.urlopen(loginURL, str)
loginHTML 
= sock1.read()
sock1.close()

sock2 
= urllib2.urlopen(scoreURL)
scoreHTML 
= sock2.read()
sock2.close()

sock3 
= urllib2.urlopen(logoutURL)
sock3.close()

from urpparser import URPParser
parser 
= URPParser()
parser.feed(scoreHTML)
print



posted @ 2007-08-03 19:50 ZelluX 阅读(560) | 评论 (0)编辑 收藏

如果直接编译myls.c,会报错
/tmp/cceQcwN0.o: In function `main':
myls.c:(.text+0x24): undefined reference to `err_quit'
myls.c:(.text+0x5b): undefined reference to `err_sys'
collect2: ld 返回 1

需要下载随书附带的源代码并编译所需的库文件
源代码下载:http://www.blogjava.net/Files/zellux/apue.linux3.tar.Z.zip
(下载后去掉.zip后缀)

apue/README 文件中有具体的编译方法,对于Linux系统比较简单,进入lib.rhlin目录,然后运行make,就会在apue目录下生成libmisc.a,以后编译的时候连接这个库就行了。

以书中的第一个程序myls.c为例
#include <sys/types.h>
#include 
<dirent.h>

#include 
"ourhdr.h"

int main(int argc, char* argv[])
{
    DIR             
*dp;
    
struct dirent   *dirp;

    
if (argc != 2)
        err_quit(
"a single argument (the directory name) is required");

    
if ( (dp = opendir(argv[1])) == NULL)
        err_sys(
"can't open %s", argv[1]);

    
while ( (dirp = readdir(dp)) != NULL)
        printf(
"%s\n", dirp->d_name);

    closedir(dp);
    exit(
0);
}

$ gcc myls.c libmisc.a
出现几个Warning:
libmisc.a(strerror.o): In function `strerror':
strerror.c:(.text+0x18): warning: `sys_errlist' is deprecated; use `strerror' or `strerror_r' instead
strerror.c:(.text+0xf): warning: `sys_nerr' is deprecated; use `strerror' or `strerror_r' instead
看来这本书的确太老了
$ ./a.out .
就会列出当前目录下的所有文件

posted @ 2007-08-03 01:13 ZelluX 阅读(2223) | 评论 (2)编辑 收藏

《窃听风暴》的男主角乌尔里希·穆埃(Ulrich Mühe) 病逝了。。。
好片子,好演员,可惜了。。。

CSAPP 第七章Linking太枯燥了  啃了半天总算看到一点实际经历中遇到过的。

在编译阶段,编译器把全局变量标记为strong或者weak,并导出到汇编程序中,由汇编程序把这些信息隐式地添加到relocatable object file的符号表(symbol table)中。
函数和被初始化的全局变量被标记为strong,未初始化的全局变量被标记为weak。
Unix连接器(linker)使用下面的规则来处理多个符号的情况:
1. 不允许多个strong symbol的存在
2. 如果有一个strong symbol和若干个weak symbol,使用strong symbol
3. 只有若干个weak symbol,则使用其中任意一个

几个例子(未特殊说明的情况,变量定义均在全局范围):
1. foo1.c和bar1.c中都有int main()方法,即存在了两个strong symbol,连接器就会产生一条错误信息。
2.
/* foo3.c */
#include 
<stdio.h>
void f(void);

int x = 15213;

int main()
{
    f();
    printf(
"x = %d\n", x);
    
return 0;
}

/* bar3.c */
int x;

void f()
{
    x 
= 15212;
}
main()方法调用f()后,x变为15212并被输出。
注意这可能不是main()方法的作者原来的意图。
类似的情况也可能发生在两个weak symbol同名的时候。

3. 全局变量类型不同的情况:
/* foo5.c */
#include 
<stdio.h>
void f(void);

int x = 15213;
int y = 15212;

int main()
{
    f();
    printf(
"x = 0x%x  y = 0x%x \n", x, y);
    
return 0;
}

/* bar4.c */
double x;

void f()
{
    x 
= -0.0;
}
根据书上的内容,
linux> gcc -o foobar5 foo5.c bar5.c
linux> ./foobar5
结果应该是
x = 0x0  y = 0x80000000

但是在自己机器上编译时报错了,可能连接器版本较高,会自动找出这种错误
/usr/bin/ld: Warning: alignment 4 of symbol `x' in /tmp/ccupQXSG.o is smaller than 8 in /tmp/ccNNG9XZ.o
是double和int大小不义导致的对齐问题


这些问题都比较细小难以被查觉,通常在程序执行了一段时间后才出现较严重的问题,因此很难被修复,尤其当许多程序员不清楚连接器的工作方式的时候。
另外可以使用GCC的-warn-common标记(flag),使得它在解析多个同名的全局变量时发出警告。
试了下没成功@@
gcc --warn-common提示无法识别的命令行选项,gcc -Wall则不会发出警告。

posted @ 2007-08-02 23:45 ZelluX 阅读(865) | 评论 (0)编辑 收藏

1.基于dictionary的字符串格式化
>>> params = {"server":"mpilgrim", "database":"master", "uid":"sa", "pwd":"secret"}
>>> "%(pwd)s" % params
'secret'
这个东西的用处在于和locals的搭配使用,比如样例程序中
def handle_comment(self, text):
    self.pieces.append(
"<!--%(text)s-->" % locals()) 

就读取了text变量的内容。
不过这样和直接用text变量有什么区别呢?貌似"<!--%s-->" % text也可以啊
水木上问了一下,得到的答案是
发信人: Essien5 (宝贝晶~), 信区: Python
标  题: Re: 关于locals()的用处
发信站: 水木社区 (Thu Aug  2 11:16:37 2007), 转信

好处就是多个变量是代码很好维护,一一对应
'%s%s.......%s'%(a,b,c,d,....,z)
'%(a)s%(b)s......%(z)s'%locals()
第一种写法前面的%s和后面的变量很难对应起来,bug的源泉
后一个就非常直观了
而且要往中间再随便插变量也方便


2. 自己的类继承了SGMLParser后,需要对特殊标记处理,可以以start_或do_开始命名相关函数。
可以这样做的原因在于python的自醒机制(introspection)

    def finish_starttag(self, tag, attrs):
        
try:
            method 
= getattr(self, 'start_' + tag)
        
except AttributeError:
            
try:
                method 
= getattr(self, 'do_' + tag)
            
except AttributeError:
                self.unknown_starttag(tag, attrs)
                
return -1
            
else:
                self.handle_starttag(tag, method, attrs)
                
return 0
        
else:
            self.stack.append(tag)
            self.handle_starttag(tag, method, attrs)
            
return 1
程序首先尝试获得start_tagname的方法,如果失败则继续尝试获得do_tagname,如果仍然不能找到,则调用unknown_starttag方法。
感觉这和Java的反射机制很相似,例如Javabean中的getter setter方法,也是通过特殊命名的形式让其他对象了解自己的。

3. import 语句可以写在任何地方。

posted @ 2007-08-02 00:30 ZelluX 阅读(328) | 评论 (0)编辑 收藏

Software版进不去了,一进去就会自动退出,WEB模式下一看是有个名字乱码的文章

2976  plantxue  Aug 1 19:54 ?鶳鹛鶳鹇鶳鸺遭遇文件名不合法 (85)
2977  basic  Aug 1 20:08  Adobe.CS3.Production.Premium.Activation-AGAiN (55)
2978  basic  Aug 1 20:09  ?鶳鹛鶳鹇鶳鸺遭遇文件名不合法 (49)

看来web模式下发主题带有特殊字符的帖子可以起到一定的效果的

posted @ 2007-08-01 20:21 ZelluX 阅读(333) | 评论 (0)编辑 收藏

前 言
软件质量是被大多数程序员挂在嘴上而不是放在心上的东西!
除了完全外行和真正的编程高手外,初读本书,你最先的感受将是惊慌:“哇!我以前捏造的C++/C 程序怎么会有那么多的毛病?”
别难过,作者只不过比你早几年、多几次惊慌而已。
请花一两个小时认真阅读这本百页经书,你将会获益匪浅,这是前面N-1 个读者的建议。
http://www.blogjava.net/Files/zellux/c.zip

posted @ 2007-08-01 18:16 ZelluX 阅读(383) | 评论 (0)编辑 收藏

转一篇wikipedia上的文章
http://zh.wikipedia.org/wiki/%E7%B4%85%E9%BB%91%E6%A8%B9

红黑树是一种自平衡二叉查找树,是在计算机科学中用到的一种数据结构,典型的用途是实现关联数组。它是在1972年Rudolf Bayer发明的,他称之为"对称二叉B树",它现代的名字是在 Leo J. Guibas 和 Robert Sedgewick1978年写的一篇论文中获得的。它是复杂的,但它的操作有着良好的最坏情况运行时间,并且在实践中是高效的: 它可以在O(log n)时间内做查找,插入和删除,这里的n是树中元素的数目。

用途和好处

红黑树和AVL树一样都对插入时间、删除时间和查找时间提供了最好可能的最坏情况担保。这不只是使它们在时间敏感的应用如即时应用(real time application)中有价值,而且使它们有在提供最坏情况担保的其他数据结构中作为建造板块的价值;例如,在计算几何中使用的很多数据结构都可以基于红黑树。

红黑树在函数式编程中也特别有用,在这里它们是最常用的持久数据结构之一,它们用来构造关联数组集合,在突变之后它们能保持为以前的版本。除了O(log n)的时间之外,红黑树的持久版本对每次插入或删除需要O(log n)的空间。

红黑树是 2-3-4树的 一种等同。换句话说,对于每个 2-3-4 树,都存在至少一个数据元素是同样次序的红黑树。在 2-3-4 树上的插入和删除操作也等同于在红黑树中颜色翻转和旋转。这使得 2-3-4 树成为理解红黑树背后的逻辑的重要工具,这也是很多介绍算法的教科书在红黑树之前介绍 2-3-4 树的原因,尽管 2-3-4 树在实践中不经常使用。



性质

红黑树是每个节点都带有颜色属性的二叉查找树,颜色或红色黑色。在二叉查找树强制一般要求以外,对于任何有效的红黑树我们增加了如下的额外要求:

性质1. 节点是红色或黑色。

性质2. 根是黑色。

性质3. 所有叶子都是黑色(包括NIL)。

性质4. 每个红色节点的两个子节点都是黑色。(从每个叶子到根的所有路径上不能有两个连续的红色节点)

性质5. 从任一节点到其每个叶子的所有路径都包含相同数目的黑色节点。

An example of a red-black tree

这些约束强制了红黑树的关键性质: 从根到叶子的最长的可能路径不多于最短的可能路径的两倍长。结果是这个树大致上是平衡的。因为操作比如插入、删除和查找某个值的最坏情况时间都要求与树的 高度成比例,这个在高度上的理论上限允许红黑树在最坏情况下都是高效的,而不同于普通的二叉查找树

要知道为什么这些特性确保了这个结果,注意到属性4导致了路径不能有两个毗连的红色节点就足够了。最短的可能路径都是黑色节点,最长的可能路径有交替的红色和黑色节点。因为根据属性5所有最长的路径都有相同数目的黑色节点,这就表明了没有路径能多于任何其他路径的两倍长。

在很多树数据结构的表示中,一个节点有可能只有一个子节点,而叶子节点包含数据。用这种范例表示红黑树是可能的,但是这会改变一些属性并使算法复 杂。为此,本文中我们使用 "nil 叶子" 或"空(null)叶子",如上图所示,它不包含数据而只充当树在此结束的指示。这些节点在绘图中经常被省略,导致了这些树好象同上述原则相矛盾,而实际 上不是这样。与此有关的结论是所有节点都有两个子节点,尽管其中的一个或两个可能是空叶子。


操作

因为每一个红黑树也是一个特化的二叉查找树,因此红黑树上的只读操作与普通二叉查找树上的只读操作相同。然而,在红黑树上进行插入操作和删除操作会导致不再符合红黑树的性质。恢复红黑树的属性需要少量(O(log n))的颜色变更(实际是非常快速的)和不超过三次树旋转(对于插入操作是两次)。虽然插入和删除很复杂,但操作时间仍可以保持为 O(log n) 次。

插入

我们首先以二叉查找树的方法增 加节点并标记它为红色。(如果设为黑色,就会导致根到叶子的路径上有一条路上,多一个额外的黑节点,这个是很难调整的。但是设为红色节点后,可能会导致出 现两个连续红色节点的冲突,那么可以通过颜色调换(color flips)和树旋转来调整。) 下面要进行什么操作取决于其他临近节点的颜色。同人类的家族树中一样,我们将使用术语叔父节点来指一个节点的父节点的兄弟节点。注意:

  • 性质1[1]和性质3[2]总是保持着。
  • 性质4[3]只在增加红色节点、重绘黑色节点为红色,或做旋转时受到威胁。
  • 性质5[4]只在增加黑色节点、重绘红色节点为黑色,或做旋转时受到威胁。

在下面的示意图中,将要插入的节点标为NN的父节点标为PN的祖父节点标为GN的叔父节点标为U。在图中展示的任何颜色要么是由它所处情形所作的假定,要么是这些假定所暗含的。

对于每一种情况,我们将使用 C示例代码来展示。通过下列函数,可以找到一个节点的叔父和祖父节点:

node grandparent(node n) {
return n->parent->parent;
}

node uncle(node n) {
if (n->parent == grandparent(n)->left)
return grandparent(n)->right;
else
return grandparent(n)->left;
}

情形1: 新节点N位于树的根上,没有父节点。在这种情形下,我们把它重绘为黑色以满足性质2[5]。因为它在每个路径上对黑节点数目增加一,性质5[4]符合。

void insert_case1(node n) {
if (n->parent == NULL)
n->color = BLACK;
else
insert_case2(n);
}

情形2: 新节点的父节点P是黑色,所以性质4[3]没有失效(新节点是红色的)。在这种情形下,树仍是有效的。性质5[4]受到威胁,因为新节点N有两个黑色叶子儿子;但是由于新节点N是红色,通过它的每个子节点的路径就都有同通过它所取代的黑色的叶子的路径同样数目的黑色节点,所以这个性质依然满足。

void insert_case2(node n) {
if (n->parent->color == BLACK)
return; /* 树仍旧有效 */
else
insert_case3(n);
}

注意: 在下列情形下我们假定新节点有祖父节点,因为父节点是红色;并且如果它是根,它就应当是黑色。所以新节点总有一个叔父节点,尽管在情形4和5下它可能是叶子。

情况 3 示意图

情形3: 如果父节点P和叔父节点U二者都是红色,则我们可以将它们两个重绘为黑色并重绘祖父节点G为红色(用来保持性质5[4])。现在我们的新节点N有了一个黑色的父节点P。因为通过父节点P或叔父节点U的任何路径都必定通过祖父节点G,在这些路径上的黑节点数目没有改变。但是,红色的祖父节点G的父节点也有可能是红色的,这就违反了性质4[3]。为了解决这个问题,我们在祖父节点G上递归地进行情形1的整个过程。

void insert_case3(node n) {
if (uncle(n) != NULL && uncle(n)->color == RED) {
n->parent->color = BLACK;
uncle(n)->color = BLACK;
grandparent(n)->color = RED;
insert_case1(grandparent(n));
}
else
insert_case4(n);
}

注意: 在余下的情形下,我们假定父节点P 是其父亲G 的左子节点。如果它是右子节点,情形4情形5中的应当对调。

情况 4 示意图

情形4: 父节点P是红色而叔父节点U是黑色或缺少; 还有,新节点N是其父节点P的右子节点,而父节点P又是其父节点的左子节点。在这种情形下,我们进行一次左旋转调换新节点和其父节点的角色; 接着,我们按情形5处理以前的父节点P。这导致某些路径通过它们以前不通过的新节点N或父节点P中的一个,但是这两个节点都是红色的,所以性质5[4]没有失效。

void insert_case4(node n) {
if (n == n->parent->right && n->parent == grandparent(n)->left) {
rotate_left(n->parent);
n = n->left;
} else if (n == n->parent->left && n->parent == grandparent(n)->right) {
rotate_right(n->parent);
n = n->right;
}
insert_case5(n);
}
情况 5 示意图

情形5: 父节点P是红色而叔父节点U 是黑色或缺少,新节点N 是其父节点的左子节点,而父节点P又是其父节点G的左子节点。在这种情形下,我们进行针对祖父节点P 的一次右旋转; 在旋转产生的树中,以前的父节点P现在是新节点N和以前的祖父节点G 的父节点。我们知道以前的祖父节点G是黑色,否则父节点P就不可能是红色。我们切换以前的父节点P和祖父节点G的颜色,结果的树满足性质4[3]。性质5[4]也仍然保持满足,因为通过这三个节点中任何一个的所有路径以前都通过祖父节点G ,现在它们都通过以前的父节点P。在各自的情形下,这都是三个节点中唯一的黑色节点。

void insert_case5(node n) {
n->parent->color = BLACK;
grandparent(n)->color = RED;
if (n == n->parent->left && n->parent == grandparent(n)->left) {
rotate_right(grandparent(n));
} else {
/* Here, n == n->parent->right && n->parent == grandparent(n)->right */
rotate_left(grandparent(n));
}
}

注意插入实际上是原地算法,因为上述所有调用都使用了尾部递归

[编辑] 删除

如果需要删除的节点有两个儿子,那么问题可以被转化成删除另一个只有一个儿子的节点的问题(为了表述方便,这里所指的儿子,为非叶子节点的儿子)。对于二叉查找树,在删除带有两个非叶子儿子的节点的时候,我们找到要么在它的左子树中的最大元素、要么在它的右子树中的最小元素,并把它的值转移到要删除的节点中(如在这里所展示的那样)。我们接着删除我们从中复制出值的那个节点,它必定有少于两个非叶子的儿子。因为只是复制了一个值而不违反任何属性,这就把问题简化为如何删除最多有一个儿子的节点的问题。它不关心这个节点是最初要删除的节点还是我们从中复制出值的那个节点。

在本文余下的部分中,我们只需要讨论删除只有一个儿子的节点(如果它两个儿子都为空,即均为叶子,我们任意将其中一个看作它的儿 子)。如果我们删除一个红色节点,它的父亲和儿子一定是黑色的。所以我们可以简单的用它的黑色儿子替换它,并不会破坏属性3和4。通过被删除节点的所有路 径只是少了一个红色节点,这样可以继续保证属性5。另一种简单情况是在被删除节点是黑色而它的儿子是红色的时候。如果只是去除这个黑色节点,用它的红色儿 子顶替上来的话,会破坏属性4,但是如果我们重绘它的儿子为黑色,则曾经通过它的所有路径将通过它的黑色儿子,这样可以继续保持属性4。

需要进一步讨论的是在要删除的节点和它的儿子二者都是黑色的时候,这是一种复杂的情况。我们首先把要删除的节点替换为它的儿子。出于方便,称呼这个儿子为N,称呼它的兄弟(它父亲的另一个儿子)为S。在下面的示意图中,我们还是使用P称呼N的父亲,SL称呼S的左儿子,SR称呼S的右儿子。我们将使用下述函数找到兄弟节点:

node sibling(node n) {
if (n == n->parent->left)
return n->parent->right;
else
return n->parent->left;
}

我们可以使用下列代码进行上述的概要步骤,这里的函数 replace_node 替换 childn 在树中的位置。出于方便,在本章节中的代码将假定空叶子被用不是 NULL 的实际节点对象来表示(在插入章节中的代码可以同任何一种表示一起工作)。

void delete_one_child(node n) {
/* Precondition: n has at most one non-null child */
node child = (is_leaf(n->right)) ? n->left : n->right;
replace_node(n, child);
if (n->color == BLACK) {
if (child->color == RED)
child->color = BLACK;
else
delete_case1(child);
}
free(n);
}

如果 N 和它初始的父亲是黑色,则删除它的父亲导致通过 N 的路径都比不通过它的路径少了一个黑色节点。因为这违反了属性 4,树需要被重新平衡。有几种情况需要考虑:

情况 1: N 是新的根。在这种情况下,我们就做完了。我们从所有路径去除了一个黑色节点,而新根是黑色的,所以属性都保持着。

void delete_case1(node n) {
if (n->parent == NULL)
return;
else
delete_case2(n);
}

注意: 在情况2、5和6下,我们假定 N 是它父亲的左儿子。如果它是右儿子,则在这些情况下的应当对调。

情况 2 示意图

情况 2: S 是红色。在这种情况下我们在N的父亲上做左旋转,把红色兄弟转换成N的祖父。我们接着对调 N 的父亲和祖父的颜色。尽管所有的路径仍然有相同数目的黑色节点,现在 N 有了一个黑色的兄弟和一个红色的父亲,所以我们可以接下去按 4、5或6情况来处理。(它的新兄弟是黑色因为它是红色S的一个儿子。)

void delete_case2(node n) {
if (sibling(n)->color == RED) {
n->parent->color = RED;
sibling(n)->color = BLACK;
if (n == n->parent->left)
rotate_left(n->parent);
else
rotate_right(n->parent);
}
delete_case3(n);
}
情况 3 示意图

情况 3: N 的父亲、S 和 S 的儿子都是黑色的。在这种情况下,我们简单的重绘 S 为红色。结果是通过S的所有路径, 它们就是以前通 过 N 的那些路径,都少了一个黑色节点。因为删除 N 的初始的父亲使通过 N 的所有路径少了一个黑色节点,这使事情都平衡了起来。但是,通过 P 的所有路径现在比不通过 P 的路径少了一个黑色节点,所以仍然违反属性4。要修正这个问题,我们要从情况 1 开始,在 P 上做重新平衡处理。

void delete_case3(node n) {
if (n->parent->color == BLACK &&
sibling(n)->color == BLACK &&
sibling(n)->left->color == BLACK &&
sibling(n)->right->color == BLACK)
{
sibling(n)->color = RED;
delete_case1(n->parent);
}
else
delete_case4(n);
}
情况 4 示意图

情况 4: S 和 S 的儿子都是黑色,但是 N 的父亲是红色。在这种情况下,我们简单的交换 N 的兄弟和父亲的颜色。这不影响不通过 N 的路径的黑色节点的数目,但是它在通过 N 的路径上对黑色节点数目增加了一,添补了在这些路径上删除的黑色节点。

void delete_case4(node n) {
if (n->parent->color == RED &&
sibling(n)->color == BLACK &&
sibling(n)->left->color == BLACK &&
sibling(n)->right->color == BLACK)
{
sibling(n)->color = RED;
n->parent->color = BLACK;
}
else
delete_case5(n);
}
情况 5 示意图

情况 5: S 是黑色,S 的左儿子是红色,S 的右儿子是黑色,而 N 是它父亲的左儿子。在这种情况下我们在 S 上做右旋转,这样 S 的左儿子成为 S 的父亲和 N 的新兄弟。我们接着交换 S 和它的新父亲的颜色。所有路径仍有同样数目的黑色节点,但是现在 N 有了一个右儿子是红色的黑色兄弟,所以我们进入了情况 6。N 和它的父亲都不受这个变换的影响。

void delete_case5(node n) {
if (n == n->parent->left &&
sibling(n)->color == BLACK &&
sibling(n)->left->color == RED &&
sibling(n)->right->color == BLACK)
{
sibling(n)->color = RED;
sibling(n)->left->color = BLACK;
rotate_right(sibling(n));
}
else if (n == n->parent->right &&
sibling(n)->color == BLACK &&
sibling(n)->right->color == RED &&
sibling(n)->left->color == BLACK)
{
sibling(n)->color = RED;
sibling(n)->right->color = BLACK;
rotate_left(sibling(n));
}
delete_case6(n);
}
情况 6 示意图

情况 6: S 是黑色,S 的右儿子是红色,而 N 是它父亲的左儿子。在这种情况下我们在 N 的父亲上做左旋转,这样 S 成为 N 的父亲和 S 的右儿子的父亲。我们接着交换 N 的父亲和 S 的颜色,并使 S 的右儿子为黑色。子树在它的根上的仍是同样的颜色,所以属性 3 没有被违反。但是,N 现在增加了一个黑色祖先: 要幺 N 的父亲变成黑色,要么它是黑色而 S 被增加为一个黑色祖父。所以,通过 N 的路径都增加了一个黑色节点。

此时,如果一个路径不通过 N,则有两种可能性:

  • 它通过 N 的新兄弟。那么它以前和现在都必定通过 S 和 N 的父亲,而它们只是交换了颜色。所以路径保持了同样数目的黑色节点。
  • 它通过 N 的新叔父,S 的右儿子。那么它以前通过 S、S 的父亲和 S 的右儿子,但是现在只通过 S,它被假定为它以前的父亲的颜色,和 S 的右儿子,它被从红色改变为黑色。合成效果是这个路径通过了同样数目的黑色节点。

在任何情况下,在这些路径上的黑色节点数目都没有改变。所以我们恢复了属性 4。在示意图中的白色节点可以是红色或黑色,但是在变换前后都必须指定相同的颜色。

void delete_case6(node n) {
sibling(n)->color = n->parent->color;
n->parent->color = BLACK;
if (n == n->parent->left) {
/* Here, sibling(n)->color == BLACK &&
sibling(n)->right->color == RED */
sibling(n)->right->color = BLACK;
rotate_left(n->parent);
}
else
{
/* Here, sibling(n)->color == BLACK &&
sibling(n)->left->color == RED */
sibling(n)->left->color = BLACK;
rotate_right(n->parent);
}
}

同样的,函数调用都使用了尾部递归,所以算法是就地的。此外,在旋转之后不再做递归调用,所以进行了恒定数目(最多 3 次)的旋转。




渐进边界的证明

包含n个内部节点的红黑树的高度是 O(log(n))。

定义:

  • h(v) = 以节点v为根的子树的高度。
  • bh(v) = 从v到子树中任何叶子的黑色节点的数目(如果v是黑色则不计数它)(也叫做黑色高度)。

引理: 以节点v为根的子树有至少2bh(v) − 1个内部节点。

引理的证明(通过归纳高度):

基础: h(v) = 0

如果v的高度是零则它必定是 nil,因此 bh(v) = 0。所以:

2bh(v) − 1 = 20 − 1 = 1 − 1 = 0

归纳假设: h(v) = k 的v有 2bh(v) − 1 − 1 个内部节点暗示了 h(v') = k+1 的 v'有2bh(v') − 1 个内部节点。

因为 v' 有 h(v') > 0 所以它是个内部节点。同样的它有黑色高度要么是 bh(v') 要么是 bh(v')-1 (依据v'是红色还是黑色)的两个儿子。通过归纳假设每个儿子都有至少 2bh(v') − 1 − 1 个内部接点,所以 v' 有:

2bh(v') − 1 − 1 + 2bh(v') − 1 − 1 + 1 = 2bh(v') − 1

个内部节点。

使用这个引理我们现在可以展示出树的高度是对数性的。因为在从根到叶子的任何路径上至少有一半的节点是黑色(根据红黑树属性4),根的黑色高度至少是h(root)/2。通过引理我们得到:

n \geq 2^{{h(root) \over 2}} - 1 \leftrightarrow \; \log{(n+1)} \geq {h(root) \over 2} \leftrightarrow \; h(root) \leq 2\log{(n+1)}

因此根的高度是O(log(n))。

posted @ 2007-08-01 00:01 ZelluX 阅读(472) | 评论 (0)编辑 收藏

from smth.org

= malloc(n * sizeof(int));
for (i = 0; i < n; i++)
   p[i] 
= i;

output(p, n);

for (i = n - 1; i > 0; i--)
   
if (p[i] > p[i - 1])
   {
      
for (j = n - 1; p[j] < p[i - 1]; j--);
      swap(
&(p[i - 1]), &(p[j]));

      
for (j = i, k = n - 1; j < k; j++, k--)
         swap(
&(p[j]), &(p[k]));

      ouput(p, n);
      i 
= n;
   }

free(p);

posted @ 2007-07-31 11:58 ZelluX 阅读(466) | 评论 (0)编辑 收藏

把总长度求出来,然后用和背包问题类似的dp算法求是否可以达到这个总长度的一半,但是超时了。
找到一个优化方案,结果0ms就过了,orz
http://162.105.81.202/course/problemSolving/dividingProve.doc
以下论证均转自这篇文章。
 结论 对于任意一种珠宝的个数n,如果n>=8, 可以将n改写为 11(n为奇数) 或 12(n为偶数)。

证明:

对于任意一组数,6的个数为n(n>=8)

一、如果可以分成两堆,我们可以分成两种情况:
   1.
      两堆里都有6,那么我们可知:把n改为n-2,仍然可分。
(两堆各减一个6)
2. 只有一堆里有6,设为左边,那么左边的总和不小于6*8=48。
我们观察,5*6=6*5 ,4*3=6*2 , 3*2=6 , 2*3=6 , 1*6=6
而 5*5 + 4*2 + 3*1 + 2*2 + 1*5 = 25 + 8 + 3 + 4 + 5 = 45 < 48
由抽屉原理右边必然存在
(多于5个的5 或者 多于2个的4 或者 多于1个的3
或者 多于2个的2 或者 多于5个的1)
即右边至少存在一组数的和等于若干个6,比如右边有3个4,这样把左边的2个6与右边的3个4交换,则又出现左右都有6的情况。 根据1,我们还是可以把n改为n-2且可分的状态不变。
综合1,2。我们可以看出只要原来n的个数=8,我们就可以把它改为n-2,这样操作一直进行到n<8。我们可以得出结论,对于大于等于8的偶数,可以换成6。
对于大于8的奇数,可以换成7。换完之后仍然可分。

二、如果不能分成两堆:
显然改为n-2时同样也不能分,那么对于大于等于8的偶数,可以换成6;对于大于8的奇数,可以换成7。换完之后仍然不可分。

综合一、二,我们得出结论把不小于8的偶数改为8,大于8的奇数改为7,原来可分与否的性质不会改变。

以上是对6的讨论,同样的方法可以推出
5的个数 6*4 + 4*4 + 3*4 + 2*4 + 1*4 = 64 < 5*13
即5的个数多于12时,偶数换为12,奇数换为11
4的个数 6*1 + 5*3 + 3*3 + 2*1 + 1*3 = 35 < 4*9
即4的个数多于8时,偶数换为8,奇数换为7
3的个数 5*2 + 4*2 + 2*2 + 1*2 = 24 < 3*9
即3的个数多于8时,偶数换为8,奇数换为7
2的个数 5*1 + 3*1 + 1*1 = 9 < 2*5
即2的个数多于4时,偶数换为4,奇数换为3
1的个数 多于5则必然可分(在总数是偶数的前提下)

综上所述,
对于任意一种珠宝的个数n,如果n>=8, 可以将n改写为 11(n为奇数) 或 12(n为偶数)。

进一步分析:
对每个数(1-6),以上只是粗略的估计,可以进一步减少其最大有效取值,例如,
对于6,5*5 + 4*2 + 3*1 + 2*2 + 1*5 = 25 + 8 + 3 + 4 + 5 = 45
就有4和2不能同时出现,5和1不能同时出现,3个5和1个3不能同时出现,4个5不能和1个4同时出现等等,所以组合不出6的整数倍的情况的总价值至多为25,所以当6的个数大于6时,奇数可改为5,偶数可改为6。
1-5 也有类似情况。

为了得出精确值,下面先我们讨论这样一个数论命题。

命题:
可重复的从自然数集中取出n个数(n>=2),其中必有若干个数之和能被n整除。

证明:设取出的n个自然数为a1,a2,a3,.....an

考虑这样的n+1个数 0, a1, a1+a2 , a1+a2+a3 , ...... , a1+a2+a3+...+an, 由于自然数模n的剩余类有n个,所以以上n+1个数中必有两个同余。 这两个数的差必被n整除,而且这两个数的差就是原来的n个数中的一些数的和。
这就证明了命题。

由以上命题
对于6而言,我们至多从{1,2,3,4,5}中可重复的找出5个数使它们不能组合成6的倍数。
所以这些数的和小于等于5*5=25
对于5而言,我们至多从{1,2,3,4,6}中可重复的找出4个数使它们不能组合成5的倍数。
所以这些数的和小于等于6*4=24
对于4而言,我们至多从{1,2,3,5,6}中可重复的找出3个数使它们不能组合成4的倍数。
所以这些数的和小于等于3*6=18 , 然而,两个6就是4的倍数, 所以最多有一个6
此时不能有两个5(2*5+6=16是4的倍数), 最多才6 + 5 + 3 = 14 < 3*5 =15
所以这些数的和小于等于3*5=15
对于3而言,我们至多从{1,2,4,5,6}中可重复的找出2个数使它们不能组合成3的倍数。
所以这些数的和小于等于2*5=10

(6就是3的倍数,所以不能取6)

对于2而言,我们至多从{1,3,4,5,6}中可重复的找出1个数使它们不能组合成6的倍数。

所以这些数的和小于等于1*5=5



考虑到 4*6 < 25 < 5*6 , 我们可以算出6的最大有效个数为5 。

考虑到 4*5 < 24 < 5*5 , 我们可以算出5的最大有效个数为5 。但是其实应该修正为6, 如果遇到如下特殊情况,左边5个6,右边6个5。此时虽然左右可以交换,但是交换后仍然只有一边有5,与(一、2)中讨论情况不符。

考虑到 3*4 < 15 < 4*4 , 我们可以算出5的最大有效个数为4 。但是其实应该修正为5, 如果遇到如下特殊情况,左边4个5,右边5个4。此时虽然左右可以交换,但是交换后仍然只有一边有4,与(一、2)中讨论情况不符。

考虑到 3*3 < 10 < 4*3 , 我们可以算出5的最大有效个数为4 。但是其实应该修正为5, 如果遇到如下特殊情况,左边3个5,右边5个3。此时虽然左右可以交换,但是交换后仍然只有一边有3,与(一、2)中讨论情况不符。

考虑到 2*2 < 5 < 3*2 , 我们可以算出5的最大有效个数为3 。 但是其实应该修正为4,如果遇到如下特殊情况,左边1个3和1个5,右边4个2。此时虽然左右可以交换,但是交换后仍然只有一边有2,与(一、2)中讨论情况不符。


我们得出最后的精确结论:

奇数改为 偶数改为
6的个数大于5 5 4
5的个数大于6 5 6
4的个数大于5 5 4
3的个数大于5 5 4
2的个数大于4 3 4 



优化后的代码:
#include <iostream>
using namespace std;

long n[6];
long sum;
const long MAX_N = 60000;

int dividable()
{
    
int f[MAX_N];
    
for (int i = 0; i <= sum; i++)
        f[i] 
= 0;
    f[
0= 1;
    
for (int i = 0; i < 6; i++)
    {
        
for (int j = 1; j <= n[i]; j++)
        {
            
int base = j * (i + 1);
            
if (base > sum) break;
            
for (int k = sum - (i+1); k >= base - i - 1; k--)
                
if (f[k])
                    f[k 
+ i + 1= 1;
            
if (f[sum]) return 1;
        }
    }
    
return f[sum];
}

int main()
{
    
long cases = 0;
    
while (true)
    {
        sum 
= 0;
        
for (long i = 0; i < 6; i++)
        {
            cin 
>> n[i];
        }
        
if (n[5> 5) n[5= 4 + n[5% 2;
        
if (n[4> 6) n[4= 6 - n[4% 2;
        
if (n[3> 5) n[3= 4 + n[3% 2;
        
if (n[2> 5) n[2= 4 + n[2% 2;
        
if (n[1> 4) n[1= 4 - n[1% 2;
        
for (long i = 0; i < 6; i++)
        {
            sum 
+= n[i] * (i + 1);
        }
        
if (sum == 0)
            
break;
        cases
++;
        cout 
<< "Collection #" << cases << ":\n";
        
if (sum % 2 != 0)
        {
            cout 
<< "Can't be divided.\n\n";
            
continue;
        }
        sum 
/= 2;
        
if (dividable())
            cout 
<< "Can be divided.\n";
        
else
            cout 
<< "Can't be divided.\n";
        cout 
<< endl;
    }
    
return 0;
}


posted @ 2007-07-30 19:59 ZelluX 阅读(2775) | 评论 (3)编辑 收藏

仅列出标题
共39页: First 上一页 17 18 19 20 21 22 23 24 25 下一页 Last