Friday, January 30, 2009

八荣八耻

更多精彩请到 http://www.139ya.com

一直没有完全学习过，这次既然看到了就贴在这里，好好学习一下

以热爱祖国为荣以危害祖国为耻
以服务人民为荣以背离人民为耻
以崇尚科学为荣以愚昧无知为耻
以辛勤劳动为荣以好逸恶劳为耻
以团结互助为荣以损人利己为耻
以诚实守信为荣以见利忘义为耻
以遵纪守法为荣以违法乱纪为耻
以艰苦奋斗为荣以骄奢淫逸为耻

更多精彩请到 http://www.139ya.com

转自: http://topic.csdn.net/u/20080203/15/b0023b9c-b4f1-43a0-b49e-799e730af961.html

更多：http://zh.wikipedia.org/wiki/%E7%BD%91%E7%BB%9C%E8%AF%84%E8%AE%BA%E5%91%98

一直看到为GCD拍马，唱赞歌，歪曲事实，涂脂抹粉之流称为五毛，五毛党。
不知道为何如此称呼，上网查询之后，贴于此处。

“五毛”最早见诸官方文件，是2006年初安徽省宣传部《关于南昌、长沙、郑州宣传文化工作的考察报告》透露：“2004年10月开始，长沙市委外宣办坚持每天向市委、市政府主要领导报送《长沙舆情快报》。为此，他们从市委办公厅、市委党校、市委政研室等单位选聘了一批网络评论员，建立了网络评论员队伍，建立并完善了网络评论督查、考核、总结、表彰制度。网络评论员每月底薪600元。网评员主要职责是密切监控网络舆情，提供舆情信息，并有针对性地开展网络宣传策划、网络舆情引导工作。网评员每周围绕一个中心，在中国精神文明网、人民网、新华网等20多个国内著名网站论坛上，围绕长沙市三个文明建设的新做法、新成就、新经验，发布贴文、图片。”

网评员实行计件工资制，底薪600元，按发贴量加薪，每发一帖，键入“网络评论员管理系统”进行统计。一帖“五毛”，“五毛”由此而来。

湖南省委宣传部对湖南在全国网络监控的先进地位颇为自毫，湖南省委宣传部2007年编辑发行《我们这个家----2006中共湖南省委宣传部家书》，透露了很多网络监控的信息。湖南的经验在全国推广后，中宣部成立舆情信息局，全国各省宣传部成立舆情信息处，往下延伸，形成一套完整的网络监控系统。湖南省委宣传部借调人员聂廷芳等人在《在宣传部的日子里》等文章透露，他们搜罗网上涉及湖南的文章言论，每天编辑《涉湘舆情》，还经常与网站交涉，删除文章，“正确引导”网上舆论；祝平良则在《忙碌让我充实》一文透露：湖南舆情信息工作是全国先进，每个月报送中宣部的信息达到了800多条，（忙不过来时，在网上挖掘）临时发展和聘请网上舆情信息员。

除专职网评员外，2006年，湖南省宣传部还召开工作人员“人人都当网评员”，宣传战线的工作人员闻风动员，人人兼职赚“五毛”，极大地壮大了湖南的“五毛”队伍，在网络这一无形世界上，形成一条有特色的风景线。

另外，请其他朋友补充下五毛工作手册。

Friday, January 23, 2009

adobe contribute

更多精彩请到 http://www.139ya.com

帮助: http://help.adobe.com/zh_CN/Contribute/5.0_Using/index.html

overview: http://grok.lsu.edu/Article.aspx?articleId=5675

Adobe Contribute CS3 is a program for editing websites. It's original intention was to allow a wider variety of people within an organization to update webpages. They accomplished this goal by reducing the amount of technical design skills needed for the process.

Contribute is primarily used by non-programmers as it employs an interface environment that allows those with little programming experience to keep website and blog content updated and edited.

There are pros and cons to using Contribute to create and edit your content, as opposed to a more complete design environment such as Adobe Dreamweaver CS3. Below is a list of advantages and disadvantages to Adobe Contribute.

Advantages:

Contribute eliminates the need for multiple programs to change simple errors such as changing spelling on a webpage.
Several users can update a website simultaneously.
Administrators can ensure the style, code and integrity of a website is preserved while allowing users to update the site content.
Administrators can assign different permissions to users; some users may be able to edit text on a page, while others would have more options.
Templates created using Dreamweaver can be used in contribute as well.
Allows management of multiple blog accounts and allows offline blog entry capabilities.

Disadvantages:

Contribute is a client-side application, so you will only be able to edit a website on a machine that has Contribute installed.
Contribute is a website editing tool, not a website design tool. A web designer will still be required to build the initial website.
Updating website content through Contribute may be slower than when using a more development-oriented tool, since each page must be downloaded and uploaded individually.
Users cannot access source code, therefore any coding must be done in Dreamweaver or another web design program.

adobe SDK and server

Software development kits (SDKs) contain reference manuals, specifications and protocols, technical notes, sample code, and/or development tools — a complete toolset for taking full advantage of Adobe technology.

Support is available for the following SDKs and server products:

Software development kits and tools

Adobe® Acrobat® SDK
Adobe Acrobat Capture® SDK
Adobe Acrobat Connect™ Pro Collaboration Builder SDK
Adobe AIR™ SDK
Adobe After Effects® SDK
Adobe Audition® SDK
Adobe Breeze® SyncSWF SDK
Adobe Bridge SDK
Adobe Creative Suite® development tools
Adobe Flex®
Adobe Flex SDK
Adobe Font Development Kit for OpenType® (AFDKO)
Adobe FrameMaker® Developer Kit
Adobe Illustrator® SDK
Adobe InCopy® SDK
Adobe InDesign® SDK
Adobe InDesign Server SDK
Adobe Media Player Content Development Kit
Adobe PageMaker® SDK
Adobe PDF Library SDK
Adobe Photoshop® SDK
Adobe PostScript®
Adobe Premiere® Pro SDK
Adobe Version Cue® SDK
SMP SDK

Server products

Adobe ColdFusion®
Adobe Contribute® Publishing Server
Adobe Flash® Media Server family
Adobe Flex (ILOG component)
Adobe Flex Builder™
Adobe FrameMaker Server
Adobe JRun™
Adobe PDF Generator
Adobe RoboHelp® Server

最小化安装 Ubuntu

Ubuntu 的默认安装方式或许并不为所有用户所接受。譬如说吧，有的用户并不想使用 GNOME 桌面环境，也有的用户并不需要预先安装的所有软件。为了解决上述诸如此类的问题，在安装最小化的 Ubuntu 的基础上，根据各人之喜好执行定制化安装，可能是较好的折中方案。

在安装之前需要确定的一件事情是，如何选择安装 CD。根据本文的要求，下载 Alternate install CD 是比较适合的。为了便于安装，应该将下载后的 ISO 文件烧录成光盘。

首先，安装 Ubuntu 基本系统。以 Ubuntu 6.10 为例，当插入安装盘后，计算机从光盘引导系统，这时在初始安装菜单中选择“Install a command-line system”，之后与一般的安装过程并无二致。

在基本系统安装完成后，会要求重新启动一次系统，使用在安装过程中设置的帐号及密码登录。

现在，执行指令 sudo vim /etc/apt/sources.list，以便对 sources.list 文件进行编辑。在 VIM 打开文件后，将 deb http:// 或 deb-src http:// 前面包含的注释符号（#）删除。然后保存所作的修改。

为了完成后续的安装过程，需要继续执行指令 sudo apt-get update。

至此，最小化的 Ubuntu 安装已经就绪。

如果需要安装桌面环境，那么还可以执行以下的选择：

安装 X 窗口系统：sudo apt-get install x-window-system-core。
安装登录管理器：sudo apt-get install xdm/gdm/kdm[注]。最常见的图形化登录管理器包括 XDM、GDM、KDM，用户可根据自己的需要选择其中之一。
安装桌面环境或窗口管理器：sudo apt-get install ubuntu-desktop/kubuntu-desktop/xubuntu-desktop。这将分别安装 GNOME、KDE、XFCE 桌面环境。对于 GNOME、KDE、XFCE 这些桌面环境来说，为了获得更强的定制效果，也可仅安装最基本的组件，如：sudo apt-get install gnome-core/kde-core/xfce4。当然，如果不需要桌面环境，也可选择安装窗口管理器代替。那样的话，可以执行指令 sudo apt-get install fluxbox/icewm/enlightenment/fvwm。
安装软件：sudo apt-get install firefox/gaim/xmms。这将安装 Firefox 浏览器、Gaim 聊天程序、XMMS 音乐播放器。同样，不必拘泥于此处的示例，完全可以按自己的喜好来安装。

一旦完成上述过程的安装，重启系统，将会享受到一个完全自由的系统。

注释

类似 xdm/gdm/kdm 这样的写法需要读者选择其中一项才能无误地执行命令。

祝各位新春快乐！

更多精彩请到 http://www.139ya.com

如题

cup cake build

更多精彩请到 http://www.139ya.com

Examples to use this rysnc source.

1) sync the total cupcake to the local dir "/root/cupcake"

rsync --port 8873 -aP 10.194.72.89::cupcake-all /root/cupcake-all

2) sync the code of cupcake to the local dir "/root/cupcake"

rsync --port 8873 -aP 10.194.72.89::cupcake /root/cupcake

Please read rysnc's help to know how to do the incremental sync or total sync (remove the local change).

BTW:

1) one build issue in cupcake was found, which can't support the high-version gcc (like 4.3). So please install some lower gcc, such as gcc4.1, to complete the build.

To install the gcc/g++ 4.1 with the following command in debian or ubuntu.

apt-get install gcc-4.1 g++-4.1

To build the cupcake with gcc/g++ 4.1

make CC=gcc-4.1 CXX=g++-4.1

老大的年终讲话

更多精彩请到 http://www.139ya.com

All,

Today is the last working before Spring Festival Holiday, now it is the season to enjoy the time to have a good rest. I'd like to take this opportunity to thank everyone for your hard working in 2008.

2009 is going to be a much tougher year for Motorola, as well as each motorolan. I really appreciated your understanding on current situation in Motorola and depression of global economic circumstance and market, as well as the potential impact to each individual here in Motorola. Anyway this is part of life and everyone has to face. Let's look forward.

Best wishes to you and your family, HAPPY CHINESE NEW YEAR.

***************

Thursday, January 22, 2009

Firmware (固件) 是什么?

更多精彩请到 http://www.139ya.com

Firmware is the controler software for a device. It is written on a flash rom and can be update with a flash program to correct bugs in the controller software or to improve performance of a device.

Firmware是一种设备的控制软件，写在Flash ROM 中。可以用Flash程序来纠正控制软件中的错误或改善设备的性能。

嵌入式系统 Boot Loader 技术内幕

2003 年 12 月 01 日

本文详细地介绍了基于嵌入式系统中的 OS 启动加载程序 ―― Boot Loader 的概念、软件设计的主要任务以及结构框架等内容。

1. 引言

在专用的嵌入式板子运行 GNU/Linux 系统已经变得越来越流行。一个嵌入式 Linux 系统从软件的角度看通常可以分为四个层次：

1. 引导加载程序。包括固化在固件(firmware)中的 boot 代码(可选)，和 Boot Loader 两大部分。

2. Linux 内核。特定于嵌入式板子的定制内核以及内核的启动参数。

3. 文件系统。包括根文件系统和建立于 Flash 内存设备之上文件系统。通常用 ram disk 来作为 root fs。

4. 用户应用程序。特定于用户的应用程序。有时在用户应用程序和内核层之间可能还会包括一个嵌入式图形用户界面。常用的嵌入式 GUI 有：MicroWindows 和 MiniGUI 懂。

引导加载程序是系统加电后运行的第一段软件代码。回忆一下 PC 的体系结构我们可以知道，PC 机中的引导加载程序由 BIOS(其本质就是一段固件程序)和位于硬盘 MBR 中的 OS Boot Loader（比如，LILO 和 GRUB 等）一起组成。BIOS 在完成硬件检测和资源分配后，将硬盘 MBR 中的 Boot Loader 读到系统的 RAM 中，然后将控制权交给 OS Boot Loader。Boot Loader 的主要运行任务就是将内核映象从硬盘上读到 RAM 中，然后跳转到内核的入口点去运行，也即开始启动操作系统。

而在嵌入式系统中，通常并没有像 BIOS 那样的固件程序（注，有的嵌入式 CPU 也会内嵌一段短小的启动程序），因此整个系统的加载启动任务就完全由 Boot Loader 来完成。比如在一个基于 ARM7TDMI core 的嵌入式系统中，系统在上电或复位时通常都从地址 0x00000000 处开始执行，而在这个地址处安排的通常就是系统的 Boot Loader 程序。

本文将从 Boot Loader 的概念、Boot Loader 的主要任务、Boot Loader 的框架结构以及 Boot Loader 的安装等四个方面来讨论嵌入式系统的 Boot Loader。

2. Boot Loader 的概念

简单地说，Boot Loader 就是在操作系统内核运行之前运行的一段小程序。通过这段小程序，我们可以初始化硬件设备、建立内存空间的映射图，从而将系统的软硬件环境带到一个合适的状态，以便为最终调用操作系统内核准备好正确的环境。

通常，Boot Loader 是严重地依赖于硬件而实现的，特别是在嵌入式世界。因此，在嵌入式世界里建立一个通用的 Boot Loader 几乎是不可能的。尽管如此，我们仍然可以对 Boot Loader 归纳出一些通用的概念来，以指导用户特定的 Boot Loader 设计与实现。

1. Boot Loader 所支持的 CPU 和嵌入式板

每种不同的 CPU 体系结构都有不同的 Boot Loader。有些 Boot Loader 也支持多种体系结构的 CPU，比如 U-Boot 就同时支持 ARM 体系结构和MIPS 体系结构。除了依赖于 CPU 的体系结构外，Boot Loader 实际上也依赖于具体的嵌入式板级设备的配置。这也就是说，对于两块不同的嵌入式板而言，即使它们是基于同一种 CPU 而构建的，要想让运行在一块板子上的 Boot Loader 程序也能运行在另一块板子上，通常也都需要修改 Boot Loader 的源程序。

2. Boot Loader 的安装媒介（Installation Medium）

系统加电或复位后，所有的 CPU 通常都从某个由 CPU 制造商预先安排的地址上取指令。比如，基于 ARM7TDMI core 的 CPU 在复位时通常都从地址 0x00000000 取它的第一条指令。而基于 CPU 构建的嵌入式系统通常都有某种类型的固态存储设备(比如：ROM、EEPROM 或 FLASH 等)被映射到这个预先安排的地址上。因此在系统加电后，CPU 将首先执行 Boot Loader 程序。

下图1就是一个同时装有 Boot Loader、内核的启动参数、内核映像和根文件系统映像的固态存储设备的典型空间分配结构图。

3. 用来控制 Boot Loader 的设备或机制

主机和目标机之间一般通过串口建立连接，Boot Loader 软件在执行时通常会通过串口来进行 I/O，比如：输出打印信息到串口，从串口读取用户控制字符等。

4. Boot Loader 的启动过程是单阶段（Single Stage）还是多阶段（Multi-Stage）

通常多阶段的 Boot Loader 能提供更为复杂的功能，以及更好的可移植性。从固态存储设备上启动的 Boot Loader 大多都是 2 阶段的启动过程，也即启动过程可以分为 stage 1 和 stage 2 两部分。而至于在 stage 1 和 stage 2 具体完成哪些任务将在下面讨论。

5. Boot Loader 的操作模式 (Operation Mode)

大多数 Boot Loader 都包含两种不同的操作模式："启动加载"模式和"下载"模式，这种区别仅对于开发人员才有意义。但从最终用户的角度看，Boot Loader 的作用就是用来加载操作系统，而并不存在所谓的启动加载模式与下载工作模式的区别。

启动加载（Boot loading）模式：这种模式也称为"自主" （Autonomous）模式。也即 Boot Loader 从目标机上的某个固态存储设备上将操作系统加载到 RAM 中运行，整个过程并没有用户的介入。这种模式是 Boot Loader 的正常工作模式，因此在嵌入式产品发布的时侯，Boot Loader 显然必须工作在这种模式下。

下载（Downloading）模式：在这种模式下，目标机上的 Boot Loader 将通过串口连接或网络连接等通信手段从主机（Host）下载文件，比如：下载内核映像和根文件系统映像等。从主机下载的文件通常首先被 Boot Loader 保存到目标机的 RAM 中，然后再被 Boot Loader 写到目标机上的FLASH 类固态存储设备中。Boot Loader 的这种模式通常在第一次安装内核与根文件系统时被使用；此外，以后的系统更新也会使用 Boot Loader 的这种工作模式。工作于这种模式下的 Boot Loader 通常都会向它的终端用户提供一个简单的命令行接口。

像 Blob 或 U-Boot 等这样功能强大的 Boot Loader 通常同时支持这两种工作模式，而且允许用户在这两种工作模式之间进行切换。比如，Blob 在启动时处于正常的启动加载模式，但是它会延时 10 秒等待终端用户按下任意键而将 blob 切换到下载模式。如果在 10 秒内没有用户按键，则 blob 继续启动 Linux 内核。

6. BootLoader 与主机之间进行文件传输所用的通信设备及协议

最常见的情况就是，目标机上的 Boot Loader 通过串口与主机之间进行文件传输，传输协议通常是 xmodem／ymodem／zmodem 协议中的一种。但是，串口传输的速度是有限的，因此通过以太网连接并借助 TFTP 协议来下载文件是个更好的选择。

此外，在论及这个话题时，主机方所用的软件也要考虑。比如，在通过以太网连接和 TFTP 协议来下载文件时，主机方必须有一个软件用来的提供 TFTP 服务。

在讨论了 BootLoader 的上述概念后，下面我们来具体看看 BootLoader 的应该完成哪些任务。

3. Boot Loader 的主要任务与典型结构框架

在继续本节的讨论之前，首先我们做一个假定，那就是：假定内核映像与根文件系统映像都被加载到 RAM 中运行。之所以提出这样一个假设前提是因为，在嵌入式系统中内核映像与根文件系统映像也可以直接在 ROM 或 Flash 这样的固态存储设备中直接运行。但这种做法无疑是以运行速度的牺牲为代价的。

从操作系统的角度看，Boot Loader 的总目标就是正确地调用内核来执行。

另外，由于 Boot Loader 的实现依赖于 CPU 的体系结构，因此大多数 Boot Loader 都分为 stage1 和 stage2 两大部分。依赖于 CPU 体系结构的代码，比如设备初始化代码等，通常都放在 stage1 中，而且通常都用汇编语言来实现，以达到短小精悍的目的。而 stage2 则通常用C语言来实现，这样可以实现给复杂的功能，而且代码会具有更好的可读性和可移植性。

Boot Loader 的 stage1 通常包括以下步骤(以执行的先后顺序)：

硬件设备初始化。
为加载 Boot Loader 的 stage2 准备 RAM 空间。
拷贝 Boot Loader 的 stage2 到 RAM 空间中。
设置好堆栈。
跳转到 stage2 的 C 入口点。

Boot Loader 的 stage2 通常包括以下步骤(以执行的先后顺序)：

初始化本阶段要使用到的硬件设备。
检测系统内存映射(memory map)。
将 kernel 映像和根文件系统映像从 flash 上读到 RAM 空间中。
为内核设置启动参数。
调用内核。

3.1 Boot Loader 的 stage1

3.1.1 基本的硬件初始化

这是 Boot Loader 一开始就执行的操作，其目的是为 stage2 的执行以及随后的 kernel 的执行准备好一些基本的硬件环境。它通常包括以下步骤（以执行的先后顺序）：

1． 屏蔽所有的中断。为中断提供服务通常是 OS 设备驱动程序的责任，因此在 Boot Loader 的执行全过程中可以不必响应任何中断。中断屏蔽可以通过写 CPU 的中断屏蔽寄存器或状态寄存器（比如 ARM 的 CPSR 寄存器）来完成。

2． 设置 CPU 的速度和时钟频率。

3． RAM 初始化。包括正确地设置系统的内存控制器的功能寄存器以及各内存库控制寄存器等。

4． 初始化 LED。典型地，通过 GPIO 来驱动 LED，其目的是表明系统的状态是 OK 还是 Error。如果板子上没有 LED，那么也可以通过初始化 UART 向串口打印 Boot Loader 的 Logo 字符信息来完成这一点。

5． 关闭 CPU 内部指令／数据 cache。

3.1.2 为加载 stage2 准备 RAM 空间

为了获得更快的执行速度，通常把 stage2 加载到 RAM 空间中来执行，因此必须为加载 Boot Loader 的 stage2 准备好一段可用的 RAM 空间范围。

由于 stage2 通常是 C 语言执行代码，因此在考虑空间大小时，除了 stage2 可执行映象的大小外，还必须把堆栈空间也考虑进来。此外，空间大小最好是 memory page 大小(通常是 4KB)的倍数。一般而言，1M 的 RAM 空间已经足够了。具体的地址范围可以任意安排，比如 blob 就将它的 stage2 可执行映像安排到从系统 RAM 起始地址 0xc0200000 开始的 1M 空间内执行。但是，将 stage2 安排到整个 RAM 空间的最顶 1MB(也即(RamEnd-1MB) - RamEnd)是一种值得推荐的方法。

为了后面的叙述方便，这里把所安排的 RAM 空间范围的大小记为：stage2_size(字节)，把起始地址和终止地址分别记为：stage2_start 和 stage2_end(这两个地址均以 4 字节边界对齐)。因此：

stage2_end＝stage2_start＋stage2_size

另外，还必须确保所安排的地址范围的的确确是可读写的 RAM 空间，因此，必须对你所安排的地址范围进行测试。具体的测试方法可以采用类似于 blob 的方法，也即：以 memory page 为被测试单位，测试每个 memory page 开始的两个字是否是可读写的。为了后面叙述的方便，我们记这个检测算法为：test_mempage，其具体步骤如下：

1．先保存 memory page 一开始两个字的内容。

2．向这两个字中写入任意的数字。比如：向第一个字写入 0x55，第 2 个字写入 0xaa。

3．然后，立即将这两个字的内容读回。显然，我们读到的内容应该分别是 0x55 和 0xaa。如果不是，则说明这个 memory page 所占据的地址范围不是一段有效的 RAM 空间。

4．再向这两个字中写入任意的数字。比如：向第一个字写入 0xaa，第 2 个字中写入 0x55。

5．然后，立即将这两个字的内容立即读回。显然，我们读到的内容应该分别是 0xaa 和 0x55。如果不是，则说明这个 memory page 所占据的地址范围不是一段有效的 RAM 空间。

6．恢复这两个字的原始内容。测试完毕。

为了得到一段干净的 RAM 空间范围，我们也可以将所安排的 RAM 空间范围进行清零操作。

3.1.3 拷贝 stage2 到 RAM 中

拷贝时要确定两点：(1) stage2 的可执行映象在固态存储设备的存放起始地址和终止地址；(2) RAM 空间的起始地址。

3.1.4 设置堆栈指针 sp

堆栈指针的设置是为了执行 C 语言代码作好准备。通常我们可以把 sp 的值设置为(stage2_end-4)，也即在 3.1.2 节所安排的那个 1MB 的 RAM 空间的最顶端(堆栈向下生长)。

此外，在设置堆栈指针 sp 之前，也可以关闭 led 灯，以提示用户我们准备跳转到 stage2。

经过上述这些执行步骤后，系统的物理内存布局应该如下图2所示。

3.1.5 跳转到 stage2 的 C 入口点

在上述一切都就绪后，就可以跳转到 Boot Loader 的 stage2 去执行了。比如，在 ARM 系统中，这可以通过修改 PC 寄存器为合适的地址来实现。

图2 bootloader 的 stage2 可执行映象刚被拷贝到 RAM 空间时的系统内存布局

3.2 Boot Loader 的 stage2

正如前面所说，stage2 的代码通常用 C 语言来实现，以便于实现更复杂的功能和取得更好的代码可读性和可移植性。但是与普通 C 语言应用程序不同的是，在编译和链接 boot loader 这样的程序时，我们不能使用 glibc 库中的任何支持函数。其原因是显而易见的。这就给我们带来一个问题，那就是从那里跳转进 main() 函数呢？直接把 main() 函数的起始地址作为整个 stage2 执行映像的入口点或许是最直接的想法。但是这样做有两个缺点：1)无法通过main() 函数传递函数参数；2)无法处理 main() 函数返回的情况。一种更为巧妙的方法是利用 trampoline(弹簧床)的概念。也即，用汇编语言写一段trampoline 小程序，并将这段 trampoline 小程序来作为 stage2 可执行映象的执行入口点。然后我们可以在 trampoline 汇编小程序中用 CPU 跳转指令跳入 main() 函数中去执行；而当 main() 函数返回时，CPU 执行路径显然再次回到我们的 trampoline 程序。简而言之，这种方法的思想就是：用这段 trampoline 小程序来作为 main() 函数的外部包裹(external wrapper)。

下面给出一个简单的 trampoline 程序示例(来自blob)：

.text
.globl _trampoline
_trampoline:
 bl main
 /* if main ever returns we just call it again */
 b _trampoline

可以看出，当 main() 函数返回后，我们又用一条跳转指令重新执行 trampoline 程序――当然也就重新执行 main() 函数，这也就是 trampoline(弹簧床)一词的意思所在。

3.2.1初始化本阶段要使用到的硬件设备

这通常包括：（1）初始化至少一个串口，以便和终端用户进行 I/O 输出信息；（2）初始化计时器等。

在初始化这些设备之前，也可以重新把 LED 灯点亮，以表明我们已经进入 main() 函数执行。

设备初始化完成后，可以输出一些打印信息，程序名字字符串、版本号等。

3.2.2 检测系统的内存映射（memory map）

所谓内存映射就是指在整个 4GB 物理地址空间中有哪些地址范围被分配用来寻址系统的 RAM 单元。比如，在 SA-1100 CPU 中，从 0xC000,0000 开始的 512M 地址空间被用作系统的 RAM 地址空间，而在 Samsung S3C44B0X CPU 中，从 0x0c00,0000 到 0x1000,0000 之间的 64M 地址空间被用作系统的 RAM 地址空间。虽然 CPU 通常预留出一大段足够的地址空间给系统 RAM，但是在搭建具体的嵌入式系统时却不一定会实现 CPU 预留的全部 RAM 地址空间。也就是说，具体的嵌入式系统往往只把 CPU 预留的全部 RAM 地址空间中的一部分映射到 RAM 单元上，而让剩下的那部分预留 RAM 地址空间处于未使用状态。由于上述这个事实，因此 Boot Loader 的 stage2 必须在它想干点什么 (比如，将存储在 flash 上的内核映像读到 RAM 空间中) 之前检测整个系统的内存映射情况，也即它必须知道 CPU 预留的全部 RAM 地址空间中的哪些被真正映射到 RAM 地址单元，哪些是处于 "unused" 状态的。

(1) 内存映射的描述

可以用如下数据结构来描述 RAM 地址空间中的一段连续(continuous)的地址范围：

typedef struct memory_area_struct {
 u32 start; /* the base address of the memory region */
 u32 size; /* the byte number of the memory region */
 int used;
} memory_area_t;

这段 RAM 地址空间中的连续地址范围可以处于两种状态之一：(1)used=1，则说明这段连续的地址范围已被实现，也即真正地被映射到 RAM 单元上。(2)used=0，则说明这段连续的地址范围并未被系统所实现，而是处于未使用状态。

基于上述 memory_area_t 数据结构，整个 CPU 预留的 RAM 地址空间可以用一个 memory_area_t 类型的数组来表示，如下所示：

memory_area_t memory_map[NUM_MEM_AREAS] = {
 [0 ... (NUM_MEM_AREAS - 1)] = {
  .start = 0,
  .size = 0,
  .used = 0
 },
};

(2) 内存映射的检测

下面我们给出一个可用来检测整个 RAM 地址空间内存映射情况的简单而有效的算法：

/* 数组初始化 */
for(i = 0; i < NUM_MEM_AREAS; i++)
 memory_map[i].used = 0;
/* first write a 0 to all memory locations */
for(addr = MEM_START; addr < MEM_END; addr += PAGE_SIZE)
 * (u32 *)addr = 0;
for(i = 0, addr = MEM_START; addr < MEM_END; addr += PAGE_SIZE) {
    /*
     * 检测从基地址 MEM_START+i*PAGE_SIZE 开始,大小为
* PAGE_SIZE 的地址空间是否是有效的RAM地址空间。
     */
    调用3.1.2节中的算法test_mempage()；
    if ( current memory page isnot a valid ram page) {
  /* no RAM here */
  if(memory_map[i].used )
   i++;
  continue;
 }
 
 /*
  * 当前页已经是一个被映射到 RAM 的有效地址范围
  * 但是还要看看当前页是否只是 4GB 地址空间中某个地址页的别名？
  */
 if(* (u32 *)addr != 0) { /* alias? */
  /* 这个内存页是 4GB 地址空间中某个地址页的别名 */
  if ( memory_map[i].used )
   i++;
  continue;
 }
 
 /*
  * 当前页已经是一个被映射到 RAM 的有效地址范围
  * 而且它也不是 4GB 地址空间中某个地址页的别名。
  */
 if (memory_map[i].used == 0) {
  memory_map[i].start = addr;
  memory_map[i].size = PAGE_SIZE;
  memory_map[i].used = 1;
 } else {
  memory_map[i].size += PAGE_SIZE;
 }
} /* end of for (…) */

在用上述算法检测完系统的内存映射情况后，Boot Loader 也可以将内存映射的详细信息打印到串口。

3.2.3 加载内核映像和根文件系统映像

(1) 规划内存占用的布局

这里包括两个方面：(1)内核映像所占用的内存范围；（2）根文件系统所占用的内存范围。在规划内存占用的布局时，主要考虑基地址和映像的大小两个方面。

对于内核映像，一般将其拷贝到从(MEM_START＋0x8000) 这个基地址开始的大约1MB大小的内存范围内(嵌入式 Linux 的内核一般都不操过 1MB)。为什么要把从 MEM_START 到 MEM_START＋0x8000 这段 32KB 大小的内存空出来呢？这是因为 Linux 内核要在这段内存中放置一些全局数据结构，如：启动参数和内核页表等信息。

而对于根文件系统映像，则一般将其拷贝到 MEM_START+0x0010,0000 开始的地方。如果用 Ramdisk 作为根文件系统映像，则其解压后的大小一般是1MB。

（2）从 Flash 上拷贝

由于像 ARM 这样的嵌入式 CPU 通常都是在统一的内存地址空间中寻址 Flash 等固态存储设备的，因此从 Flash 上读取数据与从 RAM 单元中读取数据并没有什么不同。用一个简单的循环就可以完成从 Flash 设备上拷贝映像的工作：


while(count) {
 *dest++ = *src++; /* they are all aligned with word boundary */
 count -= 4; /* byte number */
};

3.2.4 设置内核的启动参数

应该说，在将内核映像和根文件系统映像拷贝到 RAM 空间中后，就可以准备启动 Linux 内核了。但是在调用内核之前，应该作一步准备工作，即：设置 Linux 内核的启动参数。

Linux 2.4.x 以后的内核都期望以标记列表(tagged list)的形式来传递启动参数。启动参数标记列表以标记 ATAG_CORE 开始，以标记 ATAG_NONE 结束。每个标记由标识被传递参数的 tag_header 结构以及随后的参数值数据结构来组成。数据结构 tag 和 tag_header 定义在 Linux 内核源码的include/asm/setup.h 头文件中：

/* The list ends with an ATAG_NONE node. */
#define ATAG_NONE 0x00000000
struct tag_header {
 u32 size; /* 注意，这里size是字数为单位的 */
 u32 tag;
};
……
struct tag {
 struct tag_header hdr;
 union {
  struct tag_core  core;
  struct tag_mem32 mem;
  struct tag_videotext videotext;
  struct tag_ramdisk ramdisk;
  struct tag_initrd initrd;
  struct tag_serialnr serialnr;
  struct tag_revision revision;
  struct tag_videolfb videolfb;
  struct tag_cmdline cmdline;
  /*
   * Acorn specific
   */
  struct tag_acorn acorn;
  /*
   * DC21285 specific
   */
  struct tag_memclk memclk;
 } u;
};

在嵌入式 Linux 系统中，通常需要由 Boot Loader 设置的常见启动参数有：ATAG_CORE、ATAG_MEM、ATAG_CMDLINE、ATAG_RAMDISK、ATAG_INITRD等。

比如，设置 ATAG_CORE 的代码如下：

params = (struct tag *)BOOT_PARAMS;
 params->hdr.tag = ATAG_CORE;
 params->hdr.size = tag_size(tag_core);
 params->u.core.flags = 0;
 params->u.core.pagesize = 0;
 params->u.core.rootdev = 0;
 params = tag_next(params);

其中，BOOT_PARAMS 表示内核启动参数在内存中的起始基地址，指针 params 是一个 struct tag 类型的指针。宏 tag_next() 将以指向当前标记的指针为参数，计算紧临当前标记的下一个标记的起始地址。注意，内核的根文件系统所在的设备ID就是在这里设置的。

下面是设置内存映射情况的示例代码：

for(i = 0; i < NUM_MEM_AREAS; i++) {
  if(memory_map[i].used) {
   params->hdr.tag = ATAG_MEM;
   params->hdr.size = tag_size(tag_mem32);
   params->u.mem.start = memory_map[i].start;
   params->u.mem.size = memory_map[i].size;
   
   params = tag_next(params);
  }
}

可以看出，在 memory_map［］数组中，每一个有效的内存段都对应一个 ATAG_MEM 参数标记。

Linux 内核在启动时可以以命令行参数的形式来接收信息，利用这一点我们可以向内核提供那些内核不能自己检测的硬件参数信息，或者重载(override)内核自己检测到的信息。比如，我们用这样一个命令行参数字符串"console=ttyS0,115200n8"来通知内核以 ttyS0 作为控制台，且串口采用 "115200bps、无奇偶校验、8位数据位"这样的设置。下面是一段设置调用内核命令行参数字符串的示例代码：

char *p;
 /* eat leading white space */
 for(p = commandline; *p == ' '; p++)
  ;
 /* skip non-existent command lines so the kernel will still
   * use its default command line.
  */
 if(*p == '\0')
  return;
 params->hdr.tag = ATAG_CMDLINE;
 params->hdr.size = (sizeof(struct tag_header) + strlen(p) + 1 + 4) >> 2;
 strcpy(params->u.cmdline.cmdline, p);
 params = tag_next(params);

请注意在上述代码中，设置 tag_header 的大小时，必须包括字符串的终止符'\0'，此外还要将字节数向上圆整4个字节，因为 tag_header 结构中的size 成员表示的是字数。

下面是设置 ATAG_INITRD 的示例代码，它告诉内核在 RAM 中的什么地方可以找到 initrd 映象(压缩格式)以及它的大小：

 params->hdr.tag = ATAG_INITRD2;
 params->hdr.size = tag_size(tag_initrd);
 
 params->u.initrd.start = RAMDISK_RAM_BASE;
 params->u.initrd.size = INITRD_LEN;
 
 params = tag_next(params);

下面是设置 ATAG_RAMDISK 的示例代码，它告诉内核解压后的 Ramdisk 有多大（单位是KB）：

params->hdr.tag = ATAG_RAMDISK;
params->hdr.size = tag_size(tag_ramdisk);
 
params->u.ramdisk.start = 0;
params->u.ramdisk.size = RAMDISK_SIZE; /* 请注意，单位是KB */
params->u.ramdisk.flags = 1; /* automatically load ramdisk */
 
params = tag_next(params);

最后，设置 ATAG_NONE 标记，结束整个启动参数列表：

static void setup_end_tag(void)
{
 params->hdr.tag = ATAG_NONE;
 params->hdr.size = 0;
}

3.2.5 调用内核

Boot Loader 调用 Linux 内核的方法是直接跳转到内核的第一条指令处，也即直接跳转到 MEM_START＋0x8000 地址处。在跳转时，下列条件要满足：

1． CPU 寄存器的设置：

R0＝0；
R1＝机器类型 ID；关于 Machine Type Number，可以参见 linux/arch/arm/tools/mach-types。
R2＝启动参数标记列表在 RAM 中起始基地址；

2． CPU 模式：

必须禁止中断（IRQs和FIQs）；
CPU 必须 SVC 模式；

3． Cache 和 MMU 的设置：

MMU 必须关闭；
指令 Cache 可以打开也可以关闭；
数据 Cache 必须关闭；

如果用 C 语言，可以像下列示例代码这样来调用内核：

void (*theKernel)(int zero, int arch, u32 params_addr) = (void (*)(int, int, u32))KERNEL_RAM_BASE;
……
theKernel(0, ARCH_NUMBER, (u32) kernel_params_start);

注意，theKernel()函数调用应该永远不返回的。如果这个调用返回，则说明出错。

4. 关于串口终端

在 boot loader 程序的设计与实现中，没有什么能够比从串口终端正确地收到打印信息能更令人激动了。此外，向串口终端打印信息也是一个非常重要而又有效的调试手段。但是，我们经常会碰到串口终端显示乱码或根本没有显示的问题。造成这个问题主要有两种原因：(1) boot loader 对串口的初始化设置不正确。(2) 运行在 host 端的终端仿真程序对串口的设置不正确，这包括：波特率、奇偶校验、数据位和停止位等方面的设置。

此外，有时也会碰到这样的问题，那就是：在 boot loader 的运行过程中我们可以正确地向串口终端输出信息，但当 boot loader 启动内核后却无法看到内核的启动输出信息。对这一问题的原因可以从以下几个方面来考虑：

(1) 首先请确认你的内核在编译时配置了对串口终端的支持，并配置了正确的串口驱动程序。

(2) 你的 boot loader 对串口的初始化设置可能会和内核对串口的初始化设置不一致。此外，对于诸如 s3c44b0x 这样的 CPU，CPU 时钟频率的设置也会影响串口，因此如果 boot loader 和内核对其 CPU 时钟频率的设置不一致，也会使串口终端无法正确显示信息。

(3) 最后，还要确认 boot loader 所用的内核基地址必须和内核映像在编译时所用的运行基地址一致，尤其是对于 uClinux 而言。假设你的内核映像在编译时用的基地址是 0xc0008000，但你的 boot loader 却将它加载到 0xc0010000 处去执行，那么内核映像当然不能正确地执行了。

5. 结束语

Boot Loader 的设计与实现是一个非常复杂的过程。如果不能从串口收到那激动人心的"uncompressing linux.................. done, booting the kernel……"内核启动信息，恐怕谁也不能说："嗨，我的 boot loader 已经成功地转起来了！"。

Wednesday, January 21, 2009

中缀到后缀表达式的转换

///////////////////////////////////////////////////////////////////////////////
//
//  FileName    :   postfix.cpp
//  Version     :   0.10
//  Author      :   Luo Cong
//  Date        :   2005-1-6 16:00:54
//  Comment     :  
//
///////////////////////////////////////////////////////////////////////////////

// 算法：
// 1)检查输入的下一元素。
// 2)假如是个操作数，输出。
// 3)假如是个开括号，将其压栈。
// 4)假如是个运算符，则
//   i) 假如栈为空，将此运算符压栈。
//   ii) 假如栈顶是开括号，将此运算符压栈。
//   iii) 假如此运算符比栈顶运算符优先级高，将此运算符压入栈中。
//   iv) 否则栈顶运算符出栈并输出，重复步骤4。
// 5)假如是个闭括号，栈中运算符逐个出栈并输出，直到遇到开括号。开括号出栈并丢弃。
// 6)假如输入还未完毕，跳转到步骤1。
// 7)假如输入完毕，栈中剩余的所有操作符出栈并输出它们。

#include <stdio.h>
#include "stack.h"

// 返回操作符的优先级
// +和-的优先级是一样的，*和/的优先级也是一样的，但+和-的优先级要比*和/的低。
static int GetPRI(const char optr)
{
   switch (optr)
   {
   case '+': return 1;
   case '-': return 1;
   case '*': return 2;
   case '/': return 2;
   default : return 0;
   }
}

// 在这个函数中完成对栈顶的操作符和当前操作符的优先级对比，
// 并决定是输出当前的操作符还是对当前的操作符进行入栈处理。
static void ProcessStackPRI(
   CStack<char> &stack,
   const char optr,
   char **szPostfix
)
{
   ASSERT(*szPostfix);

   int i;
   int nRetCode;
   char chStackOptr;
   int nCount = stack.GetCount();

   for (i = 0; i <= nCount; ++i)
   {
       nRetCode = stack.top(&chStackOptr);
       if (
           (0 == nRetCode) ||                  // 栈顶为空，新操作符添加到栈顶
           (GetPRI(chStackOptr) < GetPRI(optr))// 栈顶操作符优先级比当前的要低
       )
       {
           stack.push(optr);
           break;
       }
       else
       {
           // 如果栈顶操作符优先级不低于当前的，则栈顶元素出栈并输出：
           stack.pop();
           *(*szPostfix)++ = chStackOptr;
       }
   }
}

static void Infix2Postfix(
   const char *szInfix,
   char *szPostfix
)
{
   ASSERT(szPostfix);

   char chOptr;
   int nRetCode;
   CStack<char> stack;

   while (*szInfix)
   {
       switch (*szInfix)
       {
       // 忽略空格和TAB：
       case ' ':
       case '\t':
           break;

       // 对操作符进行优先级判断，以便决定是入栈还是输出：
       case '+':
       case '-':
       case '*':
       case '/':
           nRetCode = stack.IsEmpty();
           if (!nRetCode)
               ProcessStackPRI(stack, *szInfix, &szPostfix);
           else
               stack.push(*szInfix);   // 当栈为空时，毫无疑问操作符应该入栈
           break;

       // 遇到左括号时，无条件入栈，因为它的优先级是最高的
       case '(':
           stack.push(*szInfix);
           break;

       // 遇到右括号时，逐个把栈中的操作符出栈，直到遇到左括号为止
       case ')':
           do
           {
               nRetCode = stack.pop(&chOptr);
               if (nRetCode && ('(' != chOptr))            // 左括号本身不输出
                   *szPostfix++ = chOptr;
           } while (!stack.IsEmpty() && ('(' != chOptr));  // 遇到左括号为止
           break;

       // 其余的情况，直接输出即可
       default:
           *szPostfix++ = *szInfix;
           break;
       }
       ++szInfix;
   }
   // 如果输入的内容已经分析完毕，那么就把栈中剩余的操作符全部出栈
   while (!stack.IsEmpty())
   {
       nRetCode = stack.pop(&chOptr);
       *szPostfix++ = chOptr;
   }
   *szPostfix = '\0';
}

int main()
{
   char *szInfix = "a+b*c+(d*e+f)*g";
   char szPostfix[255];

#ifdef _DEBUG
   _CrtSetDbgFlag(_CRTDBG_ALLOC_MEM_DF | _CRTDBG_LEAK_CHECK_DF);
#endif

   Infix2Postfix(szInfix, szPostfix);

   printf("Infix   : %s\n", szInfix);
   printf("Postfix : %s\n", szPostfix);
}

算法的时间复杂度（计算实例）

更多精彩请到 http://www.139ya.com

转自: http://blog.chinaunix.net/u/26481/showart_479537.html

算法的时间复杂度

2007年12月02日星期日 01:17
定义：如果一个问题的规模是n，解这一问题的某一算法所需要的时间为T(n)，它是n的某一函数 T(n)称为这一算法的“时间复杂性”。

当输入量n逐渐加大时，时间复杂性的极限情形称为算法的“渐近时间复杂性”。

我们常用大O表示法表示时间复杂性，注意它是某一个算法的时间复杂性。大O表示只是说有上界，由定义如果f(n)=O(n)，那显然成立f(n)=O(n^2)，它给你一个上界，但并不是上确界，但人们在表示的时候一般都习惯表示前者。

此外，一个问题本身也有它的复杂性，如果某个算法的复杂性到达了这个问题复杂性的下界，那就称这样的算法是最佳算法。

“ 大O记法”：在这种描述中使用的基本参数是 n，即问题实例的规模，把复杂性或运行时间表达为n的函数。这里的“O”表示量级 (order)，比如说“二分检索是 O(logn)的”,也就是说它需要“通过logn量级的步骤去检索一个规模为n的数组”记法 O ( f(n) )表示当 n增大时，运行时间至多将以正比于 f(n)的速度增长。

这种渐进估计对算法的理论分析和大致比较是非常有价值的，但在实践中细节也可能造成差异。例如，一个低附加代价的O(n2)算法在n较小的情况下可能比一个高附加代价的 O(nlogn)算法运行得更快。当然，随着n足够大以后，具有较慢上升函数的算法必然工作得更快。

O(1)

Temp=i;i=j;j=temp;

以上三条单个语句的频度均为1，该程序段的执行时间是一个与问题规模n无关的常数。算法的时间复杂度为常数阶，记作T(n)=O(1)。如果算法的执行时间不随着问题规模n的增加而增长，即使算法中有上千条语句，其执行时间也不过是一个较大的常数。此类算法的时间复杂度是O(1)。

O(n^2)

2.1. 交换i和j的内容
sum=0；（一次）
for(i=1;i<=n;i++) （n次）
for(j=1;j<=n;j++) （n^2次）
sum++；（n^2次）
解：T(n)=2n^2+n+1 =O(n^2)

2.2.
for (i=1;i
{
y=y+1; ①
for (j=0;j<=(2*n);j++)
x++; ②
}
解：语句1的频度是n-1
语句2的频度是(n-1)*(2n+1)=2n^2-n-1
f(n)=2n^2-n-1+(n-1)=2n^2-2
该程序的时间复杂度T(n)=O(n^2).

O(n)

2.3.
a=0;
b=1; ①
for (i=1;i<=n;i++) ②
{
s=a+b;　　　　③
b=a;　　　　　④
a=s;　　　　　⑤
}
解：语句1的频度：2,
语句2的频度： n,
语句3的频度： n-1,
语句4的频度：n-1,
语句5的频度：n-1,
T(n)=2+n+3(n-1)=4n-1=O(n).

O(log2n )

2.4.
i=1; ①
while (i<=n)
i=i*2; ②
解：语句1的频度是1,
设语句2的频度是f(n), 则：2^f(n)<=n;f(n)<=log2n
取最大值f(n)= log2n,
T(n)=O(log2n )

O(n^3)

2.5.
for(i=0;i
{
for(j=0;j
{
for(k=0;k
x=x+2;
}
}
解：当i=m, j=k的时候,内层循环的次数为k当i=m时, j 可以取 0,1,...,m-1 , 所以这里最内循环共进行了0+1+...+m-1=(m-1)m/2次所以,i从0取到n, 则循环共进行了: 0+(1-1)*1/2+...+(n-1)n/2=n(n+1)(n-1)/6所以时间复杂度为O(n^3).

我们还应该区分算法的最坏情况的行为和期望行为。如快速排序的最坏情况运行时间是 O(n^2)，但期望时间是 O(nlogn)。通过每次都仔细地选择基准值，我们有可能把平方情况 (即O(n^2)情况)的概率减小到几乎等于 0。在实际中，精心实现的快速排序一般都能以 (O(nlogn)时间运行。
下面是一些常用的记法：

访问数组中的元素是常数时间操作，或说O(1)操作。一个算法如果能在每个步骤去掉一半数据元素，如二分检索，通常它就取 O(logn)时间。用strcmp比较两个具有n个字符的串需要O(n)时间。常规的矩阵乘算法是O(n^3)，因为算出每个元素都需要将n对元素相乘并加到一起，所有元素的个数是n^2。
指数时间算法通常来源于需要求出所有可能结果。例如，n个元素的集合共有2n个子集,所以要求出所有子集的算法将是O(2n)的。指数算法一般说来是太复杂了，除非n的值非常小，因为，在这个问题中增加一个元素就导致运行时间加倍。不幸的是，确实有许多问题 (如著名的“巡回售货员问题” )，到目前为止找到的算法都是指数的。如果我们真的遇到这种情况，通常应该用寻找近似最佳结果的算法替代之。

时间复杂度

更多精彩请到 http://www.139ya.com

时间复杂度

　　（1）时间频度
　　一个算法执行所耗费的时间，从理论上是不能算出来的，必须上机运行测试才能知道。但我们不可能也没有必要对每个算法都上机测试，只需知道哪个算法花费的时间多，哪个算法花费的时间少就可以了。并且一个算法花费的时间与算法中语句的执行次数成正比例，哪个算法中语句执行次数多，它花费时间就多。一个算法中的语句执行次数称为语句频度或时间频度。记为T(n)。
　　（2）时间复杂度
　　在刚才提到的时间频度中，n称为问题的规模，当n不断变化时，时间频度T(n)也会不断变化。但有时我们想知道它变化时呈现什么规律。为此，我们引入时间复杂度概念。
　　一般情况下，算法中基本操作重复执行的次数是问题规模n的某个函数，用T(n)表示，若有某个辅助函数f(n),使得当n趋近于无穷大时，T（n)/f(n)的极限值为不等于零的常数，则称f(n)是T(n)的同数量级函数。记作 T(n)=Ｏ(f(n)),称Ｏ(f(n)) 为算法的渐进时间复杂度，简称时间复杂度。
　　在各种不同算法中，若算法中语句执行次数为一个常数，则时间复杂度为O(1),另外，在时间频度不相同时，时间复杂度有可能相同，如T(n)=n^2+3n+4与T(n)=4n^2+2n+1它们的频度不同，但时间复杂度相同，都为O(n^2)。
　　按数量级递增排列，常见的时间复杂度有：
　　常数阶O(1),对数阶O(log(2)n),线性阶O(n),
　　线性对数阶O(nlog(2)n),平方阶O(n^2)，立方阶O(n^3),...，
　　k次方阶O(n^k),指数阶O(2^n)。随着问题规模n的不断增大，上述时间复杂度不断增大，算法的执行效率越低。
　　（3）算法的时间复杂度
　　若要比较不同的算法的时间效率，首先要确定一个度量标准，最直接的办法就是将计算法转化为程序，在计算机上运行，通过计算机内部的计时
　　功能获得精确的时间，然后进行比较。但该方法受计算机的硬件、软件等因素的影响，会掩盖算法本身的优劣，所以一般采用事先分析估算的算法，
　　即撇开计算机软硬件等因素，只考虑问题的规模（一般用用自然数n表示），认为一个特定的算法的时间复杂度，只采取于问题的规模，或者说它是
　　问题的规模的函数。
　　为了方便比较，通常的做法是，从算法选取一种对于所研究的问题（或算法模型）来说是基本运算的操作，以其重复执行的次数作为评价算法时间
　　复杂度的标准。该基本操作多数情况下是由算法最深层环内的语句表示的，基本操作的执行次数实际上就是相应语句的执行次数。

一般 T（n）=O(f(n))
　　O(1)<O(log2n)<O(n)<O(n log2 n)<O(n^2)<O(n^3)<O(2^n)所以要选择时间复杂度量级低的算法。

Tuesday, January 20, 2009

站内搜索 co-op

在blogger中贴代码

更多精彩请到 http://www.139ya.com

新手遇到的难题，我开始也对此很头痛，直接拷贝别人的代码框却不成功。现在弄明白了，其实很简单，就是先要在你的模板中加入一个CSS代码。
Step1：进入到控制台－模板－修改HTML ，“扩展窗口小部件模板” 前不用打勾。在模板内容里找到下面这段代码，你可以通过按Ctrl+F搜索“skin”两次找到
]]></b:skin>
</head>

然后将下面的代码段拷贝加到上面代码的前面，就是那两个中括号前面

CODE {
display: block; /* fixes a strange ie margin bug */
font-family: Courier New;
font-size: 8pt;
overflow:auto;
background: #f0f0f0 url(http://klcintw.images.googlepages.com/Code_BG.gif) left top repeat-y;
border: 1px solid #ccc;
padding: 10px 10px 10px 21px;
max-height:200px;
line-height: 1.2em;
}

Step2：在Html模式下，把文章中将要引用的代码前后分别用<code> 和 </code> 包起来，这样就可以显示成代码框了。

需要注意的是如果引用的程序中含有<> 括号，要把"<"用“<”代替，“>”用">"代替，不然<>的内容就会被Blogger的编辑器当成代码执行而不显示。

code paste test

更多精彩请到 http://www.139ya.com


<html>
<head>
<meta http-equiv="Content-Type" content="text/html; charset=utf-8" />
<title>Code Box</title>
<style type="text/css">
pre.code {
border:1px solid #99BBE8;
padding:2px;
}
.code-box {
border:1px solid #99BBE8;
margin:5px 2px;
}
.code-box-head {
margin:0px;
height:26px;
line-height:26px;
font-size:20px;
background:url(http://w.886.cn/4gYC/120961475/120961475_1902.gif) #D3E1F1;
border-bottom:1px solid #99BBE8;
margin-bottom:0px;
padding:0px 2px;
color:#15428B;
}
.code-box-head a {
text-indent:0px;
border:1px solid #D3E1F1;
margin:2px 3px;
height:20px;
line-height:20px;
padding:0px 4px;
float:right;
font-size:12px;
text-decoration:none;
color:#7692AD
}
.code-box-head a:hover {border:1px solid #99BBE8;}
.code-box-content {
margin:0px;
background-color:#FFFFFF;
padding:2px;
color:#000066;
}
</style>
<script src='http://greatghoul.go1.icpcn.com/blogger/CodeBox.js' type='text/javascript'/></script>
</head>
<body>
<pre class="code" title="HEAD">
使用方法:
<pre class="code html" title="代码标题">
class 中code是必须的.当贴出的代码为html代码时,加上 html
转换后的代码(转换工具见文末)
</pre>
</pre>
<pre class="code">
Some Code
</pre>
</body>
</html>

Run Android Application from Command Line

更多精彩请到 http://www.139ya.com

转自: http://learnandroid.blogspot.com/2008/01/run-android-application-from-command.html

Sometime, we want to start the android application program from command line (Android Shell). Before, we usually clicking on the icon at application folder to run our program. So, there is an alternative way to run the program.

We use the Android Shell and issue am command to brought up the program. below is an example to do that.
1. Make sure that android emulator is running
2. Enter the shell with issuing command at command shell (prompt): adb shell
3. Issue am command. am command syntax is as follow :

am [start|instrument]
am start [-a ] [-d ] [-t ]
[-c [-c ] ...]
[-e [-e ...]
[-n ] [-D] []
am instrument [-e ] [-p ]
[-w]

for example we have android program with Manifest like below:

package="com.iftitah.android.contact">

.
.

To run the code issue command like this (in one line):

am start -a android.intent.action.MAIN -n
com.iftitah.android.contact/com.iftitah.android.contact.Contact

ok, Have a nice try!

HOWTO Build Android-X86 Full Source

更多精彩请到 http://www.139ya.com

转自: http://groups.google.co.jp/group/android-porting/browse_thread/thread/66862bdb52dac936

HOWTO Build Android-X86 Full Source
====================================
Last Modified on 23-Dec-2008 23:10

I Summarized how to build android full source for x86 target.

0. My development environments
- OS : Ubuntu 8.10 Distribution ( 2.6.27-4-generic )
- CPU: Intel(R) Core(TM)2 Duo CPU T5750 @ 2.00GHz ( Samsung SENS
R60 Laptop )
- RAM: Samsung DDR Ram
- Target: Eee PC (ASUS)

1. Query of Linux distribution information
- At first, Prepare ASUS Eee 701 Lattop or Samsung nettop (NC01).
And then, confirm system information on your linux distribution
like belows.

$ uname -a
Linux invain-laptop 2.6.27-4-generic #1 SMP Wed Sep 24 01:30:51 UTC
2008 i686 GNU/Linux

$ gcc --version
gcc (Ubuntu 4.3.2-1ubuntu10) 4.3.2
Copyright (C) 2008 Free Software Foundation, Inc.
This is free software; see the source for copying conditions. There
is NO
warranty; not even for MERCHANTABILITY or FITNESS FOR A PARTICULAR
PURPOSE.

2. repo init and Sync
- You have to download android full source for x86 architecture like
ASUS Eee PC 701.
- Eee pc dev tree is "git://android.git.kernel.org/platform/vendor/
asus/eee_701.git".
$ cd ~
$ mkdir bin_x86 && cd bin_x86
$ mkdir mydroid && cd mydroid
$ repo init -u git://android.git.kernel.org/platform/manifest.git -b
cupcake
$ repo sync
$ vi ./.repo/local_manifest.xml

$ repo sync
... A new repo command ( 1.8) is available.
... You should upgrade soon:

cp /home/invain/bin_x86/mydroid/.repo/repo/repo /home/invain/bin/
repo

Initializing project platform/vendor/asus/eee_701 ...
remote: Counting objects: 33, done.
remote: Compressing objects: 100% (31/31), done.
remote: Total 33 (delta 2), reused 33 (delta 2)
Unpacking objects: 100% (33/33), done.
From git://android.git.kernel.org/platform/vendor/asus/eee_701
* [new branch] cupcake -> korg/cupcake
* [new branch] master -> korg/master

3. Building x86 android full source
$ TARGET_ARCH=x86 TARGET_PRODUCT=eee_701 DISABLE_DEXPREOPT=true make -
j2 installer_img

build/core/product_config.mk:207: WARNING: adding test OTA key
============================================
TARGET_PRODUCT=eee_701
TARGET_BUILD_VARIANT=eng
TARGET_SIMULATOR=
TARGET_BUILD_TYPE=release
TARGET_ARCH=x86
HOST_ARCH=x86
HOST_OS=linux
HOST_BUILD_TYPE=release
BUILD_ID=
============================================
build/core/main.mk:178: implicitly installing apns-conf_sdk.xml
............... Below Omission ...................

* Toouble Shooting

$ vi external/srec/tools/thirdparty/OpenFst/fst/lib/../../fst/lib/
vector-fst.h
$ vi external/srec/tools/thirdparty/OpenFst/fst/lib/symbol-table.cpp
$ vi frameworks/base/tools/aidl/aidl.cpp --> #include ,
#include
and so on......

$ vi
$ ls -lh out/target/product/eee_701/
total 753M
-rw-r--r-- 1 oedev oedev 2.5M 2008-12-20 21:23 boot.img
-rw-r--r-- 1 oedev oedev 57 2008-12-20 22:15 clean_steps.mk
drwxr-xr-x 4 oedev oedev 4.0K 2008-12-20 21:32 data
drwxr-xr-x 2 oedev oedev 4.0K 2008-12-20 19:54 grub
drwxr-xr-x 4 oedev oedev 4.0K 2008-12-20 22:36 installer
-rw-r--r-- 1 oedev oedev 388M 2008-12-20 22:38 installer.img
-rw-r--r-- 1 oedev oedev 1.9M 2008-12-20 18:45 kernel
drwxr-xr-x 12 oedev oedev 4.0K 2008-12-20 22:33 obj
-rw-r--r-- 1 oedev oedev 592K 2008-12-20 21:10 ramdisk.img
drwxr-xr-x 9 oedev oedev 4.0K 2008-12-20 21:09 root
drwxr-xr-x 4 oedev oedev 4.0K 2008-12-20 19:55 symbols
drwxr-xr-x 12 oedev oedev 4.0K 2008-12-20 21:29 system
-rw-r--r-- 1 oedev oedev 355M 2008-12-20 22:34 system.img
-rw-r--r-- 1 oedev oedev 5.0M 2008-12-20 21:32 userdata.img

$ file out/target/product/eee_701/installer.img
out/target/product/eee_701/installer.img: x86 boot sector;
GRand Unified Bootloader, stage1 version 0x3; partition 2:
ID=0x83, starthead 0, startsector 10926, 783672 sectors, code offset
0x48

$ file out/target/product/eee_701/system.img
out/target/product/eee_701/system.img: Linux rev 0.0 ext2 filesystem
data

$ file out/target/product/eee_701/userdata.img
out/target/product/eee_701/userdata.img: Linux rev 0.0 ext2 filesystem
data

$ sudo mount -o loop boot.img /mnt
total 2.5M
-rw-r--r-- 1 oedev oedev 77 2008-12-20 21:23 cmdline
-rw-r--r-- 1 oedev oedev 1.9M 2008-12-20 21:23 kernel
-rw-r--r-- 1 oedev oedev 592K 2008-12-20 21:23 ramdisk

$ cat /mnt/cmndline
console=tty0 console=ttyS1,115200n8 console=tty0
androidboot.hardware=eee_701

$ cp /mnt/ramdisk /tmp/ramdisk.gz
$ cd /tmp
$ gunzip ramdisk.gz
$ cpio -iv < ramdisk
sys
init.goldfish.rc
system
data
init.rc
proc
init
default.prop
sbin
sbin/adbd
init.eee_701.rc
lib
lib/modules
lib/modules/i915.ko
lib/modules/font.ko
lib/modules/drm.ko
lib/modules/cfbcopyarea.ko
lib/modules/cfbimgblt.ko
lib/modules/bitblit.ko
lib/modules/cfbfillrect.ko
lib/modules/softcursor.ko
lib/modules/fbcon.ko
lib/modules/atl2.ko
dev
2955 blocks

$ file /tmp/init
/tmp/init: ELF 32-bit LSB executable, Intel 80386, version 1 (SYSV),
statically linked, not stripped

4. Make USB Stick Installer
$ dd if=out/target/product/eee_701/installer.img of=/dev/your choice>

5. Now. Enjoy X86 Android Platform!

End of Line.

Linux系统的进程管理

更多精彩请到 http://www.139ya.com

Linux系统的进程管理

在Linux系统里，当前正在运行的程序实例称为进程。比如，当你启动Apache的时候，系统会为它分配一个进程ID。然后就可以用这个ID监视和控制这个程序。

进程监视和控制是任何Linux系统管理员的核心任务。一个管理员可以终止（"kill"）、重启一个进程，甚至可以为它指定一个不同的优先级。标准的 Linux命令"ps"和"top"通常用于查看当前的进程列表。下面我来说明如何用这些命令和其它命令来管理Linux系统中的进程。

用ps监视进程
一个监视Linux的标准工具就是"ps"，它是进程状态的简称。这个命令返回正在运行的程序的信息。这些信息可能包括程序是在哪个用户名下运行的，使用了多少CPU以及运行了多长时间。如果你要手工终止程序或者确定是哪个程序让系统变慢时，这些信息是很有用的。

如果你只是键入了"ps"这个命令，那么只能列出运行在当前终端下的进程。下面的例子是通过远程shell运行"ps"输出的结果：

　　$ ps
　　PID TTY TIME CMD
　　4684 pts/14 00:00:00 bash
　　27107 pts/14 00:00:00 ps

从输出可以看出，分配给这个用户/终端的进程只有Bash shell和ps命令本身。你还可以看到为每个进程列出的PID（进程ID）和TTY、TIME和CMD。TTY指明这个进程正在运行在哪个终端上，TIME指明了这个进程已经使用了多少CPU时间，CMD则是启动这个进程的命令名称。

用户可以看到，标准的ps命令只能列出基本的信息。要想获得Linux系统上运行的进程的详细信息，你必须加入一些命令行参数。

加入ps常用的aux参数后可以显示其他用户启动的进程（a）、查看系统中属于自己的进程（x）以及启动这个进程的用户和它启动的时间（u）。

现在还有其它更多的信息，增加了USER、 %CPU、%MEM、 VSZ、RSS、STAT和START这几个域。现在我们来看一下这些信息是什么含义。

首先，用户可以看到所有的进程，而不仅仅是运行在终端上的那些。USER域指明了是哪个用户启动了这个命令。很多进程和系统一起启动，而且会把根或者一些系统帐号列为USER。当然，其它一些进程是单独运行的。这个信息本身就可以帮助你缩小问题范围。假如某个用户启动了脚本，占用了服务器大量的I/O。如果能马上找到是谁在运行这个程序，那么就可以大大加快解决问题的速度。

%CPU、 %MEM、VSZ和RSS这几个域都与系统资源有关。首先，用户可以查看某个进程占用了多少CPU。这个信息是实时显示的，所以很难用ps捕捉峰值。可能用户会发现，为了找到引发问题的那个进程需要不停地运行ps命令。

除了CPU使用情况，还可以看到内存使用及其VSZ（虚拟内存大小）和RSS（常驻集大小）。VSZ表示如果一个程序完全驻留在内存的话需要占用多少内存空间，而RSS指明了当前实际占用了多少内存。如果能够了解一个进程当前占用了多少内存，那么就可以确定这个进程是在正常运行还是出现了异常。程序通常都会消耗比正常情况更多的内存和CPU。虽然程序员都在尽力确保代码正确地使用资源，但是有时候还是要由管理员来决定终止还是重启进程。

用户可能会注意到在ps aux命令的输出结果里，大部分TTY域有个"？"。这是因为这些程序或者在系统启动的时候就开始运行了，或者是由初始化脚本（init script）启动的。这些进程没有控制终端，所以作了标记。另外，linux-sanity-check命令有一个TTY的值为pts/14。这个命令是远程连接运行的，有与其关联的一个终端。当你的机器开放了多条连接，而你又想确定某个命令运行在哪个窗口的时候，这个信息是很有用的。

STAT 显示了进程当前的状态。在我们的例子里，很多进程处在睡眠状态，STAT域里的"S"指明了这一状态。这仅仅表明这些进程在等待某些事件发生--可能是用户输入或者系统资源的可用性。linux-sanity-check命令则有一个R状态，这个状态表明进程当前正在运行。有时候你可以浏览一下这个列表然后找那些R状态的进程。如果大部分进程处在睡眠状态而又有问题发生，那么只关注那些正在运行的进程是最好的方法。那种状态不一定能说明发生了问题，但是有时候如果进程运行的时间过长可能意味着发生了某些深层次的问题。

应用 Valgrind 发现 Linux 程序的内存问题

2008 年 11 月 27 日

如何定位应用程序开发中的内存问题，一直是 inux 应用程序开发中的瓶颈所在。有一款非常优秀的 linux 下开源的内存问题检测工具：valgrind，能够极大的帮助你解决上述问题。掌握 valgrind 的使用以及工作原理，能够有效地定位进而避免应用开发中的内存问题。

应用 Valgrind 发现 Linux 程序的内存问题

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

Valgrind 概述

体系结构

Valgrind是一套Linux下，开放源代码（GPL V2）的仿真调试工具的集合。Valgrind由内核（core）以及基于内核的其他调试工具组成。内核类似于一个框架（framework），它模拟了一个CPU环境，并提供服务给其他工具；而其他工具则类似于插件 (plug-in)，利用内核提供的服务完成各种特定的内存调试任务。Valgrind的体系结构如下图所示：

图 1 Valgrind 体系结构

Valgrind包括如下一些工具：

Memcheck。这是valgrind应用最广泛的工具，一个重量级的内存检查器，能够发现开发中绝大多数内存错误使用情况，比如：使用未初始化的内存，使用已经释放了的内存，内存访问越界等。这也是本文将重点介绍的部分。
Callgrind。它主要用来检查程序中函数调用过程中出现的问题。
Cachegrind。它主要用来检查程序中缓存使用出现的问题。
Helgrind。它主要用来检查多线程程序中出现的竞争问题。
Massif。它主要用来检查程序中堆栈使用中出现的问题。
Extension。可以利用core提供的功能，自己编写特定的内存调试工具。

Linux 程序内存空间布局

要发现Linux下的内存问题，首先一定要知道在Linux下，内存是如何被分配的？下图展示了一个典型的Linux C程序内存空间布局：

图 2：典型内存空间布局

一个典型的Linux C程序内存空间由如下几部分组成：

代码段（.text）。这里存放的是CPU要执行的指令。代码段是可共享的，相同的代码在内存中只会有一个拷贝，同时这个段是只读的，防止程序由于错误而修改自身的指令。
初始化数据段（.data）。这里存放的是程序中需要明确赋初始值的变量，例如位于所有函数之外的全局变量：int val=100。需要强调的是，以上两段都是位于程序的可执行文件中，内核在调用exec函数启动该程序时从源程序文件中读入。
未初始化数据段（.bss）。位于这一段中的数据，内核在执行该程序前，将其初始化为0或者null。例如出现在任何函数之外的全局变量：int sum;
堆（Heap）。这个段用于在程序中进行动态内存申请，例如经常用到的malloc，new系列函数就是从这个段中申请内存。
栈（Stack）。函数中的局部变量以及在函数调用过程中产生的临时变量都保存在此段中。

内存检查原理

Memcheck检测内存问题的原理如下图所示：

Memcheck 能够检测出内存问题，关键在于其建立了两个全局表。

Valid-Value 表：

对于进程的整个地址空间中的每一个字节(byte)，都有与之对应的 8 个 bits；对于 CPU 的每个寄存器，也有一个与之对应的 bit 向量。这些 bits 负责记录该字节或者寄存器值是否具有有效的、已初始化的值。

Valid-Address 表

对于进程整个地址空间中的每一个字节(byte)，还有与之对应的 1 个 bit，负责记录该地址是否能够被读写。

检测原理：

当要读写内存中某个字节时，首先检查这个字节对应的 A bit。如果该A bit显示该位置是无效位置，memcheck 则报告读写错误。
内核（core）类似于一个虚拟的 CPU 环境，这样当内存中的某个字节被加载到真实的 CPU 中时，该字节对应的 V bit 也被加载到虚拟的 CPU 环境中。一旦寄存器中的值，被用来产生内存地址，或者该值能够影响程序输出，则 memcheck 会检查对应的V bits，如果该值尚未初始化，则会报告使用未初始化内存错误。

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

Valgrind 使用

第一步：准备好程序

为了使valgrind发现的错误更精确，如能够定位到源代码行，建议在编译时加上-g参数，编译优化选项请选择O0，虽然这会降低程序的执行效率。

这里用到的示例程序文件名为：sample.c（如下所示）,选用的编译器为gcc。

生成可执行程序 gcc –g –O0 sample.c –o sample

第二步：在valgrind下，运行可执行程序。

利用valgrind调试内存问题，不需要重新编译源程序，它的输入就是二进制的可执行程序。调用Valgrind的通用格式是：valgrind [valgrind-options] your-prog [your-prog-options]

Valgrind 的参数分为两类，一类是 core 的参数，它对所有的工具都适用；另外一类就是具体某个工具如 memcheck 的参数。Valgrind 默认的工具就是 memcheck，也可以通过“--tool=tool name”指定其他的工具。Valgrind 提供了大量的参数满足你特定的调试需求，具体可参考其用户手册。

这个例子将使用 memcheck，于是可以输入命令入下：valgrind /sample.

第三步：分析 valgrind 的输出信息。

以下是运行上述命令后的输出。

清单 2

左边显示类似行号的数字（32372）表示的是 Process ID。
最上面的红色方框表示的是 valgrind 的版本信息。
中间的红色方框表示 valgrind 通过运行被测试程序，发现的内存问题。通过阅读这些信息，可以发现：
1. 这是一个对内存的非法写操作，非法写操作的内存是4 bytes。
2. 发生错误时的函数堆栈，以及具体的源代码行号。
3. 非法写操作的具体地址空间。
最下面的红色方框是对发现的内存问题和内存泄露问题的总结。内存泄露的大小（40 bytes）也能够被检测出来。

示例程序显然有两个问题，一是fun函数中动态申请的堆内存没有释放；二是对堆内存的访问越界。这两个问题均被valgrind发现。

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

利用Memcheck发现常见的内存问题

在Linux平台开发应用程序时，最常遇见的问题就是错误的使用内存，我们总结了常见了内存错误使用情况，并说明了如何用valgrind将其检测出来。

使用未初始化的内存

问题分析：

对于位于程序中不同段的变量，其初始值是不同的，全局变量和静态变量初始值为0，而局部变量和动态申请的变量，其初始值为随机值。如果程序使用了为随机值的变量，那么程序的行为就变得不可预期。

下面的程序就是一种常见的，使用了未初始化的变量的情况。数组a是局部变量，其初始值为随机值，而在初始化时并没有给其所有数组成员初始化，如此在接下来使用这个数组时就潜在有内存问题。

清单 3

结果分析：

假设这个文件名为：badloop.c，生成的可执行程序为badloop。用memcheck对其进行测试，输出如下。

清单 4

输出结果显示，在该程序第11行中，程序的跳转依赖于一个未初始化的变量。准确的发现了上述程序中存在的问题。

内存读写越界

问题分析：

这种情况是指：访问了你不应该/没有权限访问的内存地址空间，比如访问数组时越界；对动态内存访问时超出了申请的内存大小范围。下面的程序就是一个典型的数组越界问题。pt是一个局部数组变量，其大小为4，p初始指向pt数组的起始地址，但在对p循环叠加后，p超出了pt数组的范围，如果此时再对p 进行写操作，那么后果将不可预期。

结果分析：

假设这个文件名为badacc.cpp，生成的可执行程序为badacc，用memcheck对其进行测试，输出如下。

输出结果显示，在该程序的第15行，进行了非法的写操作；在第16行，进行了非法读操作。准确地发现了上述问题。

内存覆盖

问题分析：

C 语言的强大和可怕之处在于其可以直接操作内存，C 标准库中提供了大量这样的函数，比如 strcpy, strncpy, memcpy, strcat 等，这些函数有一个共同的特点就是需要设置源地址 (src)，和目标地址(dst)，src 和 dst 指向的地址不能发生重叠，否则结果将不可预期。

下面就是一个 src 和 dst 发生重叠的例子。在 15 与 17 行中，src 和 dst 所指向的地址相差 20，但指定的拷贝长度却是 21，这样就会把之前的拷贝值覆盖。第 24 行程序类似，src(x+20) 与 dst(x) 所指向的地址相差 20，但 dst 的长度却为 21，这样也会发生内存覆盖。

清单 7

结果分析：

假设这个文件名为 badlap.cpp，生成的可执行程序为 badlap，用 memcheck 对其进行测试，输出如下。

输出结果显示上述程序中第15，17，24行，源地址和目标地址设置出现重叠。准确的发现了上述问题。

动态内存管理错误

问题分析：

常见的内存分配方式分三种：静态存储，栈上分配，堆上分配。全局变量属于静态存储，它们是在编译时就被分配了存储空间，函数内的局部变量属于栈上分配，而最灵活的内存使用方式当属堆上分配，也叫做内存动态分配了。常用的内存动态分配函数包括：malloc, alloc, realloc, new等，动态释放函数包括free, delete。

一旦成功申请了动态内存，我们就需要自己对其进行内存管理，而这又是最容易犯错误的。下面的一段程序，就包括了内存动态管理中常见的错误。

常见的内存动态管理错误包括：

申请和释放不一致

由于 C++ 兼容 C，而 C 与 C++ 的内存申请和释放函数是不同的，因此在 C++ 程序中，就有两套动态内存管理函数。一条不变的规则就是采用 C 方式申请的内存就用 C 方式释放；用 C++ 方式申请的内存，用 C++ 方式释放。也就是用 malloc/alloc/realloc 方式申请的内存，用 free 释放；用 new 方式申请的内存用 delete 释放。在上述程序中，用 malloc 方式申请了内存却用 delete 来释放，虽然这在很多情况下不会有问题，但这绝对是潜在的问题。

申请和释放不匹配

申请了多少内存，在使用完成后就要释放多少。如果没有释放，或者少释放了就是内存泄露；多释放了也会产生问题。上述程序中，指针p和pt指向的是同一块内存，却被先后释放两次。

释放后仍然读写

本质上说，系统会在堆上维护一个动态内存链表，如果被释放，就意味着该块内存可以继续被分配给其他部分，如果内存被释放后再访问，就可能覆盖其他部分的信息，这是一种严重的错误，上述程序第16行中就在释放后仍然写这块内存。

结果分析：

假设这个文件名为badmac.cpp，生成的可执行程序为badmac，用memcheck对其进行测试，输出如下。

输出结果显示，第14行分配和释放函数不一致；第16行发生非法写操作，也就是往释放后的内存地址写值；第17行释放内存函数无效。准确地发现了上述三个问题。

内存泄露

问题描述：

内存泄露（Memory leak）指的是，在程序中动态申请的内存，在使用完后既没有释放，又无法被程序的其他部分访问。内存泄露是在开发大型程序中最令人头疼的问题，以至于有人说，内存泄露是无法避免的。其实不然，防止内存泄露要从良好的编程习惯做起，另外重要的一点就是要加强单元测试（Unit Test），而memcheck就是这样一款优秀的工具。

下面是一个比较典型的内存泄露案例。main函数调用了mk函数生成树结点，可是在调用完成之后，却没有相应的函数：nodefr释放内存，这样内存中的这个树结构就无法被其他部分访问，造成了内存泄露。

在一个单独的函数中，每个人的内存泄露意识都是比较强的。但很多情况下，我们都会对malloc/free 或new/delete做一些包装，以符合我们特定的需要，无法做到在一个函数中既使用又释放。这个例子也说明了内存泄露最容易发生的地方：即两个部分的接口部分，一个函数申请内存，一个函数释放内存。并且这些函数由不同的人开发、使用，这样造成内存泄露的可能性就比较大了。这需要养成良好的单元测试习惯，将内存泄露消灭在初始阶段。

结果分析：

假设上述文件名位tree.h, tree.cpp, badleak.cpp，生成的可执行程序为badleak，用memcheck对其进行测试，输出如下。

该示例程序是生成一棵树的过程，每个树节点的大小为12（考虑内存对齐），共8个节点。从上述输出可以看出，所有的内存泄露都被发现。Memcheck将内存泄露分为两种，一种是可能的内存泄露（Possibly lost），另外一种是确定的内存泄露（Definitely lost）。Possibly lost 是指仍然存在某个指针能够访问某块内存，但该指针指向的已经不是该内存首地址。Definitely lost 是指已经不能够访问这块内存。而Definitely lost又分为两种：直接的（direct）和间接的（indirect）。直接和间接的区别就是，直接是没有任何指针指向该内存，间接是指指向该内存的指针都位于内存泄露处。在上述的例子中，根节点是directly lost，而其他节点是indirectly lost。

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

总结

本文介绍了valgrind的体系结构，并重点介绍了其应用最广泛的工具：memcheck。阐述了memcheck发现内存问题的基本原理，基本使用方法，以及利用memcheck如何发现目前开发中最广泛的五大类内存问题。在项目中尽早的发现内存问题，能够极大地提高开发效率，valgrind 就是能够帮助你实现这一目标的出色工具。

Monday, January 19, 2009

Android Cupcake源码编译笔记

更多精彩请到 http://www.139ya.com

转自: Android Cupcake源码编译笔记

一直在想下份Android 的源代码来编译，学习。在http://android.git.kerner.org/下了好多天都没下完，repo sync老出错，而且出错就退出，不会自动重试，
正郁闷中，发现www.androidin.com的下载恢复了，赶整下了个，还有点小大，压缩包1G，解压后将近2G，编译了一天，终于得到了3个文件：ramdisk.img,system.img
,userdata.img,现在将编译的过程记下来做个参考。
编译环境：VMware Workstation5中装ubuntu 8.10
1. 首先，要安装JDK 5或6，下载地址http://java.sun.com/javase/downloads/index.jsp,安装完后设置好JAVA环境变量。
2. 去www.androidin.com下载Android Cupcake源码
3. 解压下载的cupcake.tar.gz
4. 我的ubuntu没有安装g++，安装g++: apt-get install g++
5. 安装库文件
apt-get install flex bison gperf libsdl1.2-dev libesd0-dev libwxgtk2.6-dev zlib1g-dev curl libncurses5-dev zlib1g-dev libx11-dev build-essential
python libdevice-serialport-perl imagemagick

6. 进入cupcake文件夹，make

7. 过一会，编译出错，都是却少了头文件引用，vim打开出错的文件，手动添加头文件，继续make，出错，加头文件，多次重复，大概有20次，具体数没数，不确定有多少次
报错。添加头文件要点：
提示缺strcpm,strdup等声明的，添加 #include
提示缺exit,malloc等声明的，添加 #include
提示缺sort声明的，添加 #include
提示缺unlink声明的，添加 #include
8. 我编译时，unlink是最后一处错误，改了这个后又编译了2个小时，终于结束。
编译完会产生OUT目录，要运行，好象还要make sdk,我在这一步，java库报错了，没有完成，将“ramdisk.img,system.img,userdata.img”在下载的android SDK开发包的模拟
器中可以正常运行。

Shrek Cat

更多精彩请到 http://www.139ya.com

Saturday, January 17, 2009

微软的面试题答案

更多精彩请到 http://www.139ya.com

第一组题答案：

　　1）三根绳，第一根点燃两端，第二根点燃一端，第三根不点，第一根绳烧完（30分钟）后，点燃第二根绳的另一端，第二根绳烧完（45分钟）后，点燃第三根绳子两端，第三根绳烧完（1小时15分）后，计时完成

　　2）根据抽屉原理，4个

　　3）3升装满；3升-〉5升（全注入）；3升装满；3升-〉5升（剩1升）；5升倒掉；3升-〉5升（注入1升）；3升装满；3升-〉5升；完成（另：可用回溯法编程求解）

　　4）问其中一人：另外一个人会说哪一条路是通往诚实国的？回答者所指的那条路必然是通往说谎国的。

　　5）12个球：
第一次：4，4 如果平了：那么剩下的球中取3放左边,取3个好球放右边，称：如果左边重，那么取两个球称一下，哪个重哪个是次品，平的话第三个重，是次品，轻的话同理，如果平了，那么剩下一个次品，还可根据需要称出次品比正品轻或者重，如果不平：那么不妨设左边重右边轻，为了便于说明，将左边4颗称为重球，右边4颗称为轻球，剩下4颗称为好球，取重球2颗，轻球2颗放在左侧，右侧放3颗好球和一颗轻球，如果左边重，称那两颗重球，重的一个次品，平的话右边轻球次品。如果右边重，称左边两颗轻球，轻的一个次品。如果平，称剩下两颗重球，重的一个次品，平的话剩下那颗轻球次品

　　13个球：
　　第一次：4，4，如果平了。剩5颗球用上面的方法仍旧能找出次品，只是不能知道次品是重是轻。如果不平，同上

　　6）
　　o o o
　　 o o o
　　o o o

　　7）
　　23次，因为分针要转24圈，时针才能转1圈，而分针和时针重合两次之间的间隔显然>1小时，它们有23次重合机会，每次重合中秒针有一次重合机会，所以是23次
　　重合时间可以对照手表求出，也可列方程求出

　　8）
　　在地球表面种树，做一个地球内接的正四面体，内接点即为所求　　

　　第二组无标准答案

　　第三组

　　1. 分成1,2,4三段，第一天给1，第二天给2取回1，第3天给1，第4天给4取回1、2，第5天给1，第6天给2取回1，第七天给1

　　2. 求出火车相遇时间，鸟速乘以时间就是鸟飞行的距离

　　3. 四个罐子中分别取1,2,3,4颗药丸，称出比正常重多少，即可判断出那个罐子的药被污染

　　4. 三个开关分别：关，开，开10分钟，然后进屋，暗且凉的为开关1控制的灯，亮的为开关2控制的灯，暗且热的为开关3控制的灯

　　5. 因为可以用1，2，5，10组合成任何需要的货币值，日常习惯为10进制

　　6. 题意不理解...*_*

　　7. 012345 0126(9)78

　　第四组都是很难的题目

　　第一题：97 0 1 2 0 或者 97 0 1 0 2 （提示：可用逆推法求出）

　　第二题：3架飞机5架次，飞法：
　　ABC 3架同时起飞，1/8处，C给AB加满油，C返航，1/4处，B给A加满油，B返航，A到达1/2处，C从机场往另一方向起飞，3/4处，C同已经空油箱的A平分剩余油量，同时B从机场起飞，AC到7/8处同B平分剩余油量，刚好3架飞机同时返航。所以是3架飞机5架次。

　　第三题：需要建立数学模型
　　（提示，严格证明该模型最优比较麻烦，但确实可证，大胆猜想是解题关键）
　　题目可归结为求数列 an=500/(2n+1) n=0,1,2,3......的和Sn什么时候大于等于1000,解得n>6
　　当n=6时，S6=977.57
　　所以第一个中转点离起始位置距离为1000-977.57=22.43公里
　　所以第一次中转之前共耗油 22.43*(2*7+1)=336.50升
　　此后每次中转耗油500升
　　所以总耗油量为7*500+336.50=3836.50升

　　第四题：需要建立数学模型
　　题目可归结为求自然数列的和S什么时候大于等于100，解得n>13
　　第一个杯子可能的投掷楼层分别为：14，27，39，50，60，69，77，84，90，95，99，100

　　第五题：3和4（可严格证明）
　　设两个数为n1，n2，n1>=n2，甲听到的数为n=n1+n2，乙听到的数为m=n1*n2
　　证明n1=3，n2=4是唯一解
　　证明：要证以上命题为真，不妨先证n=7
　1)必要性：
　　 i) n>5 是显然的，因为n<4不可能，n=4或者n=5甲都不可能回答不知道
　　 ii) n>6 因为如果n=6的话，那么甲虽然不知道（不确定2+4还是3+3）但是无论是2，4还是3，3乙都不可能说不知道（m=8或者m=9的话乙说不知道是没有道理的）
　　 iii) n<8>=8的话，就可以将n分解成 n=4+x 和 n=6+(x-2)，那么m可以是4x也可以是6(x-2)而4x=6(x-2)的必要条件是x=6即n=10，那样n又可以分解成8+2，所以总之当 n>=8时，n至少可以分解成两种不同的合数之和，这样乙说不知道的时候，甲就没有理由马上说知道。
　　以上证明了必要性

　2)充分性
　　当n=7时，n可以分解成2+5或3+4
　　显然2+5不符合题意，舍去，容易判断出3+4符合题意，m=12，证毕
　　于是得到n=7 m=12 n1=3 n2=4是唯一解。

　　第六题：7只（数学归纳法证明）
　　1）若只有1只病狗，因为病狗主人看不到有其他病狗，必然会知道自己的狗是病狗（前提是一定存在病狗），所以他会在第一天把病狗处决。
　　2）设有k只病狗的话，会在第k天被处决，那么，如果有k+1只，病狗的主人只会看到k只病狗，而第k天没有人处决病狗，病狗主人就会在第k+1天知道自己的狗是病狗，于是病狗在第k+1天被处决
　　3）由1）2）得，若有n只病狗，必然在第n天被处决

　　第七题：（提示：可用图论方法解决）
　　BONO&EDGE过（2分），BONO将手电带回（1分），ADAM&LARRY过（10分），EDGE将手电带回（2分），BONO&EDGE过（2分） 2+1+10+2+2=17分钟

　　第八题：
　　约定好一个人作为报告人（可以是第一个放风的人）
　　规则如下：
　　1、报告人放风的时候开灯并数开灯次数
　　2、其他人第一次遇到开着灯放风时，将灯关闭
　　3、当报告人第100次开灯的时候，去向监狱长报告，要求监狱长放人......
　　按照概率大约30年后（10000天）他们可以被释放
　　第五组无标准答案
　　第六组部分题参考答案：
　　4.
　　char * strcpy(char * pstrDest,const char * pstrSource)
　　{
　　assert((pstrDest!=NULL)&&(pstrSource!=NULL));
　　char * pstr=pstrDest;
　　while((*(pstrDest++)=*(pstrSource++))!='\0');
　　 return pstr;
　　}

　　5.
　　char * strrev(char * pstr)
　　{
　　assert(pstr!=NULL);
　　char * p=pstr;
　　char * pret=pstr;
　　while(*(p++)!='\0');
　　p--;
　　char tmp;
　　while(p>pstr)
　　{
　　 tmp=*p;
　　 *(p--)=*(pstr);
　　 *(pstr++)=tmp;
　　}
　　return pret;

微软的面试题

更多精彩请到 http://www.139ya.com

第一组

　　1.烧一根不均匀的绳，从头烧到尾总共需要1个小时。现在有若干条材质相同的绳子，问如何用烧绳的方法来计时一个小时十五分钟呢？

　　2.你有一桶果冻，其中有黄色、绿色、红色三种，闭上眼睛抓取同种颜色的两个。抓取多少个就可以确定你肯定有两个同一颜色的果冻？

　　3.如果你有无穷多的水，一个3公升的提捅，一个5公升的提捅，两只提捅形状上下都不均匀，问你如何才能准确称出4公升的水？

　　4.一个岔路口分别通向诚实国和说谎国。来了两个人，已知一个是诚实国的，另一个是说谎国的。诚实国永远说实话，说谎国永远说谎话。现在你要去说谎国，但不知道应该走哪条路，需要问这两个人。请问应该怎么问？

5.12个球一个天平，现知道只有一个和其它的重量不同，问怎样称才能用三次就找到那个球。13个呢？（注意此题并未说明那个球的重量是轻是重，所以需要仔细考虑）

　　6.在9个点上画10条直线，要求每条直线上至少有三个点？

　　7.在一天的24小时之中，时钟的时针、分针和秒针完全重合在一起的时候有几次？都分别是什么时间？你怎样算出来的？

　　8.怎么样种植4棵树木，使其中任意两棵树的距离相等？

　　第二组

　　1.为什么下水道的盖子是圆的？

　　2.中国有多少辆汽车？

　　3.将汽车钥匙插入车门，向哪个方向旋转就可以打开车锁？

　　4.如果你要去掉中国的34个省（含自治区、直辖市和港澳特区及台湾省）中的任何一个，你会去掉哪一个，为什么？

　　5.多少个加油站才能满足中国的所有汽车？

　　6.想象你站在镜子前，请问，为什么镜子中的影象可以颠倒左右，却不能颠倒上下？

　　7.为什么在任何旅馆里，你打开热水，热水都会瞬间倾泻而出？

　　8.你怎样将Excel的用法解释给你的奶奶听？

9.你怎样重新改进和设计一个ATM银行自动取款机？

　　10.如果你不得不重新学习一种新的计算机语言，你打算怎样着手来开始？

　　11.如果你的生涯规划中打算在5年内受到奖励，那获取该项奖励的动机是什么？观众是谁？

　　12.如果微软告诉你，我们打算投资五百万美元来启动你的投资计划，你将开始什么样商业计划？为什么？

　　13.如果你能够将全世界的电脑厂商集合在一个办公室里，然后告诉他们将被强迫做一件事，那件事将是什么？

　　第三组

　　1.你让工人为你工作7天，回报是一根金条，这个金条平分成相连的7段，你必须在每天结束的时候给他们一段金条。如果只允许你两次把金条弄断，你如何给你的工人付费？

　　2.有一辆火车以每小时15公里的速度离开北京直奔广州，同时另一辆火车每小时20公里的速度从广州开往北京。如果有一只鸟，以30公里每小时的速度和两辆火车同时启动，从北京出发，碰到另一辆车后就向相反的方向返回去飞，就这样依次在两辆火车之间来回地飞，直到两辆火车相遇。请问，这只鸟共飞行了多长的距离？

　　3.你有四个装药丸的罐子，每个药丸都有一定的重量，被污染的药丸是没被污染的药丸的重量+1。只称量一次，如何判断哪个罐子的药被污染了？

　　4.门外三个开关分别对应室内三盏灯，线路良好，在门外控制开关时候不能看到室内灯的情况，现在只允许进门一次，确定开关和灯的对应关系？

　　5.人民币为什么只有1、2、5、10的面值？

　　6.你有两个罐子以及50个红色弹球和50个蓝色弹球，随机选出一个罐子，随机选出一个弹球放入罐子，怎么给出红色弹球最大的选中机会？在你的计划里，得到红球的几率是多少？

　　7.给你两颗6面色子，可以在它们各个面上刻上0-9任意一个数字，要求能够用它们拼出任意一年中的日期数值

第四组

　　第一题 . 五个海盗抢到了100颗宝石，每一颗都一样大小和价值连城。他们决定这么分：
　　抽签决定自己的号码（1、2、3、4、5）
　　首先，由1号提出分配方案，然后大家表决，当且仅当超过半数的人同意时，按照他的方案进行分配，否则将被扔进大海喂鲨鱼，如果1号死后，再由2号提出分配方案，然后剩下的4人进行表决，当且仅当超过半数的人同意时，按照他的方案进行分配，否则将被扔入大海喂鲨鱼，依此类推
　　条件：每个海盗都是很聪明的人，都能很理智地做出判断，从而做出选择。
　　问题：第一个海盗提出怎样的分配方案才能使自己的收益最大化？

　　第二题 . 一道关于飞机加油的问题，已知：
　　每个飞机只有一个油箱，飞机之间可以相互加油（注意是相互，没有加油机），一箱油可供一架飞机绕地球飞半圈，
　　问题：为使至少一架飞机绕地球一圈回到起飞时的飞机场，至少需要出动几架飞机？（所有飞机从同一机场起飞，而且必须安全返回机场，不允许中途降落，中间没有飞机场）

　　第三题. 汽车加油问题
　　一辆载油500升的汽车从A开往1000公里外的B，已知汽车每公里耗油量为1升，A处有无穷多的油，其他任何地点都没有油，但该车可以在任何地点存放油以备中转，问从A到B最少需要多少油

　　第四题. 掷杯问题
　　一种杯子，若在第N层被摔破，则在任何比N高的楼层均会破，若在第M层不破，则在任何比M低的楼层均会破，给你两个这样的杯子，让你在100层高的楼层中测试，要求用最少的测试次数找出恰巧会使杯子破碎的楼层。

　　第五题. 推理游戏
　　教授选出两个从2到9的数，把它们的和告诉学生甲，把它们的积告诉学生乙，让他们轮流猜这两个数
　　甲说：“我猜不出”
　　乙说：“我猜不出”
　　甲说：“我猜到了”
　　乙说：“我也猜到了”
　　问这两个数是多少

　　第六题. 病狗问题
　　一个住宅区内有100户人家，每户人家养一条狗，每天傍晚大家都在同一个地方遛狗。已知这些狗中有一部分病狗，由于某种原因，狗的主人无法判断自己的狗是否是病狗，却能够分辨其他的狗是否有病，现在，上级传来通知，要求住户处决这些病狗，并且不允许指认他人的狗是病狗（就是只能判断自己的），过了7天之后，所有的病狗都被处决了，问，一共有几只病狗？为什么？

　　第七题. U2合唱团在17分钟内得赶到演唱会场，途中必需跨过一座桥，四个人从桥的同一端出发，你得帮助他们到达另一端，天色很暗，而他们只有一只手电筒。一次同时最多可以有两人一起过桥，而过桥的时候必须持有手电筒，所以就得有人把手电筒带来带去，来回桥两端。手电筒是不能用丢的方式来传递的。四个人的步行速度各不同，若两人同行则以较慢者的速度为准。BONO需花1分钟过桥,EDGE需花2分钟过桥,ADAM需花5分钟过桥,LARRY需花10分钟过桥,他们要如何在17分钟内过桥呢？

　　第八题. 监狱里有100个房间，每个房间内有一囚犯。一天，监狱长说，你们狱房外有一电灯，你们在放风时可以控制这个电灯（熄或亮）。每天只能有一个人出来放风，并且防风是随机的。如果在有限时间内，你们中的某人能对我说：“我敢保证，现在每个人都已经至少放过一次风了。”我就放了你们！问囚犯们要采取什么策略才能被监狱长放掉？如果采用了这种策略，大致多久他们可以被释放？

　　第五组

　　1.某手机厂家由于设计失误，有可能造成电池寿命比原来设计的寿命短一半（不是冲放电时间），解决方案就是免费更换电池或给50元购买该厂家新手机的折换券。请给所有已购买的用户写信告诉解决方案。

　　2.一高层领导在参观某博物馆时，向博物馆馆员小王要了一块明代的城砖作为纪念，按国家规定，任何人不得将博物馆收藏品变为私有。博物馆馆长需要如何写信给这位领导，将城砖取回。

　　3.营业员小姐由于工作失误，将2万元的笔记本电脑以1.2万元错卖给李先生，王小姐的经理怎么写信给李先生试图将钱要回来？

　　4.给你一款新研制的手机，如果你是测试组的组长，你会如何测试？

　　5.如何为函数int atoi(const char * pstr)编写测试向量？

　　第六组

　　1.链表和数组的区别在哪里？

2.编写实现链表排序的一种算法。说明为什么你会选择用这样的方法？

　　3.编写实现数组排序的一种算法。说明为什么你会选择用这样的方法？

　　4.请编写能直接实现char * strcpy(char * pstrDest,const char * pstrSource)函数功能的代码。

　　5.编写反转字符串的程序，要求优化速度、优化空间。

　　6.在链表里如何发现循环链接？

　　7.给出洗牌的一个算法，并将洗好的牌存储在一个整形数组里。

　　8.写一个函数，检查字符是否是整数，如果是，返回其整数值。（或者：怎样只用4行代码

　　9.给出一个函数来输出一个字符串的所有排列。

　　10.请编写实现void * malloc(int)内存分配函数功能一样的代码。

　　11.给出一个函数来复制两个字符串A和B。字符串A的后几个字节和字符串B的前几个字节重叠。

　　12.怎样编写一个程序，把一个有序整数数组放到二叉树中？

　　13.怎样从顶部开始逐层打印二叉树结点数据？请编程。

　　14.怎样把一个链表掉个顺序（也就是反序，注意链表的边界条件并考虑空链表）？ --

　　15.请编写能直接实现int atoi(const char * pstr)函数功能的代码。

24点数字游戏题解

更多精彩请到 http://www.139ya.com

转自: http://blogger.org.cn/blog/more.asp?name=njucs&id=3772

24点游戏

数字游戏题解
by starfish

[说明：此文改编自我写的一篇解题报告，原题是某年国家集训队组队赛题目]

问题描述

80年代全世界流行一种数字游戏，在中国我们把这种游戏称为“24点”。现在我们
把这个有趣的游戏推广一下：您作为游戏者将得到6个不同的自然数作为操作数，
以及另外一个自然数作为理想目标数，而您的任务是对这6个操作数进行适当的算
术运算，要求运算结果小于或等于理想目标数，并且我们希望所得结果是最优的，
即结果要最接近理想目标数。
您可以使用的运算只有：+，-，*，/，您还可以使用（）来改变运算顺序。注意：
所有的中间结果必须是整数，所以一些除法运算是不允许的（例如，（2*2）/4是
合法的，2*（2/4）是不合法的）
下面我们给出一个游戏的具体例子：
若给出的6个操作数是：1，2，3，4，7和25，理想目标数是573；
则最优结果是573：（（（4*25-1）*2）-7）*3。

输入：

输入文件名为game.in。输入文件仅一行，包含7个整数，前6个整数Mi,
1<=Mi<=100，表示操作数，最后一个整数T, 1<=T<=1000,表示理想目标数。输出：输出文件名为game.out。输出文件有两行，第一行仅一个整数，表示您的程序计算得到的最优结果；第二行是一个表达式，即您得到的最优结果的运算方案。输入输出示例：输入文件 1 2 3 4 7 25 573 输出文件 573 ((4*25-1)*2)-7)*3 算法分析首先我们要对这个问题进行数学抽象。定义1：对于有理数组成的多重集合S ， f(S) 定义如下：如果 S 是空集或只包含一个元素，则 f(S)=S ；否则 f(S)=∪ f( ( S-{r1, r2}) ∪ {r} ) ，对于每一个 r=r1+r2 , r1-r2 , r1×r2 ，r1÷r2(r2≠0)，且r1, r2取遍 S 中所有元素的组成的二元组。定义1说明：要计算集合S中的元素通过四则混合运算所能得到的所有值，我们只需要任取 S 中的两个元素 r1 , r2 ，分别计算 r1 , r2 的加减乘除运算，然后用所得的结果与 S 中剩下的其他数字进行四则混合运算。只要取遍所有的 r1 , r2 ，最后得到的所有结果的并集就是 S 中的元素通过四则混合运算所能得到的所有值的集合。根据上述定义，在本问题中，集合 S 就是由输入中给定的6个正整数组成的集合，题目所求就是找出 f(S) 中小于或等于目标数的最大数。定义2：给定两个多重集合 S1 , S2，定义 comb( S1, S2 ) = ∪ { r1+r2 , r1-r2, r1×r2, r1÷r2(r2≠0) } (1.1) 其中 ( r1 , r2 ) ∈ S1 × S2。定义2实际上定义了两个集合中的元素两两进行加减乘除运算所能得到的结果集合。定理1：对于有理数组成的多重集合 S ，如果 S 至少有两个元素，则 f(S)=∪ comb( f(S1), f(S - S1) ) (1.2) 其中 S1 取遍 S 的所有非空真子集。定理1的含义是：要计算 S 中的元素通过四则混合运算所能得到的所有值，可以先将 S 分解为两个子集 S1 和 S- S1 ，分别计算 S1 和 S-S1 中的元素进行四则混合运算所能得到的结果集合，即 f(S1) 和 f(S-S1) ，然后对这两个集合中的元素进行加减乘除运算，即 comb( f(S1), f(S-S1) ) ，最后得到的所有集合的并集就是 f(S) 。限于篇幅，定理1的正确性易用数学归纳法证明。定义1和定理1实际上分别给出了计算f(S)的两种不同的方法。根据定义1，可以递归地计算f(S) ，其算法伪代码如下：算法1 function f(S) begin 1. if |S| <> 0) and (r1 mod r2 = 0) then
14. begin
15. r ← r1 / r2;
16. T ← T + f(S – {r1, r2} + {r});
17. end
18. end
19. return T;
20. end
end

上述伪代码中使用了+, - 来分别表示集合的并和差运算。算法1每次选择两个数字
进行某种运算，然后将结果与剩下的数字递归地进行运算，最后求得所有数字进行
四则混合运算的结果。当然，在具体实现该算法的过程中有很多可以优化的地方，
比如根据加法交换律， a+b+c=a+c+b ，因此我们可以规定：如果上一层递归作了
加法运算，这一层仅当满足当前的操作数大于上一层的两个操作数的时候才进行加
法运算，以确保 a+b+c 这样的式子中的操作数总是从小到大排列，这样就可以避
免重复进行等价的加法计算。类似地我们可以对乘法也作此规定。在进行减法的时
候，我们可以规定只能计算大数减小数，因为最后所需计算得到的目标数是一个正
数，如果计算过程中出现负数，肯定有另外一个较大的正数与其作加法或者有另外
一个负数与其做乘除法以消除负号。因此我们总可以调整运算次序使得四则混合运
算的每一步的中间结果都是正数。在作除法的时候，因为题目规定中间结果只能是
整数，所以也只需要用大数除小数，且仅当能除尽的时候才进行除法。对于本题而
言，初始的集合 S 中一共有6个操作数，每次递归都可以合并两个操作数，所以递
归到第5层的时候集合 S 中只剩下一个数，这个数就是原先的6个操作数进行四则
混合运算所能得到的结果。本题只要求最接近目标值的结果，所以实现上述算法的
时候可以只记录当前最优的结果。对于本题也可以利用递归回溯构造出所有的四则
混合运算的语法树，但本质上与算法1是没有区别的。

定理1则给出了另一种计算f(S)的方法。我们当然也可以根据(1.2)式直接地递归计
算f(S)，但那样的话会有很多冗余计算。例如对于S={1,2,3,4}，
f(S) = comb( f({ 1 }), f({ 2,3,4}) )∪ ... ∪ comb( f({ 1,2 }), f({
3,4 }) ) ∪ ...;
计算f(S)的时候需要计算 f({ 2,3,4 })和f({ 3,4 }) ，又因为
f({2,3,4}) = comb(f({ 2 }), f({3,4})) ∪ ...;
在计算 f({ 2,3,4}) 的时候又要重复地计算 f({ 3,4 }) ，这就产生了冗余的计
算。这种情况下直接地递归就不适用。必须按照一定的顺序，递推地进行计算。这
种将递归改为递推，以解决冗余的算法设计策略，就叫做动态规划。

下面我们具体阐述一下该算法的步骤。设初始时集合 S 中的 n 个数字分别为
x[0], x[1],...,x[n-1] ，我们可以用一个二进制数k来表示S 的子集 S[k] ，
x[i] ∈ S[k] 当且仅当二进制数k的第i位为1。于是我们用一个数组 F[0..2^n-1]
就可以保存函数f对于S的所有子集的函数值（注意，函数f的函数值是一个集合）
，且 F[2^n-1]=f(S) 就是所求。

算法2
1. for i ← 0 to 2^n-1
2. do F[i]←Φ;
3. for i ← 0 to n-1
4. do F[2^i]← {x[i]};
5. for x ← 1 to 2^n-1 do
6. begin
7. for i ← 1to x-1 do
8. begin
9. if x∧i=i then
10. begin
11. j ← x – i;
12. if i < i="i" i="i" 15="" 3="" function="" s1="" for="" each="" y="" in="" s2="" do="" begin="" t="" if="" x=""> y then
9. begin
10. T ← T + {(x – y)};
11. if (y <> 0) and (x mod y = 0)
12. then T ← T + {(x / y)};
13. end
14. else begin
15. T ← T + {(y – x)};
16. if (x <> 0) and (y mod x = 0)
17. then T ← T + {(y / x)};
18. end;
19. end;
20. end;
21. return T;

comp在进行计算的时候不考虑参数集合S1和S2的顺序，进行减法的时候始终用大
数减小数，这样保证运算过程中不出现负数（这样做的理由前文已经阐明）。

因为我们只关心最后的f(S)中最接近目标值的数字，并且题目只要求求出任何一组
最优解，所以算法2中的集合不需要是多重集合，只要是一般的集合即可。换句话
说，集合F[i]中所有的元素互不相同，重复出现元素的我们只保留其中一个。这样
可以大大减少计算中的冗余。做了这样的处理后，算法2的效率至少不会比算法1差
，因为算法1中所能采用的主要剪枝手段是排除等价的表达式，但因为等价的两个
表达式计算出的结果也一定相同，而算法2排除了所有结果相同的表达式，所以算
法2的效率至少不会比算法1差，算法2中所进行的计算基本上都是得到最优解所必
需的计算。

在实现算法2的过程中，集合可以用一个链表加上一个哈希表来实现。链表中保存
每个表达式及其值，哈希表用来记录该集合中是否存在某个特定值的表达式。当向
集合中插入一个新的表达式的时候，首先检查哈希表，看看该集合是否已经有和新
表达式值相同的表达式，如果有的话就不插入，否则将新的表达式追加到链表末尾
。采用这种数据结构，可以在常数时间内完成集合的插入和删除操作。利用链表，
集合的并操作也很容易高效地实现。

在实现算法2的过程中，可以不必保存表达式的字符串，只需要记录下当前的值是
由哪两个集合中的元素通过哪种运算得到的，最后再根据最优解递归地计算出最优
解的表达式。这样只在最后构造最优解的表达式时才进行字符串操作，程序运行效
率能提高7～8倍左右。另外，在comb函数中进行乘法运算的时候要注意考虑运算结
果超出整数范围的情况。

经过以上优化，利用算法2实现的程序对于100个随机生成的测试数据总共只需要5
秒左右就可以出解，平均每个数据只需要50毫秒即可出解（测试用的CPU为赛扬
1GB）。这样的效率已经非常令人满意了。

附录：

1。根据算法1计算24点的代码

#include
#include
#include

using namespace std;

const double PRECISION = 1E-6;
const int COUNT_OF_NUMBER = 4;
const int NUMBER_TO_CAL = 24;

double number[COUNT_OF_NUMBER];
string expression[COUNT_OF_NUMBER];

bool Search(int n)
{
if (n == 1) {
if ( fabs(number[0] - NUMBER_TO_CAL) < i =" 0;" j =" i" a =" number[i];" b =" number[j];" expa =" expression[i];" expb =" expression[j];" i =" 0;">> x;
number[i] = x;
itoa(x, buffer, 10);
expression[i] = buffer;
}

if ( Search(COUNT_OF_NUMBER) ) {
cout << "Success." <<>
#include
#include
#include
#include
#include
#include
#include
using namespace std;

const char* INPUT_FILE = "game.in";
const char* OUTPUT_FILE = "game.out";
const int NUMBER_COUNT = 6;
const int STATE_COUNT = (1 << max_number =" 100;" max_expection =" 1000;" max_value =" MAX_EXPECTION"> NodeList;

struct State {
bitset exist;
NodeList nodelist;
};

int number[NUMBER_COUNT], expection;
State state[STATE_COUNT];

void ReadData()
{
ifstream fin(INPUT_FILE);

for (int i = 0; i <>> number[i];
}
fin >> expection;
}

void Init()
{
Node node ;
for (int i = 0; i < value =" number[i];" left =" node.right" i =" state[a].nodelist.begin();" j =" state[b].nodelist.begin();" value =" (*i).value" left =" a;" right =" b;" leftvalue =" (*i).value;" rightvalue =" (*j).value;" opr =" '+';" tmp =" double((*i).value)" value =" (*i).value" left =" a;" right =" b;" leftvalue =" (*i).value;" rightvalue =" (*j).value;" opr =" '*';">= (*j).value) {
node.value = (*i).value - (*j).value;
node.left = a;
node.right = b;
node.leftvalue = (*i).value;
node.rightvalue = (*j).value;
node.opr = '-';
} else {
node.value = (*j).value - (*i).value;
node.left = b;
node.right = a;
node.leftvalue = (*j).value;
node.rightvalue = (*i).value;
node.opr = '-';
}

if ( (node.value <= MAX_VALUE) && (!state[x].exist[no de.value]) ) { state[x].nodelist.push_back(node); state[x].exist[node.value] = true; } ///////////////////////////////////////////////////// if ( ((*j).value != 0) && ((*i).value >= (*j).value) &
&
((*i).value % (*j).value == 0) )
{
node.value = (*i).value / (*j).value;
node.left = a;
node.right = b;
node.leftvalue = (*i).value;
node.rightvalue = (*j).value;
node.opr = '/';
} else if ( ((*i).value != 0) && ((*j).value >= (*i).

value) &&
((*j).value % (*i).value == 0) )
{
node.value = (*j).value / (*i).value;
node.left = b;
node.right = a;
node.leftvalue = (*j).value;
node.rightvalue = (*i).value;
node.opr = '/';
}

if ( (node.value <= MAX_VALUE) && (!state[x].exist[no

de.value]) )
{
state[x].nodelist.push_back(node);
state[x].exist[node.value] = true;
}
/////////////////////////////////////////////////////

}
}
}

void Solve()
{
Init();

for (int x = 2; x < STATE_COUNT; x++) {
for (int i = 1; i < x; i++) {
if ( (x & i) == i ) {
int j = x - i;
if (i <= j) {
Merge(i, j, x);
}
}
}
}
}

void PrintExpression(ostream& out, Node node)
{
if (node.left == -1) {
out << node.value;
} else {
NodeList::const_iterator iter;

out << "(";

for (iter = state[node.left].nodelist.begin();
iter != state[node.left].nodelist.end();
iter++)
{
if ((*iter).value == node.leftvalue) {
PrintExpression(out, *iter);
break;
}
}

out << node.opr;

for (iter = state[node.right].nodelist.begin();
iter != state[node.right].nodelist.end();
iter++)
{
if ((*iter).value == node.rightvalue) {
PrintExpression(out, *iter);
break;
}
}

out << ")";
}
}

void Output()
{
ofstream fout(OUTPUT_FILE);

int bestValue = -INT_MAX;
NodeList::const_iterator iter, bestIter;

NodeList& nodelist = state[STATE_COUNT-1].nodelist;

for (iter = nodelist.begin(); iter != nodelist.end(); iter++)
{
if ( ((*iter).value <= expection) && (bestValue < (*iter).val

ue) ) {
bestValue = (*iter).value;
bestIter = iter;
}
}
fout << bestValue << endl;
PrintExpression(fout, *bestIter );
fout << endl;
}

int main()
{
ReadData();
Solve();
Output();
return 0;
}

Friday, January 30, 2009

Friday, January 23, 2009

Software development kits and tools

Server products

Thursday, January 22, 2009

Wednesday, January 21, 2009

Tuesday, January 20, 2009

应用 Valgrind 发现 Linux 程序的内存问题

Monday, January 19, 2009

Saturday, January 17, 2009

Soyez bienvenu

S’abonner à

Libellés

Archive de blog

Ma liste de blogs

Qui êtes-vous ?