博文
快速排序(2006-05-16 20:15:00)
摘要：分而治之方法还可以用于实现另一种完全不同的排序方法，这种排序法称为快速排序（quick sort）。在这种方法中， n 个元素被分成三段（组）：左段l e f t，右段r i g h t和中段m i d d l e。中段仅包含一个元素。左段中各元素都小于等于中段元素，右段中各元素都大于等于中段元素。因此l e f t和r i g h t中的元素可以独立排序，并且不必对l e f t和r i g h t的排序结果进行合并。m i d d l e中的元素被称为支点( p i v o t )。图1 4 - 9中给出了快速排序的伪代码。/ /使用快速排序方法对a[ 0 :n- 1 ]排序从a[ 0 :n- 1 ]中选择一个元素作为m i d d l e，该元素为支点把余下的元素分割为两段left 和r i g h t，使得l e f t中的元素都小于等于支点，而right 中的元素都大于等于支点递归地使用快速排序方法对left 进行排序递归地使用快速排序方法对right 进行排序所得结果为l e f t + m i d d l e + r i g h t图14-9 快速排序的伪代码考察元素序列[ 4 , 8 , 3 , 7 , 1 , 5 , 6 , 2 ]。假设选择元素6作为支点，则6位于m i d d l e；4，3，1，5，2位于l e f t；8，7位于r i g h t。当left 排好序后，所得结果为1，2，3，4，5；当r i g h t排好序后，所得结果为7，8。把right 中的元素放在支点元素之后， l e f t中的元素放在支点元素之前，即可得到最终的结果[ 1 , 2 , 3 , 4 , 5 , 6 , 7 , 8 ]。把元素序列划分为l e f t、m i d d l e和r i g h t可以就地进行（见程序1 4 - 6）。在程序1 4 - 6中，支点总是取位置1中的元素。也可以采用其他选择方式来提高排序性能，本章稍后部分将给出这样一种选择。程序14-6 快速排序templatevoid QuickSort(T*a, int n){// 对a[0:n-1] 进行快速排序{// 要求a[n] 必需有最大关键值quickSort(a, 0, n-1);templatevoid quickSort(T a[], int l, int r){// 排序......
想成为嵌入式程序员应知道的0x10个基本问题（转）(2006-05-01 16:45:00)
摘要：C语言测试是招聘嵌入式系统程序员过程中必须而且有效的方法。这些年，我既参加也组织了许多这种测试，在这过程中我意识到这些测试能为带面试者和被面试者提供许多有用信息，此外，撇开面试的压力不谈，这种测试也是相当有趣的。从被面试者的角度来讲，你能了解许多关于出题者或监考者的情况。这个测试只是出题者为显示其对ANSI标准细节的知识而不是技术技巧而设计吗？这个愚蠢的问题吗？如要你答出某个字符的ASCII值。这些问题着重考察你的系统调用和内存分配策略方面的能力吗？这标志着出题者也许花时间在微机上而不上在嵌入式系统上。如果上述任何问题的答案是“是”的话，那么我知道我得认真考虑我是否应该去做这份工作。从面试者的角度来讲，一个测试也许能从多方面揭示应试者的素质：最基本的，你能了解应试者C语言的水平。不管怎么样，看一下这人如何回答他不会的问题也是满有趣。应试者是以好的直觉做出明智的选择，还是只是瞎蒙呢？当应试者在某个问题上卡住时是找借口呢，还是表现出对问题的真正的好奇心，把这看成学习的机会呢？我发现这些信息与他们的测试成绩一样有用。有了这些想法，我决定出一些真正针对嵌入式系统的考题，希望这些令人头痛的考题能给正在找工作的人一点帮住。这些问题都是我这些年实际碰到的。其中有些题很难，但它们应该都能给你一点启迪。这个测试适于不同水平的应试者，大多数初级水平的应试者的成绩会很差，经验丰富的程序员应该有很好的成绩。为了让你能自己决定某些问题的偏好，每个问题没有分配分数，如果选择这些考题为你所用，请自行按你的意思分配分数。预处理器（Preprocessor）
1 . 用预处理指令#define 声明一个常数，用以表明1年中有多少秒（忽略闰年问题）
#define SECONDS_PER_YEAR (60 * 60 * 24 * 365)UL我在这想看到几件事情：•; #define 语法的基本知识（例如：不能以分号结束，括号的使用，等等）
•; 懂得预处理器将为你计算常数表达式的值，因此，直接写出你是如何计算一年中有多少秒而不是计算出实际的值，是更清晰而没有代价的。•; 意识到这个表达式将使一个16位机的整型数溢出-因此要用到长整型符号L,告诉编译器这个常数是的长整型数。•; 如果你在你的表达式中用到UL（表示无符号长整型），那么你有了一个好的起......
关于volatile关键字的说明以及测试 (转)(2006-05-01 16:26:00)
摘要：
volatile关键字是一种类型修饰符，用它声明的类型变量表示可以被某些编译器未知的因素更改，比如
操作系统、硬件或者其它线程等。遇到这个关键字声明的变量，编译器对访问该变量的代码就不再进行
优化，从而可以提供对特殊地址的稳定访问。
使用该关键字的例子如下：
int volatile nVint;
当要求使用volatile 声明的变量的值的时候，系统总是重新从它所在的内存读取数据，即使它前面的指
令刚刚从该处读取过数据。而且读取的数据立刻被保存。
例如：
volatile int i=10;int a = i;。。。//其他代码，并未明确告诉编译器，对i进行过操作int b = i;
volatile 指出 i是随时可能发生变化的，每次使用它的时候必须从i的地址中读取，因而编译器生成的
汇编代码会重新从i的地址读取数据放在b中。而优化做法是，由于编译器发现两次从i读数据的代码之间
的代码没有对i进行过操作，它会自动把上次读的数据放在b中。而不是重新从i里面读。这样以来，如果
i是一个寄存器变量或者表示一个端口数据就容易出错，所以说volatile可以保证对特殊地址的稳定访问
。
注意，在vc6中，一般调试模式没有进行代码优化，所以这个关键字的作用看不出来。下面通过插入汇编
代码，测试有无volatile关键字，对程序最终代码的影响：
首先用classwizard建一个win32 console工程，插入一个voltest.cpp文件，输入下面的代码：
#include <stdio.h>void main(){ int i=10; int a = i;
printf("i= %d\n",a); //下面汇编语句的作用就是改变内存中i的值，但是又不让编译器知道 __asm { mov dword ptr [ebp-4], 20h }
int b = i; printf("i= %d\n",b);}
然后，在调试版本模式运行程......
辗转相除法 求最大公约数(转)(2006-05-01 15:52:00)
摘要：辗转相除法 「辗转相除法」又叫做「欧几里得算法」,是公元前 300 年左右的希腊数学家欧几里得在他的著作《几何原本》提出的.利用这个方法,可以较快地求出两个自然数的最大公因数,即 HCF 或叫做 gcd.所谓最大公因数,是指几个数的共有的因数之中最大的一个,例如 8 和 12 的最大公因数是 4,记作 gcd(8,12)=4. 在介绍这个方法之前,先说明整除性的一些特点,注以下文的所有数都是正整数,以后不再重覆. 我们可以这样给出整除以的定义: 对於两个自然数 a 和 b,若存在正整数 q,使得 a=bq,则 b 能整除 a,记作 b | a,我们叫 b 是 a 的因数,而 a 是 b 的倍数. 那麼如果 c | a,而且 c | b,则 c 是 a 和 b 的公因数. 由此,我们可以得出以下一些推论: 推论一:如果 a | b,若 k 是整数,则 a | kb.因为由 a | b 可知 ha=b,所以 (hk)a=kb,即 a | kb. 推论二:如果 a | b 以及 a | c,则 a | (b±c).因为由 a | b 以及 a | c,可知 ha=b,ka=c,二式相加,得 (h+k)a=b+c,即 a | (b+c).同样把二式相减可得 a | (b-c). 推论三:如果 a | b 以及 b | a,则 a=b.因为由 a | b 以及 b | a,可知 ha=b,a=kb,因此 a=k(ha),hk=1,由於 h 和 k 都是正整数,故 h=k=1,因此 a=b. 辗转相除法是用来计算两个数的最大公因数,在数值很大时尤其有用而且应用在电脑程式上也十分简单.其理论如下: 如果 q 和 r 是 m 除以 n 的商及余数,即 m=nq+r,则 gcd(m,n)=gcd(n,r). 证明是这样的: 设 a=gcd(m,n),b=gcd(n,r) 则有 a | m 及 a | n,因此 a | (m-nq)(这是由推论一及推论二得出的),即 a | r 及 a | n,所以 a | b 又 b | r 及 b | n,所以 b | (nq+r),即 b | m 及 b | n,所以b | a.因为 a | b 并且 b | a,所以 a=b,即 gcd(m,n)=gcd(n,r). 例如计算 gcd(546, 429),由於 546=1(429)+117,42......
日本到底哪些方面领先中国？(转贴)（正视现实努力奋斗）(2006-04-14 09:08:00)
摘要：
日本的传统强项是制造业。制造高质量的产品，长久以来被认为是日本人的特征。与此同时，日本经过几十年的积累和认真研究，加上其认真苦干的精神，在某些领域，日本已经掌握了世界最尖端技术，以制造业为基础，尖端技术为前导，可以确保日本在未来几十年继续保持经济领域的领先地位。加上日本的总体社会环境是一个良性循环状态，也为其持续性的发展提供了保证。 总地来说，日本在下列领域掌握着领先技术。 超导技术:`日本开始研究超导新干线，预计时速将到达500公里。实力公司包括：日立，东芝，日本车辆，三菱重工等。 材料技术：NEC,东芝，日立，古河电工，神户制铁所，住友电工，东京电力，等等； 纳米技术：高速通信技术，NEC,日立；下一代DVD技术：SONY；东芝；下下一代DVD技术：日立；平面显示屏技术：佳能，SONY，双叶电子；硅技术：东京微电子，尼康； MEMS：三菱电机，夏普，松下； 宇宙：石川岛播磨重工；川崎重工，三菱重工；东芝，NEC，三菱电机； 在传统行业领域，世界现状大致如下： 钢铁：第一名是卢森堡的公司，第二荷兰公司，第三名是新日本制铁；第四名是JFE制铁（日本）；中国的宝钢排在第六位（与日本合资）； 化学：三菱化学排在第五位。前四名是美国和德国瓜分；旭化成第九位。 汽车：GM暂时排在第一，估计会被第二位的丰田超过；日产第8；本田第九； 家用电器：前十五名被日本包揽：松下，日立，东芝，夏普，三菱电机是前五名； 半导体：日立和三菱合资的半导体公司排第四位，英特尔高居榜首； 通信领域：NTT独占鳌头。 一般认为，新技术从研究到成熟是一个阶段，从成熟到应用是第二阶段。第二个阶段的时间10-15年。换句话说，如果现在想应用一项新技术，它必须在10年之前就已经成熟了，否则不能应用。日本正在计划建设超导新干线，也就是说，他的超导方面的研究，在十年前就已经成熟了。 日本在某些领域面对的强大对手依然是美国。偶尔有某些欧洲老牌公司在销售额方面领先。在可以预见的将来，中国不可能成为日本的对手，因为中国无论在传统领域还是在新技术方面，都不值得一提。上述所有行业，以前15名为基准，只能看到一个中国公司的名字：宝钢，还是采用日本的技术的合资企业。 普通日本人的吃学住医 我在日本生活十多年，博士毕业收入比日本人略高。和普通日本人的生......
约瑟夫环－－别人的(2006-04-03 19:11:00)
摘要：
/*要求:用循环链表实现约瑟夫环程序,给定犯人编号分别是3，1，7，2，4，8，4。
*报数初值由用户输入，打印输出队列。
*令m=20作为测试数值,正确的出列顺序为6,1,4,7,2,3,5
*ch.nan@163.com 整理于2005.12.01 */
/*******************************************************************************/
#include <stdio.h>
#include <malloc.h>
#define N 7 //定义N=7，表示有7个链表单元
#define OVERFLOW 0
#define OK 1
typedef struct LNode{ //定义链表结构
int password;
int order;
......
约瑟夫环(2006-04-03 18:32:00)
摘要：#include<stdio.h>#include<stdlib.h>#define TRUE 1#define FALSE 0#define OK 1#define ERROR 0#define INFESIBLE -1#define OVERFLOW -2typedef int status;typedef int BOOL;typedef int ElemType;typedef struct Node{ ElemType pasword; int number; struct Node *next;}LNode,*linklist;
linklist Initlinklist(void){ linklist p; ElemType psw; p=(linklist)malloc(sizeof(LNode)); if(!p) { printf("can't init linklist!\n"); exit(0); } printf("please enter the first pasword:\n"); scanf("%d",&psw); p->number=1; p->next=NULL; p->pasword=psw; return p;}
void Insertlinklist(linklist p,ElemType a[],int n){ int i; linklist q,h; h=p; for(i=1;i<n+1;i++) { q=(linklist)malloc(sizeof(LNode)); if(!q) { printf("can't malloc room\n"); system("pause"); exit(0); } q->......
C/C++程序员面试问题(2006-03-17 12:29:00)
摘要：主要针对应界毕业的同学和一年以下工作经验的人；希望对大家有帮助；算法：1．什么是NPC，NP-Hard？2．起泡排序的时间复杂度是多少？说出至少一个比它更快的算法；排序的极限时间复杂度是多少？3．有一个链表，如何判断它是一个循环链表？如果链表是单向的呢？如果出现循环的点可能在任意位置呢？如果缓存空间是有限的，比如是一个常数呢？如果只能使用2个缓存呢？4．有一个文件，保存了若干个整数，如何以平均的概率随机得到其中的一个整数？如果整数的个数是未知的呢？如果整数是以字符串形式存放，如：（即如何得到随机的一个字符串）123-456…如果只允许便历文件一次呢？5．用两组数据，都在内存中，对它们排序分别需要1和2分钟；那么使用两个线程一起排序，大概需要多少时间？C/C++：1．C与C++的异同，优劣；2．C，C++，VC，BC，TC的区别；3．C++中try…catch关键字的用法与优点；4．枚举的用法，以及它与宏的区别；5．const的用法，以及声明const变量与宏的区别；6．C++中引用与指针的区别；7．C++中virtual与inline的含义分别是什么？虚函数的特点；内联函数的特点；一个函数能否即是虚函数又是内联函数？8．以下关键字的含义与用法：extern，extern “C”，static，explicit，register，#undef，#ifndef9．什么是函数重载与覆盖？为什么C不支持函数重载？为什么C++能支持函数重载？10．VC中，编译工具条内的Debug与Release选项是什么含义？11．编写my_memcpy函数，实现与库函数memcpy类似的功能，不能使用任何库函数；12．编写my_strcpy函数，实现与库函数strcpy类似的功能，不能使用任何库函数；13．编写gbk_strlen函数，计算含有汉字的字符串的长度，汉字作为一个字符处理；已知：汉字编码为双字节，其中首字节<0，尾字节在0~63以外；（如果一个字节是-128~127）14．函数assert的用法；15．为什么在头文件的最前面都会看到这样的代码：#ifndef _STDIO_H_#define _STDIO_H_16．为什么数组名作为参数，会改变数组的内容，而其它类型如int却不会改变变量的值？......
从初学者到电子工程师 第三课 合格电子工程师是怎样炼成的？ (2006-03-16 18:22:00)
摘要：从初学者到电子工程师 第三课 合格电子工程师是怎样炼成的？ 不好意思，第二课没有写完，又开一课--老树当过老师，有毁人不倦的习惯，再者，这个问题想了很久了，也基本想通了。 在网络上很多初学者在问：怎样成为一个合格的电子工程师？ 这个问题有很多答案。老树谈谈自己的看法。 第一步 入门-51核心和基本电路 中国人有10亿啊，每年有多少大学生毕业呢？我不知道。但是我看到有一张照片，招聘会上熙熙攘攘，人来人往，十分震撼。从来没有一个时刻让我感觉到中国的人力资源是如此的丰富。但是，从现在的大学毕业出来的学生学到了什么东西呢？一些理论，跟实际脱钩的理论。有没有用呢？有点用。但是，在企业中，需要的是实际干点事情出来，实际解决问题。所以说，很多企业不想要大学本科出来的大学生，说动手，没有动手能力，不知道电阻电容长得什么样子，能够做什么？但是又自视甚高，对工资的期望值比较高。等到能够干点事情了，又拍拍屁股跑了。所以企业现在喜欢使用大专中专甚至是职业学校培训出来的小孩，至少这些孩子们知道自己的份量，能够实实在在地做事。要知道，他们很多人的天赋并不差，有些人甚至可以说聪明，只是因为很多人是家庭条件不好，打小就是苦孩子，没有条件接受良好的教育。一旦给机会，他们都比较珍惜。 现在的大学，误人子弟甚多。扩招是没有错，但是，实验室扩了吗？教室扩了吗？教师扩了吗？至少实验室是没有扩。老树认得的一个研究生说，只有到了一个阶段，才能到实验室作实验。很多导师就是把学生当奴隶一样干活，要是在干活中能够学到东西那就算是运气好的；运气不好的，直接就是导师的廉价的劳力了，学不到东西，活倒干了不少。 但是，既然学生要拿文凭，要应付考试，没有办法，那怎么自救？ 如果励志要做一名出色的电子工程师，老树可以谈谈自己的看法。 做一个电子工程师，先从51学起，这是得到公认的。不需老树饶舌。 首先，去买一个开发板，越便宜的越好，在上面可以练练keil C。最好再买一个仿真器，这样调试的效率高。当然这个不便宜，但是我觉得可以志同道合的哥几个合买。反正1天24小时，每人8个小时轮流上，有个几个月，C51语言也就差不多了。 其次，看看老树的文章，看看需要学点什么基本的东西。北京的大学生有福啊，没事到中发去转转，认认老树的文章上说得哪些电阻、电容、三极管、芯片、接插件什么的，看看自己的电脑上的主板、网卡、声卡、显卡是怎么画的，找找感......
2.10 开关电源芯片 (2006-03-16 18:21:00)
摘要：2.10 开关电源芯片 相对于线性稳压器来说，开关电源在计算机主板上、工控机主板和各种各样的电路板上起着电压变换的作用。例如：将低电压，比如：电池转换成稳定的3.3V或者5V，或者将高电压转化成DC5V、DC3.3V，或者将DC5V转换成3.3V和1.8V，例如，ARM的电路板就需要这样的芯片，3.3V给ARM供电，1.8V给arm的core供电。以上 由于采用了开关电路，电源芯片的工作频率高，发热小，效率高。 同样的，还是芯片的巨头，MAXIM、LINEAR和TI等公司在电源转换芯片上是最为卓越，无论从产品的种类，还是质量都是上佳的； 经常看电子产品世界和电子技术应用的网友一定对maxim的电源芯片印象巨深。五花八门的电源芯片，让你无法选择到底选用那种是自己的所需要的。 在maxim的产品树中，对电源是这样分类的： Power Supplies and Battery Management Switchmode DC-DC Power Supplies 408 Isolated Power Supplies 22 Low-Dropout Linear Regulators 75 White LED Drivers 13 Low-Side MOSFET Drivers 14 High-Side MOSFET Drivers 6 ORing MOSFET Controllers 2 Battery Chargers 36 Battery Protectors, Selectors and Monitors 17 Regulator + Reset Circuits 4 Current Sense Amplifiers 22 LCD/ECB/CCFL Display Bias Supply 87 ALSO SEE:......