算法初步-高级语言程序设计-课件-北京工业大学.ppt

1、第3讲 算法初步,一、解题方法 二、算法举例-穷举法 三、算法举例-递推与迭代法 四、良好的编程风格,一、解题方法,分析问题，想出策略；自顶向下，逐步求精。 例如，编写一个通讯录程序 通讯录需要存储什么数据？存在什么地方？ 程序的功能 输入一个新名字 删除一个名字 显示整个通讯录 搜索一个名字 进入、退出程序等 。具体到每一项功能 菜单，将这些功能分类别设计,用计算机解决问题的步骤,分析问题 选择解决方案 编写程序 调试程序 测试程序,数据结构设计 算法设计,程序 = 数据结构 +算法,如何组织数据 C语言提供了丰富的手段,数据结构,数据对象：分析所研究问题，提炼出性质相同的数据元素。 对象之

2、间的关系 通讯录数据 用于管理的数据 在此基础上，想出处理的方法-算法,算法,算法是指用计算机解决问题的程序或步骤，这些程序或步骤必须是明确和有效的，而且能够在有限步之内完成。 算法的特征： 确定性 逻辑性 有穷性,用程序流程图描述算法,描述算法的方法有很多 程序流程图：图形化的描述程序执行过程（图是工程师的语言） 使得思想集中于算法设计，不受语言细节干扰 再依据算法，用语言编写程序 程序流程图的图形符号：P60,开始,结束,显示菜单,获取用户选择,处理用户选择,用户选择了结束,N,Y,再继续细化，画子流程图,主程序,输入新名字,删除名字,显示整个通讯录,搜索一个名字,进入程序,例：求一元二次

3、方程ax2+bx+c=0 的解,#include #include main( ) int a, b, c,t; printf( Input a,b,c： ); scanf( %d%d%d, ,二、算法举例-穷举法,列出所有可能情况，逐个排查，从中找出符合条件的解。 关键是明确问题所有可能性，注意可能情况是有限的。 用什么基本控制结构？ 优点？缺点？,循环,时间效率可能不高,问题分析 利用素数的定义来判别。对于给定整数x，用2x-1之间的每个整数试除，若都不能整除则是素数，否则不是素数。 一次试除成功（不能整除），并不能说明x是素数，只有所有试除都成功，才能断定x是素数；但一次试除失败（能整除

4、），则可断定x不是素数,例：判断给定整数是否是素数,解决方案 数据结构设计 整型变量存储素数：int x ; 算法设计 穷举的范围-循环开始和结束：2x-1 数据元素的关系-循环的步进：1 逐个排查的过程-循环的内容：试除,例：判断给定整数是否是素数,#include main( ) int x, t; printf( Enter an integer: ); scanf( %d, ,问题描述 某人有钱百枚，希望买一百只鸡；公鸡5枚钱一只，母鸡3枚钱一只，而小鸡3只1枚钱。试问：如果用百枚钱买百只鸡，可以包含几只公鸡、几只母鸡和几只小鸡 问题分析 公鸡、母鸡和小鸡的数量之和为100。 采用穷举

5、法，将100只鸡中的所有公鸡、母鸡和小鸡的组合枚举一遍，找出价钱正好是100的组合。,例：百钱买百鸡,解决方案 数据结构 设: x公鸡的个数 y母鸡的个数 z小鸡的个数 算法 遍历x、y、z，三层循环嵌套 循环起止：x：0100/5；y：0100/3； z：0100 步进：1 循环内容：排查条件： 5x+3y+z/3=100 x+y+z=100,15x+9y+z=300,#include main( ) int x, y, z;/* 公鸡、母鸡、小鸡的个数 */ for( x=0; x=100/5; x+ ) for( y=0; y=100/3; y+ ) for( z=0; z=100; z

6、+ ) if (x+y+z =100 ,三、算法举例-递推与迭代法,递推与迭代的基本策略是将复杂的运算划分为可以重复操作的分步递增方式进行求解的解题方法。 关键在于： 递推公式：据前项计算后项的重复计算公式 边界条件：计算的初值 如：递推公式：n! = n * (n-1)! -循环体 边界条件：0! = 1 -初始,P67,例3-4: 等比数列前n项求和,Sn=a1+a2 + a3 +a4 + +an,循环体：,初始值：,变量：比率用变量ratio,变量：item,和：sum,累加,main( ) int i; long item, ratio, sum, n; printf( nEnter

7、the first item and ratio: ); scanf( %ld%ld, ,例：按位分解整数,问题分析 利用整除求余运算实现将整数分解 例如，7326 7326/1000可得到最高位7；7326%1000可得到余数326； 按此规律继续-递推公式。 到个位时结束-边界条件。,#include main( ) long x, y, m; printf( Enter an integer: ); scanf( %ld, ,四、良好的编程风格,依据规约，编写正确的程序 完全按要求实现功能 格式 一行一语句。太长的语句可占多行，使其不溢出画面。 括号嵌套缩进对应，不要齐头并进 适当留空格

8、、空行等，增加可读性 下面是一段微软的代码：,int WinMain(HINSTANCE hInstance, HINSTANCE hPrevInstance, LPSTR lpCmdLine, int nCmdShow) MSG msg; HACCEL hAccelTable; / Initialize global strings LoadString(hInstance, IDS_APP_TITLE, szTitle, MAX_LOADSTRING); LoadString(hInstance, IDC_A, szWindowClass, MAX_LOADSTRING); MyRegis

9、terClass(hInstance); / Perform application initialization: if (!InitInstance (hInstance, nCmdShow) return FALSE; hAccelTable = LoadAccelerators(hInstance, (LPCTSTR)IDC_A); / Main message loop: while (GetMessage( ,不好的例子,#include int main()printf(Hello,World.n);return 0;,main() int i,x,max=0; for(i=0;imax) ma