程序员面试宝典,参考书,程序员面试宝典(第三版) 欧立奇 等编著 电子工业出版社 程序员求职成功路 周扬荣 编著 机械工业出版社 高质量程序设计指南 林锐 等编著 电子工业出版社,1、结构化程序设计思想 2、编译器 3、C语言 4、编程规范 5、操作系统 6、内存管理 7、优化 8、测试 9、求职之路,2010年7月编程语言排行榜,一、结构化程序设计思想,Edsger Wybe Dijkstra 1930-2002,1965年， Dijkstra指出：“可以从高级语言中取消GOTO语句”,著名计算机科学家沃思(Nikiklaus Wirth)提出一个公式数据结构算法程序 程序算法数据结构程序设计方法语言工具和环境算法是灵魂，数据结构是加工对象，语言是工具，编程需要采用合适的方法。 算法是解决“做什么”和“怎么做”的问题。程序中的操作语句，实际上就是算法的体现。,1966年Bohm等证明了，只用顺序、选择、循环三种基本的控制结构就能实现任何单入口单出口的没有“死循环”的程序。 1968年Dijkstra再次建议从一切高级语言中取消GOTO语句，只使用三种基本控制结构编写程序。,扩展的结构程序设计 为了实际使用方便起见，常常还允许使用DO_UNTIL和DOCASE两种控制结构,修正的结构程序设计,如果需在循环体中或选择语句的内部有出口时，可以使用LEAVE（BREAK）结构。,While S do Begin LEAVE / BREAK End;,受限制的GOTO语句,70年代初采用结构化程序设计取得成功的例子： 1971，IBM，纽约时报信息库管理系统，8.3万行 美国宇航局空间实验室飞行模拟系统，40万行 1972年Mills提出“程序应该只有一个入口和一个出口”，从而补充了结构程序设计的规则。,SP经典定义,如果一个程序的代码块仅仅通过顺序、选择和循环这三种控制结构进行连接，并且每个代码块只有一个入口和一个出口，则称这个程序是结构化的。 结构程序设计是一种尽可能少用GOTO语句的程序设计技术，它采用自顶向下、逐步细化的设计方法和单入口单出口的控制技术。,结构化程序设计方法,自顶向下 逐步细化 模块化设计 结构化编码,自顶向下逐步求精的程序设计技术,自顶向下、逐步求精 若想让计算机解题必须用清晰而无两义性的方式给它提供算法。要求： 找出一个算法，它能提供所解问题的从输入到输出所需的映象。 选择一种程序语言写出程序，用计算机能接受的方式表述算法。 关键是如何找出算法。因为写出程序，只是表述算法，应该没有困难。,编程过程,问题解决 一个复杂的过程. 算法 解决问题所使用的一系列合乎逻辑的、简洁的步骤. 解决问题包含的步骤: 分析问题，找出解决问题的模型。 根据模型设计出适合计算机特点的处理方法即算法 选择适合的计算机语言进行编程，以实现算法。 上机编辑、调试、运行所编制的程序得到结果 对结果进行分析，整理出文字材料即文档。,算法的特点,有穷性：一个算法应包含有限个操作步骤。 确定性：每个步骤应该是确定的。 有0个或多个输入 有1个或多个输出 有效性：每个步骤都能有效执行。,例1(I),例1：由键盘输入三个整数，输出其中最大的数； S1.输入a,b,c三个整数 S2.求出三个数中的最大数 S3.输出最大数,如何求出最大数？现在还没有讨论,例1(II),S2.求出三个数中的最大数 算法一： S2.1 如果ab,执行2.2，否则执行2.3 S2.2 如果ac，最大数为a，否则最大数为c S2.3 如果bc，最大数为b，否则最大数为c,例1(III),S2.求出三个数中的最大数 算法二：（引入temp变量） S2.1 如果ab,temp=a，否则temp=b S2.2 如果tempc，max=temp，max=c,例2：判断一个整数m是否为素数 算法如下： S1：输入m的值。 S2：判断m是否为素数。 S3：输出m是否为素数。 S4：算法结束。,第2步分析：判断整数m（m2）是否为素数的方法是：如果m不能被i整除（i为2到m-1的所有整数），则m是素数。 算法如下： S2.1：i赋初值为2：标记m是素数 S2.2：判断m能否被i整除。若能，标记m不为素数，结束循环。 S2.3：若m不为被i整除，给i的值加1。若im,则转到S3。,例3(I),例3：编程找出1000以内的所有“完数”，并按照下面格式输出因子： 6 Its factors are 1,2,3 S1:a=2 S2:如果a1000,执行S3，否则转S7 S3:求出a的所有因子 S4:如果是完数，按照格式输出 S5：a=a+1 S6：转S2 S7：算法结束,例3(II),S3 分析：判断整数a是否为完数的算法是：从1到a-1找出因子，看这些因子的和是否等于a S3.1:i=1,n=0(n记录找到的第几个因子) S3.2:判断ia，如果成立转3.3，否则结束a的分解，转到S4 S3.3：如果i是a的因子,保存因子到kn, n=n+1(因子个数加1) S3.4:i=i+1，转3.2,例3(III),S4 分析：判断是否为完数，将数a减去所有的因子，得数为0的既是完数 S4.1 i=0,s=a S4.2 如果i=n，s=s-kn;否则转S4.4 S4.3 i=i+1；转到S4.2 S4.4 如果s=0，按照格式输出a和所有的因子,例3(IV)(S3-S4整合),S3.1:i=1,n=0(n记录找到的第几个因子) ，s=a S3.2:判断ia，如果成立转3.3，否则结束a的分解，转到S4 S3.3：如果i是a的因子,保存因子到kn, n=n+1(因子个数加1),s=s-kn S3.4:i=i+1，转3.2,例4：测定字母偶的出现频率,测定小写字符串中相邻字母偶出现频率。例如，针对 the cat 对 th 、he 、ca 、at 计数。设有说明： int conmat2626 ; 字母偶 he 的出现次数存入下标变量 conmath-ae-a,首先把该问题分解成如下几步： S1 初始化计数器数组conmat ； S2 统计每个字母偶的出现频率； S3 输出统计结果。,initial 初始化,statistical 统计,out 输出,求精上述PAD中的每一个步骤： S1:初始化数组conmat ,显然应该一行一行的初始化；对于每行又应该一个元素一个元素的初始化。,初始化 第i行,S2:考虑统计部分： 假设被统计的字符串是从终端输入的，则显然我们应该把该字符串全部读入，并在读入的过程中边读边统计。用下图表示。,读 ( prevchar ),statistical,while(!EOF),统计一次,结束,def,读(thischar),再考虑S2具体统计算法，为统计字母偶的出现频率，显然在读入字符串的过程中应该始终保存两个字符 prevchar 、thischar ，并且当该两个字符都是字母时，相应计数单元加1；最后在读入下一个字符之前还应该把保存的两个字符向前串。,最后考虑输出部分, 我们把结果输出成两个 2613 的表，每个表元素是相应字母偶的出现次数： * a b c d e . m a b . z * n o p q r . z a b . z,打印一个表（第一个表），显然应该先打印表头再打印下边各行,打印表头,打印表体,outone,结束,beginch ,endch,打印表头可以求精成先输出一个“*”；再顺次输出各个字符。 顺次输出各个字符是一个循环。,打印表头,打印表体,outone,结束,beginch ,endch,输出(*),输出(n),顺次输出各个字符,打印表体应该一行一行的打印， 每行应该先打印行头，再打印本行各个元素； 打印本行各个元素，应该一个元素一个元素的打印，是一个循环,打印表体,outone,结束,beginch ,endch,输出(*),输出(n),for( c1=a; c1=z; c1+),输出一行,输出(c1),输出(n),输出本行各个元素,例5：三个齿轮啮合问题,设有三个齿轮互相衔接，求当三个齿轮的某两对齿互相衔接后到下一次这两对齿再互相衔接，每个齿轮最少各转多少圈。 解:这是求最小公倍数的问题。每个齿轮需转圈数是三个齿轮齿数的最小公倍数除以自己的齿数。设 三个齿轮的齿数分别为:na、nb、nc ； 啮合最小圈数分别为:ma、mb、mc ； 三齿轮齿数的最小公倍数为k3 。,计算步骤表示为：,读入三齿轮齿数和输出结果，分别只是一次调用读或写函数，不必求精。,求精计算三齿数的最小公倍数k3 。 可以把该问题分解成 先求两个齿数na与nb的最小公倍数k2 ， 然后再求k2与第三个齿数 nc 的最小公倍数k3 ， k3即为na、nb、nc三个齿轮齿数的最小公倍数。 设已经有求两个数的最小公倍数的函数 int lowestcm( int x, int y ) 则该求精过程可表示成 。,求精求两个数的最小公倍数的函lowestcm 。 x、y的最小公倍数是x、y 的积除以x、y 的最大公约数。设已经有求两个数的最大公约数的函数 int gcd(int x, int y) 则该求精过程可表示成：,采用展转相除法求两个数的最大公约数，函数 int gcd(int x, int y) 定义如下,函数gcd是一个递归函数，先采用分支求精过程、再采用递归求精过程，可以求精成下图,最后，分别计算啮合的最小圈数可以被求精成下图 。,例6：验证三角形外心定理,三角形三条边的垂直平分线交于一点，该点是三角形外接圆的圆心。 解：不失一般性，假设三角形的任意一条边都不平行于任意一个坐标轴。依据平面几何知识，该问题的验证步骤应该是： 读入三点a,b,c的坐标(x1,y1)、(x2,y2)、(x3,y3)； 检验三点是否构成一个三角形； 若三点构成三角形，则验证外心定理 。,读入三点坐标只是一个读语句，不必求精 ，下边求精检验是否三角形和验证外心定理。,检验三点是否构成三角形使用一个bool型函数isTriange ，可以求精成： 求两点p1,p2确定的直线方程L12 ； 判断若p3在L12上， 则 isTriange 为false ， 否则isTriange为true 。,求两点间直线方程可以写一个函数 line(x1,y1,x2,y2, *a,*b ) 并求精成下图 。,验证外心定理可以如下进行： 求每条边的垂直平分线； 验证该三条直线是否交于一点； 若交于一点， 则验证该点到三角形各顶点距离是否相等否则 错误命题。,求每条边的垂直平分线方程可以写一个求一条线段的垂直平分线方程的函数，然后分别三次调用该函数 。,求一条边的垂直平分线方程可以先调用前述函数 line，求该边的直线方程;再求该边的中点,然后求过该中点的与该边垂直的直线方程，得下图,验证该三条直线是否交于一点编成一个函数isOnePoint ，可以 先求两条直线的交点， 然后再判断第三条直线是否过该点。,设有一个函数 distance (x1,y1,x2,y2) 可以计算两点间距离，验证三条垂直平分线的交点到三角形各顶点距离是否相等，是一个布尔表达式。,算法的描述,1.自然语言描述:用自然语言给出解决问题的详细步骤.如前面的例子。 2.流程图：用图框表示。 3.N-S图 4.PAD图 4.伪代码：使用介于自然语言和计算机语言之间的文字、符号来描述算法。 5. 计算机语言：采用这种方法必须严格遵守所使用的语言的语法规则。,程序流程图(I),传统流程图里常用的符号,开始或结束框 “处理框”-运算步骤 输入或输出框 判断框 连接符：一个程序中两个部分之间的连接 程序的流程线 注释,