第3讲算法初步一、解题方法二、算法举例---穷举法三、算法举例---递推与迭代法四、良好的编程风格用计算机解决问题的步骤分析问题选择解决方案?数据结构设计编写程序?算法设计调试程序测试程序程序= 数据结构+算法如何组织数据C语言提供了丰富的手段算法算法是指用计算机解决问题的程序或步骤，这些程序或步骤必须是明确和有效的，而且能够在有限步之内完成。算法的特征：确定性逻辑性有穷性一、解题方法分析问题，想出策略；自顶向下，逐步求精。例如，编写一个通讯录程序通讯录需要存储什么数据？程序的功能输入一个新联系人删除一个联系人显示整个通讯录搜索一个联系人进入、退出程序等……。具体到每一项功能菜单，将这些功能分类别整合数据结构数据对象：分析所研究问题，提炼出性质相同的数据元素。对象之间的关系通讯录数据用于管理的数据在此基础上，想出处理的方法---算法用程序流程图描述算法描述算法的方法有很多程序流程图：图形化的描述程序执行过程（图是工程师的语言）使得思想集中于算法设计，不受语言细节干扰再依据算法，用语言编写程序程序流程图的图形符号：P641开始显示菜单再继续获取用户选择细化处理用户选择，画子N流用户选择了结束程图Y结束void main(){intflag=0;intMenuItem= 0;printf(\通讯录程序\\n\printf(\、输入一个新的联系人\\n\printf(\、删除一个联系人\\n\printf(\、显示全部联系人信息\\n\printf(\、查询指定联系人信息\\n\printf(\、退出通讯录程序\\n\while( !flag ){printf(\请输入菜单序号，选择对应菜单项：\scanf(\… //选择语句，控制程序调用分支}}例：求一元二次方程ax2+bx+c=0 的解模块调用图主程序输入新名字显示整个通讯录进入程序……删除名字搜索一个名字……switch (MenuItem){case 1: //在这编写输入一个新的联系人的程序break;case 2://在这编写删除一个联系人的程序break;case 3://在这编写显示全部联系人信息的程序break;case 4://在这编写查询指定联系人信息的程序break;case 5://在这编写退出通讯录程序的程序flag++;break;default:printf(\输入数字错误，请重新输入：\} 开始 输入a,b,c b2-4ac→ t t < 0 Y NNt = 0 Y输出两个解输出一个解 输出“无解” 结束 2#include #include main( ){inta, b, c,t;printf( \：\scanf( \t = b*b -4*a*c;if (t<0)printf( \else if ( t==0 )printf( \else {double t0;t0 = sqrt( (double)t);printf( \(-b+t0)/(2*a), (-b-t0)/(2*a) );}}例：判断给定整数是否是素数问题分析利用素数的定义来判。只能被1和自己整除对于给定整数x，用2~x-1之间的每个整数试除，若都不能整除则是素数，否则不是素数。一次试除成功（不能整除），并不能说明x是素数，只有所有试除都成功，才能断定x是素数；但一次试除失败（能整除），则可断定x不是素数 开始 输入x 2 → t N t < x Y Y x%t==0 N t 加1 输出“不是素数” 输出“是素数” 结束 二、算法举例---穷举法列出所有可能情况，逐个排查，从中找出符合条件的解。关键是明确问题所有可能性，注意可能情况应是有限的。用什么基本控制结构？优点？缺点？循环时间效率可能不高解决方案数据结构设计整型变量存储素数：intx ;算法设计穷举的范围---循环开始和结束：2~x-1 数据元素的关系---循环的步进：1逐个排查的过程---循环的内容：试除#include main( ){intx, t;printf( \scanf( \for (t = 2; tmain( ){intx, y, z;/* 公鸡、母鸡、小鸡的个数*/for( x=0; x<=100/5; x++ )for( y=0; y<=100/3; y++ )for( z=0; z<=100; z++ ) {if (x+y+z==100 &&15*x+9*y+z==300)printf( \}}intmain(){inti,n,f=1; /* 定义变量*/printf(\请输入n的值：\\n\scanf(\i = 0;while(imain( ){long x, y, m;printf( \scanf( \y =x; /* 初始化*/m =1;//计算整数位数while (y>=10) {m *= 10;y = y/10;} //m与输入整数同样位数do{ /* 分解整数*/printf( “%ld\\t”, x / m );//输出当前最高位x= x%m;m=m / 10; //准备对应的m值} while ( m >= 1 );}intWinMain(HINSTANCEhInstance, HINSTANCE hPrevInstance, LPSTR lpCmdLine, intnCmdShow){MSG msg;HACCEL hAccelTable;// Initialize global stringsLoadString(hInstance, IDS_APP_TITLE, szTitle, MAX_LOADSTRING);LoadString(hInstance, IDC_A, szWindowClass, MAX_LOADSTRING);MyRegisterClass(hInstance);// Perform application initialization:if (!InitInstance(hInstance, nCmdShow)) {return FALSE;}hAccelTable= LoadAccelerators(hInstance, (LPCTSTR)IDC_A);// Main message loop:while (GetMessage(&msg, NULL, 0, 0)) {if (!TranslateAccelerator(msg.hwnd, hAccelTable, &msg)) {TranslateMessage(&msg);DispatchMessage(&msg);}}return msg.wParam;}例：按位分解整数问题分析利用整除求余运算实现将整数分解例如，73267326/1000可得到最高位7；732600可得到余数326；按此规律继续---递推公式。到个位时结束---边界条件。（需先知整数位数，四位数时，为1000）四、良好的编程风格依据规约，编写正确的程序完全按要求实现功能格式一行一语句。太长的语句可占多行，使其不溢出画面。括号嵌套缩进对应对齐，不要齐头并进适当留空格、空行等，增加可读性…下面是一段微软的代码：不好的例子#include intmain(){printf(\0;}main(){inti,x,max=0;for(i=0;i<80;i++){x=getchar();if(x>max){max=x;}}}//与本书P51对比5每个变量有明确的角色，主要变量写注释。注释（反映你的文字水平）文件注释函数注释程序片断关键点注释关键数据结构注释通常没必要每句话写注释程序员友好你的程序是给人看的，不要写的晦涩难懂。正确性可懂度时间复杂度空间复杂度健壮性可扩展性可移植性…6